More Web Proxy on the site http://driver.im/

research-article

Practical Lattice-Based Zero-Knowledge Proofs for Integer Relations

Authors:

Vadim Lyubashevsky,

Ngoc Khanh Nguyen,

Gregor SeilerAuthors Info & Claims

CCS '20: Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security

Pages 1051 - 1070

https://doi.org/10.1145/3372297.3417894

Published: 02 November 2020 Publication History

Abstract

We present a novel lattice-based zero-knowledge proof system for showing that (arbitrary-sized) committed integers satisfy additive and multiplicative relationships. The proof sizes of our schemes are between two to three orders of magnitude smaller than in the lattice proof system of Libert et al. (CRYPTO 2018) for the same relations. Because the proof sizes of our protocols grow linearly in the integer length, our proofs will eventually be longer than those produced by quantum-safe succinct proof systems for general circuits (e.g. Ligero, Aurora, etc.). But for relations between reasonably-sized integers (e.g. $512$-bit), our proofs still result in the smallest zero-knowledge proof system based on a quantum-safe assumption. Of equal importance, the run-time of our proof system is at least an order of magnitude faster than any other quantum-safe scheme.

Supplementary Material

MOV File (Copy of CCS2020_fpc522_Practical Lattice-Based - Nano Zii.mov)

Presentation video

Download
112.37 MB

References

[1]

Scott Ames, Carmit Hazay, Yuval Ishai, and Muthuramakrishnan Venkitasubramaniam. 2017. Ligero: Lightweight Sublinear Arguments Without a Trusted Setup. In ACM Conference on Computer and Communications Security. ACM, 2087--2104.

Digital Library

[2]

Thomas Attema, Vadim Lyubashevsky, and Gregor Seiler. 2020. Practical Product Proofs for Lattice Commitments. IACR Cryptology ePrint Archive (2020). http://eprint.iacr.org/2020/517

[3]

Shi Bai and Steven D. Galbraith. 2014. An Improved Compression Technique for Signatures Based on Learning with Errors. In CT-RSA. 28--47.

[4]

Carsten Baum, Ivan Damgård, Vadim Lyubashevsky, Sabine Oechsner, and Chris Peikert. 2018. More Efficient Commitments from Structured Lattice Assumptions. In SCN. 368--385.

[5]

Carsten Baum and Vadim Lyubashevsky. 2017. Simple Amortized Proofs of Shortness for Linear Relations over Polynomial Rings. IACR Cryptology ePrint Archive, Vol. 2017 (2017), 759. http://eprint.iacr.org/2017/759

[6]

Carsten Baum and Ariel Nof. 2020. Concretely-Efficient Zero-Knowledge Arguments for Arithmetic Circuits and Their Application to Lattice-Based Cryptography. In Public Key Cryptography (1) (Lecture Notes in Computer Science), Vol. 12110. Springer, 495--526.

[7]

Eli Ben-Sasson, Alessandro Chiesa, Michael Riabzev, Nicholas Spooner, Madars Virza, and Nicholas P. Ward. 2019. Aurora: Transparent Succinct Arguments for R1CS. In EUROCRYPT (1) (Lecture Notes in Computer Science), Vol. 11476. Springer, 103--128.

Digital Library

[8]

Jonathan Bootle, Vadim Lyubashevsky, and Gregor Seiler. 2019. Algebraic Techniques for Short(er) Exact Lattice-Based Zero-Knowledge Proofs. In CRYPTO (1) (Lecture Notes in Computer Science), Vol. 11692. Springer, 176--202.

[9]

Joppe W. Bos, Léo Ducas, Eike Kiltz, Tancrè de Lepoint, Vadim Lyubashevsky, John M. Schanck, Peter Schwabe, Gregor Seiler, and Damien Stehlé. 2018. CRYSTALS - Kyber: A CCA-Secure Module-Lattice-Based KEM. In 2018 IEEE European Symposium on Security and Privacy, EuroS&P. 353--367.

[10]

Jelle Don, Serge Fehr, and Christian Majenz. 2020. The Measure-and-Reprogram Technique 2.0: Multi-Round Fiat-Shamir and More. CoRR, Vol. abs/2003.05207 (2020).

[11]

Jelle Don, Serge Fehr, Christian Majenz, and Christian Schaffner. 2019. Security of the Fiat-Shamir Transformation in the Quantum Random-Oracle Model. In CRYPTO (2) (Lecture Notes in Computer Science), Vol. 11693. Springer, 356--383.

[12]

Lé o Ducas, Eike Kiltz, Tancrè de Lepoint, Vadim Lyubashevsky, Peter Schwabe, Gregor Seiler, and Damien Stehlé. 2018. CRYSTALS-Dilithium: A Lattice-Based Digital Signature Scheme. IACR Trans. Cryptogr. Hardw. Embed. Syst., Vol. 2018, 1 (2018), 238--268.

[13]

Muhammed F. Esgin, Ngoc Khanh Nguyen, and Gregor Seiler. 2020. Practical Exact Proofs from Lattices: New Techniques to Exploit Fully-Splitting Rings. IACR Cryptology ePrint Archive (2020). http://eprint.iacr.org/2020/518

[14]

Muhammed F. Esgin, Ron Steinfeld, Joseph K. Liu, and Dongxi Liu. 2019 a. Lattice-Based Zero-Knowledge Proofs: New Techniques for Shorter and Faster Constructions and Applications. In CRYPTO (1) (Lecture Notes in Computer Science), Vol. 11692. Springer, 115--146.

[15]

Muhammed F. Esgin, Ron Steinfeld, Amin Sakzad, Joseph K. Liu, and Dongxi Liu. 2019 b. Short Lattice-Based One-out-of-Many Proofs and Applications to Ring Signatures. In Applied Cryptography and Network Security - 17th International Conference, ACNS 2019, Bogota, Colombia, June 5--7, 2019, Proceedings (Lecture Notes in Computer Science), Robert H. Deng, Valérie Gauthier-Umana, Martin Ochoa, and Moti Yung (Eds.), Vol. 11464. Springer, 67--88. https://doi.org/10.1007/978--3-030--21568--2_4

[16]

Muhammed F. Esgin, Raymond K. Zhao, Ron Steinfeld, Joseph K. Liu, and Dongxi Liu. 2019 c. MatRiCT: Efficient, Scalable and Post-Quantum Blockchain Confidential Transactions Protocol. In ACM Conference on Computer and Communications Security. ACM, 567--584.

[17]

Joe Kilian. 1992. A Note on Efficient Zero-Knowledge Proofs and Arguments (Extended Abstract). In STOC. ACM, 723--732.

[18]

Eike Kiltz, Vadim Lyubashevsky, and Christian Schaffner. 2018. A Concrete Treatment of Fiat-Shamir Signatures in the Quantum Random-Oracle Model. In EUROCRYPT (3) (Lecture Notes in Computer Science), Vol. 10822. Springer, 552--586.

[19]

Adeline Langlois and Damien Stehlé. 2015. Worst-case to average-case reductions for module lattices. Designs, Codes and Cryptography, Vol. 75, 3 (2015), 565--599.

Digital Library

[20]

Beno^i t Libert, San Ling, Khoa Nguyen, and Huaxiong Wang. 2018. Lattice-Based Zero-Knowledge Arguments for Integer Relations. In CRYPTO (2) (Lecture Notes in Computer Science), Vol. 10992. Springer, 700--732.

[21]

Qipeng Liu and Mark Zhandry. 2019. Revisiting Post-quantum Fiat-Shamir. In CRYPTO (2) (Lecture Notes in Computer Science), Vol. 11693. Springer, 326--355.

[22]

Vadim Lyubashevsky. 2009. Fiat-Shamir with Aborts: Applications to Lattice and Factoring-Based Signatures. In ASIACRYPT. 598--616.

[23]

Vadim Lyubashevsky. 2019. Basic Lattice Cryptography: Encryption and Fiat-Shamir Signatures. (2019).

[24]

Vadim Lyubashevsky and Gregor Seiler. 2019. NTTRU: Truly Fast NTRU Using NTT. IACR Trans. Cryptogr. Hardw. Embed. Syst., Vol. 2019, 3 (2019), 180--201.

[25]

Silvio Micali. 2000. Computationally Sound Proofs. SIAM J. Comput., Vol. 30, 4 (2000), 1253--1298.

Digital Library

[26]

Gregor Seiler. 2018. Faster AVX2 optimized NTT multiplication for Ring-LWE lattice cryptography. IACR Cryptology ePrint Archive, Vol. 2018 (2018), 39. http://eprint.iacr.org/2018/039.

Cited By

Li WZhang ZGuo YChow SWan Z(2025)Succinct Hash-Based Arbitrary-Range ProofsIEEE Transactions on Information Forensics and Security10.1109/TIFS.2024.349780620(145-158)Online publication date: 2025
https://doi.org/10.1109/TIFS.2024.3497806
Wood TThomas KDean MKannan SLearney R(2024)Towards Post-Quantum Verifiable CredentialsProceedings of the 19th International Conference on Availability, Reliability and Security10.1145/3664476.3669932(1-10)Online publication date: 30-Jul-2024
https://dl.acm.org/doi/10.1145/3664476.3669932
Bai WChen LGao QZhang Z(2024)MPC-in-the-Head Framework without Repetition and its Applications to the Lattice-based Cryptography2024 IEEE Symposium on Security and Privacy (SP)10.1109/SP54263.2024.00157(578-596)Online publication date: 19-May-2024
https://doi.org/10.1109/SP54263.2024.00157
Show More Cited By

Index Terms

Practical Lattice-Based Zero-Knowledge Proofs for Integer Relations
1. Security and privacy
  1. Cryptography
    1. Public key (asymmetric) techniques

Recommendations

On New Zero-Knowledge Proofs for Lattice-Based Group Signatures with Verifier-Local Revocation
Information Security
Abstract
For lattice-based group signatures with verifier-local revocation (VLR), a group member who issues a signature on behalf of the whole group can validly prove to the verifiers with an efficient non-interactive zero-knowledge proof protocol, from ...
On New Zero-Knowledge Proofs for Fully Anonymous Lattice-Based Group Signature Scheme with Verifier-Local Revocation
Applied Cryptography and Network Security Workshops
Abstract
The first lattice-based verifier-local revocation group signature (GS-VLR) was introduced by Langlois et al. in 2014, and subsequently, a full and corrected version was proposed by Ling et al. in 2018. However, zero-knowledge proofs in both ...
Lattice-based certificateless encryption scheme

Certificateless public key cryptography (CL-PKC) can solve the problems of certificate management in a public key infrastructure (PKI) and of key escrows in identity-based public key cryptography (ID-PKC). In CL-PKC, the key generation center (KGC) does ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CCS '20: Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security

October 2020

2180 pages

ISBN:9781450370899

DOI:10.1145/3372297

General Chairs:
Jay Ligatti
University of South Florida, USA
,
Xinming Ou
University of South Florida, USA
,
Program Chairs:
Jonathan Katz
University of Maryland, USA
,
Giovanni Vigna
University of California-Santa Barbara, USA

Copyright © 2020 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSAC: ACM Special Interest Group on Security, Audit, and Control

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 November 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung

Conference

CCS '20

Sponsor:

SIGSAC

CCS '20: 2020 ACM SIGSAC Conference on Computer and Communications Security

November 9 - 13, 2020

Virtual Event, USA

Acceptance Rates

Overall Acceptance Rate 1,261 of 6,999 submissions, 18%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

35
Total Citations
View Citations
649
Total Downloads

Downloads (Last 12 months)79
Downloads (Last 6 weeks)7

Reflects downloads up to 28 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Li WZhang ZGuo YChow SWan Z(2025)Succinct Hash-Based Arbitrary-Range ProofsIEEE Transactions on Information Forensics and Security10.1109/TIFS.2024.349780620(145-158)Online publication date: 2025
https://doi.org/10.1109/TIFS.2024.3497806
Wood TThomas KDean MKannan SLearney R(2024)Towards Post-Quantum Verifiable CredentialsProceedings of the 19th International Conference on Availability, Reliability and Security10.1145/3664476.3669932(1-10)Online publication date: 30-Jul-2024
https://dl.acm.org/doi/10.1145/3664476.3669932
Bai WChen LGao QZhang Z(2024)MPC-in-the-Head Framework without Repetition and its Applications to the Lattice-based Cryptography2024 IEEE Symposium on Security and Privacy (SP)10.1109/SP54263.2024.00157(578-596)Online publication date: 19-May-2024
https://doi.org/10.1109/SP54263.2024.00157
Günsay EBetin Onur CCenk M(2024)A different base approach for better efficiency on range proofsJournal of Information Security and Applications10.1016/j.jisa.2024.10386085:COnline publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1016/j.jisa.2024.103860
Klooß MLai RNguyen NOsadnik M(2024)RoK, Paper, SISsors Toolkit for Lattice-Based Succinct ArgumentsAdvances in Cryptology – ASIACRYPT 202410.1007/978-981-96-0935-2_7(203-235)Online publication date: 10-Dec-2024
https://dl.acm.org/doi/10.1007/978-981-96-0935-2_7
Hwang ISeo JSong Y(2024)Concretely Efficient Lattice-Based Polynomial Commitment from Standard AssumptionsAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68403-6_13(414-448)Online publication date: 16-Aug-2024
https://doi.org/10.1007/978-3-031-68403-6_13
Bambury HBeguinet HRicosset TSageloli É(2024)Polytopes in the Fiat-Shamir with Aborts ParadigmAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68376-3_11(339-372)Online publication date: 16-Aug-2024
https://doi.org/10.1007/978-3-031-68376-3_11
Hofheinz DHostáková KLangrehr RUrsu B(2024)On Structure-Preserving Cryptography and LatticesPublic-Key Cryptography – PKC 202410.1007/978-3-031-57725-3_9(255-287)Online publication date: 15-Apr-2024
https://dl.acm.org/doi/10.1007/978-3-031-57725-3_9
Wang ZLai QLiu F(2024)Ring/Module Learning with Errors Under Linear Leakage – Hardness and ApplicationsPublic-Key Cryptography – PKC 202410.1007/978-3-031-57722-2_9(275-304)Online publication date: 14-Apr-2024
https://doi.org/10.1007/978-3-031-57722-2_9
Chen ZJiang YSong XChen L(2023)A Survey on Zero-Knowledge Authentication for Internet of ThingsElectronics10.3390/electronics1205114512:5(1145)Online publication date: 27-Feb-2023
https://doi.org/10.3390/electronics12051145
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten