ETH Zürich » Computer Science » Theory » Cryptography

Complexity Theory

The security of most of today's cryptosystems are based on the computational intractability of certain computational problems. Yet from a cryptographic point of view, complexity theory is still in its childhood, far from proving the kind of results needed to prove the security of cryptographic schemes. The following publications deal with complexity-theoretic issues.

A note on the role of complexity theory in cryptography


Research Highlights

  • Parallel repetition of games. In [Hol06b] a significantly simplified proof of Ran Raz' (SIAM J. Comput. 27, 1998) parallel repetition theorem for games was given.
  • Pseudo-random generators from one-way functions. In a seminal paper, Håstad, Impagliazzo, Levin, and Luby showed that pseudo-random generators exist if and only if one-way functions exist. The construction they propose to obtain a pseudo-random generator from an n-bit one-way function uses O(n^8) random bits in the input (which is the most important complexity measure of such a construction). In [Hol06a] a significantly simplified and improved reduction is presented.

Publications Concerning This Topic

Kfir Barhum and Ueli Maurer
UOWHFs from OWFs: Trading regularity for efficiency
Progress in Cryptology — LATINCRYPT 2012, Lecture Notes in Computer Science, Springer-Verlag, vol. 7533, pp. 234–253, Oct 2012.
Available files: [ PDF ] [ Abstract ] [ BibTeX ]
Divesh Aggarwal and Chandan Dubey
Improved hardness results for unique shortest vector problem
In submission, 2012.
Available files: [ Abstract ] [ BibTeX ]
Divesh Aggarwal and Ueli Maurer
The Leakage-Resilience Limit of a Computational Problem is Equal to its Unpredictability Entropy
Advances in Cryptology - Asiacrypt 2011, Lecture Notes in Computer Science, Springer-Verlag, vol. 7073, pp. 686-701, 2011.
Available files: [ PDF ] [ Abstract ] [ BibTeX ]
Thomas Holenstein
Parallel Repetition: Simplifications and the No-Signaling Case
Proc. 39th ACM Symposium on Theory of Computing — STOC 2007, pp. 411–419, Jun 2007.
Available files: [ Abstract ] [ BibTeX ]
Thomas Holenstein
Parallel Repetition: Simplifications and the No-Signaling Case
Jul 2006, Available at http://arxiv.org/abs/cs.CC/0607139.
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 ]
Thomas Holenstein
Pseudorandom Generators from One-Way Functions: A Simple Construction for Any Hardness
Theory of Cryptography Conference — TCC 2006, Lecture Notes in Computer Science, Springer-Verlag, pp. 443–461, Mar 2006.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Ueli Maurer
Abstract Models of Computation in Cryptography
Cryptography and Coding 2005, Lecture Notes in Computer Science, Springer-Verlag, vol. 3796, pp. 1–12, Dec 2005.
Available files: [ PDF ] [ Abstract ] [ BibTeX ]
Martin Hirt and Jesper Buus Nielsen
Upper Bounds on the Communication Complexity of Optimally Resilient Cryptographic Multiparty Computation
Advances in Cryptology — ASIACRYPT 2005, Lecture Notes in Computer Science, Springer-Verlag, vol. 3788, pp. 79–99, Dec 2005.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Thomas Holenstein and Renato Renner
One-Way Secret-Key Agreement and Applications to Circuit Polarization and Immunization of Public-Key Encryption
Advances in Cryptology — CRYPTO 2005, Lecture Notes in Computer Science, Springer-Verlag, pp. 478–493, Aug 2005.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Thomas Holenstein
Key Agreement from Weak Bit Agreement
Proc. 37th ACM Symposium on Theory of Computing — STOC 2005, pp. 664–673, May 2005.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Thomas Holenstein, Ueli Maurer, and Johan Sjödin
Complete Classification of Bilinear Hard-Core Functions
Advances in Cryptology — CRYPTO 2004, Lecture Notes in Computer Science, Springer-Verlag, vol. 3152, pp. 73–91, Aug 2004.
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 ]
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 ]
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 ]
Ueli Maurer and Stefan Wolf
The Generic Complexity of Index-Search Problems and Applications to Cryptography
1997, Manuscript.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Stefan Dziembowski
Bounded-Variable Fixpoint Queries are {PSPACE}-complete
Computer Science Logic '96, Lecture Notes in Computer Science, Springer-Verlag, vol. 1258, pp. 89–105, Sep 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 ]
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 ]
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 ]
Ueli Maurer
Factoring with an Oracle
Advances in Cryptology — EUROCRYPT '92, Lecture Notes in Computer Science, Springer-Verlag, vol. 658, pp. 429–436, May 1992, Final version: [Mau96].
Available files: [ Abstract ] [ BibTeX ]

© IACR | Springer | ACM | IEEE


Main Research Page