Paper 2021/927

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

Shuichi Katsumata

Abstract

Many of the recent advanced lattice-based Σ-/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 classical ROM, existing proof techniques are incapable of proving them secure in the 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 -/public-coin HVZK interactive protocols into QROM secure NIZKs. Our transform builds on a new primitive called 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 . This compares favorably to the Unruh transform that requires a factor of more than .

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in CRYPTO 2021
Keywords
zero knowledgepost quantumlattices
Contact author(s)
shuichi katsumata000 @ gmail com
History
2021-07-09: received
Short URL
https://ia.cr/2021/927
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/927,
      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},
      url = {https://eprint.iacr.org/2021/927}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.