Faugère-Lachartre implementation for linear algebra for Gröbner bases

Fayssal’s code which implements the Faugère-Lachartre approach to linear algebra for Gröbner bases is available on Github now. Fayssal did a Master’s project on linear algebra for Gröbner bases in the team of Jean-Charles Faugère.

A Fully Homomorphic Cryptosystem with Approximate Perfect Secrecy

At CT-RSA 2013 a paper titled “A Fully Homomorphic Cryptosystem with Approximate Perfect Secrecy” by Michal Hojsík and Veronika Půlpánová was presented. Here is the abstract:

We propose a new fully homomorphic cryptosystem called Symmetric Polly Cracker (SymPC) and we prove its security in the information theoretical settings. Namely, we prove that SymPC approaches perfect secrecy in bounded CPA model as its security parameter grows (which we call approximate perfect secrecy). In our construction, we use a Gröbner basis to generate a polynomial factor ring of ciphertexts and use the underlying field as the plaintext space. The Gröbner basis equips the ciphertext factor ring with a multiplicative structure that is easily algorithmized, thus providing an environment for a fully homomorphic cryptosystem.

The proposal seems to have succeeded where we could not: a fully homomorphic encryption scheme that also is information theoretic secure. Indeed, the authors reference our work and point out that they are taking a different approach (from ours) which allows them to succeed in realising these two goals.

To understand the claim made, here’s a quick rehash of our Symmetric Polly Cracker (SPC) for d=1 and b=2.

The secret key is a Gröbner basis . To encrypt we pick and publish where is the message we want to encrypt. Decryption is easy if we know because it is equivalent to computing normal forms modulo . Indeed, it can be shown that the problem of finding under a chosen plaintext attack is as hard as finding which we assume is a hard problem. This scheme is homomorphic: we can do additions and multiplications of ciphertexts which decrypt to the sums and products of plaintexts. However, the scheme is not fully homomorphic as the ciphertext size increases with each multiplication. Also, the problem of computing the Gröbner basis becomes easy once we published many encryptions, so the scheme only supports a limited number of encryptions. So far, so general.

Now, let’s take a look at the new approach. Despite the claim that “A Fully Homomorphic Cryptosystem with Approximate Perfect Secrecy” is a new approach, it is – as far as I can see – a tweak of this general construction (essentially going back to Koblitz and Fellows). The two tweaks are:

is augmented with the so-called “field polynomials” as they evaluate to zero on every element of (Note: the actual construction is slightly different, which I ignore here for clarity of presentation).
Instead of limiting the number of encryptions to some such that the Gröbner basis problem is assumed to be hard, the number of encryptions is limited to some value .

The first tweak means that after a certain number of multiplications ciphertexts do not grow in size any more. That is, the largest monomial (under some degree compatible ordering) is . This allows to call the scheme “compact” and hence allows to declare it a fully homomorphic scheme under the technical definition of compactness. Yet, this means that ciphertexts are exponentially big in (e.g., if , we are talking about ciphertexts with bits). I am not convinced these should be called “compact”.

The second tweak implies that a computationally unbound attacker’s chance of breaking the scheme approaches zero as approaches infinity. There simply aren’t enough equations to recover . Hence, at the cost of making the scheme exceptionally short-lived it is information theoretic secure (asymptotically).

Linear Algebra for Gröbner Bases over GF(2): M4RI

Two days ago I wrote about LELA’s implementation of Gaussian elimination for Gröbner basis computations over $\mathbb{F}_2$ . Yesterday, I implemented LELA’s algorithm (which is from Faugere & Lachartre paper) in M4RI. Continue reading “Linear Algebra for Gröbner Bases over GF(2): M4RI” →

Linear Algebra for Gröbner Bases over GF(2): LELA

The Efficient Linear Algebra for Gröbner Basis Computations workshop in Kaiserslautern two weeks ago was a welcome opportunity to finally test out LELA, a library specifically written for linear algebra for Gröbner basis computations including for GF(2). The library implements the “Faugère-Lachartre” algorithm (a similar trick, though less developed, appeared before in PolyBoRi) and uses M4RI for dense parts over GF(2).

So, I ran my benchmark matrices through LELA, discovered a bug in the process, then Bradford returned the favour and discovered a bug in M4RI … Finally, below are the timings. The column PLE is the PLE algorithm as implemented in M4RI, M4RI is the M4RI algorithm as implemented in M4RI, GB is a very naive variant of the algorithm LELA uses and LELA is, well, LELA.

problem	m	n	density	PLE	M4RI	GB	LELA
HFE 25	12307	13508	0.076	1.0	0.5	0.8	0.56
HFE 30	19907	29323	0.067	4.7	2.7	4.7	3.42
HFE 35	29969	55800	0.059	19.3	9.2	19.5	13.92
Mutant	26075	26407	0.184	5.7	3.9	2.1	12.07
n=24, m=26	37587	38483	0.038	20.6	21.0	19.3	7.72
n=24, m=26	37576	32288	0.040	18.6	28.4	17.0	4.09
SR(2,2,2,4) c	5640	14297	0.003	0.4	0.2	0.1	0.40
SR(2,2,2,4) c	13665	17394	0.013	2.1	3.0	2.0	1.78
SR(2,2,2,4) c	11606	16282	0.035	1.9	4.4	1.5	0.81
SR(2,2,2,4)	13067	17511	0.008	1.9	2.0	1.3	1.45
SR(2,2,2,4)	12058	16662	0.015	1.5	1.9	1.6	1.01
SR(2,2,2,4)	115834	118589	0.003	528.2	578.5	522.9	48.39

What this table means is that one can expect more than an order of magnitude of speed-up when using LELA – which is dedicated to these computations – instead of M4RI – which does not have the specialised algorithm implemented yet. For very small matrices sometimes M4RI/PLE win, but then not by a large margin. The only row where LELA doesn’t do so good is Mutant, which – btw. – is not an F4 matrix but comes from the MXL2 algorithm. It is possible that LELA’s sparse data structures are not that well equipped to deal with this rather dense matrix.

I am in the process of implementing the algorithm LELA uses in M4RI and will report updated timings here.

Call for Papers: 3nd International Conference on Symbolic Computation and Cryptography

CIEM – Castro Urdiales, Spain, 11-13 July 2012, http://scc2012.unican.es/

CALL FOR PAPERS

IMPORTANT DATES

Deadline for submission: April 28, 2012
Notification of acceptance or rejection: May 18, 2012
Deadline for final version: May 30, 2012
Deadline for registration: June 12, 2012
Deadline for special issue JSC: September 30, 2012

SCC 2012 is the third edition of a new series of conferences where research and development in symbolic computation and cryptography may be presented and discussed. It is organized in response to the growing interest in applying and developing methods, techniques, and software tools of symbolic computation for cryptography. The use of Lattice Reduction algorithms in cryptology and the application of Groebner bases in the context of algebraic attacks are typical examples of explored applications. The SCC 2012 conference is co-located with third Workshop on Mathematical Cryptology (WMC 2012, http://wmc2012.unican.es/) , an event also organized by research group Algorithmic Mathematics And Cryptography (AMAC), which will be held on 9-11 July 2012.

Continue reading “Call for Papers: 3nd International Conference on Symbolic Computation and Cryptography” →

Summer School on Tools :: Mykonos, Greece :: 28.5 – 1.6.

Slightly redacted announcement for the 2012 Summer School on Tools below.

Following the success of the ECRYPT Workshop on Tools for Cryptanalysis 2010,the ECRYPT II Symmetric Techniques Virtual Lab (SymLab) is pleased to announce the 2012 Summer School on Tools. Covering selected topics in both symmetric and asymmetric cryptography, this summer school will provide a thorough overview of some of the most important cryptographic tools that emerged in recent years. While the summer school is aimed primarily at postgraduate students, attendance is open to all. Continue reading “Summer School on Tools :: Mykonos, Greece :: 28.5 – 1.6.” →

SymbolicData

Sage has many optional packages, about 50 actually. However, it is not necessarily well known what some of these do. For example, recently William asked me to fix some issue in the optional database_symbolic_data (still needing review btw. hint hint) package which bought it back to my attention. Shortly after, Burcin mentioned to me that he spent considerable time copy’n’pasting some standard ideals from some package to Sage’s input format. Time which he probably wouldn’t have spent if he’d known about the SymbolicData.org database and it’s Sage interface. Here’s in it action: Continue reading “SymbolicData” →

Ring-LWE and the GB(N) Problem

Over at the Bristol Cryptography Blog Martijn Stam writes about our “Polly Cracker, Revisted” paper:

We did not discuss the paper in great detail, but Jake did mention one interesting avenue for continued research. Given that this new approach allows one to cast both LWE and approximate GCD in the same framework, can one also capture ring-LWE. If so, this might enable a better comparison of the various fully homomorphic encryption (FHE) schemes out there. The hope expressed by Jake was that this might allow a reduction to standard LWE (for the current batch of ring-LWE schemes), which would boost our confidence in those schemes.

This motivated me to express the Ring-LWE problem in a language of Gröbner bases, here’s what I could come up with so far. Continue reading “Ring-LWE and the GB(N) Problem” →

Challenge matrices

Now, that we have a decent PNG reader/writer in M4RI, it’s much easier to get some challenge matrices out of the library. Below, I list and link a few such matrices as they appear during Gröbner basis computations.

file	matrix dimensions	density	PLE	M4RI	GB
HFE 25 matrix 5 (5.1M)	12307 x 13508	0.07600	1.03	0.59	0.81
HFE 30 matrix 5 (16M)	19907 x 29323	0.06731	4.79	2.70	4.76
HFE 35 matrix 5 (37M)	29969 x 55800	0.05949	19.33	9.28	19.51
Mutant matrix (39M)	26075 x 26407	0.18497	5.71	3.98	2.10
random n=24, m=26 matrix 3 (30M)	37587 x 38483	0.03832	20.69	21.08	19.36
random n=24_ m=26 matrix 4 (24M)	37576 x 32288	0.04073	18.65	28.44	17.05
SR(2,2,2,4) compressed, matrix 2 (328K)	5640 x 14297	0.00333	0.40	0.29	0.18
SR(2,2,2,4) compressed, matrix 4 (2.4M)	13665 x 17394	0.01376	2.18	3.04	2.04
SR(2,2,2,4) compressed, matrix 5 (2.8M)	11606 x 16282	0.03532	1.94	4.46	1.59
SR(2,2,2,4) matrix 6 (1.4M)	13067 x 17511	0.00892	1.90	2.09	1.38
SR(2,2,2,4) matrix 7 (1.7M)	12058 x 16662	0.01536	1.53	1.93	1.66
SR(2,2,2,4) matrix 9 (36M)	115834 x 118589	0.00376	528.21	578.54	522.98

The first three rows are from GB computations for the hidden field equations cryptosystem (those matrices were provided by Michael Brickenstein). The “mutant” row is a matrix as it appears during a run of the MXL2 algorithm on a random system (I believe). It was contributed by Wael Said. The rows “random n=25,m=26” are matrices as they appear during a GB computation with PolyBoRi for a random system of equations in 24 variables and 26 equations. The remaining rows are matrices from PolyBoRi computations on small scale AES instances. Those rows which have “compressed” in their description correspond to systems where “linear variables” were eliminate before running the Gröbner basis algorithm.

The last three columns give running times (quite rough ones!) for computing an echelon form (not reduced) using (a) the M4RI algorithm, (b) PLE decomposition and (c) a first implementation of the TRSM for trivial pivots trick. As you can see, currently it’s not straight-forward to pick which strategy to use to eliminate matrices appearing during Gröbner basis computations: the best algorithm to pick varies between different problems and the differences can be dramatic.

Chen & Nguyen’s algorithm and Arora & Ge’s algorithm

In Faster Algorithms for Approximate Common Divisors: Breaking Fully-Homomorphic-Encryption Challenges over the Integers Yuanmi Chen and Phong Q. Nguyen (preprint here) propose a new algorithm for solving the approximate GCD problem. It drops the complexity from $2^{2\rho}$ to $2^{3/2\rho}$ in the general case and from $2^{\rho}$ to $2^{\rho/2}$ in the partial case (one multiple of $p$ is given noise-free) which is a pretty big deal.

The algorithm is based on two key ideas (explained using the partial approximate GCD problem):

1. Noisy solving reduced to noise-free solving

Similar to Arora & Ge’s algorithm for solving LWE Chen and Nguyen reduce the approximate solving problem to a noise-free solving problem. In fact, the strategy is exactly the same (cf. also this post). Given noisy ideal elements $f_i = \sum h_i g_i + r_i$ where $g_i$ are generators of the ideal, $h_i$ are ring elements and $r_i$ are small noise terms, then

$F_i = f_i \cdot \prod (f_i + j)(f_i - j)$

will be elements of the ideal $I$ spanned by $g_i$ if $j$ is big enough (depending on the exact setup we may drop the $-j$ part). In the approximate GCD case $g_0$ is simply a small odd integer (often denoted $p$ ). Additionally, if we are given some sufficient “description” of some sufficiently big ideal $\langle G_1,\dots,G_s \rangle = J \supset I$ (i.e., all elements of $I$ are in $J$ but not vice versa and $J$ is considerably bigger than $I$ ) then we can compute

$F_i = f_i \cdot \prod (f_i + j)(f_i - j) \mod J$

which keeps the size of $F_i$ small-ish. This is the role of $x_0$ , the noise free multiple of $p$ in the partial approximate GCD problem. Now, one simply solves the noise free system $F_1,\dots,F_m$ . In the PAGCD case this means to compute a single GCD, in the multivariate polynomial case (including LWE) this means to compute a Gröbner basis (or linearise, which is the same thing for the cases we are concerned with). Hence, so far Arora&Ge and Chen&Nguyen are really the same thing (it should be mentioned that this ideal due to Nguyen was already mentioned in this paper) applied to different rings.

However, this is not really why the Chen & Nguyen algorithm is efficient (although this already provides a speed-up by a factor of 5).

2. Efficient multiplication

The key idea to drop the exponent from $2^{\rho}$ to $2^{\rho/2}$ is as follows. Instead of computing with integers we compute univariate polynomials mod $x_0$ , i.e. one defines

$f_j(x) = \prod_{j=0}^{j-1} (x_1 - (x + i)) \in \mathbb{F}_{x_0}[x]$

and notices that for $\rho' = \lfloor \rho/2 \rfloor$ :

$\prod_{i=0}^{2^\rho-1} (x_1 - i) = \prod_{k=0}^{2^{\rho - \rho'} -1} f_{2^{\rho'}}(2^{\rho'}k)$

i.e., we can reduce $2^\rho -1$ multiplications to $2^{\rho - \rho'} - 1$ multiplications and $2^{\rho - \rho'} - 1$ polynomial evaluations. It turns out, this can be done in $\mathcal{O}(2^{\rho'})$ . For the details read the paper.

But to get back to my previous point: It turns out the Arora&Ge perspective on noisy system solving is also useful for approximate GCDs. Which provides further evidence that it is useful to generalise LWE and AGCD to ideal theoretic problems in multivariate polynomial rings.