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

Article

Lattice mixing and vanishing trapdoors: a framework for fully secure short signatures and more

Author:

Xavier BoyenAuthors Info & Claims

PKC'10: Proceedings of the 13th international conference on Practice and Theory in Public Key Cryptography

Pages 499 - 517

https://doi.org/10.1007/978-3-642-13013-7_29

Published: 26 May 2010 Publication History

Abstract

We propose a framework for adaptive security from hard random lattices in the standard model. Our approach borrows from the recent Agrawal-Boneh-Boyen families of lattices, which can admit reliable and punctured trapdoors, respectively used in reality and in simulation. We extend this idea to make the simulation trapdoors cancel not for a specific forgery but on a non-negligible subset of the possible challenges. Conceptually, we build a compactly representable, large family of input-dependent “mixture” lattices, set up with trapdoors that “vanish” for a secret subset which we hope the forger will target. Technically, we tweak the lattice structure to achieve “naturally nice” distributions for arbitrary choices of subset size. The framework is very general. Here we obtain fully secure signatures, and also IBE, that are compact, simple, and elegant.

References

[1]

Agrawal, S., Boneh, D., Boyen, X.: Efficient lattice (H)IBE in the standard model. In: EUROCRYPT (2010)

[2]

Agrawal, S., Boneh, D., Boyen, X.: Lattice basis delegation in fixed dimension and shorter-ciphertext hierarchical IBE (2010) (manuscript)

[3]

Agrawal, S., Boyen, X.: Identity-based encryption from lattices in the standard model (2009) (manuscript), http://www.cs.stanford.edu/~xb/ab09/

[4]

Aharonov, D., Regev, O.: Lattice problems in NP n coNP. Journal of the ACM 52(5), 749-765 (2005)

[5]

Ajtai, M.: Generating hard instances of lattice problems (extended abstract). In: STOC (1996)

[6]

Ajtai, M.: Generating hard instances of the short basis problem. In: Wiedermann, J., Van Emde Boas, P., Nielsen, M. (eds.) ICALP 1999. LNCS, vol. 1644, p. 1. Springer, Heidelberg (1999)

[7]

Alwen, J., Peikert, C.: Generating shorter bases for hard random lattices. In: STACS (2009)

[8]

Boneh, D., Boyen, X.: Efficient selective-ID secure identity based encryption without random oracles. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 223-238. Springer, Heidelberg (2004)

[9]

Boneh, D., Boyen, X.: Efficient lattice (H)IBE in the standard model from the BB-1 framework (2009) (manuscript), http://rump2009.cr.yp.to/

[10]

Canetti, R., Halevi, S., Katz, J.: A forward-secure public-key encryption scheme. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656. Springer, Heidelberg (2003)

[11]

Cash, D., Hofheinz, D., Kiltz, E.: How to delegate a lattice basis. Cryptology ePrint Archive, Report 2009/351 (2009), http://eprint.iacr.org/

[12]

Gama, N., Nguyen, P.Q.: Predicting lattice reduction. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 31-51. Springer, Heidelberg (2008)

[13]

Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: STOC (2008)

[14]

Hohenberger, S., Waters, B.: Short and stateless signatures from the RSA assumption. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 654-670. Springer, Heidelberg (2009)

[15]

Lovász, L.: An Algorthmic Theory of Numbers, Graphs and Convexity. SIAM, Philadelphia (1986)

[16]

Lyubashevsky, V., Micciancio, D.: Asymptotically efficient lattice-based digital signatures. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 37-54. Springer, Heidelberg (2008)

[17]

Micciancio, D., Goldwasser, S.: Complexity of lattice problems: a cryptographic perspective. Kluwer Series on Engineering and Computer Science (2002)

[18]

Micciancio, D., Regev, O.: Worst-case to average-case reductions based on gaussian measures. In: FOCS (2004)

[19]

Micciancio, D., Regev, O.:Worst-case to average-case reductions based on Gaussian measures. SIAM Journal of Computing 37(1), 267-302 (2007)

[20]

Micciancio, D., Regev, O.: Lattice-based cryptography. In: Bernstein, D.J., Buchmann, J. (eds.) Post-quantum Cryptography. Springer, Heidelberg (2008)

[21]

Peikert, C.: Bonsai trees (or, arboriculture in lattice-based cryptography). Cryptology ePrint Archive, Report 2009/359 (2009), http://eprint.iacr.org/

[22]

Peikert, C., Rosen, A.: Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 145-166. Springer, Heidelberg (2006)

[23]

Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: STOC (2005)

[24]

Waters, B.: Efficient identity-based encryption without random oracles. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 114-127. Springer, Heidelberg (2005)

Cited By

Chen CLai QLu YYu Y(2024)More Efficient Two-Stage Sampling Technique and Its ApplicationsData Security and Privacy Protection10.1007/978-981-97-8546-9_5(88-108)Online publication date: 25-Oct-2024
https://dl.acm.org/doi/10.1007/978-981-97-8546-9_5
Hanaoka GKatsumata SKimura KTakemure KYamada S(2024)Tighter Adaptive IBEs and VRFs: Revisiting Waters’ Artificial AbortTheory of Cryptography10.1007/978-3-031-78020-2_5(124-155)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1007/978-3-031-78020-2_5
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
Show More Cited By

Lattice mixing and vanishing trapdoors: a framework for fully secure short signatures and more
1. Theory of computation

Recommendations

Lattice signatures without trapdoors
EUROCRYPT'12: Proceedings of the 31st Annual international conference on Theory and Applications of Cryptographic Techniques

We provide an alternative method for constructing lattice-based digital signatures which does not use the "hash-and-sign" methodology of Gentry, Peikert, and Vaikuntanathan (STOC 2008). Our resulting signature scheme is secure, in the random oracle ...
Lattice Trapdoors and IBE from Middle-Product LWE
Theory of Cryptography
Abstract
Middle-product learning with errors (MP-LWE) was recently introduced by Rosca, Sakzad, Steinfeld and Stehlé (CRYPTO 2017) as a way to combine the efficiency of Ring-LWE with the more robust security guarantees of plain LWE. While Ring-LWE is at ...
Identity-Based Signature from Lattices Without Trapdoors
Information and Communications Security
Abstract
Currently, the majority of lattice-base identity-based signature (LB-IBS) schemes rely on lattice trapdoor technique introduced by Gentry, Peikert, and Vaikuntanathan. However, this approach significantly impacts computational efficiency. In light ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

PKC'10: Proceedings of the 13th international conference on Practice and Theory in Public Key Cryptography

May 2010

517 pages

ISBN:3642130127

Editors:
Phong Q. Nguyen
Département d'Informatique, École Normale Supérieure, 45 rue d'Ulm, Paris Cedex 05, France
,
David Pointcheval
Département d'Informatique, École Normale Supérieure, 45 rue d'Ulm, Paris Cedex 05, France

Sponsors

Ingenico: Ingenico
Google Inc.
ENS: ENS
technicolor

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 26 May 2010

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

80
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Chen CLai QLu YYu Y(2024)More Efficient Two-Stage Sampling Technique and Its ApplicationsData Security and Privacy Protection10.1007/978-981-97-8546-9_5(88-108)Online publication date: 25-Oct-2024
https://dl.acm.org/doi/10.1007/978-981-97-8546-9_5
Hanaoka GKatsumata SKimura KTakemure KYamada S(2024)Tighter Adaptive IBEs and VRFs: Revisiting Waters’ Artificial AbortTheory of Cryptography10.1007/978-3-031-78020-2_5(124-155)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1007/978-3-031-78020-2_5
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
Blömer JBobolz JPorzenheim L(2023)A Generic Construction of an Anonymous Reputation System and Instantiations from LatticesAdvances in Cryptology – ASIACRYPT 202310.1007/978-981-99-8724-5_13(418-452)Online publication date: 4-Dec-2023
https://dl.acm.org/doi/10.1007/978-981-99-8724-5_13
Pursharthi KMishra D(2023)Cryptanalysis with Countermeasure on the SIS Based Signature SchemeSecurity, Privacy, and Applied Cryptography Engineering10.1007/978-3-031-51583-5_6(92-100)Online publication date: 14-Dec-2023
https://dl.acm.org/doi/10.1007/978-3-031-51583-5_6
Kumar RPadhye SRawal S(2023)Cryptanalysis of Short and Provable Secure Lattice-Based Signature SchemeSecurity, Privacy, and Applied Cryptography Engineering10.1007/978-3-031-51583-5_5(86-91)Online publication date: 14-Dec-2023
https://dl.acm.org/doi/10.1007/978-3-031-51583-5_5
Chen SChen JMiyaji AChen K(2023)Constant-Size Group Signatures with Message-Dependent Opening from LatticesProvable and Practical Security10.1007/978-3-031-45513-1_10(166-185)Online publication date: 20-Oct-2023
https://dl.acm.org/doi/10.1007/978-3-031-45513-1_10
Chen LDong CEl Kassem NNewton CWang Y(2023)Hash-Based Direct Anonymous AttestationPost-Quantum Cryptography10.1007/978-3-031-40003-2_21(565-600)Online publication date: 16-Aug-2023
https://dl.acm.org/doi/10.1007/978-3-031-40003-2_21
Han SLiu SWang ZGu D(2023)Almost Tight Multi-user Security Under Adaptive Corruptions from LWE in the Standard ModelAdvances in Cryptology – CRYPTO 202310.1007/978-3-031-38554-4_22(682-715)Online publication date: 20-Aug-2023
https://dl.acm.org/doi/10.1007/978-3-031-38554-4_22
Jeudy CRoux-Langlois ASanders O(2023)Lattice Signature with Efficient Protocols, Application to Anonymous CredentialsAdvances in Cryptology – CRYPTO 202310.1007/978-3-031-38545-2_12(351-383)Online publication date: 20-Aug-2023
https://dl.acm.org/doi/10.1007/978-3-031-38545-2_12
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents