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
Divesh Aggarwal and Chandan DubeyImproved 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