Tag: sage

Fplll Days 3: July 6 – 14, Amsterdam

We’ll have an fplll coding sprint aka “FPLLL Days” in July. This time around, we plan a slightly modified format compared to previous instances. That is, in order to encourage new developers to get involved, we plan to have a 2 day tutorial session (shorter or longer depending on participants/interest) before the start of FPLLL Days proper.

Continue reading “Fplll Days 3: July 6 – 14, Amsterdam” →

On dual lattice attacks against small-secret LWE and parameter choices in HElib and SEAL

My paper on solving small, sparse secret instances is now on ePrint. Here’s the abstract:

We present novel variants of the dual-lattice attack against LWE in the presence of an unusually short secret. These variants are informed by recent progress in BKW-style algorithms for solving LWE. Applying them to parameter sets suggested by the homomorphic encryption libraries HElib and SEAL yields revised security estimates. Our techniques scale the exponent of the dual-lattice attack by a factor of (2\,L)/(2\,L+1) when \log q = \Theta{\left(L \log n\right)}, when the secret has constant hamming weight h and where L is the maximum depth of supported circuits. They also allow to half the dimension of the lattice under consideration at a multiplicative cost of 2^{h} operations. Moreover, our techniques yield revised concrete security estimates. For example, both libraries promise 80 bits of security for LWE instances with n=1024 and \log_2 q \approx {47}, while the techniques described in this work lead to estimated costs of 68 bits (SEAL) and 62 bits (HElib).

If you want to see what its effect would be on your favourite small, sparse secret instance of LWE, the code for estimating the running time is included in our LWE estimator. The integration into the main function estimate_lwe is imperfect, though. To get you started, here’s the code used to produce the estimates for the rolling example in the paper.

  • Our instance’s secret has hamming weight h=64 and a ternary secret. We always use sieving as the SVP oracle in BKZ: 

    sage: n, alpha, q = fhe_params(n=2048, L=2)
sage: kwds = {"optimisation_target": "sieve", "h":64, "secret_bounds":(-1,1)}

  • We establish a base line: 

    sage: print cost_str(sis(n, alpha, q, optimisation_target="sieve"))

  • We run the scaled normal form approach from Section 4 and enable amortising costs from Section 3 by setting use_lll=True: 

    sage: print cost_str(sis_small_secret_mod_switch(n, alpha, q, use_lll=True, **kwds))

  • We run the approach from Section 5 for sparse secrets. Setting postprocess=True enables the search for solutions \mathbf{s}_1 with very low hamming weight (page 17): 

    sage: print cost_str(drop_and_solve(sis, n, alpha, q, postprocess=True, **kwds))

  • We combine everything: 

    sage: f = sis_small_secret_mod_switch
sage: print cost_str(drop_and_solve(f, n, alpha, q, postprocess=True, **kwds))

GSW13: 3rd Generation Homomorphic Encryption from Learning with Errors

This week our reading group studied Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based by Craig Gentry, Amit Sahai and Brent Waters: a 3rd generation fully homomorphic encryption scheme.

The paper is partly motivated by that multiplication in previous schemes was complicated or at least not natural. Let’s take the BGV scheme where ciphertexts are simply LWE samples a_i, b_i = -\langle a_i, s\rangle + \mu_i \cdot \lceil q/2\rfloor + e_i for a_i \in \mathbb{Z}_q^n and b_i \in \mathbb{Z}_q with \mu_i being the message bit \in \{0,1\} and e_i is some “small” error. Let’s write this as c_i = (a_i, b_i) \in \mathbb{Z}_q^{n+1} because it simplifies some notation down the line. In this notation, multiplication can be accomplished by c_1 \otimes c_2 because \langle c_1 \otimes c_2, s \otimes s\rangle \approx \mu_1 \cdot \mu_2. However, we now need to map s \otimes s back to s using “relinearisation”, this is the “unnatural” step.

However, this is only unnatural in this particular representation. To see this, let’s rewrite a_i, b_i as a linear multivariate polynomial f_i = b_i - \sum_{j=1}^n a_{ij} \cdot x_j \in \mathbb{Z}_q[x_1,\dots,x_n]. This polynomial evaluates to \approx \mu on the secret s = (s_1,\dots,s_n). Note that evaluating a polynomial on s is the same as reducing it modulo the set of polynomials G = (x_1 - s_1,\dots, x_n - s_n).

Continue reading “GSW13: 3rd Generation Homomorphic Encryption from Learning with Errors” →

fplll days 1

We’ll have a first fplll coding sprint aka “fplll days” from June 20 to June 24 at ENS Lyon.

The idea of fplll days is inspired by and might follow the format of Sage Days which are semi-regularly organised by the SageMath community. The idea is simply to get a bunch of motivated developers in a room to work on code. Judging from experience in the SageMath community, lots of interesting projects get started and completed.

We intend to combine the coding sprint with the lattice meeting (to be confirmed), so we’d be looking at 3 days of coding plus 2 days of regular lattice meeting. We might organise one talk per coding day, to give people a reason to gather at a given time of the day, but the focus would be very much on working on fplll together.

If you’d like to attend, please send an e-mail to one of the maintainers e.g. me.

Cysignals

If you’ve written a fair amount of Cython code in your time, chances are that you got frustrated by

  1. buggy C/C++ code crashing your Python shell and
  2. the fact that you cannot interrupt C/C++ functions.

For example, the following Cython code cannot be interrupted: 

while True:
    pass

On the other hand, if you have written Cython code in Sage, then you might have come across its nifty sig_on(), sig_off() and sig_check() macros which prevent crashes and allow your calls to C/C++ code to be interrupted. Sage had signal handling — crashes, interrupts — forever (see below).

Cysignals is Sage’s signal handling reborn as a stand-alone module, i.e. it allows to wrap C/C++ code blocks in sig_on() and sig_off() pairs which catch signals such as SIGSEGV. Using it is straight-forward. Simply add 

include "cysignals/signals.pxi"

to each Cython module and then wrap long-running computations in sig_on() / sig_off() pairs or check for signals with sig_check(). See the cysignals documentation for details.

We have a first pre-release out. Pre-release because we haven’t switched Sage to the new, stand-alone code yet. Once this is done, we’ll publish version 1.0 since some version of this code has been in use on many different systems for at least decade.

Continue reading “Cysignals” →

First CoDiMa Training School in Computational Discrete Mathematics

This winter school sounds excellent:

We have just finalised the date and location for the First CoDiMa Training School in Computational Discrete Mathematics which will take place at the University of Manchester on November 16th-20th, 2015. This school is intended for post-graduate students and researchers from UK institutions. It will start with the 2-days hands-on Software Carpentry workshop covering basic concepts and tools, including working with the command line, version control and task automation, continued with introductions to GAP and SageMath systems, and followed by the series of lectures and exercise classes on a selection of topics in computational discrete mathematics.

The School’s website and the registration details will be announced shortly. In the meantime, if you’re interested in attending, please keep the dates in your diary and check for updates on our website and on our Twitter @codima_project, or tell us about your interest writing to contact at codima.ac.uk so that we will be able to notify you when the registration will begin.

PolyBoRi is dead, it needs your help

On the Sage development list a discussion is going on what to do about PolyBoRi. For those who do not know PolyBoRi, for computing Gröbner bases for Boolean polynomials it is pretty much the only (open-source) game in town (as far as I know):

The core of PolyBoRi is a C++ library, which provides high-level data types for Boolean polynomials and monomials, exponent vectors, as well as for the underlying polynomial rings and subsets of the powerset of the Boolean variables. As a unique approach, binary decision diagrams are used as internal storage type for polynomial structures.

On top of this C++-library we provide a Python interface. This allows parsing of complex polynomial systems, as well as sophisticated and extendable strategies for Gröbner base computation. PolyBoRi features a powerful reference implementation for Gröbner basis computation.

Boolean polynomials show up a lot in cryptography and other areas of computer science.

The trouble with PolyBoRi is that both authors of PolyBoRi – Alexander Dreyer and Michael Brickenstein – left academia and have jobs now which have nothing to do with PolyBoRi. Hence, PolyBoRi is currently not maintained. This is a big problem. In particular, there are some issues with PolyBoRi which cannot be ignored forever:

  • PolyBoRi uses Python (yay) but only Python 2. At some point the world – i.e. Sage – will switch to Python 3 and PolyBoRi is the only obstacle to that switch except for the Sage Python library itself.
  • PolyBoRi uses Scons as a build system. Everybody would be a lot happier if it was switched to using autotools (which are a lot more awesome than many people realise).

In the long-term the Singular team might get involved and keep PolyBoRi alive, but this is not certain. Also, there is a push for a decision about what to do with PolyBoRi in Sage now.

The current proposal on the table is to drop PolyBoRi from the default Sage installation, i.e. to demote it to an optional package. In my mind, this would be very bad as Sage and PolyBoRi benefit from the tight integration that currently exists. Also, in my experience, optional packages tend to simply not work that well as they are not tested in each release.

Hence, if you care about PolyBoRi you should consider to

  1. let us know in the relevant thread on the mailing list if you use PolyBoRi in Sage.
  2. volunteer to help to autotool-ify PolyBoRi if you speak autotools. (If you don’t speak autotools, you should learn, they are awesome.)
  3. volunteer to help to port PolyBoRi from Python 2 to Python 3.

I’m up for getting involved, but I don’t want to take on the responsibility alone.

Update (2015-06-13): A fair share of work has already been done by Andrew. Still, anyone up for helping out?