Paper 2022/141

Efficient Hybrid Exact/Relaxed Lattice Proofs and Applications to Rounding and VRFs

Muhammed F. Esgin, Monash University, CSIRO's Data61
Ron Steinfeld, Monash University
Dongxi Liu, CSIRO's Data61
Sushmita Ruj, UNSW Sydney

In this work, we study hybrid exact/relaxed zero-knowledge proofs from lattices, where the proved relation is exact in one part and relaxed in the other. Such proofs arise in important real-life applications such as those requiring verifiable PRF evaluation and have so far not received significant attention as a standalone problem. We first introduce a general framework, LANES+, for realizing such hybrid proofs efficiently by combining standard relaxed proofs of knowledge RPoK and the LANES framework (due to a series of works in Crypto'20, Asiacrypt'20, ACM CCS'20). The latter framework is a powerful lattice-based proof system that can prove exact linear and multiplicative relations. The advantage of LANES+ is its ability to realize hybrid proofs more efficiently by exploiting RPoK for the high-dimensional part of the secret witness while leaving a low-dimensional secret witness part for the exact proof that is proven at a significantly lower cost via LANES. Thanks to the flexibility of LANES+, other exact proof systems can also be supported. We apply our LANES+ framework to construct substantially shorter proofs of rounding, which is a central tool for verifiable deterministic lattice-based cryptography. Based on our rounding proof, we then design an efficient long-term verifiable random function (VRF), named LaV. LaV leads to the shortest VRF outputs among the proposals of standard (i.e., long-term and stateless) VRFs based on quantum-safe assumptions. Of independent interest, we also present generalized results for challenge difference invertibility, a fundamental soundness security requirement for many proof systems.

Note: Clarified some discussion about range proof (last paragraph of P.26 and last paragraph of P.32)

Available format(s)
Cryptographic protocols
Publication info
A minor revision of an IACR publication in CRYPTO 2023
LatticeZero-Knowledge ProofPost-QuantumLearning with RoundingVerifiable Random Function
Contact author(s)
muhammed esgin @ monash edu
ron steinfeld @ monash edu
dongxi liu @ data61 csiro au
sushmita ruj @ unsw edu au
2023-09-01: last of 2 revisions
2022-02-09: received
See all versions
Short URL
Creative Commons Attribution


      author = {Muhammed F. Esgin and Ron Steinfeld and Dongxi Liu and Sushmita Ruj},
      title = {Efficient Hybrid Exact/Relaxed Lattice Proofs and Applications to Rounding and VRFs},
      howpublished = {Cryptology ePrint Archive, Paper 2022/141},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.