Description
An algebraic attack is a method for cryptanalysis which is based on finding and solving a system of nonlinear equations. Recently, algebraic attacks where found helpful in cryptanalysing stream ciphers based on linear feedback shift registers. The efficiency of these attacks greatly depends on the degree of the nonlinear equations.<br/> At Crypto 2003, Courtois proposed fast algebraic attacks. The main idea is to decrease the degree of the equations using a precomputation algorithm. Unfortunately, the correctness of the precomputation algorithm was neither proven, nor was it obvious in all cases. In the first part of the talk, an introduction to fast algebraic attacks is given. In the second part, the results introduced in the paper "Improving Fast Algebraic Attacks" (FSE 2004) are presented in more detail. This includes the missing proof of correctness and an improvement of the precomputation algorithm. All aspects will be illustrated on the Bluetooth keystream generator E_0.
Next sessions
-
Algorithms for post-quantum commutative group actions
Speaker : Marc Houben - Inria Bordeaux
At the historical foundation of isogeny-based cryptography lies a scheme known as CRS; a key exchange protocol based on class group actions on elliptic curves. Along with more efficient variants, such as CSIDH, this framework has emerged as a powerful building block for the construction of advanced post-quantum cryptographic primitives. Unfortunately, all protocols in this line of work are[…] -
Endomorphisms via Splittings
Speaker : Min-Yi Shen - No Affiliation
One of the fundamental hardness assumptions underlying isogeny-based cryptography is the problem of finding a non-trivial endomorphism of a given supersingular elliptic curve. In this talk, we show that the problem is related to the problem of finding a splitting of a principally polarised superspecial abelian surface. In particular, we provide formal security reductions and a proof-of-concept[…]-
Cryptography
-