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

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

Cybersecurity Seminars Online seminar
Monday, 12 July 2021
3 pm - 4 pm (AEST)

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 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 Sigma-/public-coin HVZK interactive protocols into QROM secure NIZKs. Our transform builds on a new primitive called 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 favourably to the Unruh transform that requires a factor of more than 50.

This talk is based on the following work:
Shuichi Katsumata, "A New Simple Technique to Bootstrap Various Lattice Zero-Knowledge Proofs to QROM Secure NIZKs", CRYPTO, 2021.

About the speaker

Shuichi Katsumata
Researcher, AIST

Dr. Shuichi Katsumata is a full-time researcher at the National Institute of Advanced Industrial Science and Technology (AIST), Japan, and is affiliated with PQShield, UK as a research consultant. He earned his PhD at the University of Tokyo in 2019. His area of research includes, but not limited to, lattices-based crypto, zero-knowledge proofs, and advanced forms of public key encryption and signature schemes such as identity-based encryption and ring signatures.

Monash University values the privacy of every individual's personal information and is committed to the protection of that information from unauthorised use and disclosure except where permitted by law. For information about the handling of your personal information please see Data Protection and Privacy Procedure and the relevant Data Protection and Privacy Collection Statement that applies to you depending on the nature of your interaction with us.

If you have any questions about how Monash University is collecting and handling your personal information, please contact our Data Protection and Privacy Office at dataprotectionofficer@monash.edu.


Event contact

Share this event