ETH Zürich » Computer Science » Theory » Cryptography

Public Key Cryptography

Research Highlights

  • Generic equivalence of breaking RSA and factoring. A long-standing open problem in cryptography is whether breaking the RSA cryptosystem is as hard as factoring the modulus, or whether it is potentially much easier. It is proved in [AM09] that breaking RSA and factoring are equivalent in a generic model of computation. Any generic algorithm for breaking RSA can be transformed into a factoring algorithm.
  • Inexistence of field-homomorphic one-way permutations. If a one-way permutation were field-homomorphic, this would allow for entirely new applications in cryptography, including secure computation with encrypted data. It was proved in [MR07] that field-homomorphic one-way permutations cannot exist.
  • Abstract models of computation in cryptography. Computational security proofs in cryptography, without unproven intractability assumptions, exist today only if one restricts the computational model. For example, one can prove a lower bound on the complexity of computing discrete logarithms in a cyclic group if one considers only generic algorithms which can not exploit the properties of the representation of the group elements. In [Mau05] an abstract model of computation is proposed which allows to capture such reasonable restrictions on the power of algorithms. All previously considered generic algorithms are special cases of this model, in which proofs are more elegant and simpler.
  • Cramer-Shoup cryptosystem. This public-key cryptosystem proposed in [CS98] was the first public-key cryptosystem secure (under a concrete intractability assumption) against the adaptive chosen-message attacks, the most powerful type of attack. All previous such schemes were highly inefficient.
  • Diffie-Hellman and discrete logarithms. In [Mau94] and [MW98d] we solved a long-standing open complexity-theoretic problem in cryptography, namely proving that breaking the Diffie-Hellman key agreement protocol (the first proposed public-key scheme by which public-key cryptography was founded) is as hard as computing discrete logarithms in the underlying group. It is easy to construct groups for which the equivalence holds while for an arbitrary group the equivalence holds under a very plausible number-theoretic conjecture.
  • Group signature scheme. In [CS97] the first efficient group signature scheme for large groups was proposed. A group signature scheme allows members of a group (e.g. a company) to sign anonymously on behalf of the group. In case of dispute a special authority can determine the identity of the signer.
  • Generation of prime numbers. In [Mau95a] the fastest known algorithm for generating prime numbers was proposed. The algorithm generates provable primes rather than only probable primes and is nevertheless faster than the known algorithms based on pseudo-primality tests. Several security conditions needed in public-key cryptography can be guaranteed without additional cost.
  • Non-interactive public-key cryptography, identity-based encryption (IBE). In 1984, Shamir proposed the concept of non-interactive public-key encryption where a user's identity can be used as his public-key and hence need not be requested. The first realization of this concept was proposed in [MY96]. Later this concept became known as identity-based encryption (IBE) and has developed into a prominent area of cryptography.

Publications Concerning This Topic

Sandro Coretti, Ueli Maurer, and Björn Tackmann
Constructing Confidential Channels from Authenticated Channels—Public-Key Encryption Revisited
Advances in Cryptology—ASIACRYPT 2013, Lecture Notes in Computer Science, Springer, vol. 8269, pp. 134–153, Dec 2013.
Available files: [ PDF ] [ Abstract ] [ BibTeX ]
Christian Matt and Ueli Maurer
A Constructive Approach to Functional Encryption
Cryptology ePrint Archive, Report 2013/559, Sep 2013.
Available files: [ PDF ] [ Abstract ] [ BibTeX ]
Markulf Kohlweiss, Ueli Maurer, Cristina Onete, Björn Tackmann, and Daniele Venturi
Anonymity-preserving Public-Key Encryption: A Constructive Approach
Privacy Enhancing Technologies — 13th International Symposium, Lecture Notes in Computer Science, Springer, vol. 7981, pp. 19–39, Jul 2013.
Available files: [ PDF ] [ Abstract ] [ BibTeX ]
Sandro Coretti, Ueli Maurer, and Björn Tackmann
A Constructive Perspective on Key Encapsulation
Number Theory and Cryptography, Lecture Notes in Computer Science, Springer, vol. 8260, pp. 226–239, 2013.
Available files: [ Abstract ] [ BibTeX ]
Joel Alwen and Chris Peikert
Generating Shorter Bases for Hard Random Lattices
Theory Comput. Syst., vol. 48, no. 3, pp. 535-553, 2011.
Available files: [ PDF ] [ Abstract ] [ BibTeX ]
Marc Fischlin, Anja Lehmann, Thomas Ristenpart, Thomas Shrimpton, Martijn Stam, and Stefano Tessaro
Random Oracles With(out) Programmability
Advances in Cryptology — ASIACRYPT 2010, Lecture Notes in Computer Science, Springer-Verlag, vol. 6477, pp. 303–320, Dec 2010.
Available files: [ PDF ] [ Abstract ] [ BibTeX ]
Joel Alwen, Yevgeniy Dodis, Moni Naor, Gil Segev, Shabsi Walfish, and Daniel Wichs
Public-Key Encryption in the Bounded-Retrieval Model
Advances in Cryptology - EUROCRYPT 2010, Lecture Notes in Computer Science, Springer-Verlag, vol. 6110, pp. 113-134, Aug 2010.
Available files: [ PDF ] [ Abstract ] [ BibTeX ]
Joel Alwen, Yevgeniy Dodis, and Daniel Wichs
Leakage-Resilient Public-Key Cryptography in the Bounded-Retrieval Model
Advances in Cryptology — CRYPTO 2009, Lecture Notes in Computer Science, Springer-Verlag, vol. 5973, pp. 36-54, Aug 2009.
Available files: [ PDF ] [ Abstract ] [ BibTeX ]
Joel Alwen and Chris Peikert
Generating Shorter Bases for Hard Random Lattices
26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009, Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, vol. 3, pp. 75-86, 2009.
Available files: [ PDF ] [ Abstract ] [ BibTeX ]
Douglas Wikström
Designated Confirmer Signatures Revisited
Theory of Cryptography Conference — TCC 2007, Lecture Notes in Computer Science, Springer-Verlag, vol. 4392, pp. 342–361, 2007.
Available files: [ Abstract ] [ BibTeX ]
Thomas Holenstein
Strengthening Key Agreement using Hard-Core Sets
PhD Thesis, {ETH Zurich}, 2006, Reprint as vol. 7 of ETH Series in Information Security and Cryptography}, {ISBN 3-86626-088-2}, {H}artung-{G}orre {V}erlag, {K}onstanz, 2006.
Available files: [ PDF ] [ Abstract ] [ BibTeX ]
Yevgeniy Dodis, Roberto Oliveira, and Krzysztof Pietrzak
On the Generic Insecurity of the Full Domain Hash
Advances in Cryptology — CRYPTO 2005, Lecture Notes in Computer Science, Springer-Verlag, vol. 3621, pp. 449–466, Aug 2005.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Marc Fischlin
Completely Non-Malleable Schemes
Automata, Languages and Programming — ICALP 2005, Lecture Notes in Computer Science, Springer-Verlag, vol. 3580, pp. 779–790, Jul 2005.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Endre Bangerter, Jan Camenisch, and Ueli Maurer
Efficient Proofs of Knowledge of Discrete Logarithms and Representations in Groups with Hidden Order
Public Key Cryptography — PKC 2005, Lecture Notes in Computer Science, Springer-Verlag, vol. 3386, pp. 154–171, Jan 2005.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Ueli Maurer
Intrinsic Limitations of Digital Signatures and How to Cope With Them
Proceedings of the 6th Information Security Conference — ISC '03, Lecture Notes in Computer Science, Springer-Verlag, vol. 2851, pp. 180–192, Oct 2003.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Ueli Maurer and Stefan Wolf
The {D}iffie-{H}ellman Protocol
Designs, Codes and Cryptography, Special Issue Public Key Cryptography, Kluwer Academic Publishers, vol. 19, no. 3, pp. 147–171, Jan 2000.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Ronald Cramer and Victor Shoup
Signature Schemes Based on the Strong {RSA} Assumption
5th {ACM} Conference on Computer and Communications Security — CCS '99, ACM, pp. 46–51, Nov 1999.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Anna Lysyanskaya, Ronald Rivest, Amit Sahai, and Stefan Wolf
Pseudonym Systems
Proceedings of Selected Areas in Cryptography — SAC '99, Lecture Notes in Computer Science, Springer-Verlag, vol. 1758, pp. 184–199, Aug 1999.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Ueli Maurer and Stefan Wolf
The Relationship Between Breaking the {D}iffie-{H}ellman Protocol and Computing Discrete Logarithms
SIAM Journal on Computing, vol. 28, no. 5, pp. 1689–1721, Apr 1999.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Ueli Maurer and Stefan Wolf
{D}iffie-{H}ellman, {D}ecision {D}iffie-{H}ellman, and Discrete Logarithms
IEEE International Symposium on Information Theory — ISIT '98, IEEE, pp. 327, Aug 1998.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Ronald Cramer and Victor Shoup
A Practical Public Key Cryptosystem Provably Secure against Adaptive Chosen Ciphertext Attack
Advances in Cryptology — CRYPTO '98, Lecture Notes in Computer Science, Springer-Verlag, vol. 1462, pp. 13–25, Aug 1998.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Ueli Maurer and Stefan Wolf
Lower Bounds on Generic Algorithms in Groups
Advances in Cryptology — EUROCRYPT '98, Lecture Notes in Computer Science, Springer-Verlag, vol. 1403, pp. 72–84, May 1998.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Ueli Maurer and Stefan Wolf
On the Hardness of the {D}iffie-{H}ellman Decision Problem
1998, Manuscript.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Jan Camenisch and Markus Stadler
Efficient Group Signature Schemes for Large Groups
Advances in Cryptology — CRYPTO '97, Lecture Notes in Computer Science, Springer-Verlag, vol. 1294, pp. 410–424, Aug 1997.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Jan Camenisch
Efficient and Generalized Group Signatures
Advances in Cryptology — EUROCRYPT '97, Lecture Notes in Computer Science, Springer-Verlag, vol. 1233, pp. 465–479, May 1997.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Ueli Maurer and Yacov Yacobi
A Non-interactive Public-Key Distribution System
Designs, Codes and Cryptography, vol. 9, no. 3, pp. 305–316, Nov 1996, Preliminary version: [MY91].
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Daniel Bleichenbacher and Ueli Maurer
On the Efficiency of One-time Digital Signatures
Advances in Cryptology — ASIACRYPT '96, Lecture Notes in Computer Science, Springer-Verlag, vol. 1163, pp. 196–209, Nov 1996.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Ueli Maurer and Stefan Wolf
{D}iffie-{H}ellman Oracles
Advances in Cryptology — CRYPTO '96, Lecture Notes in Computer Science, Springer-Verlag, vol. 1109, pp. 268–282, Aug 1996.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Daniel Bleichenbacher
Generating {ElGamal} Signatures Without Knowing the Secret Key
Advances in Cryptology — EUROCRYPT '96, Lecture Notes in Computer Science, Springer-Verlag, vol. 1070, pp. 10–18, May 1996.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Ueli Maurer and Stefan Wolf
On the Complexity of Breaking the {D}iffie-{H}ellman Protocol
Technical Report no. 244, Institute for Theoretical Computer Science, ETH Zurich, Apr 1996.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Daniel Bleichenbacher and Ueli Maurer
Optimal Tree-based One-time Digital Signature Schemes
Proc. 13th Symposium on Theoretical Aspects of Computer Science — STACS '96, Lecture Notes in Computer Science, Springer-Verlag, vol. 1046, pp. 363–374, Feb 1996.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Ueli Maurer and Pierre Schmid
A Calculus for Security Bootstrapping in Distributed Systems
Journal of Computer Security, vol. 4, no. 1, pp. 55–80, 1996, Preliminary version: [MS94].
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Ueli Maurer
On the Oracle Complexity of Factoring Integers
Computational Complexity, vol. 5, no. 4, pp. 237–247, 1996, Preliminary version: [Mau92f].
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Daniel Bleichenbacher, Wieb Bosma, and Arjen K. Lenstra
Some Remarks on {L}ucas-Based Cryptosystems
Advances in Cryptology — CRYPTO '95, Lecture Notes in Computer Science, Springer-Verlag, vol. 963, pp. 386–396, Aug 1995.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Markus Stadler, Jean-Marc Piveteau, and Jan Camenisch
Fair Blind Signatures
Advances in Cryptology — EUROCRYPT '95, Lecture Notes in Computer Science, Springer-Verlag, vol. 921, pp. 209–219, May 1995.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Ueli Maurer
Fast Generation of Prime Numbers and Secure Public-Key Cryptographic Parameters
Journal of Cryptology, vol. 8, no. 3, pp. 123–155, 1995, Preliminary version: [Mau89].
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Ueli Maurer
Towards the Equivalence of Breaking the {D}iffie-{H}ellman Protocol and Computing Discrete Logarithms
Advances in Cryptology — CRYPTO '94, Lecture Notes in Computer Science, Springer-Verlag, vol. 839, pp. 271–281, Aug 1994.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Daniel Bleichenbacher and Ueli Maurer
Directed Acyclic Graphs, One-way Functions and Digital Signatures
Advances in Cryptology — CRYPTO '94, Lecture Notes in Computer Science, Springer-Verlag, vol. 963, pp. 75–82, Aug 1994.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Jan Camenisch, Jean-Marc Piveteau, and Markus Stadler
Blind Signatures Based on the Discrete Logarithm Problem
Advances in Cryptology — EUROCRYPT '94, Lecture Notes in Computer Science, Springer-Verlag, vol. 950, pp. 428–432, May 1994.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Ueli Maurer and Yacov Yacobi
A Remark on a Non-Interactive Public-Key Distribution System
Advances in Cryptology — EUROCRYPT '92, Lecture Notes in Computer Science, Springer-Verlag, vol. 658, pp. 458–460, May 1992, This is a note on [MY91]. See [MY96] for the final version.
Available files: [ Abstract ] [ BibTeX ]
Kenji Koyama, Ueli Maurer, Tatsuaki Okamoto, and Scott Vanstone
New Public-Key Schemes Based on Elliptic Curves over the Ring ${Z}_n$
Advances in Cryptology — CRYPTO '91, Lecture Notes in Computer Science, Springer-Verlag, vol. 576, pp. 252–266, Aug 1991.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Ueli Maurer and Yacov Yacobi
Non-Interactive Public-key Cryptography
Advances in Cryptology — EUROCRYPT '91, Lecture Notes in Computer Science, Springer-Verlag, vol. 547, pp. 498–507, Apr 1991, Final version: [MY96], see also the note in [MY92].
Available files: [ Abstract ] [ BibTeX ]

© IACR | Springer | ACM | IEEE


Main Research Page