Lattice-based zero-knowledge proofs

new techniques for shorter and faster constructions and applications

Muhammed F. Esgin, Ron Steinfeld, Joseph K. Liu, Dongxi Liu

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

Abstract

We devise new techniques for design and analysis of efficient lattice-based zero-knowledge proofs (ZKP). First, we introduce one-shot proof techniques for non-linear polynomial relations of degree≥ 2, where the protocol achieves a negligible soundness error in a single execution, and thus performs signicantly better in both computation and communication compared to prior protocols requiring multiple repetitions. Such proofs with degree ≥ 2 have been crucial ingredients for important privacy-preserving protocols in the discrete logarithm setting, such as Bulletproofs (IEEE S&P '18) and arithmetic circuit arguments (EUROCRYPT '16). In contrast, one-shot proofs in lattice-based cryptography have previously only been shown for the linear case (k = 1) and a very specific quadratic case (k = 2), which are obtained as a special case of our technique.

Moreover, we introduce two speedup techniques for lattice-based ZKPs: a CRT-packing technique supporting "inter-slot" operations, and "NTTfriendly" tools that permit the use of fully-splitting rings. The former technique comes at almost no cost to the proof length, and the latter one barely increases it, which can be compensated for by tweaking the rejection sampling parameters while still having faster computation overall.

To illustrate the utility of our techniques, we show how to use them to build efficient relaxed proofs for important relations, namely proof of commitment to bits, one-out-of-many proof, range proof and set membership proof. Despite their relaxed nature, we further show how our proof systems can be used as building blocks for advanced cryptographic tools such as ring signatures.

Our ring signature achieves a dramatic improvement in length over all the existing proposals from lattices at the same security level. The computational evaluation also shows that our construction is highly likely to outperform all the relevant works in running times. Being efficient in both aspects, our ring signature is particularly suitable for both small-scale and large-scale applications such as cryptocurrencies and e-voting systems. No trusted setup is required for any of our proposals.

Original languageEnglish
Title of host publicationAdvances in Cryptology – CRYPTO 2019
Subtitle of host publication39th Annual International Cryptology Conference Santa Barbara, CA, USA, August 18–22, 2019 Proceedings, Part I
EditorsAlexandra Boldyreva, Daniele Micciancio
Place of PublicationCham Switzerland
PublisherSpringer
Pages115-146
Number of pages32
ISBN (Electronic)9783030269487
ISBN (Print)9783030269470
DOIs
Publication statusPublished - 2019
EventAdvances in Cryptology 2019 - Santa Barbara, United States of America
Duration: 18 Aug 201922 Aug 2019
Conference number: 39th
https://crypto.iacr.org/2019/

Publication series

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

Conference

ConferenceAdvances in Cryptology 2019
Abbreviated titleCRYPTO 2019
CountryUnited States of America
CitySanta Barbara
Period18/08/1922/08/19
Internet address

Keywords

  • CRT packing
  • Lattice-based cryptography
  • One-out-of-many proof
  • Range proof
  • Ring signature
  • Set membership proof
  • Zero-knowledge proof

Cite this

Esgin, M. F., Steinfeld, R., Liu, J. K., & Liu, D. (2019). Lattice-based zero-knowledge proofs: new techniques for shorter and faster constructions and applications. In A. Boldyreva, & D. Micciancio (Eds.), Advances in Cryptology – CRYPTO 2019 : 39th Annual International Cryptology Conference Santa Barbara, CA, USA, August 18–22, 2019 Proceedings, Part I (pp. 115-146). (Lecture Notes in Computer Science ; Vol. 11692 ). Cham Switzerland: Springer. https://doi.org/10.1007/978-3-030-26948-7_5
Esgin, Muhammed F. ; Steinfeld, Ron ; Liu, Joseph K. ; Liu, Dongxi. / Lattice-based zero-knowledge proofs : new techniques for shorter and faster constructions and applications. Advances in Cryptology – CRYPTO 2019 : 39th Annual International Cryptology Conference Santa Barbara, CA, USA, August 18–22, 2019 Proceedings, Part I. editor / Alexandra Boldyreva ; Daniele Micciancio. Cham Switzerland : Springer, 2019. pp. 115-146 (Lecture Notes in Computer Science ).
@inproceedings{22202b1d44db49daa6b34fc0e40f5810,
title = "Lattice-based zero-knowledge proofs: new techniques for shorter and faster constructions and applications",
abstract = "We devise new techniques for design and analysis of efficient lattice-based zero-knowledge proofs (ZKP). First, we introduce one-shot proof techniques for non-linear polynomial relations of degree k ≥ 2, where the protocol achieves a negligible soundness error in a single execution, and thus performs signicantly better in both computation and communication compared to prior protocols requiring multiple repetitions. Such proofs with degree k ≥ 2 have been crucial ingredients for important privacy-preserving protocols in the discrete logarithm setting, such as Bulletproofs (IEEE S&P '18) and arithmetic circuit arguments (EUROCRYPT '16). In contrast, one-shot proofs in lattice-based cryptography have previously only been shown for the linear case (k = 1) and a very specific quadratic case (k = 2), which are obtained as a special case of our technique.Moreover, we introduce two speedup techniques for lattice-based ZKPs: a CRT-packing technique supporting {"}inter-slot{"} operations, and {"}NTTfriendly{"} tools that permit the use of fully-splitting rings. The former technique comes at almost no cost to the proof length, and the latter one barely increases it, which can be compensated for by tweaking the rejection sampling parameters while still having faster computation overall.To illustrate the utility of our techniques, we show how to use them to build efficient relaxed proofs for important relations, namely proof of commitment to bits, one-out-of-many proof, range proof and set membership proof. Despite their relaxed nature, we further show how our proof systems can be used as building blocks for advanced cryptographic tools such as ring signatures.Our ring signature achieves a dramatic improvement in length over all the existing proposals from lattices at the same security level. The computational evaluation also shows that our construction is highly likely to outperform all the relevant works in running times. Being efficient in both aspects, our ring signature is particularly suitable for both small-scale and large-scale applications such as cryptocurrencies and e-voting systems. No trusted setup is required for any of our proposals.",
keywords = "CRT packing, Lattice-based cryptography, One-out-of-many proof, Range proof, Ring signature, Set membership proof, Zero-knowledge proof",
author = "Esgin, {Muhammed F.} and Ron Steinfeld and Liu, {Joseph K.} and Dongxi Liu",
year = "2019",
doi = "10.1007/978-3-030-26948-7_5",
language = "English",
isbn = "9783030269470",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "115--146",
editor = "Alexandra Boldyreva and Daniele Micciancio",
booktitle = "Advances in Cryptology – CRYPTO 2019",

}

Esgin, MF, Steinfeld, R, Liu, JK & Liu, D 2019, Lattice-based zero-knowledge proofs: new techniques for shorter and faster constructions and applications. in A Boldyreva & D Micciancio (eds), Advances in Cryptology – CRYPTO 2019 : 39th Annual International Cryptology Conference Santa Barbara, CA, USA, August 18–22, 2019 Proceedings, Part I. Lecture Notes in Computer Science , vol. 11692 , Springer, Cham Switzerland, pp. 115-146, Advances in Cryptology 2019, Santa Barbara, United States of America, 18/08/19. https://doi.org/10.1007/978-3-030-26948-7_5

Lattice-based zero-knowledge proofs : new techniques for shorter and faster constructions and applications. / Esgin, Muhammed F.; Steinfeld, Ron; Liu, Joseph K.; Liu, Dongxi.

Advances in Cryptology – CRYPTO 2019 : 39th Annual International Cryptology Conference Santa Barbara, CA, USA, August 18–22, 2019 Proceedings, Part I. ed. / Alexandra Boldyreva; Daniele Micciancio. Cham Switzerland : Springer, 2019. p. 115-146 (Lecture Notes in Computer Science ; Vol. 11692 ).

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

TY - GEN

T1 - Lattice-based zero-knowledge proofs

T2 - new techniques for shorter and faster constructions and applications

AU - Esgin, Muhammed F.

AU - Steinfeld, Ron

AU - Liu, Joseph K.

AU - Liu, Dongxi

PY - 2019

Y1 - 2019

N2 - We devise new techniques for design and analysis of efficient lattice-based zero-knowledge proofs (ZKP). First, we introduce one-shot proof techniques for non-linear polynomial relations of degree k ≥ 2, where the protocol achieves a negligible soundness error in a single execution, and thus performs signicantly better in both computation and communication compared to prior protocols requiring multiple repetitions. Such proofs with degree k ≥ 2 have been crucial ingredients for important privacy-preserving protocols in the discrete logarithm setting, such as Bulletproofs (IEEE S&P '18) and arithmetic circuit arguments (EUROCRYPT '16). In contrast, one-shot proofs in lattice-based cryptography have previously only been shown for the linear case (k = 1) and a very specific quadratic case (k = 2), which are obtained as a special case of our technique.Moreover, we introduce two speedup techniques for lattice-based ZKPs: a CRT-packing technique supporting "inter-slot" operations, and "NTTfriendly" tools that permit the use of fully-splitting rings. The former technique comes at almost no cost to the proof length, and the latter one barely increases it, which can be compensated for by tweaking the rejection sampling parameters while still having faster computation overall.To illustrate the utility of our techniques, we show how to use them to build efficient relaxed proofs for important relations, namely proof of commitment to bits, one-out-of-many proof, range proof and set membership proof. Despite their relaxed nature, we further show how our proof systems can be used as building blocks for advanced cryptographic tools such as ring signatures.Our ring signature achieves a dramatic improvement in length over all the existing proposals from lattices at the same security level. The computational evaluation also shows that our construction is highly likely to outperform all the relevant works in running times. Being efficient in both aspects, our ring signature is particularly suitable for both small-scale and large-scale applications such as cryptocurrencies and e-voting systems. No trusted setup is required for any of our proposals.

AB - We devise new techniques for design and analysis of efficient lattice-based zero-knowledge proofs (ZKP). First, we introduce one-shot proof techniques for non-linear polynomial relations of degree k ≥ 2, where the protocol achieves a negligible soundness error in a single execution, and thus performs signicantly better in both computation and communication compared to prior protocols requiring multiple repetitions. Such proofs with degree k ≥ 2 have been crucial ingredients for important privacy-preserving protocols in the discrete logarithm setting, such as Bulletproofs (IEEE S&P '18) and arithmetic circuit arguments (EUROCRYPT '16). In contrast, one-shot proofs in lattice-based cryptography have previously only been shown for the linear case (k = 1) and a very specific quadratic case (k = 2), which are obtained as a special case of our technique.Moreover, we introduce two speedup techniques for lattice-based ZKPs: a CRT-packing technique supporting "inter-slot" operations, and "NTTfriendly" tools that permit the use of fully-splitting rings. The former technique comes at almost no cost to the proof length, and the latter one barely increases it, which can be compensated for by tweaking the rejection sampling parameters while still having faster computation overall.To illustrate the utility of our techniques, we show how to use them to build efficient relaxed proofs for important relations, namely proof of commitment to bits, one-out-of-many proof, range proof and set membership proof. Despite their relaxed nature, we further show how our proof systems can be used as building blocks for advanced cryptographic tools such as ring signatures.Our ring signature achieves a dramatic improvement in length over all the existing proposals from lattices at the same security level. The computational evaluation also shows that our construction is highly likely to outperform all the relevant works in running times. Being efficient in both aspects, our ring signature is particularly suitable for both small-scale and large-scale applications such as cryptocurrencies and e-voting systems. No trusted setup is required for any of our proposals.

KW - CRT packing

KW - Lattice-based cryptography

KW - One-out-of-many proof

KW - Range proof

KW - Ring signature

KW - Set membership proof

KW - Zero-knowledge proof

UR - http://www.scopus.com/inward/record.url?scp=85071769450&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-26948-7_5

DO - 10.1007/978-3-030-26948-7_5

M3 - Conference Paper

SN - 9783030269470

T3 - Lecture Notes in Computer Science

SP - 115

EP - 146

BT - Advances in Cryptology – CRYPTO 2019

A2 - Boldyreva, Alexandra

A2 - Micciancio, Daniele

PB - Springer

CY - Cham Switzerland

ER -

Esgin MF, Steinfeld R, Liu JK, Liu D. Lattice-based zero-knowledge proofs: new techniques for shorter and faster constructions and applications. In Boldyreva A, Micciancio D, editors, Advances in Cryptology – CRYPTO 2019 : 39th Annual International Cryptology Conference Santa Barbara, CA, USA, August 18–22, 2019 Proceedings, Part I. Cham Switzerland: Springer. 2019. p. 115-146. (Lecture Notes in Computer Science ). https://doi.org/10.1007/978-3-030-26948-7_5