Paper 2021/927

A New Simple Technique to Bootstrap Various Lattice Zero-Knowledge Proofs to QROM Secure NIZKs

Shuichi Katsumata


Many of the recent advanced lattice-based $\Sigma$-/public-coin honest verifier (HVZK) interactive protocols based on the techniques developed by Lyubashevsky (Asiacrypt'09, Eurocrypt'12) can be transformed into a non-interactive zero-knowledge (NIZK) proof in the random oracle model (ROM) using the Fiat-Shamir transform. Unfortunately, although they are known to be secure in the $\mathit{classical}$ ROM, existing proof techniques are incapable of proving them secure in the $\mathit{quantum}$ ROM (QROM). Alternatively, while we could instead rely on the Unruh transform (Eurocrypt'15), the resulting QROM secure NIZK will incur a large overhead compared to the underlying interactive protocol. In this paper, we present a new simple semi-generic transform that compiles many existing lattice-based $\Sigma$-/public-coin HVZK interactive protocols into QROM secure NIZKs. Our transform builds on a new primitive called $\textit{extractable linear homomorphic commitment}$ protocol. The resulting NIZK has several appealing features: it is not only a proof of knowledge but also straight-line extractable; the proof overhead is smaller compared to the Unruh transform; it enjoys a relatively small reduction loss; and it requires minimal background on quantum computation. To illustrate the generality of our technique, we show how to transform the recent Bootle et al.'s 5-round protocol with an exact sound proof (Crypto'19) into a QROM secure NIZK by increasing the proof size by a factor of $2.6$. This compares favorably to the Unruh transform that requires a factor of more than $50$.

Available format(s)
Public-key cryptography
Publication info
A major revision of an IACR publication in CRYPTO 2021
zero knowledgepost quantumlattices
Contact author(s)
shuichi katsumata000 @ gmail com
2021-07-09: received
Short URL
Creative Commons Attribution


      author = {Shuichi Katsumata},
      title = {A New Simple Technique to Bootstrap Various Lattice Zero-Knowledge Proofs to QROM Secure NIZKs},
      howpublished = {Cryptology ePrint Archive, Paper 2021/927},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.