Tag Archives: paper

An All-In-One Approach to Differential Cryptanalysis for Small Block Ciphers

by

a paper that I wrote with Gregor Leander is finally done, out and accepted for presentation at SAC.

We present a framework that unifies several standard differential techniques. This unified view allows us to consider many, potentially all, output differences for a given input difference and to combine the information derived from them in an optimal way. We then propose a new attack that implicitly mounts several standard, truncated, impossible, improbable and possible future variants of differential attacks in parallel and hence allows to significantly improve upon known differential attacks using the same input difference. To demonstrate the viability of our techniques, we apply them to KATAN-32. In particular, our attack allows us to break 115 rounds of KATAN-32, which is 37 rounds more than previous work. For this, our attack exploits the non-uniformity of the difference distribution after 91 rounds which is 20 rounds more than the previously best known differential characteristic. Since our results still cover less than 1/2 of the cipher, they further strengthen our confidence in KATAN-32′s resistance against differential attacks.

 

Rank-profile revealing Gaussian elimination and the CUP matrix decomposition

by

by Claude-Pierre Jeannerod, Clément Pernet, Arne Storjohann is now available on the archive. I like this paper a lot and we also referenced it in both the M4RI elimination paper and the M4RIE paper so three cheers that it’s now available.

Abstract: Transforming a matrix over a field to echelon form, or decomposing the matrix as a product of structured matrices that reveal the rank profile, is a fundamental building block of computational exact linear algebra. This paper surveys the well known variations of such decompositions and transformations that have been proposed in the literature. We present an algorithm to compute the CUP decomposition of a matrix, adapted from the LSP algorithm of Ibarra, Moran and Hui (1982), and show reductions from the other most common Gaussian elimination based matrix transformations and decompositions to the CUP decomposition. We discuss the advantages of the CUP algorithm over other existing algorithms by studying time and space complexities: the asymptotic time complexity is rank sensitive, and comparing the constants of the leading terms, the algorithms for computing matrix invariants based on the CUP decomposition are always at least as good except in one case. We also show that the CUP algorithm, as well as the computation of other invariants such as transformation to reduced column echelon form using the CUP algorithm, all work in place, allowing for example to compute the inverse of a matrix on the same storage as the input matrix.

http://arxiv.org/abs/1112.5717

Efficient dense Gaussian elimination over the field with two elements

by

Finally, we finished our paper about Gaussian elimination in the M4RI library.

Abstract: In this work we describe an efficient implementation of a hierarchy of algorithms for Gaussian elimination upon dense matrices over the field with two elements (\mathbb{F}_2). We discuss both well-known and new algorithms as well as our implementations in the M4RI library, which has been adopted into Sage. The focus of our discussion is a block iterative algorithm for PLE decomposition which is inspired by the M4RI algorithm. The implementation presented in this work provides considerable performance gains in practice when compared to the previously fastest implementation. We provide performance figures on x86_64 CPUs to demonstrate the alacrity of our approach.

The sources of this document are available on bitbucket. But I also compiled a PDF.

Update: arXiv link.

Polly Cracker, Revisited

by

I’ve been mentioning this work a few times; well,  finally a pre-print is ready (by myself, Pooya Farshim, Jean-Charles Faugère and Ludovic Perret).

In this paper we initiate the formal treatment of cryptographic constructions – commonly known as “Polly Cracker” – based on the hardness of computing remainders modulo an ideal over multivariate polynomial rings. This work is motivated by the observation that the Ideal Remainder (IR) problem is one of the most natural candidates to build homomorphic encryption schemes. To this end, we start by formalising and studying the relation between the ideal remainder problem and the problem of computing a Gröbner basis.

We show both positive and negative results.

On the negative side, we define a symmetric Polly Cracker encryption scheme and prove that this scheme only achieves bounded CPA security under the hardness of the IR problem. Furthermore, using results from computational commutative algebra we show that a large class of algebraic transformations cannot convert this scheme to a fully secure Polly Cracker-type scheme.

On the positive side, we formalise noisy variants of the ideal membership, ideal remainder, and Gröbner basis problems. These problems can be seen as natural generalisations of the LWE problem and the approximate GCD problem over polynomial rings. After formalising and justifying the hardness of the noisy assumptions we show – following the recent progress on homomorphic encryption – that noisy encoding of messages results in a fully IND-CPA secure somewhat homomorphic encryption scheme. Together with a standard symmetric-to-asymmetric transformation for additively homomorphic schemes, we provide a positive answer to the long standing open problem proposed by Barkee et al. (and later also by Gentry) of constructing a secure Polly Cracker-type cryptosystem reducible to the hardness of solving a random system of equations. Indeed, our results go beyond that by also providing a new family of somewhat homomorphic encryption schemes based on new, but natural, hard problems.

Our results also imply that Regev’s LWE-based public-key encryption scheme is (somewhat) multiplicatively homomorphic for appropriate choices of parameters. Finally, we estimate the parameters which define our cryptosystem and give a proof-of-concept implementation.

Sage source code included, have fun.

Polynomial System Solving with Noise

by

The reason I became somewhat interested in mixed integer programming is that it is one way of solving polynomial systems which are noisy. These kind of polynomial systems pop up in crypto all over the place but so far — to my knowledge — they have not been studied extensively. In order to clarify what is meant by “polynomial system solving with noise”, we can define a familiy of Max-PoSSo problems similar to the Max-SAT family of problems (in fact, you can reduce Max-PoSSo to Max-SAT).

Polynomial system solving (PoSSo) is the problem of finding a solution to a system of polynomial equations over some field \mathbb{F}. We consider the set F=\{f_0,...,f_{m-1}\}, where each $latex f_i \in \mathbb{F}[x_0,\dots,x_{n-1}]$. A solution to $latex F$ is any point x \in \mathbb{F}^n such that $latex \forall f \in F$, we have $latex f(x) = 0$. Note that we restrict ourselves to solutions in the base field in this context.

Then by Max-PoSSo we denote the problem of finding any x \in \mathbb{F}^n which satisfies the maximum number of polynomials in F. Likewise, by Partial Max-PoSSo we denote the problem to return a point x \in \mathbb{F}^n such that for two sets of polynomials \mathcal{H} and $\mathcal{S}$ in \mathbb{F}[x_0, \dots, x_{n-1}], we have f(x) = 0 for all f \in \mathcal{H}, and the number of polynomials f \in \mathcal{S} with f(x) = 0 is maximised. Max-PoSSo is Partial Max-PoSSo with \mathcal{H} = \varnothing.

Finally, by Partial Weighted Max-PoSSo we denote the problem to return a point x \in \mathbb{F}^n such that \forall f \in \mathcal{H}: f(x) = 0 and \sum_{f \in \mathcal{S}} \mathcal{C}(f,x) is minimized where \mathcal{C}: f \in \mathcal{S},x \in \mathbb{F}^n \rightarrow \mathbb{R}_{\geq 0} is a cost function which returns 0 if f(x) = 0 and some value > 0 if f(x) \neq 0. Partial Max-PoSSo is Weighted Partial Max-PoSSo where \mathcal{C}(f,x) returns 1 if f(x) \neq 0 for all f.

It turns out one can solve Partial Weighted Max-PoSSo over \mathbb{F}_2 using mixed integer programming. Recently, Carlos and I have been busy applying these ideas to the cold boot problem, with reasonable success. An extended abstract of our work is available here. Two sets of slides discussing our techniques are also available here and here.