Short lattice-based one-out-of-many proofs and applications to ring signatures

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

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

Abstract

In this work, we construct a short one-out-of-many proof from (module) lattices, allowing one to prove knowledge of a secret associated with one of the public values in a set. The proof system builds on a combination of ideas from the efficient proposals in the discrete logarithm setting by Groth and Kohlweiss (EUROCRYPT ’15) and Bootle et al. (ESORICS ’15), can have logarithmic communication complexity in the set size and does not require a trusted setup. Our work resolves an open problem mentioned by Libert et al. (EUROCRYPT ’16) of how to efficiently extend the above discrete logarithm proof techniques to the lattice setting. To achieve our result, we introduce new technical tools for design and analysis of algebraic lattice-based zero-knowledge proofs, which may be of independent interest. Using our proof system as a building block, we design a short ring signature scheme, whose security relies on “post-quantum” lattice assumptions. Even for a very large ring size such as 1 billion, our ring signature size is only 3 MB for 128-bit security level compared to 216 MB in the best existing lattice-based result by Libert et al. (EUROCRYPT ’16).

Original languageEnglish
Title of host publicationApplied Cryptography and Network Security
Subtitle of host publication17th International Conference, ACNS 2019 Bogota, Colombia, June 5–7, 2019 Proceedings
EditorsRobert H. Deng, Valérie Gauthier-Umaña, Martín Ochoa, Moti Yung
Place of PublicationCham Switzerland
PublisherSpringer
Pages67-88
Number of pages22
ISBN (Electronic)9783030215682
ISBN (Print)9783030215675
DOIs
Publication statusPublished - 2019
EventInternational Conference on Applied Cryptography and Network Security 2019 - Bogota, Colombia
Duration: 5 Jun 20197 Jun 2019
Conference number: 17th
https://www.acns19.com/

Publication series

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

Conference

ConferenceInternational Conference on Applied Cryptography and Network Security 2019
Abbreviated titleACNS 2019
CountryColombia
CityBogota
Period5/06/197/06/19
Internet address

Keywords

  • Lattice-based cryptography
  • Ring signature
  • Zero-knowledge proof

Cite this

Esgin, M. F., Steinfeld, R., Sakzad, A., Liu, J. K., & Liu, D. (2019). Short lattice-based one-out-of-many proofs and applications to ring signatures. In R. H. Deng, V. Gauthier-Umaña, M. Ochoa, & M. Yung (Eds.), Applied Cryptography and Network Security: 17th International Conference, ACNS 2019 Bogota, Colombia, June 5–7, 2019 Proceedings (pp. 67-88). (Lecture Notes in Computer Science ; Vol. 11464 ). Cham Switzerland: Springer. https://doi.org/10.1007/978-3-030-21568-2_4
Esgin, Muhammed F. ; Steinfeld, Ron ; Sakzad, Amin ; Liu, Joseph K. ; Liu, Dongxi. / Short lattice-based one-out-of-many proofs and applications to ring signatures. Applied Cryptography and Network Security: 17th International Conference, ACNS 2019 Bogota, Colombia, June 5–7, 2019 Proceedings. editor / Robert H. Deng ; Valérie Gauthier-Umaña ; Martín Ochoa ; Moti Yung. Cham Switzerland : Springer, 2019. pp. 67-88 (Lecture Notes in Computer Science ).
@inproceedings{9b35ebaa9c3e42d4bda677629e9b7a25,
title = "Short lattice-based one-out-of-many proofs and applications to ring signatures",
abstract = "In this work, we construct a short one-out-of-many proof from (module) lattices, allowing one to prove knowledge of a secret associated with one of the public values in a set. The proof system builds on a combination of ideas from the efficient proposals in the discrete logarithm setting by Groth and Kohlweiss (EUROCRYPT ’15) and Bootle et al. (ESORICS ’15), can have logarithmic communication complexity in the set size and does not require a trusted setup. Our work resolves an open problem mentioned by Libert et al. (EUROCRYPT ’16) of how to efficiently extend the above discrete logarithm proof techniques to the lattice setting. To achieve our result, we introduce new technical tools for design and analysis of algebraic lattice-based zero-knowledge proofs, which may be of independent interest. Using our proof system as a building block, we design a short ring signature scheme, whose security relies on “post-quantum” lattice assumptions. Even for a very large ring size such as 1 billion, our ring signature size is only 3 MB for 128-bit security level compared to 216 MB in the best existing lattice-based result by Libert et al. (EUROCRYPT ’16).",
keywords = "Lattice-based cryptography, Ring signature, Zero-knowledge proof",
author = "Esgin, {Muhammed F.} and Ron Steinfeld and Amin Sakzad and Liu, {Joseph K.} and Dongxi Liu",
year = "2019",
doi = "10.1007/978-3-030-21568-2_4",
language = "English",
isbn = "9783030215675",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "67--88",
editor = "Deng, {Robert H.} and Val{\'e}rie Gauthier-Uma{\~n}a and Mart{\'i}n Ochoa and Moti Yung",
booktitle = "Applied Cryptography and Network Security",

}

Esgin, MF, Steinfeld, R, Sakzad, A, Liu, JK & Liu, D 2019, Short lattice-based one-out-of-many proofs and applications to ring signatures. in RH Deng, V Gauthier-Umaña, M Ochoa & M Yung (eds), Applied Cryptography and Network Security: 17th International Conference, ACNS 2019 Bogota, Colombia, June 5–7, 2019 Proceedings. Lecture Notes in Computer Science , vol. 11464 , Springer, Cham Switzerland, pp. 67-88, International Conference on Applied Cryptography and Network Security 2019, Bogota, Colombia, 5/06/19. https://doi.org/10.1007/978-3-030-21568-2_4

Short lattice-based one-out-of-many proofs and applications to ring signatures. / Esgin, Muhammed F.; Steinfeld, Ron; Sakzad, Amin; Liu, Joseph K.; Liu, Dongxi.

Applied Cryptography and Network Security: 17th International Conference, ACNS 2019 Bogota, Colombia, June 5–7, 2019 Proceedings. ed. / Robert H. Deng; Valérie Gauthier-Umaña; Martín Ochoa; Moti Yung. Cham Switzerland : Springer, 2019. p. 67-88 (Lecture Notes in Computer Science ; Vol. 11464 ).

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

TY - GEN

T1 - Short lattice-based one-out-of-many proofs and applications to ring signatures

AU - Esgin, Muhammed F.

AU - Steinfeld, Ron

AU - Sakzad, Amin

AU - Liu, Joseph K.

AU - Liu, Dongxi

PY - 2019

Y1 - 2019

N2 - In this work, we construct a short one-out-of-many proof from (module) lattices, allowing one to prove knowledge of a secret associated with one of the public values in a set. The proof system builds on a combination of ideas from the efficient proposals in the discrete logarithm setting by Groth and Kohlweiss (EUROCRYPT ’15) and Bootle et al. (ESORICS ’15), can have logarithmic communication complexity in the set size and does not require a trusted setup. Our work resolves an open problem mentioned by Libert et al. (EUROCRYPT ’16) of how to efficiently extend the above discrete logarithm proof techniques to the lattice setting. To achieve our result, we introduce new technical tools for design and analysis of algebraic lattice-based zero-knowledge proofs, which may be of independent interest. Using our proof system as a building block, we design a short ring signature scheme, whose security relies on “post-quantum” lattice assumptions. Even for a very large ring size such as 1 billion, our ring signature size is only 3 MB for 128-bit security level compared to 216 MB in the best existing lattice-based result by Libert et al. (EUROCRYPT ’16).

AB - In this work, we construct a short one-out-of-many proof from (module) lattices, allowing one to prove knowledge of a secret associated with one of the public values in a set. The proof system builds on a combination of ideas from the efficient proposals in the discrete logarithm setting by Groth and Kohlweiss (EUROCRYPT ’15) and Bootle et al. (ESORICS ’15), can have logarithmic communication complexity in the set size and does not require a trusted setup. Our work resolves an open problem mentioned by Libert et al. (EUROCRYPT ’16) of how to efficiently extend the above discrete logarithm proof techniques to the lattice setting. To achieve our result, we introduce new technical tools for design and analysis of algebraic lattice-based zero-knowledge proofs, which may be of independent interest. Using our proof system as a building block, we design a short ring signature scheme, whose security relies on “post-quantum” lattice assumptions. Even for a very large ring size such as 1 billion, our ring signature size is only 3 MB for 128-bit security level compared to 216 MB in the best existing lattice-based result by Libert et al. (EUROCRYPT ’16).

KW - Lattice-based cryptography

KW - Ring signature

KW - Zero-knowledge proof

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

U2 - 10.1007/978-3-030-21568-2_4

DO - 10.1007/978-3-030-21568-2_4

M3 - Conference Paper

SN - 9783030215675

T3 - Lecture Notes in Computer Science

SP - 67

EP - 88

BT - Applied Cryptography and Network Security

A2 - Deng, Robert H.

A2 - Gauthier-Umaña, Valérie

A2 - Ochoa, Martín

A2 - Yung, Moti

PB - Springer

CY - Cham Switzerland

ER -

Esgin MF, Steinfeld R, Sakzad A, Liu JK, Liu D. Short lattice-based one-out-of-many proofs and applications to ring signatures. In Deng RH, Gauthier-Umaña V, Ochoa M, Yung M, editors, Applied Cryptography and Network Security: 17th International Conference, ACNS 2019 Bogota, Colombia, June 5–7, 2019 Proceedings. Cham Switzerland: Springer. 2019. p. 67-88. (Lecture Notes in Computer Science ). https://doi.org/10.1007/978-3-030-21568-2_4