An important open question in quantum cryptography is the construction of publicly-verifiable NIZKs for QMA. Classically, one can construct NIZKs for NP in the random oracle model (and sometimes in the standard model) by compiling an honest-verifier ZK (HVZK)
Σ-protocol for NP using the Fiat-Shamir transformation. Broadbent and Grilo introduced a quantum analog of a
Σ-protocol (which they call a
Ξ-protocol) in which the prover's first message is quantum, and show that HVZK
Ξ-protocols exist for QMA. However, it is not clear how to compile such protocols into NIZKs in the (Q)ROM, because the Fiat-Shamir transformation seems to be incompatible with quantum messages. In this work we give formal evidence that this is indeed the case: we show that if generic "Fiat-Shamir-like" compilers for quantum protocols exist in the QROM (with small completeness and soundness error) then QMA = BQP.
The Fiat-Shamir transformation is a famous technique to turn identification schemes into signature schemes. The derived scheme is provably secure in the random-oracle model against classical adversaries. Still, the technique has also been suggested to be used in connection with quantum-immune identification schemes, in order to get quantum-immune signature schemes. However, a recent paper by Boneh et al. (Asiacrypt 2011) has raised the issue that results in the random-oracle model may not be immediately applicable to quantum adversaries, because such adversaries should be allowed to query the random oracle in superposition. It has been unclear if the Fiat-Shamir technique is still secure in this quantum oracle model (QROM). Here, we discuss that giving proofs for the Fiat-Shamir transformation in the QROM is presumably hard. We show that there cannot be black-box extractors, as long as the underlying quantum-immune identification scheme is secure against active adversaries and the first message of the prover is independent of its witness. Most schemes are of this type. We then discuss that for some schemes one may be able to resurrect the Fiat-Shamir result in the QROM by modifying the underlying protocol first. We discuss in particular a version of the Lyubashevsky scheme which is provably secure in the QROM.
Many evidences have showed that some intelligence agencies (often called big brother) attempt to monitor citizens’ communication by providing coerced citizens a lot of subverted cryptographic algorithms and coercing them to adopt these algorithms. Since legalized services on large number of various applications and system architectures depend on digital signature techniques, in the context some coerced users who use double authentication preventing signatures to design some novel digital signature techniques, have some convincing dissertations to defuse requests from authorities and big brothers creating some corresponding subverted signatures. As rapid progress in quantum computers, National Security Agency advisory memorandum and announcement of National Institute of Standards and Technology procedures from standardization focus on some cryptographic algorithms which are post quantum secure. Motivated by these issues, we design an algorithm substitution attack against Fiat-Shamir family based on lattices (e.g., BLISS, BG, Ring-TESLA, PASSSign and GLP) that are proven post-quantum computational secure. We also show an efficient deterable way to eliminate big brother’s threat by leaking signing keys from signatures on two messages to be public. Security proof shows that our schemes satisfy key extraction, undetectability and deterability. Through parameters analysis and performance evaluation, we demonstrate that our deterring subverted Fiat-Shamir signature is practical, which means that it can be applied to privacy and protection in some system architectures.