Tag: gröbner basis

Three sweet but short postdocs in France

The HPAC project has three one-year postdoc positions available:

Three research positions (postdoc or research engineer), offered by the French ANR project HPAC  (High Performance Algebraic Computation), are open.

Title: High Performance Algebraic Computing

Keywords: parallel computing, computer algebra, linear algebra, C/C++ programming

Locations:

  • Grenoble, France (LIG-MOAIS, LJK-CASYS),
  • Lyon, France (LIP-AriC),
  • Paris, France (LIP6-PolSys),

Starting date: between June 2014 and January 2015

Type of position: 3 postdoc or research engineer positions of 1 year each

Detailed descriptions:

General Context:

The ambition of the project HPAC is to provide international reference high-performance libraries for exact linear algebra and algebraic systems on multi-processor architectures and to influence parallel programming approaches for algebraic computing. It focuses on the design of new parallel algorithms and building blocks dedicated to exact linear algebra routines. These blocks will then be used for the parallelization of the sequential code of the LinBox and FGb libraries, state of the art for exact linear algebra and polynomial systems solving, and used in many computer algebra systems. The project combines several areas of expertise: parallel runtime and language, exact,
symbolic and symbolic/numeric algorithmic, and software engineering.

Profile of the positions:

We are seeking for candidates with solid expertise in software library design and developments (e.g. C, C++, OpenMP, Autotools, versioning,…) with preferably good background on mathematical software and computer algebra algorithmic. The main outcome of the work will depend on the type of the position (postdoc or engineer) and include code development in open-source C/C++ libraries such as LinBox, FGb, Kaapi and research publications in international journals or conferences.

Each location is seeking for candidates matching with the following keywords:

  • Lyon: (contact: Gilles….@ens-lyon.fr) High performance/parallel computer algebra, symbolic and mixed symbolic-numeric linear algebra,  validated computation, high performance Euclidean lattice computation, lattice basis reduction.
  • Grenoble: (contact: Jean-Guill…@imag.fr) Library design and development, LinBox, Sage, XKaapi, parallel exact linear algebra, work-stealing and data-flow tasks.
  • Paris: (contact: Jean-Charl…@groebner.org) Polynomial system solving, Gröbner basis computations, parallel exact linear algebra, algebraic cryptanalysis, distributed computing.

Feel free to exchange with the contact person of each site for further information.

libFES : Fast Exhaustive Search for Polynomial Systems over F2

Charles Bouillaguet set up a nice shiny website for libFES the library for exhaustive search on polynomial systems over \mathbb{F}_2. The library has a Sage interface, so it’s easy to get started. It’s also integrated in Charles’ upcoming one-stop boolean system solving patch.

He calls his benchmarketing “bragging rights” … and boy has he earned those rights! Check it out, libFES is fast!

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:

  1. 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).
  2. 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): 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.

Report: Workshop on Efficient Linear Algebra for Gröbner Basis Computations

As you may know, today is the last day of the wokshop on Efficient Linear Algebra for Gröbner Basis Computations that Christian Eder, Burcin Eröcal, Alexander Dreyer and I organised.

I have to say that I am quite pleased with how the workshop played out. We planned the whole thing to be hands on: people were strongly encouraged to work on projects, i.e., to write code preferably together, in addition to attending talks. Those who attended a Sage Days workshop in the past, will know what workshop format I am referring to. Continue reading “Report: Workshop on Efficient Linear Algebra for Gröbner Basis Computations” →

Efficient Linear Algebra for Gröbner Basis Computations – June 4-8, 2012 – Kaiserslautern, Germany

Linear algebra plays an important role in modern efficient implementations of Gröbner basis algorithms. Consequently, a number of groups aim at developing linear algebra packages for these computations: we mention the HPAC project, LELA by the Singular team, the FGB package by Jean-Charles Faugère, the M4RI libraries, specialised linear algebra routines in PolyBoRi as well as non-public projects. In this workshop we want to bring researchers interested in this problem and developers of these packages together to discuss and develop solutions. The format of this workshop will be a mixture of talks, coding sprints and design discussions.

Topics will include but are not limited to:

  • presentation of existing software packages and solutions for linear algebra suitable for Gröbner basis computations
  • presentation of scientific results on linear algebra for Gröbner basis computations
  • modular approaches to Gröbner basis computations which allow to swap linear algebra packages
  • approaches to parallelization of linear algebra routines on multicore machines, multiple machines and GPUs.
  • suitable benchmark and test matrices, ideals and their format.

Invited Speakers

  • Brice Boyer (Grenoble, France)
  • Michael Brickenstein (Oberwolfach, Germany)
  • Daniel Cabarcas (Darmstadt, Germany)
  • Jean-Charles Faugère (Paris, France)
  • Bradford Hovinen (Munich, Germany)
  • Sylvain Lachartre (Paris, France)
  • Emmanuel Thomé (Nancy, France)

The workshop will feature mathematical talks, presentations on software and coding sprints.

Registration

There is no registration fee for the workshop. Please email the organizers beforehand if you intend to participate.

It is strongly recommended that participants bring their own laptop for use during the coding sprints.

More information regarding this event is available at http://wiki.lmona.de/events/elagb