Cryptographie post-quantique

Résumé

La cryptographie post-quantique est une branche de la cryptographie visant à garantir la sécurité de l'information face à un attaquant disposant d'un calculateur quantique. Cette discipline est distincte de la cryptographie quantique, qui vise à construire des algorithmes cryptographiques utilisant des propriétés physiques, plutôt que mathématiques, pour garantir la sécurité. En l'effet, les algorithmes quantiques de Shor, de Grover et de Simon étendent les capacités par rapport à un attaquant ne disposant que d'un ordinateur classique. S'il n'existe pas à l'heure actuelle de calculateur quantique représentant une menace concrète sur la sécurité des cryptosystèmes déployés, ces algorithmes permettent conceptuellement de résoudre certains problèmes calculatoires sur lesquels sont fondés plusieurs primitives populaires. Algorithmes quantiques et cryptographie Algorithme de Shor En 1995, Peter Shor a publié un algorithme permettant de résoudre le problème du logarithme discr

Source officielle

https://fr.wikipedia.org/wiki/Cryptographie_post-quantique

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (28)

Publications associées

Chargement

Personnes associées (2)

Personnes associées

Chargement

Unités associées (1)

Unités associées

Chargement

Concepts associés (23)

Concepts associés

Chargement

Cours associés (15)

Cours associés

Chargement

Séances de cours associées (22)

Séances de cours associées

Chargement

Post-quantum cryptography is a branch of cryptography which deals with cryptographic algorithms whose hardness assumptions are not based on problems known to be solvable by a quantum computer, such as the RSA problem, factoring or discrete logarithms.This thesis treats two such algorithms and provides theoretical and practical attacks against them.The first protocol is the generalised Legendre pseudorandom function - a random bit generator computed as the Legendre symbol of the evaluation of a secret polynomial at an element of a finite field. We introduce a new point of view on the protocol by analysing the action of the group of Möbius transformations on the set of secret keys (secret polynomials).We provide a key extraction attack by creating a table which is cubic in the number of the function queries, an improvement over the previous algorithms which only provided a quadratic yield. Furthermore we provide an ever stronger attack for a new set of particularly weak keys.The second protocol that we cover is SIKE - supersingular isogeny key encapsulation.In 2017 the American National Institute of Standards and Technology (NIST) opened a call for standardisation of post-quantum cryptographic algorithms. One of the candidates, currently listed as an alternative key encapsulation candidate in the third round of the standardisation process, is SIKE.We provide three practical side-channel attacks on the 32-bit ARM Cortex-M4 implementation of SIKE.The first attack targets the elliptic curve scalar multiplication, implemented as a three-point ladder in SIKE. The lack of coordinate randomisation is observed, and used to attack the ladder by means of a differential power analysis algorithm.This allows us to extract the full secret key of the target party with only one power trace.The second attack assumes coordinate randomisation is implemented and provides a zero-value attack - the target party is forced to compute the field element zero, which cannot be protected by randomisation. In particular we target both the three-point ladder and isogeny computation in two separate attacks by providing maliciously generated public keys made of elliptic curve points of irregular order.We show that an order-checking countermeasure is effective, but comes at a price of 10% computational overhead. Furthermore we show how to modify the implementation so that it can be protected from all zero-value attacks, i.e., a zero-value is never computed during the execution of the algorithm.Finally, the last attack targets a point swapping procedure which is a subroutine of the three-point ladder. The attack successfully extracts the full secret key with only one power trace even if the implementation is protected with coordinate randomisation or order-checking. We provide an effective countermeasure --- an improved point swapping algorithm which protects the implementation from our attack.

EPFL2022

Chargement

Misuse Attacks on Post-quantum Cryptosystems

Ciprian Baetu, Fatma Betül Durak, Loïs Evan Huguenin-Dumittan, Abdullah Talayhan, Serge Vaudenay

Many post-quantum cryptosystems which have been proposed in the National Institute of Standards and Technology (NISI) standardization process follow the same meta-algorithm, but in different algebras or different encoding methods. They usually propose two constructions, one being weaker and the other requiring a random oracle. We focus on the weak version of nine submissions to NISI. Submitters claim no security when the secret key is used several times. In this paper, we analyze how easy it is to run a key recovery under multiple key reuse. We mount a classical key recovery under plaintext checking attacks (i.e., with a plaintext checking oracle saying if a given ciphertext decrypts well to a given plaintext) and a quantum key recovery under chosen ciphertext attacks. In the latter case, we assume quantum access to the decryption oracle.

SPRINGER INTERNATIONAL PUBLISHING AG2019

Chargement

Using the new VPMADD instructions for the new post quantum key encapsulation mechanism SIKE

Dusan Kostic

This paper demonstrates the use of new processor instructions VPMADD, intended to appear in the coming generation of Intel processors (codename "Cannon Lake"), in order to accelerate the newly proposed key encapsulation mechanism (KEM) named SIKE. SIKE is one of the submissions to the NIST standardization process on post-quantum cryptography, and is based on pseudo-random walks in supersingular isogeny graphs. While very small keys are the main advantage of SIKE, its extreme computational intensiveness makes it one of the slowest KEM proposals. Performance optimizations are needed. We address here the "Level 1" parameters that target 64-bit quantum security, and deemed sufficient for the NIST standardization effort. Thus, we focus on SIKE503 that operates over F p2 with a 503-bit prime p. These short operands pose a significant challenge on using VPMADD effectively. We demonstrate several optimization methods to accelerate F-p, F-p2, and the elliptic curve arithmetic, and predict a potential speedup by a factor of 1.72x.

IEEE COMPUTER SOC2019

Chargement

EPFL2022