Triply Adaptive UC NIZK
The only known non-interactive zero-knowledge (NIZK) protocol secure against adaptive corruption of the prover is based on that of Groth-Ostrovsky-Sahai (JACM’11) (GOS). However that protocol does not guarantee full adaptive soundness. Abe and Fehr (TCC’07) construct an adaptively sound variant of the GOS protocol under a knowledge-of-exponent assumption, but knowledge assumptions of this type are inherently incompatible with universally composable (UC) security. We show the first NIZK that is both secure against adaptive corruptions and guarantees adaptive soundness. In fact, being a UC NIZK protocol in a multi-party, multi-instance setting, it is also adaptive Zero-Knowledge. Our construction is very different from that of GOS: it is based on the recent line of work on NIZK using Correlation Intractable (CI) hash functions, and can be based on a variety of assumptions (e.g. LWE, or LPN and DDH). In order to adapt the use of CI functions to adaptive corruptions, we extend the CI-based technique to start from Sigma protocols that offer only computational soundness. We also apply our technique to the adaptively-secure interactive Zero-Knowledge argument of Hazay and Venkitasubramaniam (Crypto 16), which applies directly to the circuit for the desired predicate, hence avoiding expensive Karp reductions. ∗Member of the CPIIS. Supported by NSF Awards 1931714, 1801564, 1414119, and the DARPA SIEVE program.