Skip to content

Virtual FPLLL Days 6 aka Bounded Distance Development

Jump to bottom Edit New page
Jianwei Li RHUL edited this page Nov 23, 2020 · 36 revisions

Dates

19 and 20 November 2020

Format

We are going to coordinate using https://fplll-days-6.zulipchat.com/

The rest is TBD.

Schedule

We'll meet Thursday, at

  • 9:00 London time
  • 10:00 Amsterdam time
  • 17:00 Beijing time

just for everybody to say “hi”. We'll post a link where to meet on the Zulip.

We'll meet again on Friday, at 9:00 London time, 10:00 Amsterdam time, 17:00 Beijing time to catch up.

We might have an "afterparty" on Friday evening, depending on appetite for it during the event,

Projects

Add project ideas here

DONE: Resolved old tickets

Fplll had some outstanding issues that needed resolving and/or investigating. These primarily concerned documentation for what fplll errors meant and how to resolve them.

In particular issues #244 and #448 were resolved (Joe) with a further PR open for issue #190. Preliminary investigations were made in numerical stability issues cf. issue #430 and examples for fplll (cf. #235 and #443), but these are not yet finished.

DONE: CI

Revisit how we're doing CI. Should we switch to GitHub actions? Should we support more platforms?

A. In an effort to ensure that all of our users - whether you build open-source, public or private repositories - receive regular feature updates, security patches and UX/UI enhancements, we are announcing that travis-ci.org will be officially closed down completely no later than December 31st, 2020, allowing us to focus all our efforts on bringing new features and fixes to travis-ci.com and all of our awesome users like yourself on the travis-ci.com domain.

https://docs.travis-ci.com/user/migrate/open-source-repository-migration/#frequently-asked-questions

See

Triage Tickets

Friendlier G6K: BKZ

G6K could do with a higher-level BKZ calling point.

Friendlier FP(y)LLL: SVP/CVP

Calling CVP.closest_vector is usually the last thing you want to do if you want your answer quickly. Make it do the right thing™

Friendlier FP(y)LLL: BDD

I've written about 50 versions of something akin to BDD.closest_vector by reducing to uSVP. Something like this should be available in FPyLLL (using the ADSP16 success condition).

Better Sage Integration: Faster Defaults

Sage requires proof=True to enable the fast, good stuff for BKZ. That won't change, but we could preprocess with proof=False first to make the final provably correct run cheaper.

DONE: Better Sage Integration: Balanced lifting of integers mod q

Turns out this was in Sage all along under the name lift_centered().

Add something like this to ZZ.lift(), matrix(ZZ).lift() and vector(ZZ).lift()

def balanced_lift(e):
    """
    Lift e mod q to integer such that result is between -q/2 and q/2

    :param e: a value or vector mod q

    """
    from sage.rings.finite_rings.integer_mod import is_IntegerMod

    q = e.base_ring().order()
    if is_IntegerMod(e):
        e = ZZ(e)
        if e > q//2:
            e -= q
        return e
    else:
        return vector(balanced_lift(ee) for ee in e)

Lattice Enumeration using Cuda

Review https://github.com/fplll/fplll/pull/447

Gram-BKZ for Sage

On the accuracy in implementing BKZ simulators

[Li20] presented a new and simpler heuristic BKZ simulator based on dynamical systems, namely a heuristic version of Eq. (43) of [LiNg20]. It is simpler than but equivalent to Chen-Nguyen's heuristic BKZ simulator (which matches well with experiments) [CN11]. Importantly, [Li20]'s simulator does not need to update intermediate GSOs during the simulation process. Experimentally, both simulators exhibit almost the same evolution of RHF with number of tours, provided that the blocksize $\beta$ is reasonably far from the rank $n$ of input lattice. The simulator in [Li20] has no loss of accuracy in implementation, but which seems to occur in Chen-Nguyen's simulator when $\beta$ is close to $n$.

Question: Whether is there the same accuracy issue in implementing Bai-Stehl'{e}-Wen BKZ simulator [BSW18] when $\beta$ is close to $n$? If yes, how to improve Bai-Stehl'{e}-Wen BKZ simulator?

The answer is no, based on Fernando Virdia's implementation of the Bai-Stehl'{e}-Wen BKZ simulator, and FPyLLL's implementation of the Chen-Nguyen's BKZ simulator. This fact is double-checked by Shi Bai's test. There should be some bugs in the code of Chen-Nguyen's BKZ simulator provided in [Li20].

[Li20] Jianwei Li. https://github.com/lijianweithu/A-new-and-simpler-BKZ-simulator. 2020.

[LiNg20] Jianwei Li and Phong Q. Nguyen. A Complete Analysis of the BKZ Lattice Reduction Algorithm. https://eprint.iacr.org/2020/1237.pdf. 2020.

[CN11] Yuanmi Chen and Phong Q. Nguyen. BKZ 2.0: better lattice security estimates. ASIACRYPT 2011.

[BSW18] Shi Bai, Damien Stehl'{e} and Weiqiang Wen. Measuring, simulating and exploiting the head concavity phenomenon in BKZ. ASIACRYPT 2018.

BDGL sieve for G6K

Implement the asymptotic fastest sieve [1] in G6K.

[1] Anja Becker, Léo Ducas, Nicolas Gama, Thijs Laarhoven, New directions in nearest neighbor searching with applications to lattice sieving, 2016.

Attending

Please sign up on Zulip and add your name and time zone below. If you don't have edit rights here, send an e-mail to the organiser (Martin Albrecht)

  • Martin R. Albrecht GMT
  • Joe Rowell, GMT
  • Léo Ducas, GMT+1 (Amsterdam)
  • Marc Stevens, GMT+1 (Amsterdam)
  • Wessel van Woerden, GMT+1 (Amsterdam)
  • Shi Bai, GMT+8 (Beijing)
  • Emmanouil Doulgerakis, GMT+1
  • Fernando Virdia, GMT
  • Jens Zumbragel, GMT+1
  • Simon Pohmann, GMT+1
  • Jianwei Li, GMT
  • Joël Felderhoff, GTM+1 (Lyon)

Organisers

  • Martin R. Albrecht
  • Léo Ducas
Add a custom footer
Add a custom sidebar
Clone this wiki locally