Revisiting the Expected Cost of Solving uSVP and Applications to LWE

Our — together with Florian Göpfert, Fernando Virdia and Thomas Wunderer — paper Revisiting the Expected Cost of Solving uSVP and Applications to LWE is now available on ePrint. Here’s the abstract:

Reducing the Learning with Errors problem (LWE) to the Unique-SVP problem and then applying lattice reduction is a commonly relied-upon strategy for estimating the cost of solving LWE-based constructions. In the literature, two different conditions are formulated under which this strategy is successful. One, widely used, going back to Gama & Nguyen’s work on predicting lattice reduction (Eurocrypt 2008) and the other recently outlined by Alkim et al. (USENIX 2016). Since these two estimates predict significantly different costs for solving LWE parameter sets from the literature, we revisit the Unique-SVP strategy. We present empirical evidence from lattice-reduction experiments exhibiting a behaviour in line with the latter estimate. However, we also observe that in some situations lattice-reduction behaves somewhat better than expected from Alkim et al.’s work and explain this behaviour under standard assumptions. Finally, we show that the security estimates of some LWE-based constructions from the literature need to be revised and give refined expected solving costs.

Our work is essentially concerned with spelling out in more detail and experimentally verifying a prediction made in the New Hope paper on when lattice reduction successfully recovers an unusually short vector.

Denoting by v the unusually short vector in some lattice \Lambda of dimension d (say, derived from some LWE instance using Kannan’s embedding), \beta the block size used for the BKZ algorithm and \delta_0 the root-Hermite factor for \beta, then the New Hope paper predicts that v can be found if

\sqrt{\beta/d} \|v\| \leq \delta_0^{2\beta-d} \, {\mathrm{Vol}(\Lambda)}^{1/d},

under the assumption that the Geometric Series Assumption holds (until a projection of the unusually short vector is found).

The rationale is that this condition ensures that the projection of v orthogonally to the first d-\beta (Gram-Schmidt) vectors (denoted as \pi_{d-\beta+1}(v)) is shorter than the expectation for the d-\beta+1-th Gram-Schmidt vector b_{d-\beta+1}^* under the GSA and thus would be found by the SVP oracle when called on the last block of size \beta. Hence, for any \beta satisfying the above inequality, the actual behaviour would deviate from that predicted by the GSA. Finally, the argument can be completed by appealing to the intuition that a deviation from expected behaviour on random instances — such as the GSA — leads to a revelation of the underlying structural, secret information. In any event, such a deviation would already solve Decision-LWE.

In our work, we spell out this argument in more detail (e.g. how v is recovered from \pi_{d-\beta+1}(v)) and throw 23k core hours at the problem of checking if the predicted behaviour, e.g.

prediction.png

matches the observed behaviour, e.g.

observation.png

Just like for the above plots, the general answer is a clear “yes”.

Pretty Pictures or GTFO

I forgot the most important bit. The behaviour of the BKZ algorithm on uSVP(-BDD) instances can be observed in this video.

You can observe the basis approaching the GSA until the SVP oracle finds the unusually short vector \pi_{d-\beta+1}(v). From \pi_{d-\beta+1}(v), v is then immediately recovered using size reduction. The grey area is the currently worked on block. The notation in the legend isn’t consistent with the plots above or even internally (n v d), but the general idea should still be apparent. In case you’re wondering about the erratic behaviour of the tails (which occasionally goes all over the place), this is due to a bug in fpylll which has recently been fixed.

Advertisements

Adventures in Cython Templating

Fpylll makes heavy use to Cython to expose Fplll’s functionality to Python. Fplll, in turn, makes use of C++ templates. For example, double, long double, dd_real (http://crd.lbl.gov/~dhbailey/mpdist/) and mpfr_t (http://www.mpfr.org/) are supported as floating point types. While Cython supports C++ templates, we still have to generate code for all possible instantiations of the C++ templates for Python to use/call. The way I implemented these bindings is showing its limitations. For example, here’s how attribute access to the dimension of the Gram-Schmidt object looks like:

    @property
    def d(self):
        """
        Number of rows of ``B`` (dimension of the lattice).

        >>> from fpylll import IntegerMatrix, GSO, set_precision
        >>> A = IntegerMatrix(11, 11)
        >>> M = GSO.Mat(A)
        >>> M.d
        11

        """
        if self._type == gso_mpz_d:
            return self._core.mpz_d.d
        IF HAVE_LONG_DOUBLE:
            if self._type == gso_mpz_ld:
                return self._core.mpz_ld.d
        if self._type == gso_mpz_dpe:
            return self._core.mpz_dpe.d
        IF HAVE_QD:
            if self._type == gso_mpz_dd:
                return self._core.mpz_dd.d
            if self._type == gso_mpz_qd:
                return self._core.mpz_qd.d
        if self._type == gso_mpz_mpfr:
            return self._core.mpz_mpfr.d

        if self._type == gso_long_d:
            return self._core.long_d.d
        IF HAVE_LONG_DOUBLE:
            if self._type == gso_long_ld:
                return self._core.long_ld.d
        if self._type == gso_long_dpe:
            return self._core.long_dpe.d
        IF HAVE_QD:
            if self._type == gso_long_dd:
                return self._core.long_dd.d
            if self._type == gso_long_qd:
                return self._core.long_qd.d
        if self._type == gso_long_mpfr:
            return self._core.long_mpfr.d

        raise RuntimeError("MatGSO object '%s' has no core."%self)

In the code above uppercase IF and ELSE are compile-time conditionals, lowercase if and else are run-time checks. If we wanted to add Z_NR<double> to the list of supported integer types (yep, Fplll supports that), then the above Python approximation of a switch/case statement would grow by a factor 50%. The same would have to be repeated for every member function or attribute. There must be a more better way.

Continue reading “Adventures in Cython Templating”

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”

fplll 5.1 and fpylll 0.2.4dev

New versions of fplll and fpylll were released today. I’ve reproduced release notes below for greater visibility. The biggest user-visible changes for fplll are probably that

  • CVP enumeration is not experimental any more,
  • support for external enumeration libraries (go write that GPU implementation of enumeration) was added and
  • support for OSX was greatly improved.

On the fpylll side, the biggest user-visible changes are probably various API updates and a much nicer strategy/framework for gathering statistics about BKZ.

The next version of fplll will contain support for LLL reduction on Gram matrices.

Continue reading “fplll 5.1 and fpylll 0.2.4dev”

fpylll

fpylll is a Python library for performing lattice reduction on lattices over the Integers. It is based on the fplll, a C++ library which describes itself as follows:

fplll contains several algorithms on lattices that rely on floating-point computations. This includes implementations of the floating-point LLL reduction algorithm, offering different speed/guarantees ratios. It contains a ‘wrapper’ choosing the estimated best sequence of variants in order to provide a guaranteed output as fast as possible. In the case of the wrapper, the succession of variants is oblivious to the user. It also includes a rigorous floating-point implementation of the Kannan-Fincke-Pohst algorithm that finds a shortest non-zero lattice vector, and the BKZ reduction algorithm.

fplll is distributed under the GNU Lesser General Public License (either version 2.1 of the License, or, at your option, any later version) as published by the Free Software Foundation.

In short, fplll is your best bet at a publicly available fast lattice-reduction library and fpylll provides a convenient interface for it — for experimentation, development and extension — from Python.

For the rest of this post, I’ll give you a tour of the features currently implemented in fpylll and point out some areas where we could do with some help.

Continue reading “fpylll”

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.