La prochaine édition du séminaire C2 se tiendra le vendredi 21 juin 2019 dans la salle 105 couloir 25-26 du LIP6 de Sorbonne Université, métro Jussieu.
- 10h00 – Thomas Debris, INRIA Paris : Wave: a New Family of Trapdoor One-Way PSF Based on Codes.
(joint work with Nicolas Sendrier and Jean-Pierre Tillich)
We present here a new family of trapdoor one-way Preimage Sampleable Functions (PSF) based on codes, the Wave-PSF family. The trapdoor function is one-way under two computational assumptions: the hardness of generic decoding for high weights and the indistinguishability of generalized $\UV$-codes.
Our proof follows the GPV strategy \cite{GPV08}. By including rejection sampling, we ensure the proper distribution for the trapdoor inverse output. The domain sampling property of our family is ensured by using and proving a variant of the left-over hash lemma. We instantiate the new Wave-PSF family with ternary generalized $\UV$-codes to design a « hash-and-sign » signature scheme which achieves {\em existential unforgeability under adaptive chosen message attacks} (EUF-CMA) in the random oracle model. For 128 bits of classical security, signature sizes are in the order of 13 thousand bits, the public key size in the order of 3 megabytes, and the rejection rate is limited to one rejection every 10 to 12 signatures.
- 11h15 – Adrien Hauteville, INRIA Saclay : Durandal: a rank metric based signature scheme.
Joint work with Nicolas Aragon, Olivier Blazy, Philippe Gaborit and Gilles Zémor
Abstract : These last years, the interest for post-quantum cryptography has strongly increased, especially since the NIST call for post-quantum cryptosystems standardization. Code-based cryptography is a good candidate in this domain.
The Hamming metric is well-known for several years, however rank metric is a newer topic but possesses many advantages in term of keysize or security hypothesis.
This presentation introduces the Rank-based cryptography and the new signature scheme Durandal, which is a variation of the Lyubashevsky approach in Euclidean lattices.
- 13h45 – Aurore Guillevic, LORIA : A first step toward an implementation of the Tower Number Field Sieve: selecting polynomials
Joint work with Shashank Singh, IISER Bhopal, India
Abstract : In this work, we provide a first step toward a practical implementation of the Tower Number Field Sieve. This algorithm is expected to compute more efficiently discrete logarithms in finite fields GF(p^n), where p is large prime number (hundreds of bits) and n is a small composite integer (n=6,8,12 for example).
The NFS-like algorithms for discrete logarithm computation are made of four main steps: polynomial selection (two polynomials define two number fields), relation collection (collecting a large set of multiplicative relations of elements from these two number fields), linear algebra (computing the right kernel of a large sparse matrix) and finally, computing the discrete logarithm of a given target in GF(p^n) w.r.t. a generator.
We generalize to the new Tower setting the ranking formula used in the first step of NFS that selects the best parameters (polynomials) among a large set. For this we re-define the $\alpha$ function and write an exact implementation (Magma and SageMath). This function measures the bias in the smoothness probability of norms in number fields compared to random integers of the same size.
We use it to estimate the yield of polynomials, that is the expected number of relations, as a generalization of Murphy’s $E$ function, and finally the total amount of operations needed to compute a discrete logarithm with the Tower-NFS in the targeted fields.
As another application, this can be used to refine the earlier work of Barbulescu and Duquesne on estimating the running-time of the algorithm. We apply our estimates to some pairing-friendly curves, whose related pairing target field is GF(p^n), for some small composite n. For each curve, we generate curve parameters for p of increasing size every 32 bits, and p^n from 3000 bits to 12000 bits, in order to have more intuition on how does the Tower-NFS algorithm scale for increasing size of p.
- 15h00 : Leonardo Colo, Université d’Aix-Marseille : Orienting supersingular isogeny graphs
Abstract : Supersingular isogeny graphs have been used in the Charles–Goren–Lauter cryptographic hash function~\cite{CGL2006} and the supersingular isogeny Diffie–Hellman (SIDH) protocole of De\,Feo and Jao~\cite{JDF2011}. A recently proposed alternative to SIDH is the commutative supersingular isogeny Diffie–Hellman (CSIDH) protocole, in which the isogeny graph is first restricted to $\FF_p$-rational curves $E$ and $\FF_p$-rational isogenies then oriented by the quadratic subring $\ZZ[\pi] \subset \End(E)$ generated by the Frobenius endomorphism $\pi: E \rightarrow E$.
We introduce a general notion of orienting supersingular elliptic curves and their isogenies, and use this as the basis to construct a general oriented supersingular isogeny Diffie-Hellman (OSIDH) protocole.
By imposing the data of an orientation by an imaginary quadratic ring $\OO$, we obtain an augmented category of supersingular curves on which the class group $\Cl(\OO)$ acts faithfully and transitively. This idea is already implicit in the CSIDH protocol, in which supersingular curves over $\FF_p$ are oriented by the Frobenius subring $\ZZ[\pi] \simeq \ZZ[\sqrt{-p}]$. In contrast we consider an elliptic curve $E_0$ oriented by a CM order $\OO_K$ of class number one. To obtain a nontrivial group action, we consider $\ell$-isogeny chains, on which the class group of an order $\OO$ of large index $\ell^n$ in $\OO_K$ acts, a structure we call a whirlpool. The map from $\ell$-isogeny chains to its terminus forgets the structure of the orientation, and the original base curve $E_0$, giving rise to a generic supersingular elliptic curve. Within this general framework we define a new oriented supersingular isogeny Diffie-Hellman (OSIDH) protocol, which has fewer restrictions on the proportion of supersingular curves covered and on the torsion group structure of the underlying curves. Moreover, the group action can be carried out effectively solely on the sequences of moduli points (such as $j$-invariants) on a modular curve, thereby avoiding expensive isogeny computations, and is further amenable to speedup by precomputations of endomorphisms on the base curve $E_0$.
