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 ROM, existing proof techniques are incapable of proving them secure in the 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 .
@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.