We introduce a novel concept of dual-system simulation-sound non-interactive zero-knowledge (NIZK) proofs. Dual-system NIZK proof system can be seen as a two-tier proof system. As opposed to the usual notion of zero-knowledge proofs, dual-system defines an intermediate partial-simulation world, where the proof simulator may have access to additional auxiliary information about the potential language member, for example a membership bit, and simulation of proofs is only guaranteed if the membership bit is correct. Further, dual-system NIZK proofs allow a quasi-adaptive setting where the CRS can be generated based on language parameters. This allows for the further possibility that the partial-world CRS simulator may have access to further trapdoors related to the language parameters. We show that for important hard languages like the Diffie-Hellman language, such dual-system proof systems can be given which allow unbounded partial simulation soundness, and which further allow transition between partial simulation world and single-theorem full simulation world even when proofs are sought on non-members. The construction is surprisingly simple, involving only two additional group elements in asymmetric bilinear pairing groups.
As a first application we show a first single-round universally-composable password authenticated key-exchange (UC-PAKE) protocol
which is secure under dynamic corruption in the erasure model. The single message flow only requires four group elements under the SXDH assumption, which is at least two times shorter than earlier schemes.
As another application we give a short keyed-homomorphic CCA-secure encryption scheme. The ciphertext in this scheme consist of only six group elements (under the SXDH assumption) and the security reduction is linear-preserving. An earlier scheme of Libert et al based on their efficient unbounded simulation-sound QA-NIZK proofs only provided a quadratic-preserving security reduction, and further had ciphertexts almost twice as long as ours.
ePrint Report