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

research-article

Public Access

Implementation and Evaluation of Improved Gaussian Sampling for Lattice Trapdoors

Authors:

Kamil Doruk Gür,

Yuriy Polyakov,

Gerard W. Ryan,

Erkay SavasAuthors Info & Claims

WAHC '18: Proceedings of the 6th Workshop on Encrypted Computing & Applied Homomorphic Cryptography

Pages 61 - 71

https://doi.org/10.1145/3267973.3267975

Published: 15 January 2018 Publication History

Abstract

We report on our implementation of a new Gaussian sampling algorithm for lattice trapdoors. Lattice trapdoors are used in a wide array of lattice-based cryptographic schemes including digital signatures, attributed-based encryption, program obfuscation and others. Our implementation provides Gaussian sampling for trapdoor lattices with prime moduli, and supports both single- and multi-threaded execution. We experimentally evaluate our implementation through its use in the GPV hash-and-sign digital signature scheme as a benchmark. We compare our design and implementation with prior work reported in the literature. The evaluation shows that our implementation 1) has smaller space requirements and faster runtime, 2) does not require multi-precision floating-point arithmetic, and 3) can be used for a broader range of cryptographic primitives than previous implementations.

References

[1]

Aydin Aysu, Cameron Patterson, and Patrick Schaumont. 2013. Low-cost and area-efficient FPGA implementations of lattice-based cryptography. In Hardware-Oriented Security and Trust (HOST), 2013 IEEE International Symposium on . 81--86.

[2]

Dan Boneh, Craig Gentry, Sergey Gorbunov, Shai Halevi, Valeria Nikolaenko, Gil Segev, Vinod Vaikuntanathan, and Dhinakaran Vinayagamurthy. 2014. Fully Key-Homomorphic Encryption, Arithmetic Circuit ABE and Compact Garbled Circuits .Springer Berlin Heidelberg, Berlin, Heidelberg, 533--556.

[3]

Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. 2014. (Leveled) Fully Homomorphic Encryption without Bootstrapping. ACM Transactions on Computation Theory (TOCT), Vol. 6, 3 (2014), 13.

Digital Library

[4]

Zvika Brakerski, Vinod Vaikuntanathan, Hoeteck Wee, and Daniel Wichs. 2016. Obfuscating Conjunctions Under Entropic Ring LWE. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science (ITCS '16). ACM, New York, NY, USA, 147--156.

Digital Library

[5]

Yuanmi Chen and Phong Q. Nguyen. 2011. BKZ 2.0: Better Lattice Security Estimates. In ASIACRYPT (Lecture Notes in Computer Science), Vol. 7073. Springer, 1--20.

Digital Library

[6]

Jean-Franccois Dhem and Jean-Jacques Quisquater. 2000. Recent Results on Modular Multiplications for Smart Cards. Smart Card Research and Applications, Jean-Jacques Quisquater and Bruce Schneier (Eds.). Lecture Notes in Computer Science, Vol. 1820. Springer Berlin Heidelberg, 336--352.

Digital Library

[7]

Nathan Dowlin, Ran Gilad-Bachrach, Kim Laine, Kristin Lauter, Michael Naehrig, and John Wernsing. 2015. Manual for using homomorphic encryption for bioinformatics. Microsoft Research (2015).

[8]

Léo Ducas and Phong Q. Nguyen. 2012. Faster Gaussian Lattice Sampling Using Lazy Floating-Point Arithmetic .Springer Berlin Heidelberg, Berlin, Heidelberg, 415--432.

Digital Library

[9]

Rachid El Bansarkhani and Johannes Buchmann. 2014. Improvement and Efficient Implementation of a Lattice-Based Signature Scheme .Springer Berlin Heidelberg, Berlin, Heidelberg, 48--67.

Digital Library

[10]

Junfeng Fan and Frederik Vercauteren. 2012. Somewhat Practical Fully Homomorphic Encryption. Cryptology ePrint Archive, Report 2012/144. (2012). http://eprint.iacr.org/.

[11]

Nicholas Genise and Daniele Micciancio. 2018. Faster Gaussian Sampling for Trapdoor Lattices with Arbitrary Modulus. In Advances in Cryptology -- EUROCRYPT 2018, Jesper Buus Nielsen and Vincent Rijmen (Eds.). Springer International Publishing, Cham, 174--203.

[12]

Craig Gentry, Shai Halevi, and Nigel Smart. 2012. Homomorphic Evaluation of the AES Circuit. Advances in Cryptology--CRYPTO 2012, Reihaneh Safavi-Naini and Ran Canetti (Eds.). Lecture Notes in Computer Science, Vol. 7417. Springer Berlin / Heidelberg, 850--867.

Digital Library

[13]

Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. 2008. Trapdoors for Hard Lattices and New Cryptographic Constructions. In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing (STOC '08). ACM, New York, NY, USA, 197--206.

Digital Library

[14]

Craig Gentry, Amit Sahai, and Brent Waters. 2013. Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based. Advances in Cryptology--CRYPTO 2013 . Springer, 75--92.

[15]

Shai Halevi and Victor Shoup. 2014. HElib-An Implementation of homomorphic encryption. (2014).

[16]

Vadim Lyubashevsky, Chris Peikert, and Oded Regev. 2013. A Toolkit for Ring-LWE Cryptography. In EUROCRYPT, Vol. 7881. Springer, 35--54.

[17]

Daniele Micciancio. 2011. Lattice-based cryptography. Encyclopedia of Cryptography and Security. Springer, 713--715.

[18]

Daniele Micciancio and Chris Peikert. 2012. Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller. In EUROCRYPT. 700--718.

Digital Library

[19]

Daniele Micciancio and Oded Regev. 2009. Lattice-based Cryptography .Springer Berlin Heidelberg, Berlin, Heidelberg, 147--191.

[20]

Daniele Micciancio and Michael Walter. 2017. Gaussian Sampling over the Integers: Efficient, Generic, Constant-Time. In Advances in Cryptology -- CRYPTO 2017, Jonathan Katz and Hovav Shacham (Eds.). Springer International Publishing, Cham, 455--485.

[21]

Chris Peikert. 2009. Public-key cryptosystems from the worst-case shortest vector problem. In Proceedings of the forty-first annual ACM symposium on Theory of computing. ACM, 333--342.

Digital Library

[22]

Chris Peikert. 2010. An Efficient and Parallel Gaussian Sampler for Lattices. In CRYPTO. 80--97.

Digital Library

[23]

Chris Peikert. 2016. A Decade of Lattice Cryptography. Foundations and Trends® in Theoretical Computer Science, Vol. 10, 4 (2016), 283--424.

Digital Library

[24]

Oded Regev. 2004. Quantum Computation and Lattice Problems. SIAM J. Comput., Vol. 33, 3 (2004), 738--760. Preliminary version in FOCS 2002.

Digital Library

[25]

Oded Regev. 2006. Lattice-based cryptography. In Annual International Cryptology Conference . Springer, 131--141.

Digital Library

Cited By

Chen EZhu YLiang KYin H(2023)Secure Remote Cloud File Sharing With Attribute-Based Access Control and Performance OptimizationIEEE Transactions on Cloud Computing10.1109/TCC.2021.310432311:1(579-594)Online publication date: 1-Jan-2023
https://doi.org/10.1109/TCC.2021.3104323
Deng JChen SChen JMeng W(2023)A Survey on Discrete Gaussian Samplers in Lattice Based CryptographyEmerging Information Security and Applications10.1007/978-3-031-23098-1_6(87-107)Online publication date: 4-Jan-2023
https://doi.org/10.1007/978-3-031-23098-1_6
Bert PEberhart GPrabel LRoux-Langlois ASabt M(2021)Implementation of Lattice Trapdoors on Modules and ApplicationsPost-Quantum Cryptography10.1007/978-3-030-81293-5_11(195-214)Online publication date: 15-Jul-2021
https://doi.org/10.1007/978-3-030-81293-5_11
Show More Cited By

Index Terms

Implementation and Evaluation of Improved Gaussian Sampling for Lattice Trapdoors
1. Security and privacy
  1. Cryptography
    1. Public key (asymmetric) techniques
      1. Digital signatures
2. Theory of computation
  1. Computational complexity and cryptography
    1. Cryptographic primitives
    2. Cryptographic protocols

Recommendations

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 ...
Post-quantum Strongly Unforgeable Identity-Based Signature Scheme from Lattices without Random Oracles
INCOS '13: Proceedings of the 2013 5th International Conference on Intelligent Networking and Collaborative Systems

Inspired by Agrawal, Boneh and Boyen's identity-based encryption scheme, we proposed a post-quantum identity-based signature scheme from lattices. In this construction, two distinct trapdoors are used to find short bases. One trapdoor enables the real ...
Improved Non-Repudiable Threshold Proxy Signature Scheme with Known Signers

In 2001, Hsu et al. proposed a non-repudiable threshold proxy signature with known signers. In their scheme, the proxy group cannot deny having signed the proxy signature if they did. However, Hsu et al.'s scheme is vulnerable to some attacks. A ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

WAHC '18: Proceedings of the 6th Workshop on Encrypted Computing & Applied Homomorphic Cryptography

October 2018

77 pages

ISBN:9781450359870

DOI:10.1145/3267973

Program Chairs:
Michael Brenner
Leibniz Universität Hannover, Germany
,
Kurt Rohloff
New Jersey Institute of Technology, USA

Copyright © 2018 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: 15 January 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Security Agency
IARPA
DARPA

Conference

CCS '18

Sponsor:

SIGSAC

CCS '18: 2018 ACM SIGSAC Conference on Computer and Communications Security

October 15 - 19, 2018

Toronto, Canada

Acceptance Rates

WAHC '18 Paper Acceptance Rate 6 of 17 submissions, 35%;

Overall Acceptance Rate 6 of 17 submissions, 35%

Upcoming Conference

CCS '25

Sponsor:
sigsac

ACM SIGSAC Conference on Computer and Communications Security

October 13 - 17, 2025

Taipei , Taiwan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
584
Total Downloads

Downloads (Last 12 months)143
Downloads (Last 6 weeks)37

Reflects downloads up to 02 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chen EZhu YLiang KYin H(2023)Secure Remote Cloud File Sharing With Attribute-Based Access Control and Performance OptimizationIEEE Transactions on Cloud Computing10.1109/TCC.2021.310432311:1(579-594)Online publication date: 1-Jan-2023
https://doi.org/10.1109/TCC.2021.3104323
Deng JChen SChen JMeng W(2023)A Survey on Discrete Gaussian Samplers in Lattice Based CryptographyEmerging Information Security and Applications10.1007/978-3-031-23098-1_6(87-107)Online publication date: 4-Jan-2023
https://doi.org/10.1007/978-3-031-23098-1_6
Bert PEberhart GPrabel LRoux-Langlois ASabt M(2021)Implementation of Lattice Trapdoors on Modules and ApplicationsPost-Quantum Cryptography10.1007/978-3-030-81293-5_11(195-214)Online publication date: 15-Jul-2021
https://doi.org/10.1007/978-3-030-81293-5_11
Cheon JCho HJung JLee JLee K(2020)Efficient Identity-Based Encryption from LWRInformation Security and Cryptology – ICISC 201910.1007/978-3-030-40921-0_14(225-241)Online publication date: 13-Feb-2020
https://doi.org/10.1007/978-3-030-40921-0_14
Hu YJia H(2019)A new Gaussian sampling for trapdoor lattices with arbitrary modulusDesigns, Codes and Cryptography10.1007/s10623-019-00635-8Online publication date: 30-Apr-2019
https://doi.org/10.1007/s10623-019-00635-8
Chen YGenise NMukherjee P(2019)Approximate Trapdoors for Lattices and Smaller Hash-and-Sign SignaturesAdvances in Cryptology – ASIACRYPT 201910.1007/978-3-030-34618-8_1(3-32)Online publication date: 22-Nov-2019
https://doi.org/10.1007/978-3-030-34618-8_1
Wang ZWu Q(2019)A Practical Lattice-Based Sequential Aggregate SignatureProvable Security10.1007/978-3-030-31919-9_6(94-109)Online publication date: 26-Sep-2019
https://doi.org/10.1007/978-3-030-31919-9_6
Walter M(2019)Sampling the Integers with Low Relative ErrorProgress in Cryptology – AFRICACRYPT 201910.1007/978-3-030-23696-0_9(157-180)Online publication date: 29-Jun-2019
https://doi.org/10.1007/978-3-030-23696-0_9
Genise NMicciancio DPolyakov Y(2019)Building an Efficient Lattice Gadget Toolkit: Subgaussian Sampling and MoreAdvances in Cryptology – EUROCRYPT 201910.1007/978-3-030-17656-3_23(655-684)Online publication date: 24-Apr-2019
https://doi.org/10.1007/978-3-030-17656-3_23
Bert PFouque PRoux-Langlois ASabt M(2018)Practical Implementation of Ring-SIS/LWE Based Signature and IBEPost-Quantum Cryptography10.1007/978-3-319-79063-3_13(271-291)Online publication date: 1-Apr-2018
https://doi.org/10.1007/978-3-319-79063-3_13
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Table of Contents