% pour n'avoir que les transparents en landscape \documentclass[12pt,a4,slidesonly]{seminar} % pour avoir les transparents et les commentaires %\documentclass[12pt,a4,article]{seminar} % pour pouvoir choisir la forme du cadre \usepackage{fancybox,amsmath,amssymb,amsfonts} \newtheorem{definition}{Definition} \newtheorem{proposition}[definition]{Proposition} \newtheorem{corollary}[definition]{Corollary} \newtheorem{theorem}[definition]{Theorem} \newtheorem{lemma}[definition]{Lemma} \newtheorem{example}{Example} \newenvironment{proof}{\begin{trivlist}\item[]{\em Proof.\\ }}% {\samepage \hfill$\diamond$\end{trivlist}} \renewcommand{\a}{\alpha} \newcommand{\m}{\mu} \renewcommand{\l}{\lambda} \newcommand{\pf}{{\bf Proof : }} \newcommand{\comb}[2] {\mbox{$\left( { #1 \atop #2 } \right)$}} \newcommand{\G}{\Gamma} \newcommand{\om}{\omega} \newcommand{\ot}{\otimes} \newcommand{\h}{\eta} \newcommand{\card}[1]{\mbox{$\mid #1 \mid$}} \newcommand{\e}{\epsilon} \newcommand{\expo}{\mbox{$m+2+\lfloor\frac{n-m-2}{d}\rfloor$}} \renewcommand{\b}{\beta} \newcommand{\un}{\underline} \slideframe{Oval} \title{Shorter keys for code based cryptosystems} \author{Philippe Gaborit (University of Limoges, France)} \date{} \begin{document} \begin{slide} \maketitle \end{slide} \begin{slide} {\bf Summary} $\bullet$ Code based cryptosystems $\bullet$ Usual attacks $\bullet$ Quasi-Cyclic McEliece scheme $\bullet$ A family of decodable quasi-cyclic codes $\bullet$ Security of the new scheme $\bullet$ Conclusion \end{slide} \begin{slide} {\bf Notation} $\bullet$ $F_q$ a field with $q$ \'el\'ements, $C$ a linear $[n,k,d]$ code $w_H(x)$: Hamming weight of a word $x$ $\bullet$ usual scalar product $x.y=\sum_1^n x_iy_i$, dual of a code $C$: $C^{\perp}=\{y \in F_q^n | x.y=, \forall y \in C\}$. $C$ a $[n,k,d]$ code $\rightarrow$ $k\times n$ generator matrix $C^{\perp}$ $\rightarrow$ $(n-k) \times n$, parity check matrix. \end{slide} \begin{slide} {\bf Code based cryptosystems} Interest: not based on number theory, does not need cryptoprocessors Hard problem: {\bf Syndrom decoding problem} Let $H$ be a binary $k\times n$ random matrix, let $s \in F_2^k$ and let $w$ be a positive integer. Does it exist a word $x$ in $F_2^n$ with weight at most $w$ such that $Hx^t=s$ ? Proven NP-complete '78 BMT Related to the decoding problem: if one knows $y=x+e$ how recover $x$ ? \end{slide} \begin{slide} {\bf McEliece cryptosystem '78} $\bullet$ Private key: $C$ a $[n,k,d]$ linear code which corrects $t$ errors, a $k \times n$ matrix $G$, a $k \times k$ invertible matrix $S$, and a $n \times n$ permutation matrix $P$. $\bullet$ Public key: $G'=SGP$ $\bullet$ Encryption: $x \rightarrow xG'+e$ with $w_H(e) \le t$. $\bullet$ Decryption: $y \rightarrow \Phi_C(yP^{-1})S^{-1}$, where $\Phi_C(z)$ is a decoding algorithm up to the distance $t$.\\ Codes proposed : Goppa codes with parameters [1024,524,101], t=50. \end{slide} \begin{slide} Complexity: Encryption : $O(n^2)$ Decryption : $O(n^2)$ Size of key : $kn$ Transmission rate: $k/n$ $\rightarrow$ very fast system but public key very big: about 500000 bits for the original system! \end{slide} \begin{slide} {\bf Niederreiter scheme} '86 \medskip \noindent {\bf Private key:} $\bullet$ Private key: $C$ a $[n,k,d]$ code which corrects $t$ errors, $H$ a parity check matrix of $C$, a $k \times n$ matrix $G$, a $k \times k$ invertible matrix $S$, and a $n \times n$ permutation matrix $P$.\\ {\bf Public key :} $H'=SHP$.\\ {\bf Encryption:} $x \rightarrow y=H'x^T$, with $x$ of weight $t$.\\ {\bf Decryption:} Decode $y$ in $z$,then $zP^{-1}$ gives $x$.\\ Variation on the McEliece scheme, permits to win on certain points (size of certain parameters). Security equivalent to McEliece scheme. \end{slide} \begin{slide} {\bf Signature scheme, Courtois,Finiasz,Sendrier '01} Encryption schemes are not all invertible like RSA 1-1. If one considers a random codeword of $F_2^n$ it is not necessary decodable in $C$. {\bf Idea:} consider a code with small covering radius (t=7-9), then the density of decodable codewords is roughly $\frac{1}{t!}$ For $h(m)$ a hashing of $m$, iterate the computation $h(m,i_0)$ until a decodable word is found, for $i_0=1,2,\cdots$. {\bf Weakness:} needs to decode $t!$ random codewords on the average before finding a suitable codeword. Moreover for security $t \approx 7-9$, implies a key of size 1 Moctet. But the signature can be very small ( $<100$ bits). \end{slide} \begin{slide} {\bf Stern authentication scheme '93} Based on zero-knowledge, probability to cheat 2/3. Big size of key, also works for signature. {\bf Sidelnikov scheme '94} Variation on McEliece by considering the Reed-Muller codes rather than Goppa codes {\bf Rank codes, Gabidulin '91} Variation on McEliece by considering another kind of distance: the rank distance. \end{slide} \begin{slide} {\bf Usual attacks} $\bullet$ {\bf Message attacks} One tries to decode directly. Information set decoding Lee and Brickell '87, Stern '89, Leon '89, Canteaut-Chabaud '98 Let $C$ $[n,k,2t+1]$ code, one chooses a random set of $k$ columns, an error woth weight $t$ is said to be {\it decodable} when its support does not meet the $k$ random columns. \end{slide} \begin{slide} The probability for an error to be decodable is then $P_{dec}=\frac{\binom{n-k}{t}}{\binom{n}{t}}$, let $P_{dec} = O(1).2^{-nH_2(t/n)-(1-k)H_2(t/(n-k))},$ for $H_2(x)=-xlog_2(x)-(1-x)log_2(1-x)$.\\ One deduce then the work for finding ONE word of weight $t$: $$ WF=\frac{P(k)}{P_{dec}},$$ where $P(k)$ is the cost of a Gaussian elimination. $P(k)$ is roughly $O(k^3)$, the different methods improve this facteur. $\rightarrow$ exponential complexity for the best known algorithm. \end{slide} \begin{slide} Original McEliece cryptosystem broken in '98 by Canteaut-Sendrier. Previous attack is optimized for $k \approx 2/3 n$. To have a security of $2^{80}$: one needs $n \ge 1400$, key $\approx$ $800$kbits. The security of the system is not as such equivalent to a NP-complete problem. \end{slide} \begin{slide} {\bf Structural attacks} One tries to recover the secret permutation matrix $P$ directly. Support splitting algorithm Sendrier '97 Algorithm which permits to decide when two codes are equivalent or not. Variation on an algorithm by Leon. Complexity: $O(2^{dim(C \cap C^{\perp})})$. Random codes have a small hull, Reed-Muller have a big hull and are not vulnerable to this attack. Goppa codes : many of them. \end{slide} \begin{slide} {\bf Quasi-Cyclic McEliece scheme} {\bf idea :} use quasi-cyclic codes to shorten the size of the public key \begin{definition} A code of length $n$ is said to be {\it quasi-cyclic} of order $s$, for $s$ a divisor of $n$, if the shift of any codeword by $s$ positions is still a codeword. \end{definition} A cyclic code is quasi-cyclic with order $s=1$. \begin{lemma} If $C$ is a cyclic code of length $n$ then $C$ is also quasi-cyclic of order $s$, for any $s$ which divides $n$. \end{lemma} \begin{lemma} If $C$ is quasi-cyclic of order $s$, then $C^{\perp}$ is also quasi-cyclic of order $s$. \end{lemma} \end{slide} \begin{slide} {\bf Compact representation of quasi-cyclic codes} Let $G$ be a generator matrix of a quasi-cyclic code. \begin{proposition}\label{quasi} Let $C$ be a $[n,k]$ quasi-cyclic code of order $s$ with $n=rs$ then there exists a $k' \times n $ matrix ${\cal G}$ (with $k' \ge k$), wihich generates $C$, of the form: \[ {\cal G}= \left( \begin{array}{ccccc} A_1 & A_2 & A_3 & \cdots & A_r \\ A_r & A_1 & A_2 & \cdots & A_{r-1} \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ A_2 & A_3 & A_4 & \cdots & A_1 \\ \end{array} \right), \] where $A_i$ are $\frac{k'}{r} \times s$ matrices. \end{proposition} \end{slide} \begin{slide} {\bf A new way to describe the key} The $A_i$ permit to recover the generator matrix by a simple shifts. {\bf Idea:} mask the structure of the matrix with a permutation $\Pi$ which preserves the quasi-cyclicity of the original matrix: \[ \Pi= \left( \begin{array}{cccc} \pi & 0 & \cdots & 0 \\ 0 & \pi & \cdots & 0 \\ \vdots & \vdots & \vdots & \vdots \\ 0 & 0 & \cdots & \pi \\ \end{array} \right), \] \end{slide} \begin{slide} one constructs the masked matrix: \[ {\cal G}'= \left( \begin{array}{ccccc} A_1\pi & A_2\pi & A_3\pi & \cdots & A_r\pi \\ A_r\pi & A_1\pi & A_2\pi & \cdots & A_{r-1}\pi \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ A_2\pi & A_3\pi & A_4\pi & \cdots & A_1\pi \\ \end{array} \right), \] \end{slide} \begin{slide} \end{slide} \begin{slide} {\bf An extraction procedure} In the scheme the same matrix has to be used to encrypt and to decrypt. The quasi-cyclic matrix may have more rows than $k$. One has then to extract a matrix in unique way which can be used for decryption and encryption. This procedure needs only to be done once. This method can also be applied to the dual code to have a smaller key. \end{slide} \begin{slide} {\bf Quasi-cyclic McEliece scheme} $\bullet$ {\bf Key creation:} Let $C$ be a $[n,k,d]$ $s$-quasi-cyclic code. One chooses a random permutation $\pi$ on $s$ coordinates. One constructs the $(n,k')$ matrix ${\cal G}$ associated to $C$, one applies the permutation $\Pi$ to {\cal G} in order to construct ${\cal G}'={\cal G}\Pi$. The public key $K_P$ is then the $\frac{k'}{r}$ first rows of ${\cal G}'$, the number of errors $t$ and the order of quasi-cyclicity. The private key is the permutation $\pi$.\\ \end{slide} \begin{slide} $\bullet$ {\bf Encryption:}\\ From the public key one rebuilds the matrix ${\cal G}'$ by quasi-cyclicity and one extracts the encryption matrix $G'$. Then one proceeds as in the usual scheme. $\bullet$ {\bf Decryption:}\\ As in the usual scheme. \end{slide} \begin{slide} {\bf A big family of quasi-cyclic codes} One needs : quasi-cyclicity, a good decoding algorithm, non vulnerability to known attacks. {\bf Problem: } find such a family of codes! Only 'small' families of quasi-cylic Goppa codes are known. An example of quasi-cyclic Goppa codes: the primitive BCH codes $[2^m-1,k,2t+1]$, which are cyclic and therefore quasi-cyclic for any divisor of $n$. \end{slide} \begin{slide} {\bf Quasi-cyclic subcodes} \begin{proposition}\label{sub} Let $C$ be a $[n,k]$ $s$-quasi-cyclic code with $n=rs$ then there exist quasi-cyclic subcodes strictly included in $C$ of order $s$ and dimension greater or equal to $k-r=k-\frac{n}{s}$. \end{proposition} {\bf sketch of proof}: one adds the $r$ $s$-shifts of a random codeword to a parity check matrix of $C$. \begin{proposition}\label{num} If $C$ is a $s$-quasi-cyclique $[n,k,d]$ code, then at least $2^{k-r}$ distincts codes can be constructed by the previous proposition. \end{proposition} \end{slide} \begin{slide} {\bf A big family of suitable codes} Since a subcode of a code is still decodable, the previous results permit to construct a big family of quasi-cyclic codes from any quasi-cyclic code. Price to pay: the dimension decreases. One can then use the family of primitive BCH codes or any known quasi-cyclic Goppa code as starting code. \end{slide} \begin{slide} {\bf Security of the new scheme} {\bf Message attack } Algorithme d\'ecodage par ensemble d'informations. L'erreur $e$ ajout\'ee ne tient pas compte de la quasi-cyclicit\'e, et donc l'algo ne peut \^etre vraiment optimis\'e pour cette structure. Il n'existe pas d'algorithme g\'en\'eral de d\'ecodage \`a distance born\'ee $d=(n-1)/2$ pour les codes cycliques (et a fortiori quasi-cyclique). \end{slide} \begin{slide} {\bf Attaque par perforation du support} T. Berger. On peut remarquer que si on perfore le support du code quasi-cyclique sur des parties du support adequate, cette op\'eration conserve l'action de la permutation. Et on peut alors utiliser l'algorithme de s\'eparation des supports pour retrouver $\pi$. $\rightarrow$ comme on part d'un grand nombre de codes on ne peut appliquer cette attaque \end{slide} \begin{slide} {\bf Proposition de param\`etres} $\bullet$ Sch\'ema de McEliece \noindent {\bf Param\`etres de s\'ecurit\'e A : $ n=4095, t=26 , s = 45$.} \noindent Param\`etres du code:$[4095,3692,53]$\\ Ordre de g\'en\'eration de la matrice: $5$\\ Cl\'e publique: $20475$ bits\\ Taux de transmission: 0.9\\ S\'ecurit\'e du message : $2^{100}$\\ S\'ecurit\'e structurelle : $2^{91}$ \end{slide} \begin{slide} \noindent {\bf Param\`etres de s\'ecurit\'e B : $ n=2047, t=31 , s = 23$.} \noindent Param\`etres du code:$[2047,1617,63]$\\ Ordre de g\'en\'eration de la matrice: $5$\\ Cl\'e publique: $12282$ bits\\ Taux de transmission: 0.79\ S\'ecurit\'e du message : $2^{80}$\\ S\'ecurit\'e structurelle : $2^{85}$ D'autres param\`etres sont possibles. M\^eme chose pour le sch\'ema de Niederreiter. \end{slide} \begin{slide} {\bf Conclusion} Ne s'adapte au sch\'ema de signature car le fait de prendre un sous-code casse le faible rayon de recourement du code. Une famille importante de codes quais-cycliques permettrait d'adapter cette id\'ee \`a la signature, pour diminuer la cl\'e jusqu'\`a 100kbits-200kbits Id\'ee d'utiliser des codes quasi-cycliques est naturelle et a permis dans d'autres applications d'obtenir de bons r\'esultats. Rend la taille de la cl\'e quasi-lin\'eaire dans la longueur du code. \end{slide} \end{document}