Paper 2018/272
MultiTheorem Preprocessing NIZKs from Lattices
Sam Kim and David J. Wu
Abstract
Noninteractive zeroknowledge (NIZK) proofs are fundamental to modern cryptography. Numerous NIZK constructions are known in both the random oracle and the common reference string (CRS) models. In the CRS model, there exist constructions from several classes of cryptographic assumptions such as trapdoor permutations, pairings, and indistinguishability obfuscation. Notably absent from this list, however, are constructions from standard lattice assumptions. While there has been partial progress in realizing NIZKs from lattices for specific languages, constructing NIZK proofs (and arguments) for all of NP from standard lattice assumptions remains open. In this work, we make progress on this problem by giving the first construction of a multitheorem NIZK for NP from standard lattice assumptions in the preprocessing model. In the preprocessing model, a (trusted) setup algorithm generates proving and verification keys. The proving key is needed to construct proofs and the verification key is needed to check proofs. In the multitheorem setting, the proving and verification keys should be reusable for an unbounded number of theorems without compromising soundness or zeroknowledge. Existing constructions of NIZKs in the preprocessing model (or even the designatedverifier model) that rely on weaker assumptions like oneway functions or oblivious transfer are only secure in a singletheorem setting. Thus, constructing multitheorem NIZKs in the preprocessing model does not seem to be inherently easier than constructing them in the CRS model. We begin by constructing a multitheorem preprocessing NIZK directly from contexthiding homomorphic signatures. Then, we show how to efficiently implement the preprocessing step using a new cryptographic primitive called blind homomorphic signatures. This primitive may be of independent interest. Finally, we show how to leverage our new latticebased preprocessing NIZKs to obtain new malicioussecure MPC protocols purely from standard lattice assumptions.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 A major revision of an IACR publication in CRYPTO 2018
 Contact author(s)
 skim13 @ cs stanford edu
 History
 20180606: revised
 20180322: received
 See all versions
 Short URL
 https://ia.cr/2018/272
 License

CC BY
BibTeX
@misc{cryptoeprint:2018/272, author = {Sam Kim and David J. Wu}, title = {MultiTheorem Preprocessing {NIZKs} from Lattices}, howpublished = {Cryptology {ePrint} Archive, Paper 2018/272}, year = {2018}, url = {https://eprint.iacr.org/2018/272} }