Efficient hybrid exact/relaxed lattice proofs and applications to rounding and VRFs

Muhammed F. Esgin, Ron Steinfeld, Dongxi Liu, Sushmita Ruj

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

1 Citation (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationAdvances in Cryptology – CRYPTO 2023 - 43rd Annual International Cryptology Conference, CRYPTO 2023 Santa Barbara, CA, USA, August 20–24, 2023 Proceedings, Part V
EditorsHelena Handschuh, Anna Lysyanskaya
Place of PublicationCham Switzerland
PublisherSpringer
Pages484-517
Number of pages34
ISBN (Electronic)9783031385544
ISBN (Print)9783031385537
DOIs
Publication statusPublished - 2023
EventAdvances in Cryptology 2023 - Santa Barbara, United States of America
Duration: 20 Aug 202324 Aug 2023
Conference number: 43rd
https://link.springer.com/chapter/10.1007/978-3-031-38554-4_16 (Proceedings)
https://crypto.iacr.org/2023/ (Website)

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume14085
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceAdvances in Cryptology 2023
Abbreviated titleCRYPTO 2023
Country/TerritoryUnited States of America
CitySanta Barbara
Period20/08/2324/08/23
Internet address

Keywords

  • Lattice
  • Learning with Rounding
  • Post-Quantum
  • Verifiable Random Function
  • Zero-Knowledge Proofs

Cite this