Search by date:
1998
|
1999
|
2000
|
2001
|
2002
|
2003
|
2004
|
2005
|
2006
|
2007
|
2008
|
2009
|
2010
|
2011
|
2012
|
2013
|
2014
|
2016
|
2017
|
2018
|
2019
| Forthcoming
If you wish to be informed about our seminars by email,
please contact Francesco Berti, Olivier Pereira or François-Xavier Standaert .
Seminars for the year 2005
January 2005
January 18, 00:00 - Products of Small Primes in Cryptology, Error Codes and Theoretical Computer Science
by David Naccache
| Date: | January 18, 2005 - 00:00 |
| Location: | Room 207, Euler Building (near Maxwell Building) Avenue Georges Lemaître, 4-6 - 1348 Louvain-la-Neuve |
| Abstract: | In formal number theory a Godel numbering is a function which assigns to each symbol and formula of some formal language a unique natural number called a Godel number (GN). The concept was first used by Kurt Godel in the proof of his incompleteness theorem in 1930 (this theorem states that in any consistent formalization of mathematics that is sufficiently strong to define the concept of natural numbers, one can construct a statement that can be neither proved nor disproved within that system). The GN of a string of integers a_0,...,a_k is simply obtained by computing the product p_0^{a_0}*...*p_k^{a_k} where p_i is the i-th prime number (i.e. p_0=2, p_1=3, p_2=5,...). Intriguingly, this very simple mathematical object has other applications than just proving Godel's incompleteness theorem: GN-based public key cryptosystems and error-correcting codes emerged during the last decade. In this talk we will sketch the proof of Godel's incompleteness theorem and overview the role of GN-encoding therein, we will then present two different public-key cryptosystems (both by Naccache and Stern, 1997 and 1998) using GN message encoding as well as a (somewhat unusual) error correcting code (unpublished, cf. https://silentbob.gemplus.com/repository/h.pdf page 688). |
| Link: |
January 24, 14:30 - "Benes and Butterfly schemes revisited"
by Jacques Patarin
| Date: | January 24, 2005 - 14:30 |
| Location: | Auditoire Euler, 002, Euler Building (near Maxwell Building) Avenue Georges Lemaître, 4-6 - 1348 Louvain-la-Neuve |
| Abstract: | In~\cite{AV96}, W. Aiello and R. Venkatesan have shown how to construct pseudo-random functions of $2n$ bits $\rightarrow 2n$ bits from pseudo-random functions of $n$ bits $\rightarrow n$ bits. They claimed that their construction, called ``Benes'', reaches the optimal bound ($m\ll 2^n$) of security against adversaries with unlimited computing power but limited by $m$ queries in an adaptive chosen plaintext attack (CPA-2). However a complete proof of this result is not given in~\cite{AV96} since one of the assertions of~\cite{AV96} is wrong. Due to this, the proof given in~\cite{AV96} is valid for most attacks, but not for all the possible chosen plaintext attacks. In this paper we will in a way fix this problem since for all $\varepsilon>0$, we will prove CPA-2 security when $m\ll 2^{n(1-\varepsilon)}$. However we will also see that the probability to distinguish Benes functions from random functions is sometime larger than the term in $\frac{m^2}{2^{2n}}$ given in~\cite{AV96}. One of the key idea in our proof will be to notice that, when $m\gg2^{2n/3}$ and $m\ll2^n$, for large number of variables linked with some critical equalities, the average number of solutions may be large (i.e. $\gg1$) while, at the same time, the probability to have at least one such critical equalities is negligible (i.e. $\ll1$). (Joint work with Audrey Montreuil) |
| Link: | http://eprint.iacr.org/2005/004 |
March 2005
March 15, 11:00 - Zero-Knowledge Identification with Multivariate Quadratic Equations
by Christopher Wolf
| Date: | March 15, 2005 - 11:00 |
| Location: | Salle Ampère - Maxwell building, ground floor. Place du Levant, 3 - 1348 Louvain-la-Neuve |
| Abstract: | Generally speaking, in an authentication scheme, a prover P wants to convince a verifier V of its identity. For a zero-knowledge protocol, we have the additional constrain that the prover does not leak any useful information to the user in the whole process. The last property makes Zero-Knowledge schemes a very interesting choice for authentication problems, e.g., in the military context ("is this my tank or a tank of the enemy?"). In this talk, we show a concrete implementation of an zero-knowledge scheme denoted the MQ^*-IP scheme. It is based on the intractability assumption of Multivariate Quadratic equations (MQ) and the Isomorphism of Polynomials problem (IP). Both are believed to be hard and their security has been extensively studied in other contexts. In contrast to many other Zero-Knowledge schemes based on NP-complete problems MQ^*-IP allows identity-based keys. This is an advantage in practical settings, as no public key infrastructure needs to be installed. |
| Link: |
May 2005
May 17, 00:00 - GSEC COURSE: Digital Rights Management: from theory to implementations.
by Pr. Jean-Jacques Quisquater
| Date: | May 17, 2005 - 00:00 |
| Location: | Unspecified location |
| Abstract: | Speakers
|
| Link: | http://www.gsec.ucl.ac.be/AS13.php |
May 27, 14:00 - "Server-aided verification"
by Marc Girault
| Date: | May 27, 2005 - 14:00 |
| Location: | Salle Ampère - Maxwell building, ground floor. Place du Levant, 3 - 1348 Louvain-la-Neuve |
| Abstract: | We introduce the server-aided verification (SAV) concept, which consists in speeding up the verification step of an authentication/signature scheme, by delegating a substantial part of computations to a powerful (but possibly untrusted) server. After giving some motivations for designing SAV protocols, we provide a simple but realistic model, which captures most situations one can meet in practice. Then, we analyze and prove in this model the security of two existing SAV protocols, namely the Lim-Lee \cite{LL95} modification of Schnorr scheme \cite{Sch89} and the Girault-Quisquater variant \cite{GQ02} of GPS scheme \cite{Gir91,PS98}. Finally, we propose a generic method for designing SAV versions of schemes based on bilinear maps, which can be applied to the Boneh-Boyen signature schemes \cite{BB04}, the Zhang-Safavi-Naini-Susilo \cite{ZSNS04} signature scheme and the Shao-Lu-Cao identification scheme \cite{SLC04}. (joint work with David Lefranc) |
| Link: |
June 2005
June 24, 17:00 - Algorithms for solving the Isomorphism of Polynomials with One Secret
by Dr. Ludovic Perret
| Date: | June 24, 2005 - 17:00 |
| Location: | Salle Ampère - Maxwell building, ground floor. Place du Levant, 3 - 1348 Louvain-la-Neuve |
| Abstract: | //Smale Scale Variants of AES n:=4; // number of round (sans compter le round d'addition de la clef// nous avons donc n+1 tours ) r:=2; // number of rows c:=2; // number of columns e:=4; // size of a word // Un état est donc un tabeau de r*c éléments de F_2^e nc:=1; // nb message clair F4<theta>:=FiniteField(2^e); AssertAttribute(F4,"PowerPrinting",false); //(n+1)*r*c*e+n*r*e variables de clefs/// n*e*r*c variables d'etat F:=PolynomialRing(F4, (n+1)*r*c*e+n*r*e+nc*n*r*c*e); // Parties linneaire et affine de la Sbox e=4 Lin4:=Matrix(F,4,4,[1,1,1,0, 0,1,1,1, 1,0,1,1, 1,1,0,1]); // Matrice de la partie linéaire Const4:=theta^2+theta; // Partie affine (Constante) // Parties lineaire et affine de la Sbox e=8 Lin8:=Matrix(F,8,8,[1,0,0,0,1,1,1,1, 1,1,0,0,0,1,1,1, 1,1,1,0,0,0,1,1, 1,1,1,1,0,0,0,1, 1,1,1,1,1,0,0,0, 0,1,1,1,1,1,0,0, 0,0,1,1,1,1,1,0, 0,0,0,1,1,1,1,1]); Const8:=Random(F4); // a revoir !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! Set_Poly:=function(f,e) SysEq:=[]; MonTemp:=Monomials(f); CoeffTemp:=Coefficients(f); CoeffTemp:=[Eltseq(CoeffTemp[j]): j in [1..#CoeffTemp]]; for l in [1..e] do EqTemp:=0; for k in [1..#CoeffTemp] do EqTemp:=EqTemp+CoeffTemp[k][l]*MonTemp[k]; end for; SysEq:=SysEq cat [EqTemp]; end for; return SysEq; end function; SymbMatWord:=function(n,r,c,e,cptv) ListWord:=[]; for i in [1..r] do for j in [1..c] do aux:=[]; for k in [0..e-1] do aux:= aux cat [theta^k*F.cptv]; cptv:=cptv+1; end for; ListWord:=ListWord cat [&+aux]; end for; end for; return [* Matrix(F,r,c,ListWord), cptv *]; end function; SymbMatkey:=function(n,r,c,e,cptk) ListWord:=[]; for i in [1..r] do for j in [1..c] do aux:=[]; for k in [0..e-1] do aux:= aux cat [theta^k*F.cptk]; cptk:=cptk+1; end for; ListWord:=ListWord cat [&+aux]; end for; end for; return [* Matrix(F,r,c,ListWord), cptk *]; end function; SymbSubBytes:=function(n,r,c,e,InputWord,OutputWord) // Application de Sbox sur les elements de InputWord SboxMat:=Matrix(F,r,c,[0: i in [1..r*c]]); for i in [1..r] do for j in [1..c] do SboxMat[i,j]:=InputWord[i,j]*OutputWord[i,j]-1; end for; end for; if e eq 4 then for i in [1..r] do for j in [1..c] do OutputWord[i,j]:=Const4+&+[Eltseq(Lin4*Matrix(F,e,1, Set_Poly(OutputWord[i,j],e)))[k]*theta^(k-1): k in [1..e]]; end for; end for; elif e eq 8 then for i in [1..r] do for j in [1..c] do OutputWord[i,j]:=Const8+&+[Eltseq(Lin8*Matrix(F,e,1, Set_Poly(OutputWord[i,j],e)))[k]*theta^(k-1): k in [1..e]]; end for; end for; end if; return SboxMat, OutputWord; end function; ShiftRows:=function(n,r,c,e, InputWord) Aux:=InputWord; for i in [0..r-1] do for j in [0..c-1] do InputWord[i+1,j+1]:=Aux[i+1,1+(j+i)mod c]; end for; end for; return InputWord; end function; MixColumns:=function(n,r,c,e, InputWord) AuxSeq:=[]; if e eq 4 then if r eq 1 then Mat41:=Matrix(F,r,r,[1]); for i in [1..c] do temp:=Matrix(F,r,1,Eltseq(Transpose(InputWord)[i])); AuxSeq:=AuxSeq cat Eltseq(Mat41*temp); end for; return Matrix(F,r,c,AuxSeq); elif r eq 2 then Mat42:= Matrix(F,r,r,[1+theta, theta, theta, 1+theta]); for i in [1..c] do temp:=Matrix(F,r,1,Eltseq(Transpose(InputWord)[i])); AuxSeq:=AuxSeq cat Eltseq(Mat42*temp); end for; return Matrix(F,r,c,AuxSeq); else Mat44:= Matrix(F,r,r,[theta, theta+1, 1, 1, 1, theta, theta+1, 1, 1, 1, theta, theta+1, theta+1, 1, 1, theta ]); for i in [1..c] do temp:=Matrix(F,r,1,Eltseq(Transpose(InputWord)[i])); AuxSeq:=AuxSeq cat Eltseq(Mat44*temp); end for; return Matrix(F,r,c,AuxSeq); end if; else if r eq 1 then Mat81:=Matrix(F,r,r,[1]); for i in [1..c] do temp:=Matrix(F,r,1,Eltseq(Transpose(InputWord)[i])); AuxSeq:=AuxSeq cat Eltseq(Mat81*temp); end for; return Matrix(F,r,c,AuxSeq); elif r eq 2 then Mat82:= Matrix(F,r,r,[1+theta, theta, theta, 1+theta]); for i in [1..c] do temp:=Matrix(F,r,1,Eltseq(Transpose(InputWord)[i])); AuxSeq:=AuxSeq cat Eltseq(Mat82*temp); end for; return Matrix(F,r,c,AuxSeq); else Mat84:= Matrix(F,r,r,[theta, theta+1, 1, 1, 1, theta, theta+1, 1, 1, 1, theta, theta+1, theta+1, 1, 1, theta ]); for i in [1..c] do temp:=Matrix(F,r,1,Eltseq(Transpose(InputWord)[i])); AuxSeq:=AuxSeq cat Eltseq(Mat84*temp); end for; return Matrix(F,r,c,AuxSeq); end if; end if; end function; Gen_Eq_Cipher:=function(n,r,c,e, Message) cptv:=(n+1)*r*c*e+n*r*e+1; //compteur des variables d'etat ListeState:=[]; ListeEq:=[]; ListeKey:=[]; for j in [1..#Message] do cptk:=1; //compteur des variables de clef AuxK:=SymbMatkey(n,r,c,e,cptk); ListeKey:=ListeKey cat [AuxK[1]]; InputWord:=ChangeRing(Message[j],F)+AuxK[1]; cptk:=AuxK[2]; ListeState:=ListeState cat [InputWord]; // Round 1..n for i in [1..n] do AuxW:=SymbMatWord(n,r,c,e,cptv); OutputWord:=AuxW[1]; cptv:=AuxW[2]; // OutputWord est la sortie de la Sbox au round n SboxMat, InputWord:=SymbSubBytes(n,r,c,e,InputWord,OutputWord); ListeEq:=ListeEq cat [SboxMat]; AuxK:=SymbMatkey(n,r,c,e,cptk); cptk:=AuxK[2]; if i ne n then InputWord:=ShiftRows(n,r,c,e, MixColumns(n,r,c,e,InputWord))+AuxK[1]; else InputWord:=ShiftRows(n,r,c,e,InputWord)+AuxK[1]; end if; // InputWord est la sortie du round de chiffrement n, et l'entrée du round n+1 ListeState:=ListeState cat [InputWord]; if j eq 1 then ListeKey:=ListeKey cat [AuxK[1]]; end if; end for; // ListeState[i]=etat apres le round i end for; return ListeEq, ListeState, ListeKey; end function; Gen_Eq_Key:=function(n,r,c,e) //compteur des variables de clef cptk:=1; ListeEq:=[]; SboxMat:=Matrix(F,r,c,[0: i in [1..r*c]]); AuxK:=SymbMatkey(n,r,c,e,cptk); InitKey:=AuxK[1]; cptk:=(n+1)*r*c*e+1; Exkey:=[InitKey:i in [1..n+1]]; if e eq 4 then if r eq 1 then SboxMat:=Matrix(F,1,1,[0]); for i in [2..n+1] do s0:=[]; for k in [0..e-1] do s0:= s0 cat [theta^k*F.cptk]; cptk:=cptk+1; end for; s0:=&+s0; Auxa:=Eltseq(Exkey[i]); Auxb:=Eltseq(Exkey[i-1]); SboxMat[1,1]:=s0*Auxb[c]-1; ListeEq:=ListeEq cat [SboxMat]; if c eq 1 then Auxa[1]:=theta^(i-1)+Const4+&+[Eltseq(Lin4*Matrix(F,e,1,Set_Poly(s0,e)))[k]*theta^(k-1): k in [1..e]]; Exkey[i]:=Matrix(F,r,c,Auxa); else for q:=0 to c-1 do Auxa[q+1]:=theta^(i-1)+Const4+&+[Eltseq(Lin4*Matrix(F,e,1, Set_Poly(s0,e)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[t+1]:t in [0..q]]; end for; Exkey[i]:=Matrix(F,r,c,Auxa); end if; end for; elif r eq 2 then SboxMat:=Matrix(F,2,1,[0,0]); for i in [2..n+1] do s0:=[];s1:=[]; for k in [0..e-1] do s0:= s0 cat [theta^k*F.cptk]; cptk:=cptk+1; end for; s0:=&+s0; for k in [0..e-1] do s1:= s1 cat [theta^k*F.cptk]; cptk:=cptk+1; end for; s1:=&+s1; Auxa:=Eltseq(Exkey[i]); Auxb:=Eltseq(Exkey[i-1]); SboxMat[1,1]:=s0*Auxb[2*c]-1; SboxMat[2,1]:=s1*Auxb[2*c-1]-1; ListeEq:=ListeEq cat [SboxMat]; if c eq 1 then Auxa[1]:=theta^(i-1)+Const4+&+[Eltseq(Lin4*Matrix(F,e,1,Set_Poly(s0,e)))[k]*theta^(k-1): k in [1..e]]; Auxa[2]:=Const4+&+[Eltseq(Lin4*Matrix(F,e,1,Set_Poly(s1,e)))[k]*theta^(k-1): k in[1..e]]; Exkey[i]:=Matrix(F,r,c,Auxa); else for q:=0 to c-1 by 2 do Auxa[r*q+1]:=theta^(i-1)+Const4+&+[Eltseq(Lin4*Matrix(F,e,1, Set_Poly(s0,e)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[r*t+1]:t in [0..q]]; Auxa[r*q+2]:=Const4+&+[Eltseq(Lin4*Matrix(F,e,1, Set_Poly(s1,e)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[r*t+2]:t in [0..q]]; end for; Exkey[i]:=Matrix(F,r,c,Auxa); end if; end for; elif r eq 4 then SboxMat:=Matrix(F,4,1,[0,0,0,0]); for i in [2..n+1] do s0:=[];s1:=[]; s2:=[]; s3:=[]; for k in [0..e-1] do s0:= s0 cat [theta^k*F.cptk]; cptk:=cptk+1; end for; s0:=&+s0; for k in [0..e-1] do s1:= s1 cat [theta^k*F.cptk]; cptk:=cptk+1; end for; s1:=&+s1; for k in [0..e-1] do s2:= s2 cat [theta^k*F.cptk]; cptk:=cptk+1; end for; s2:=&+s2; for k in [0..e-1] do s3:= s3 cat [theta^k*F.cptk]; cptk:=cptk+1; end for; s3:=&+s3; Auxa:=Eltseq(Exkey[i]); Auxb:=Eltseq(Exkey[i-1]); SboxMat[1,1]:=s0*Auxb[4*c]-1; SboxMat[2,1]:=s1*Auxb[4*c-1]-1; SboxMat[3,1]:=s2*Auxb[4*c-2]-1; SboxMat[4,1]:=s3*Auxb[4*c-3]-1; ListeEq:=ListeEq cat [SboxMat]; if c eq 1 then Auxa[1]:=theta^(i-1)+Const4+&+[Eltseq(Lin4*Matrix(F,e,1,Set_Poly(s0,e)))[k]*theta^(k-1): k in [1..e]]; Auxa[2]:=Const4+&+[Eltseq(Lin4*Matrix(F,e,1,Set_Poly(s1,e)))[k]*theta^(k-1): k in [1..e]]; Auxa[3]:=Const4+&+[Eltseq(Lin4*Matrix(F,e,1,Set_Poly(s2,e)))[k]*theta^(k-1): k in [1..e]]; Auxa[4]:=Const4+&+[Eltseq(Lin4*Matrix(F,e,1,Set_Poly(s3,e)))[k]*theta^(k-1): k in [1..e]]; Exkey[i]:=Matrix(F,r,c,Auxa); else for q:=0 to c-1 by 4 do Auxa[r*q+1]:=theta^(i-1)+Const4+&+[Eltseq(Lin4*Matrix(F,e,1, Set_Poly(s0,e)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[r*t+1]:t in [0..q]]; Auxa[r*q+2]:=Const4+&+[Eltseq(Lin4*Matrix(F,e,1, Set_Poly(s1,e)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[r*t+2]:t in [0..q]]; Auxa[r*q+3]:=Const4+&+[Eltseq(Lin4*Matrix(F,e,1, Set_Poly(s2,e)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[r*t+3]:t in [0..q]]; Auxa[r*q+4]:=Const4+&+[Eltseq(Lin4*Matrix(F,e,1, Set_Poly(s3,e)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[r*t+4]:t in [0..q]]; end for; Exkey[i]:=Matrix(F,r,c,Auxa); end if; end for; end if; elif e eq 8 then if r eq 1 then SboxMat:=Matrix(F,1,1,[0]); for i in [2..n+1] do s0:=[]; for k in [0..e-1] do s0:= s0 cat [theta^k*F.cptk]; cptk:=cptk+1; end for; s0:=&+s0; Auxa:=Eltseq(Exkey[i]); Auxb:=Eltseq(Exkey[i-1]); SboxMat[1,1]:=s0*Auxb[c]-1; ListeEq:=ListeEq cat [SboxMat]; if c eq 1 then Auxa[1]:=theta^(i-1)+Const8+&+[Eltseq(Lin8*Matrix(F,e,1,Set_Poly(s0,e)))[k]*theta^(k-1): k in [1..e]]; Exkey[i]:=Matrix(F,r,c,Auxa); else for q:=0 to c-1 do Auxa[q+1]:=theta^(i-1)+Const8+&+[Eltseq(Lin8*Matrix(F,e,1, Set_Poly(s0,e)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[t+1]:t in [0..q]]; end for; Exkey[i]:=Matrix(F,r,c,Auxa); end if; end for; elif r eq 2 then SboxMat:=Matrix(F,2,1,[0,0]); for i in [2..n+1] do s0:=[];s1:=[]; for k in [0..e-1] do s0:= s0 cat [theta^k*F.cptk]; cptk:=cptk+1; end for; s0:=&+s0; for k in [0..e-1] do s1:= s1 cat [theta^k*F.cptk]; cptk:=cptk+1; end for; s1:=&+s1; Auxa:=Eltseq(Exkey[i]); Auxb:=Eltseq(Exkey[i-1]); SboxMat[1,1]:=s0*Auxb[2*c]-1; SboxMat[2,1]:=s1*Auxb[2*c-1]-1; ListeEq:=ListeEq cat [SboxMat]; if c eq 1 then Auxa[1]:=theta^(i-1)+Const8+&+[Eltseq(Lin8*Matrix(F,e,1,Set_Poly(s0,e)))[k]*theta^(k-1): k in [1..e]]; Auxa[2]:=Const8+&+[Eltseq(Lin8*Matrix(F,e,1,Set_Poly(s1,e)))[k]*theta^(k-1): k in [1..e]]; Exkey[i]:=Matrix(F,r,c,Auxa); else for q:=0 to c-1 by 2 do Auxa[r*q+1]:=theta^(i-1)+Const8+&+[Eltseq(Lin8*Matrix(F,e,1, Set_Poly(s0,e)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[r*t+1]:t in [0..q]]; Auxa[r*q+2]:=Const8+&+[Eltseq(Lin8*Matrix(F,e,1, Set_Poly(s1,e)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[r*t+2]:t in [0..q]]; end for; Exkey[i]:=Matrix(F,r,c,Auxa); end if; end for; elif r eq 4 then SboxMat:=Matrix(F,4,1,[0,0,0,0]); for i in [2..n+1] do s0:=[];s1:=[]; s2:=[]; s3:=[]; for k in [0..e-1] do s0:= s0 cat [theta^k*F.cptk]; cptk:=cptk+1; end for; s0:=&+s0; for k in [0..e-1] do s1:= s1 cat [theta^k*F.cptk]; cptk:=cptk+1; end for; s1:=&+s1; for k in [0..e-1] do s2:= s2 cat [theta^k*F.cptk]; cptk:=cptk+1; end for; s2:=&+s2; for k in [0..e-1] do s3:= s3 cat [theta^k*F.cptk]; cptk:=cptk+1; end for; s3:=&+s3; Auxa:=Eltseq(Exkey[i]); Auxb:=Eltseq(Exkey[i-1]); SboxMat[1,1]:=s0*Auxb[4*c]-1; SboxMat[2,1]:=s1*Auxb[4*c-1]-1; SboxMat[3,1]:=s2*Auxb[4*c-2]-1; SboxMat[4,1]:=s3*Auxb[4*c-3]-1; ListeEq:=ListeEq cat [SboxMat]; if c eq 1 then Auxa[1]:=theta^(i-1)+Const8+&+[Eltseq(Lin8*Matrix(F,e,1,Set_Poly(s0,e)))[k]*theta^(k-1): k in [1..e]]; Auxa[2]:=Const8+&+[Eltseq(Lin8*Matrix(F,e,1,Set_Poly(s1,e)))[k]*theta^(k-1): k in [1..e]]; Auxa[3]:=Const8+&+[Eltseq(Lin8*Matrix(F,e,1,Set_Poly(s2,e)))[k]*theta^(k-1): k in [1..e]]; Auxa[4]:=Const8+&+[Eltseq(Lin8*Matrix(F,e,1,Set_Poly(s3,e)))[k]*theta^(k-1): k in [1..e]]; Exkey[i]:=Matrix(F,r,c,Auxa); else for q:=0 to c-1 by 4 do Auxa[r*q+1]:=theta^(i-1)+Const8+&+[Eltseq(Lin8*Matrix(F,e,1, Set_Poly(s0,e)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[r*t+1]:t in [0..q]]; Auxa[r*q+2]:=Const8+&+[Eltseq(Lin8*Matrix(F,e,1, Set_Poly(s1,e)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[r*t+2]:t in [0..q]]; Auxa[r*q+3]:=Const8+&+[Eltseq(Lin8*Matrix(F,e,1, Set_Poly(s2,e)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[r*t+3]:t in [0..q]]; Auxa[r*q+4]:=Const8+&+[Eltseq(Lin8*Matrix(F,e,1, Set_Poly(s3,e)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[r*t+4]:t in [0..q]]; end for; Exkey[i]:=Matrix(F,r,c,Auxa); end if; end for; end if; end if; return Exkey, ListeEq; end function; // ********************************************************************** // Fonctions de test du chiffrement Sbox:=function(elt) if elt eq 0 then return F4 ! 0; else return F4 ! elt^(-1); end if; end function; Expandedkey:=function(n,r,c,e,InitKey) ListeSbox:=[]; Exkey:=[InitKey:i in [1..n+1]]; if e eq 4 then if r eq 1 then SboxMat:=Matrix(F,1,1,[0]); for i in [2..n+1] do Auxa:=Eltseq(Exkey[i]); Auxb:=Eltseq(Exkey[i-1]); s0:=Sbox(Auxb[c]); SboxMat[1,1]:=s0; ListeSbox:=ListeSbox cat [SboxMat]; if c eq 1 then Auxa[1]:=theta^(i-1)+Const4+&+[Eltseq(Lin4*Matrix(F,e,1,Eltseq(s0)))[k]*theta^(k-1): k in [1..e]]; Exkey[i]:=Matrix(F,r,c,Auxa); else for q:=0 to c-1 do Auxa[q+1]:=theta^(i-1)+Const4+&+[Eltseq(Lin4*Matrix(F,e,1,Eltseq(s0)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[r*t+1]:t in [0..q]]; end for; Exkey[i]:=Matrix(F,r,c,Auxa); end if; end for; elif r eq 2 then SboxMat:=Matrix(F,2,1,[0,0]); for i in [2..n+1] do Auxa:=Eltseq(Exkey[i]); Auxb:=Eltseq(Exkey[i-1]); s0:=Sbox(Auxb[2*c]); s1:=Sbox(Auxb[2*c-1]); SboxMat[1,1]:=s0; SboxMat[2,1]:=s1; ListeSbox:=ListeSbox cat [SboxMat]; if c eq 1 then Auxa[1]:=theta^(i-1)+Const4+&+[Eltseq(Lin4*Matrix(F,e,1,Eltseq(s0)))[k]*theta^(k-1): k in [1..e]]; Auxa[2]:=Const4+&+[Eltseq(Lin4*Matrix(F,e,1,Eltseq(s1)))[k]*theta^(k-1): k in [1..e]]; Exkey[i]:=Matrix(F,r,c,Auxa); else for q:=0 to c-1 by 2 do Auxa[r*q+1]:=theta^(i-1)+Const4+&+[Eltseq(Lin4*Matrix(F,e,1,Eltseq(s0)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[r*t+1]:t in [0..q]]; Auxa[r*q+2]:=Const4+&+[Eltseq(Lin4*Matrix(F,e,1, Eltseq(s1)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[r*t+2]:t in [0..q]]; end for; Exkey[i]:=Matrix(F,r,c,Auxa); end if; end for; elif r eq 4 then SboxMat:=Matrix(F,4,1,[0,0,0,0]); for i in [2..n+1] do Auxa:=Eltseq(Exkey[i]); Auxb:=Eltseq(Exkey[i-1]); s0:=Sbox(Auxb[4*c]); s1:=Sbox(Auxb[4*c-1]); s2:=Sbox(Auxb[4*c-2]); s3:=Sbox(Auxb[4*c-3]); SboxMat[1,1]:=s0; SboxMat[2,1]:=s1; SboxMat[3,1]:=s2; SboxMat[4,1]:=s3; ListeSbox:=ListeSbox cat [SboxMat]; if c eq 1 then Auxa[1]:=theta^(i-1)+Const4+&+[Eltseq(Lin4*Matrix(F,e,1,Eltseq(s0)))[k]*theta^(k-1): k in [1..e]]; Auxa[2]:=Const4+&+[Eltseq(Lin4*Matrix(F,e,1,Eltseq(s1)))[k]*theta^(k-1): k in [1..e]]; Auxa[3]:=Const4+&+[Eltseq(Lin4*Matrix(F,e,1,Eltseq(s2)))[k]*theta^(k-1): k in [1..e]]; Auxa[4]:=Const4+&+[Eltseq(Lin4*Matrix(F,e,1,Eltseq(s3)))[k]*theta^(k-1): k in [1..e]]; Exkey[i]:=Matrix(F,r,c,Auxa); else for q:=0 to c-1 by 4 do Auxa[r*q+1]:=theta^(i-1)+Const4+&+[Eltseq(Lin4*Matrix(F,e,1,Eltseq(s0)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[r*t+1]:t in [0..q]]; Auxa[r*q+2]:=Const4+&+[Eltseq(Lin4*Matrix(F,e,1, Eltseq(s1)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[r*t+2]:t in [0..q]]; Auxa[r*q+3]:=Const4+&+[Eltseq(Lin4*Matrix(F,e,1, Eltseq(s2)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[r*t+3]:t in [0..q]]; Auxa[r*q+4]:=Const4+&+[Eltseq(Lin4*Matrix(F,e,1, Eltseq(s3)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[r*t+4]:t in [0..q]]; end for; Exkey[i]:=Matrix(F,r,c,Auxa); end if; end for; end if; elif e eq 8 then if r eq 1 then SboxMat:=Matrix(F,1,1,[0]); for i in [2..n+1] do Auxa:=Eltseq(Exkey[i]); Auxb:=Eltseq(Exkey[i-1]); s0:=Sbox(Auxb[c]); SboxMat[1,1]:=s0; ListeSbox:=ListeSbox cat [SboxMat]; if c eq 1 then Auxa[1]:=theta^(i-1)+Const8+&+[Eltseq(Lin8*Matrix(F,e,1,Eltseq(s0)))[k]*theta^(k-1): k in [1..e]]; Exkey[i]:=Matrix(F,r,c,Auxa); else for q:=0 to c-1 do Auxa[q+1]:=theta^(i-1)+Const8+&+[Eltseq(Lin8*Matrix(F,e,1,Eltseq(s0)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[r*t+1]:t in [0..q]]; end for; Exkey[i]:=Matrix(F,r,c,Auxa); end if; end for; elif r eq 2 then SboxMat:=Matrix(F,2,1,[0,0]); for i in [2..n+1] do Auxa:=Eltseq(Exkey[i]); Auxb:=Eltseq(Exkey[i-1]); s0:=Sbox(Auxb[2*c]); s1:=Sbox(Auxb[2*c-1]); SboxMat[1,1]:=s0; SboxMat[2,1]:=s1; ListeSbox:=ListeSbox cat [SboxMat]; if c eq 1 then Auxa[1]:=theta^(i-1)+Const8+&+[Eltseq(Lin8*Matrix(F,e,1,Eltseq(s0)))[k]*theta^(k-1): k in [1..e]]; Auxa[2]:=Const8+&+[Eltseq(Lin8*Matrix(F,e,1,Eltseq(s1)))[k]*theta^(k-1): k in [1..e]]; Exkey[i]:=Matrix(F,r,c,Auxa); else for q:=0 to c-1 by 2 do Auxa[r*q+1]:=theta^(i-1)+Const8+&+[Eltseq(Lin8*Matrix(F,e,1,Eltseq(s0)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[r*t+1]:t in [0..q]]; Auxa[r*q+2]:=Const8+&+[Eltseq(Lin8*Matrix(F,e,1, Eltseq(s1)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[r*t+2]:t in [0..q]]; end for; Exkey[i]:=Matrix(F,r,c,Auxa); end if; end for; elif r eq 4 then SboxMat:=Matrix(F,4,1,[0,0,0,0]); for i in [2..n+1] do Auxa:=Eltseq(Exkey[i]); Auxb:=Eltseq(Exkey[i-1]); s0:=Sbox(Auxb[4*c]); s1:=Sbox(Auxb[4*c-1]); s2:=Sbox(Auxb[4*c-2]); s3:=Sbox(Auxb[4*c-3]); SboxMat[1,1]:=s0; SboxMat[2,1]:=s1; SboxMat[3,1]:=s2; SboxMat[4,1]:=s3; ListeSbox:=ListeSbox cat [SboxMat]; if c eq 1 then Auxa[1]:=theta^(i-1)+Const8+&+[Eltseq(Lin8*Matrix(F,e,1,Eltseq(s0)))[k]*theta^(k-1): k in [1..e]]; Auxa[2]:=Const8+&+[Eltseq(Lin8*Matrix(F,e,1,Eltseq(s1)))[k]*theta^(k-1): k in [1..e]]; Auxa[3]:=Const8+&+[Eltseq(Lin8*Matrix(F,e,1,Eltseq(s2)))[k]*theta^(k-1): k in [1..e]]; Auxa[4]:=Const8+&+[Eltseq(Lin8*Matrix(F,e,1,Eltseq(s3)))[k]*theta^(k-1): k in [1..e]]; Exkey[i]:=Matrix(F,r,c,Auxa); else for q:=0 to c-1 by 4 do Auxa[r*q+1]:=theta^(i-1)+Const8+&+[Eltseq(Lin8*Matrix(F,e,1,Eltseq(s0)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[r*t+1]:t in [0..q]]; Auxa[r*q+2]:=Const8+&+[Eltseq(Lin8*Matrix(F,e,1, Eltseq(s1)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[r*t+2]:t in [0..q]]; Auxa[r*q+3]:=Const8+&+[Eltseq(Lin8*Matrix(F,e,1, Eltseq(s2)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[r*t+3]:t in [0..q]]; Auxa[r*q+4]:=Const8+&+[Eltseq(Lin8*Matrix(F,e,1, Eltseq(s3)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[r*t+4]:t in [0..q]]; end for; Exkey[i]:=Matrix(F,r,c,Auxa); end if; end for; end if; end if; return Exkey, ListeSbox; end function; SubBytes:=function(n,r,c,e, InputWord) InputWord:=Matrix(F4,r,c,[Sbox(elt): elt in Eltseq(InputWord)]); SboxOut:=InputWord; if e eq 4 then for i in [1..r] do for j in [1..c] do InputWord[i,j]:=Const4+&+[Eltseq(Lin4*Matrix(F,e,1, Eltseq(InputWord[i,j])))[k]*theta^(k-1): k in [1..e]]; end for; end for; elif e eq 8 then for i in [1..r] do for j in [1..c] do InputWord[i,j]:=Const8+&+[Eltseq(Lin8*Matrix(F,e,1, Eltseq(InputWord[i,j])))[k]*theta^(k-1): k in [1..8]]; end for; end for; end if; return [SboxOut, InputWord]; end function; AES:=function(n,r,c,e,nc) Message:=[];ListeState:=[]; ListeSbox:=[]; auxMess:=[0: i in [1..r*c]]; for i in [1..nc] do temp:=auxMess; temp[i]:=1; //Message:=Message cat [Matrix(F4,r,c,temp)]; Message:=Message cat [Matrix(F4,r,c,[Random(F4): i in [1..r*c]])]; end for; InitKey:=Matrix(F4,r,c,[Random(F4): i in [1..r*c]]); ExKey, ListeSboxKey:=Expandedkey(n,r,c,e,InitKey); for j in [1..nc] do // Round 0 State:=Message[j]+ExKey[1]; ListeState:=ListeState cat [State]; // Round 1..n for i in [1..n] do Aux:=SubBytes(n,r,c,e,State); ListeSbox:=ListeSbox cat [Aux[1]]; State:=Aux[2]; if i ne n then State:=ChangeRing(ShiftRows(n,r,c,e, MixColumns(n,r,c,e,State)),F4)+ExKey[i+1]; else State:=ChangeRing(ShiftRows(n,r,c,e,State),F4)+ExKey[n+1]; end if; // InputWord est la sortie du round de chiffrement n, et l'entrée du round n+1 ListeState:=ListeState cat [State]; end for; end for; return Message, ExKey, ListeState, ListeSbox, ListeSboxKey; end function; // ********************************************************************** //test Message, ExKey, ListeState, ListeSbox, ListeSboxKey:=AES(n,r,c,e,nc); /* Message : les clairs utilisée pour générer les nc systeme Exkey : les n+1 clefs ListeState[i] : etat après le round i ListeSbox[i] : valeur de la sortie de la Sbox (juste X->1/X) dans le chiffrement ListeSboxKey[i] : valeur de la sortie de la Sbox (juste X->1/X) dans le cadencement de clef */ ListeEqC, ListeStateSymb, ListeKeySymb:=Gen_Eq_Cipher(n,r,c,e,Message); /* ListeEqC : équations du chiffrement ListeStateSymb[i] : etat (sous forme symbolique) après le round i ListeKeySymb[i] : les n+1 clefs sous forme symbolique */ ListeK, Eq:=Gen_Eq_Key(n,r,c,e); /* Eq:= equation provenant du chiffrement du cdencement de clef */ // Je teste ici si le système que je génère admet bien une "bonne" solution test:=[]; // ********************************************************** for mat in ExKey do for i in [1..r] do for j in [1..c] do auxij:=Eltseq(F4!mat[i,j]); for k in [1..e] do test:=test cat [auxij[k]]; end for; end for; end for; end for; for mat in ListeSboxKey do for i in [1..r] do auxij:=Eltseq(F4!mat[i,1]); for k in [1..e] do test:=test cat [auxij[k]]; end for; end for; end for; for mat in ListeSbox do for i in [1..r] do for j in [1..c] do auxij:=Eltseq(F4!mat[i,j]); for k in [1..e] do test:=test cat [auxij[k]]; end for; end for; end for; end for; // ********************************************************** // equations du Chiffrement SysEqC:=[]; for mat in ListeEqC do for elt in Eltseq(mat) do SysEqC:=SysEqC cat Set_Poly(elt,e); end for; end for; // equations du cadencement des clefs SysEqK:=[]; for mat in Eq do for elt in Eltseq(mat) do SysEqK:=SysEqK cat Set_Poly(elt,e); end for; end for; // equations linéaires var. clef chif//clef cadence // #ListeKeySymb=nc*#ListeK ListeK:=[ListeK[i]-ListeKeySymb[i]: i in [1..#ListeK]]; SysEqKl:=[]; for mat in ListeK do for elt in Eltseq(mat) do SysEqKl:=SysEqKl cat Set_Poly(elt,e); end for; end for; // Equations provenant du chiffré SysEqCi:=[]; //aux:=ChangeRing(ListeState[n+1],F)-ListeStateSymb[n+1] for i in [1..nc] do for elt in Eltseq(ChangeRing(ListeState[i*(n+1)],F)-ListeStateSymb[i*(n+1)]) do SysEqCi:=SysEqCi cat Set_Poly(elt,e); end for; end for; //Systeme AES SysAES:=SysEqC cat SysEqK cat SysEqKl cat SysEqCi cat [F.i^2-F.i: i in [1..(n+1)*r*c*e+n*r*e+nc*n*r*c*e]]; testSys:=[Evaluate(elt,test): elt in SysAES]; zeroSys:=[F4!0: i in [1..#testSys]]; if testSys eq zeroSys then #SysAES; SetVerbose("Faugere", 1); time V:=Variety(Ideal(SysAES)); end if; |
| Link: |
October 2005
October 14, 11:00 - Algorithms and Architectures for Public Key Cryptography: Which Number System is Best?
by Liam Marnane
| Date: | October 14, 2005 - 11:00 |
| Location: | Room 207, Euler Building (near Maxwell Building) Avenue Georges Lemaître, 4-6 - 1348 Louvain-la-Neuve |
| Abstract: | This talk will present a number of architectures for implementing on FPGA modern Public Key Cryptographic Algorithms from the RSA and Diffie Hellman based on arithmetic in GF(p) to Identity based encryption based on arithmetic in GF(p), GF(p^m) and GF(2^m). The advantages and disadvantages of the different number systems will be highlighted and possible future research questions identified. |
| Link: |
November 2005
November 02, 11:00 - L'immunité algébrique des fonctions sur un corps fini
by Gwénolé Ars
| Date: | November 02, 2005 - 11:00 |
| Location: | Auditoire Euler, 002, Euler Building (near Maxwell Building) Avenue Georges Lemaître, 4-6 - 1348 Louvain-la-Neuve |
| Abstract: | Une définition mathématique générale de la résistance d'une fonction définie sur GF(q)^n dans GF(q)^m à la cryptanalyse algébrique est développée. Elle généralise la définition d'''Algebraic Immunity'' des chiffrements par flot à tout corps fini et aussi au chiffrement par blocs. Cette immunité algébrique correspond aux équations de plus petit terme de tête selon un certain ordre monomial. Nous donnons des propriétés de cette immunité algébrique et nous calculons aussi des bornes explicites et asymptotiques. Nous tendons la définition d'immunité aux fonctions avec mémoire mais elle dépend du nombre de sorties consécutives regardés. Nous montrons que tous les résultats obtenues sur les fonctions sans mémoire induisent des résultats similaires par simple changement linaire des valeurs n et m. Enfin, nous montrons que pour une fonction avec une mémoire de taille l et telle que m=1, si nous n'avons pas de relation ne dépendant pas de la mémoire pour l sorties consécutives, alors nous pouvons construire un polynôme qui engendre toutes les relations sans mémoire de la fonction pour un plus grand nombre de sorties. Nous utilisons cette propriété pour calculer explicitement l'immunité algébrique de ``summation generator''. |
| Link: |
November 17, 11:00 - Discrete-Log-Based Signatures May Not Be Equivalent to Discrete Log
by Damien Vergnaud
| Date: | November 17, 2005 - 11:00 |
| Location: | Room 207, Euler Building (near Maxwell Building) Avenue Georges Lemaître, 4-6 - 1348 Louvain-la-Neuve |
| Abstract: | We provide evidence that the unforgeability of several discrete-log based signatures like Schnorr signatures cannot be equivalent to the discrete log problem in the standard model. This contradicts in nature well-known proofs standing in weakened proof methodologies, in particular proofs employing various formulations of the Forking Lemma in the random oracle Model. Our impossibility proofs apply to many discrete-log-based signatures like ElGamal signatures and their extensions, DSA, ECDSA and KCDSA as well as standard generalizations of these, and even RSA-based signatures like GQ. All known reductions attesting the unforgeability of Fiat-Shamir transformed signatures in the random oracle model lead to a loss factor close to q_h in terms of execution time or success probability (q_h denotes the number of oracle queries). There exists no proof that this loss factor is necessary. We prove, however, that any random-oracle-based reduction from computing the discrete logarithm to forging Schnorr signatures must lose at least a factor close to the square root of q_h. We further conjecture that the 1/q_h loss is optimal. In any case, our results show that a proof of equivalence in the ROM (if algebraic) will *never be tight*. We believe our work sheds a new perspective as to why no efficient proof of equivalence to the discrete log problem has ever been found for Schnorr signatures despite considerable research efforts. We stress that our work sheds more light on the provable (in)security of popular signature schemes but does not explicitly lead to actual attacks on these. (Joint work with Pascal Paillier from Advanced Cryptographic Services, Gemplus Card International. A paper summarizing this work will appear in the proceedings of the Asiacrypt'05 conference.) |
| Link: |
November 23, 11:00 - On the security proof of the GQ2 authentication scheme
by Sophie Boutiton
| Date: | November 23, 2005 - 11:00 |
| Location: | Auditoire Euler, 002, Euler Building (near Maxwell Building) Avenue Georges Lemaître, 4-6 - 1348 Louvain-la-Neuve |
| Abstract: | This presentation deals with the security proof of the GQ2 authentication scheme. The three properties of completeness, soundness and zero-knowledge must be verified as for each secure 3-pass zero-knowledge protocol. In particular, we study the soundness property that reveals the security threshold of the scheme. We determine sufficient conditions to ensure that convincing the verifier with a probability higher than the security threshold in a non-negligible way, induces the knowledge of modulus factorization. First, we verify that this security threshold is underestimated by $1/2^{km}$, where $k$ is the security parameter and $m$ the number of basic numbers. Then, the generalization of the forking lemma permits to characterize the security threshold by the probability to produce key-pairs that reveal modulus factorization. The optimal security conditions of the GQ2 protocol are linked to the security threshold that is equal to $1/2^{km}$. Application: in the case of two factors congruent to 3 modulo 4, we prove that the security threshold is $1/2$. Then, we generalize the argument to any factors using a graphical representation of the square function graph on the factors groups. In some particular cases validated by simulations, we deduce an optimal security threshold of $1/2^b$ where $b$ denotes an adaptative parameter. |
| Link: |
December 2005
December 15, 11:00 - An Algebraic Approach to NTRU (q = 2^n) via Witt Vectors and
Overdetermined Systems of Nonlinear Equations
by Frederik Vercauteren
| Date: | December 15, 2005 - 11:00 |
| Location: | Auditoire Euler, 002, Euler Building (near Maxwell Building) Avenue Georges Lemaître, 4-6 - 1348 Louvain-la-Neuve |
| Abstract: | We use the theory of Witt vectors to develop an algebraic approach for studying the NTRU primitive with q parameter equal to a power of two. This results in a system of nonlinear algebraic equations over GF(2) having many symmetries, which is reminiscent of the approach of Courtois, Murphy, Pieprzyk, Robshaw and others for studying the structure of block ciphers such as the AES. We study whether this approach to NTRU provides any immediate security threat and conclude that under the most favourable assumptions, the method is of asymptotic interest but is completely impractical at current or likely future parameter sizes. |
| Link: | http://homes.esat.kuleuven.be/~fvercaut/papers/scn04.pdf.gz |
December 22, 11:15 - Asymptotically optimal computation of class polynomials
by Andreas Enge
| Date: | December 22, 2005 - 11:15 |
| Location: | Auditoire Euler, 002, Euler Building (near Maxwell Building) Avenue Georges Lemaître, 4-6 - 1348 Louvain-la-Neuve |
| Abstract: | Computing class polynomials is the main step in the construction of elliptic curves by the complex multiplication approach. I present two asymptotically optimal algorithms with a quasi-linear complexity in their output size, one of which might even be practical. |
| Link: | http://www.lix.polytechnique.fr/Labo/Andreas.Enge/ |
See also:
- COSIC seminars (KUL, Leuven)
- GRECC seminars (ENS, Paris)