Preparing Symmetric Crypto for the Quantum World

Eleni Diamanti

Olaf Grote, Andreas Ahrens, César Benavente-Peces

Current security protocols use cryptographic methods based on asymmetric and symmetric schemes. These are used for encrypted communication of information or for general data encryption. The security of these methods is based on well researched methods and known mathematical problems. These have been developed for common computing resources and with the certainty that they cannot be broken at a determinable runtime with finite resources. This excludes novel attack vectors such as those of a quantum computer using quantum algorithms. These cryptographic methods, especially the asymmetric schemes, are not prepared against quan- tum attacks and not considered quantum safe. Even the security of current quantum safe symmetric schemes is not based on proven security against quantum attacks. In order to effectively counter this threat, a new and effective strategy is necessary. One point of this strategy is the post-quantum cryptography to evaluate new quantum-safe cryptographic principles. The second point is to research security protocols which are quantum safe and resistible against quantum attacks. This paper describes the strategy of post-quantum cryptography and crypto-agility.

Gilles Brassard A

Bruce Christianson, Bruno Crispo A, James A. Malcolm

Tommaso Gagliardoni, Juliane Krämer, Patrick Struck

In this work we study the (superposition-based, or QS2) quantum security of public key encryption schemes, originally initiated by Boneh and Zhandry (CRYPTO 2013, for a classical challenge indistinguishability phase) and imprioved by Gagliardoni et al. (CRYPTO 2016, for the symmetric key case). For public key encryption schemes, no notion of quantum security with a quantum indistinguishability phase exists. In this work we close this gap by using so-called type-2 operators for encrypting the challenge message. This brings non-trivial obstacles: On the one hand, public key encryption schemes typically cannot recover the randomness during decryption. On the other hand, many real-world schemes suffer from a small probability of decryption failures. Nevertheless, we identify a class of encryption schemes, which we call recoverable, that allow to avoid decryption failures given knowledge of the original encryption randomness, and we show that for these schemes the type-2 operator can be efficiently implemented even without knowledge of the secret key. This means that, for the public key case, type-2 operators are actually very natural. We also observe that many real-world quantum-resistant schemes, including many NIST candidates, are of this type. Equipped with these results, we (1) give the first quantum security notion (qINDqCPA) for public key encryption with a quantum indistinguishability phase, (2) prove that the canonical LWE-based encryption scheme achieves our security notion, (3) show that our notion is strictly stronger than existing security notions, (4) study the general classification of quantum-resistant public key encryption schemes, and (5) compare our results to a concurrent and independent work by Chevalier et al. (2020).

Kunal Das, Arindam Sadhu