For information on talks before 2013, or when you need slides that are not linked here, please contact me directly.

Show: all with video with slides with both

See also the list of publications.

- Post-Quantum Security of Fiat-Shamir Asiacrypt 2017 (Dec 04, 2017). Slides: PowerPoint. [show details...]
**Abstract:**The Fiat-Shamir construction (Crypto 1986) is an efficient transformation in the random oracle model for creating non-interactive proof systems and signatures from sigma-protocols. In classical cryptography, Fiat-Shamir is a zero-knowledge proof of knowledge assuming that the underlying sigma-protocol has the zero-knowledge and special soundness properties. Unfortunately, Ambainis, Rosmanis, and Unruh (FOCS 2014) ruled out non-relativizing proofs under those conditions in the quantum setting.In this paper, we show under which strengthened conditions the Fiat-Shamir proof system is still post-quantum secure. Namely, we show that if we require the sigma-protocol to have computational zero-knowledge and

*statistical*soundness, then Fiat-Shamir is a zero-knowledge simulation-sound proof system (but not a proof of knowledge!). Furthermore, we show that Fiat-Shamir leads to a post-quantum secure unforgeable signature scheme when additionally assuming a "dual-mode hard instance generator" for generating key pairs. - Security of Fiat-Shamir Dagstuhl Seminar 17401 - Quantum Cryptanalysis (Oct 05, 2017). Slides: PDF. [show details...]
**Abstract:**We describe how classical security proofs for Fiat-Shamir go wrong in the quantum setting, and what can be done about it. - Post-Quantum Security of Fiat-Shamir QCrypt 2017 (Sep 20, 2017). Video. [show details...]
**Abstract:**We show the post-quantum security of the Fiat-Shamir construction (Crypto 1986), both as a proof system, and as a signature scheme. We circumvent the impossibility results from Ambainis, Rosmanis, and Unruh (FOCS 2014) by strengthening the assumptions about the underlying sigma-protocol - What can go wrong with cryptography in the quantum setting? (Jun 28, 2017).
- Formal proofs in quantum cryptography TyQI 2017 - Trustworthy Quantum Information, Paris (Jun 19, 2017).
- Post-quantum security of hash functions Frontiers of Quantum Safe Cryptography (FOQUS), Paris (Apr 29, 2017). Slides: PowerPoint. [show details...]
**Abstract:**In classical cryptography, one of the most important properties of hash functions is collision-resistance. We explain why collision-resistance is (often) not a sufficient requirement in the post-quantum setting, and present an alternative, the collapsing-property. We discuss the security of Merkle-Damgård-hashes (e.g., SHA2) and sponge-based hashes (e.g., SHA3): under which conditions are they collapsing? Finally, we study the "indifferentiability" of the sponge-construction (on which classical proofs are based), and present ongoing work for showing that the sponge-construction is not indifferentiable. - Fiat-Shamir and the Quantum Forking Conjecture Grande Region Security and Reliability Day 2017, Luxembourg (Mar 09, 2017). Slides: PowerPoint. [show details...]
**Abstract:**Fiat-Shamir is a popular construction in classical cryptography for constructing signature schemes (and non-interactive proof systems). However, when considering security against quantum attackers, the security of Fiat-Shamir is largely unknown; all we know are negative results for various cases. In the present talk, we show progress towards a security proof for Fiat-Shamir. We introduce a new conjecture, the "Quantum Forking Conjecture" (QFC). The QFC is a problem in quantum query complexity. We show that if the QFC holds, then Fiat-Shamir is secure. This reduces a complex cryptographic question (involving quantum polynomial-time adversaries etc.) to a (hopefully simpler) query complexity problem. - Fiat-Shamir and the Quantum Forking Conjecture CQT CS Seminar (Feb 01, 2017). Slides: PowerPoint. [show details...]
**Abstract:**Fiat-Shamir is a popular construction in classical cryptography for constructing signature schemes (and non-interactive proof systems). However, when considering security against quantum attackers, the security of Fiat-Shamir is largely unknown; all we know are negative results for various cases. In the present talk, we show progress towards a security proof for Fiat-Shamir. We introduce a new conjecture, the "Quantum Forking Conjecture" (QFC). The QFC is a problem in quantum query complexity. We show that if the QFC holds, then Fiat-Shamir is secure. This reduces a complex cryptographic question (involving quantum polynomial-time adversaries etc.) to a (hopefully simpler) query complexity problem. - Collapse-binding quantum commitments without random oracles Asiacrypt 2016 (Dec 05, 2016). Slides: PowerPoint. Video. [show details...]
**Abstract:**We construct collapse-binding commitments in the standard model. Collapse-binding commitments were introduced by*Unruh, Computationally binding quantum commitments, 2016*to model the computational-binding property of commitments against quantum adversaries, but only constructions in the random oracle model were known.Furthermore, we show that collapse-binding commitments imply selected other security definitions for quantum commitments, answering an open question by (Unruh 2016).

- Quantum-security of commitment schemes and hash functions Cryptography Seminar, Math. Institute, Oxford U (Nov 16, 2016). Slides: PowerPoint. [show details...]
**Abstract:**Commitment schemes are a fundamental primitive in cryptography. Their security (more precisely the computational binding property) is closely tied to the notion of collision-resistance of hash functions. Classical definitions of binding and collision-resistance turn out too be weaker than expected when used in the quantum setting. We present strengthened notions (collapse-binding commitments and collapsing hash functions), explain why they are "better", and show how they be realized under standard assumptions. - Quantum-security of commitment schemes and hash functions Estonian-Latvian Theory Days (Oct 14, 2016). Slides: PowerPoint. [show details...]
**Abstract:**Commitment schemes are a fundamental primitive in cryptography. Their security (more precisely the computational binding property) is closely tied to the notion of collision-resistance of hash functions. Classical definitions of binding and collision-resistance turn out too be weaker than expected when used in the quantum setting. We present strengthened notions (collapse-binding commitments and collapsing hash functions), explain why they are "better", and show how they be realized under standard assumptions. - Quantum-security of commitment schemes and hash functions QuICS Seminar (Sep 21, 2016). Slides: PowerPoint. [show details...]
**Abstract:**Commitment schemes are a fundamental primitive in cryptography. Their security (more precisely the computational binding property) is closely tied to the notion of collision-resistance of hash functions. Classical definitions of binding and collision-resistance turn out too be weaker than expected when used in the quantum setting. We present strengthened notions (collapse-binding commitments and collapsing hash functions), explain why they are "better", and show how they be realized under standard assumptions. - Verification of quantum cryptography QCrypt 2016 (Sep 15, 2016). Slides: PowerPoint. Video. [show details...]
**Abstract:**In recent years, the computer-aided verification of cryptographic schemes has seen great progress. For example, various state-of-the-art cryptographic schemes were analyzed using the EasyCrypt tool using a probabilistic relational Hoare logic (pRHL). However, existing tools and logics are unsuited for analysis of quantum cryptographic protocols—be it protocols using quantum mechanics or protocols secure against quantum adversariesIn this talk, we explain why pRHL is not sound for quantum cryptography, and show how to lift the ideas from pRHL to the quantum setting.

- Computationally Binding Quantum Commitments Eurocrypt 2016 (May 11, 2016). Slides: PowerPoint. [show details...]
**Abstract:**We present a new definition of computationally binding commitment schemes in the quantum setting, which we call "collapse-binding". The definition applies to string commitments, composes in parallel, and works well with rewinding-based proofs. We give simple constructions of collapse-binding commitments in the random oracle model, giving evidence that they can be realized from hash functions like SHA-3. We evidence the usefulness of our definition by constructing three-round statistical zero-knowledge quantum arguments of knowledge for all NP languages. - Verification of quantum cryptography Estonian Theory Days 2016, Käo (Jan 30, 2016). Slides: PowerPoint. [show details...]
**Abstract:**In recent years, the verification of cryptographic schemes on the computational level (i.e., without symbolic abstractions) has seen great progress. For example, various state-of-the-art cryptographic schemes were analyzed using the EasyCrypt tool using a probabilistic relational Hoare logic (pRHL). However, existing tools and logics are unsuited for analysis of quantum cryptographic protocols – be it protocols using quantum mechanics, or protocols secure against quantum adversaries. In this talk, we explain why pRHL is not sound for quantum cryptography, and show how to lift the ideas from pRHL to the quantum setting. (With the long-term goal of getting a quantum version of EasyCrypt.) - Provable security (3/3) CROSSING 2016 Winter School on Quantum Security (Jan 29, 2016). Slides: PDF. Video. [show details...]
**Abstract:**A lecture on problems and solutions related to quantum random oracles. - Provable security (2/3) CROSSING 2016 Winter School on Quantum Security (Jan 28, 2016). Slides: PDF. Video. [show details...]
**Abstract:**A lecture on problems and solutions related to quantum rewinding. - Verification of Quantum Cryptography LSV Seminar, ENS Cachan (Jan 12, 2016). [show details...]
**Abstract:**In recent years, the verification of cryptographic schemes on the computational level (i.e., without symbolic abstractions) has seen great progress. For example, various state-of-the-art cryptographic schemes were analyzed using the EasyCrypt tool using a probabilistic relational Hoare logic (pRHL). However, existing tools and logics are unsuited for analysis of quantum cryptographic protocols – be it protocols using quantum mechanics, or protocols secure against quantum adversaries. In this talk, we explain why pRHL is not sound for quantum cryptography, and show how to lift the ideas from pRHL to the quantum setting. (With the long-term goal of getting a quantum version of EasyCrypt.) - Computationally binding quantum commitments QCrypt 2015 (Oct 01, 2015). Video. [show details...]
**Abstract:**We present a new definition of computationally binding commitment schemes in the quantum setting, which we call “collapse-binding”. The definition applies to string commitments, composes in parallel, and works well with rewinding-based proofs. We give simple constructions of collapse-binding commitments in the random oracle model, giving evidence that they can be realized from hash functions like SHA-3. We evidence the usefulness of our definition by constructing three-round statistical zero-knowledge quantum arguments of knowledge for all NP languages. - Non-interactive zero-knowledge proofs in the quantum random oracle model QCrypt 2015 (Sep 29, 2015). Slides: PDF. Video. [show details...]
**Abstract:**We present a construction for non-interactive zero-knowledge proofs of knowledge in the random oracle model from general sigma-protocols. Our construction is secure against quantum adversaries. Prior constructions (by Fiat-Shamir and by Fischlin) are only known to be secure against classical adversaries, and Ambainis, Rosmanis, Unruh (FOCS 2014) gave evidence that those constructions might not be secure against quantum adversaries in general. To prove security of our constructions, we additionally develop new techniques for adaptively programming the quantum random oracle. - Non-interactive quantum zero-knowledge proofs QALGO Workshop, Riga (Sep 22, 2015). Slides: PowerPoint. [show details...]
**Abstract:**Zero-knowledge proofs are a powerful tool in cryptography, allowing to prove the truth of a fact without revealing anything else. However, in their most basic form, ZK proofs are interactive, which makes them difficult to use in practice. Efficient transformations exist that make a ZK proof non-interactive (Fiat-Shamir, in the random-oracle model). But those fail in the quantum setting. We explain the difficulties in the quantum setting, show how to circumvent them, and close with a quantum query complexity problem whose solution would lead to a much simpler protocol. - Formal Verification of Quantum Cryptography FCS 2015 (Jul 13, 2015). [show details...]
**Abstract:**Formal verification of cryptographic protocols has been an active research area for several decades, mostly in idealized symbolic models, but more recently also with respect to actual computationally bounded attackers. However, verification is always restricted to classical protocols and classical adversaries (to the best of our knowledge). Yet, if quantum computers arrive some day, we need cryptography that is secure against them. In this talk, we discuss the question what challenges we face if we wish to take into account quantum adversaries and/or quan- tum protocols. We particularly focus on the verification of cryptography against computationally bounded attackers.The talk does not require any prior knowledge in quantum cryptography. We will discuss the nature, relevance and threats of quantum cryptography in the talk.

- Non-interactive zero-knowledge proofs in the quantum random oracle model Eurocrypt 2015 (Apr 30, 2015). [show details...]
**Abstract:**We present a construction for non-interactive zero-knowledge proofs of knowledge in the random oracle model from general sigma-protocols. Our construction is secure against quantum adversaries. Prior constructions (by Fiat-Shamir and by Fischlin) are only known to be secure against classical adversaries, and Ambainis, Rosmanis, Unruh (FOCS 2014) gave evidence that those constructions might not be secure against quantum adversaries in general. To prove security of our constructions, we additionally develop new techniques for adaptively programming the quantum random oracle. - Quantum position verification in the random oracle model Estonian Theory Days 2016, Rogosi (Feb 06, 2015). [show details...]
**Abstract:**We present a quantum position verification scheme in the random oracle model. In contrast to prior work, our scheme does not require bounded storage/retrieval/entanglement assumptions. We also give an efficient position-based authentication protocol. This enables secret and authenticated communication with an entity that is only identified by its position in space. - Quantum Attacks on Classical Proof Systems (The Hardness of Quantum Rewinding) FOCS 2014 (Oct 20, 2014). Video. [show details...]
**Abstract:**Quantum zero-knowledge proofs and quantum proofs of knowledge are inherently difficult to analyze because their security analysis uses rewinding. Certain cases of quantum rewinding are handled by the results by Watrous (SIAM J Comput, 2009) and Unruh (Eurocrypt 2012), yet in general the problem remains elusive. We show that this is not only due to a lack of proof techniques: relative to an oracle, we show that classically secure proofs and proofs of knowledge are insecure in the quantum setting.More specifically, sigma-protocols, the Fiat-Shamir construction, and Fischlin's proof system are quantum insecure under assumptions that are sufficient for classical security. Additionally, we show that for similar reasons, computationally binding commitments provide almost no security guarantees in a quantum setting.

To show these results, we develop the "pick-one trick", a general technique that allows an adversary to find one value satisfying a given predicate, but not two.

- Quantum position verification in the random oracle model QCrypt 2014 (Sep 04, 2014). Slides: PDF. Video. [show details...]
**Abstract:**We present a quantum position verification scheme in the random oracle model. In contrast to prior work, our scheme does not require bounded storage/retrieval/entanglement assumptions. We also give an efficient position-based authentication protocol. This enables secret and authenticated communication with an entity that is only identified by its position in space. - Quantum Attacks on Classical Proof Systems – The Hardness of Quantum Rewinding QCrypt 2014 (Sep 04, 2014). Slides: PDF. Video. [show details...]
**Abstract:**Quantum zero-knowledge proofs and quantum proofs of knowledge are inherently difficult to analyze because their security analysis uses rewinding. Certain cases of quantum rewinding are handled by the results by Watrous (SIAM J Comput, 2009) and Unruh (Eurocrypt 2012), yet in general the problem remains elusive. We show that this is not only due to a lack of proof techniques: relative to an oracle, we show that classically secure proofs and proofs of knowledge are insecure in the quantum setting.More specifically, sigma-protocols, the Fiat-Shamir construction, and Fischlin's proof system are quantum insecure under assumptions that are sufficient for classical security. Additionally, we show that for similar reasons, computationally binding commitments provide almost no security guarantees in a quantum setting.

- Quantum Position Verification Crypto (Aug 19, 2014). Video. [show details...]
**Abstract:**We present a quantum position verification scheme in the random oracle model. In contrast to prior work, our scheme does not require bounded storage/retrieval/entanglement assumptions. We also give an efficient position-based authentication protocol. This enables secret and authenticated communication with an entity that is only identified by its position in space. - Quantum Position Verification IQC Colloquium (Jul 07, 2014). [show details...]
**Abstract:**Position verification allows us to verify the position of a device in space (e.g., for enabling access to location based services). Unfortunately, position verification is known to be insecure in principle using only classical cryptography. We show how position verification can be achieved using quantum communication. - Revocable quantum timed-release encryption Eurocrypt 2014 (May 13, 2014). Slides: PDF. [show details...]
**Abstract:**Timed-release encryption is a kind of encryption scheme that a recipient can decrypt only after a specified amount of time T (assuming that we have a moderately precise estimate of his computing power). A revocable timed-release encryption is one where, before the time T is over, the sender can "give back" the timed-release encryption, provably loosing all access to the data. We show that revocable timed-release encryption without trusted parties is possible using quantum cryptography (while trivially impossible classically).Along the way, we develop two proof techniques in the quantum random oracle model that we believe may have applications also for other protocols.

Finally, we also develop another new primitive, unknown recipient encryption, which allows us to send a message to an unknown/unspecified recipient over an insecure network in such a way that at most one recipient will get the message.

- Quantum Proofs of Knowledge Quantum Games and Protocols, Simon's Institute (Feb 25, 2014). Video. [show details...]
**Abstract:**When (re)analysing the security of classical cryptographic protocols in a quantum setting, one finds that many classical proof techniques break down. Proofs of knowledge are a typical example of this: Their proofs usually involve rewinding, which is challenging in the quantum setting due to the no-cloning theorem. We present known solutions for proving the quantum security of proofs of knowledge, with a particular focus on what is not solved. - Non-interactive zero-knowledge with quantum random oracles Estonian Theory Days, Saka (Oct 26, 2013). Slides: PowerPoint. [show details...]
**Abstract:**Using so-called random oracles (an idealization of hash functions), there are very efficient constructions for zero-knowledge proofs, needing only a single message. In particular, these give us also efficient signature schemes.Unfortunately, so far very little progress has been made to show that these protocols are also secure against adversaries with quantum computers. We show why this is the case: the constructions cannot, in general, be secure against quantum adversaries! We also present modified constructions that circumvent these impossibilities.

Caveat: This is work in progress, not all proofs exist yet, all may be wrong.

(Joint work with Andris Ambainis and Ansis Rosmanis.)

- Everlasting Multi-Party Computation Crypto 2013 (Aug 22, 2013). Video. [show details...]
**Abstract:**A protocol has everlasting security if it is secure against adversaries that are computationally unlimited after the protocol execution. This models the fact that we cannot predict which cryptographic schemes will be broken, say, several decades after the protocol execution. In classical cryptography, everlasting security is difficult to achieve: even using trusted setup like common reference strings or signature cards, many tasks such as secure communication and oblivious transfer cannot be achieved with everlasting security. An analogous result in the quantum setting excludes protocols based on common reference strings, but not protocols using a signature card. We define a variant of the Universal Composability framework, everlasting quantum-UC, and show that in this model, we can implement secure communication and general multi-party computation using signature cards as trusted setup. - Quantum rewinding and other troubles Quantum and Crypto Day, Riga (Apr 25, 2013). Video. [show details...]
**Abstract:**One is often tempted to think that a classical protocol is quantum secure, as long as it is based on quantum secure hardness assumptions (e.g., lattice based cryptography). Unfortunately, this is not always the case - classical proof techniques often break down in a quantum setting. Especially when rewinding comes into play, things get difficult. The best known example for these difficulties are zero-knowledge proofs. - Symbolic Universal Composability (Feb 21, 2013). [show details...]
**Abstract:**The definition of Universal Composability (UC; Canetti, FOCS 2001) is a cryptographic security definition that is both simple and gives very strong security guarantees. In particular, it ensures that the composition of secure protocols stays secure. The idea of UC is not, however, restricted to the cryptographic (computational) setting; instead, one can see it as a refinement relation on protocols and programs that preserves security and is composable. We show how UC can be applied in a symbolic security setting. We also show a new design technique (virtual primitives). This design technique allows to circumvent, in a symbolic UC setting, various impossibility results that apply in the cryptographic setting. Finally, we discuss the problem of automated verification in this setting. - Everlasting Security through Quantum Cryptography Formal Methods Seminar, LORIA Nancy (Feb 05, 2013). [show details...]
**Abstract:**Cryptography is a powerful tool for processing confidential data. Cryptographic protocols are, however, only as secure as the underlying encryption schemes. And we do not know whether these might not be broken at some point in the future. This leaves us in a difficult situation: If we process highly sensitive data using cryptographic protocols, an attacker might simply record all messages. Should the underlying encryption scheme be broken in the future, the attacker will then be able to decrypt all confidential data in retrospect. For highly confidential data (such as, e.g., medical records) such a situation is not acceptable.A way out is "everlasting security". A protocol with everlasting security guarantees that all data involved in the protocol stays secure, even if at some point in the future all the underlying encryption schemes are broken. Unfortunately, with traditional cryptographic techniques, everlasting security can only be achieved in very limited situations.

In this talk, we explain how everlasting security can be achieved for a wide variety of tasks by using quantum cryptography, i.e., by making use of quantum mechanical effects in the cryptographic protocol.

(No prior knowledge on quantum cryptography is required.)

- Quantum Time Vaults SECSI Working Group, ENS Cachan (Jan 30, 2013). [show details...]
**Abstract:**Time vaults (a.k.a. timed-release encryption) are encryption schemes that allow the recipient to decrypt the message after a given, preconfigured time, but no earlier. One property that classical time vaults necessarily lack is the possibility to revoke the time vault. We show that due to the no-cloning property of quantum states, we can built quantum time vaults that can be revoked (with help of the recipient). That is, after sending a time vault to the recipient, the time vault can be returned to the sender, giving him the assurance that his message will stay secret forever. - Computational Soundness without Protocol Restrictions ACM CCS 2012 (Oct 18, 2012). [show details...]
**Abstract:**The abstraction of cryptographic operations by term algebras, called Dolev-Yao models, is essential in almost all tool-supported methods for verifying security protocols. Recently significant progress was made in establishing computational soundness results: these results prove that Dolev-Yao style models can be sound with respect to actual cryptographic realizations and security definitions. However, these results came at the cost of imposing various constraints on the set of permitted security protocols: e.g., dishonestly generated keys must not be used, key cycles need to be avoided, and many more. In a nutshell, the cryptographic security definitions did not adequately capture these cases, but were considered carved in stone; in contrast, the symbolic abstractions were bent to reflect cryptographic features and idiosyncrasies, thereby requiring adaptations of existing verification tools.In this paper, we pursue the opposite direction: we consider a symbolic abstraction for public-key encryption and identify two cryptographic definitions called PROG-KDM (programmable key-dependent message) security and MKE (malicious-key extractable) security that we jointly prove to be sufficient for obtaining computational soundness without imposing assumptions on the protocols using this abstraction. In particular, dishonestly generated keys obtained from the adversary can be sent, received, and used. The definitions can be met by existing cryptographic schemes in the random oracle model. This yields the first computational soundness result for trace-properties that holds for arbitrary protocols using this abstraction (in particular permitting to send and receive dishonestly generated keys), and that is accessible to all existing tools for reasoning about Dolev-Yao models without further adaptations.

- Quantum Time Vaults Estonian-Latvian Theory Days 2016, Lilaste (Sep 29, 2012). [show details...]
**Abstract:**Time vaults (a.k.a. timed-release encryption) are encryption schemes that allow the recipient to decrypt the message after a given, preconfigured time, but no earlier. One property that classical time vaults necessarily lack is the possibility to revoke the time vault. We show that due to the no-cloning property of quantum states, we can built quantum time vaults that can be revoked (with help of the recipient). That is, after sending a time vault to the recipient, the time vault can be returned to the sender, giving him the assurance that his message will stay secret forever.