Description
We present an improved algorithm for finding low-weight multiples of polynomials over the binary field using coding heoretic methods. The associated code defined by the given olynomial has a cyclic structure, allowing an algorithm to earch for shifts of the sought minimum-weight odeword. Therefore, a code with higher dimension is onstructed, having a larger number of low-weight codewords nd through some additional processing also reduced minimum istance. Applying an algorithm for finding low-weight odewords in the constructed code yields a lower complexity or finding low-weight polynomial multiples compared to revious approaches. As an application, we show a key-recovery ttack against TCHo that has a lower complexity than the hosen security level indicate. Using similar ideas we also present a new probabilistic algorithm for finding a multiple of weight 4, which is faster than previous approaches. For example, this is relevant in correlation attacks on stream ciphers.
Prochains exposés
-
Polytopes in the Fiat-Shamir with Aborts Paradigm
Orateur : Hugo Beguinet - ENS Paris / Thales
The Fiat-Shamir with Aborts paradigm (FSwA) uses rejection sampling to remove a secret’s dependency on a given source distribution. Recent results revealed that unlike the uniform distribution in the hypercube, both the continuous Gaussian and the uniform distribution within the hypersphere minimise the rejection rate and the size of the proof of knowledge. However, in practice both these[…]-
Cryptographie
-
Primitive asymétrique
-
Mode et protocole
-
-
Post-quantum Group-based Cryptography
Orateur : Delaram Kahrobaei - The City University of New York