Practical exact proofs from lattices: new techniques to exploit fully-splitting rings

Muhammed F. Esgin, Ngoc Khanh Nguyen, Gregor Seiler

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

Abstract

We propose a very fast lattice-based zero-knowledge proof system for exactly proving knowledge of a ternary solution s→ ∈ { - 1, 0, 1 }n to a linear equation As→ = u→ over Zq, which improves upon the protocol by Bootle, Lyubashevsky and Seiler (CRYPTO 2019) by producing proofs that are shorter by a factor of 8. At the core lies a technique that utilizes the module-homomorphic BDLOP commitment scheme (SCN 2018) over the fully splitting cyclotomic ring Zq[ X] / (Xd+ 1 ) to prove scalar products with the NTT vector of a secret polynomial.

Original languageEnglish
Title of host publicationAdvances in Cryptology – ASIACRYPT 2020
Subtitle of host publication26th International Conference on the Theory and Application of Cryptology and Information Security Daejeon, South Korea, December 7–11, 2020 Proceedings, Part II
EditorsShiho Moriai, Huaxiong Wang
Place of PublicationCham Switzerland
PublisherSpringer
Pages259-288
Number of pages30
ISBN (Electronic)9783030648343
ISBN (Print)9783030648336
DOIs
Publication statusPublished - 2020
EventInternational Conference on the Theory and Application of Cryptology and Information Security 2020 - Daejeon, Korea, Republic of (South)
Duration: 7 Dec 202011 Dec 2020
Conference number: 26th
https://link.springer.com/book/10.1007/978-3-030-64834-3 (Proceedings)
https://asiacrypt.iacr.org/2020/ (Website)

Publication series

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

Conference

ConferenceInternational Conference on the Theory and Application of Cryptology and Information Security 2020
Abbreviated titleASIACRYPT 2020
CountryKorea, Republic of (South)
CityDaejeon
Period7/12/2011/12/20
Internet address

Cite this