13 March 2014, Theoretical Computer Science Seminar, Tommaso Gagliardoni (TU Darmstadt, Germany)

Abstract:

The theoretical potential of quantum computing questions the long-term security of many modern cryptographical schemes. This led to the development, in the last few decades, of post-quantum cryptography, where the security of a scheme is based on the difficulty of solving some hard mathematical problem which is considered to be too hard even for quantum computers. Most of these problems have so far survived the trial of time and their use for post-quantum primitives is therefore considered to be a fairly reasonable assumption. However, until recently, little focus has been put on analyzing the provable security (in the quantum world) of cryptographical schemes built on quantum-secure problems. This led to the paradox of developing many of such schemes, where the underlying computational assumption is quantum-hard, but the overall scheme is not provably so. At Asiacrypt 2011 a new model to deal with security proofs in the presence of quantum adversaries has been proposed as an improvement of the Random Oracle Model (ROM): the Quantum Random Oracle Model (QROM). Very recent and subsequent works have confirmed the usefulness of this tool for proving the quantum security of many primitives, from PRGs to symmetric encryption. In this talk I will describe the challenges of adapting classical proofs in the QROM. I will present one of our latest results about the security (and insecurity) of digital signatures derived from the Fiat-Shamir Transformation (FST) - a very efficient and widely used procedure to turn identification schemes into signature schemes. The FST is provably secure in the classical ROM, but such a security proof fails in the QROM. By using both QROM reprogramming and meta-reduction techniques, we have found a surprising result about the security of these signatures. I will also present another approach to realizing secure signature schemes from identification schemes in a provably secure way through the use of on-line extractors, and I will discuss the challenges and open problems to be faced when trying to adapt such proofs in the QROM setting. joint work with Oezguer Dagdelen and Marc Fischlin preprint: http://eprint.iacr.org/2013/245.pdf

For more information, please contact c.schaffner at uva.nl