Non-interactive zero-knowledge (NIZK) proofs for chosen-ciphertext security are generally considered to give an impractical construction. An interesting recent work by Seo, Abdalla, Lee, and Park (Information Sciences, July 2019) proposed an efficient semi-generic conversion method for achieving chosen-ciphertext security based on NIZK proofs in the random oracle model. The recent work by Seo et al. demonstrated that the semi-generic conversion method transforms a one-way (OW)-secure key encapsulation mechanism (KEM) into a chosen-ciphertext secure KEM while preserving tight security reduction. This paper shows that the security analysis of the semi-generic conversion method has a flaw, which comes from the OW security condition of the underlying KEM. Without changing the conversion method, this paper presents a revised security proof under the changed conditions that (1) the underlying KEM must be chosen-plaintext secure in terms of indistinguishability and (2) an NIZK proof derived from the underlying KEM via the Fiat–Shamir transform must have the properties of zero-knowledge and simulation soundness. This work extended the security proof strategy to the case of identity-based KEM (IBKEM) and also revise the security proof for IBKEM of previous method by Seo et al. Finally, this work gives a corrected security proof by applying the new proofs to several existing (IB)KEMs.
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.
We construct the first constant-round protocols for secure quantum computation in the two-party (2PQC) and multi-party (MPQC) settings with security against malicious adversaries. Our protocols are in the common random string (CRS) model. - Assuming two-message oblivious transfer (OT), we obtain (i) three-message 2PQC, and (ii) five-round MPQC with only three rounds of online (input-dependent) communication; such OT is known from quantum-hard Learning with Errors (QLWE). - Assuming sub-exponential hardness of QLWE, we obtain (i) three-round 2PQC with two online rounds and (ii) four-round MPQC with two online rounds. - When only one (out of two) parties receives output, we achieve minimal interaction (two messages) from two-message OT; classically, such protocols are known as non-interactive secure computation (NISC), and our result constitutes the first maliciously-secure quantum NISC. Additionally assuming reusable malicious designated-verifier NIZK arguments for NP (MDV-NIZKs), we give the first MDV-NIZK for QMA that only requires one copy of the quantum witness. Finally, we perform a preliminary investigation into two-round secure quantum computation where each party must obtain output. On the negative side, we identify a broad class of simulation strategies that suffice for classical two-round secure computation that are unlikely to work in the quantum setting. Next, as a proof-of-concept, we show that two-round secure quantum computation exists with respect to a quantum oracle.