Issues with Babai implementation in fpylll

[Huck Bennett]

Dear fp(y)lll developers,

First, thanks a lot for all of your work on this very nice tool!

This email documents two potential issues with documentation and implementation of Babai's algorithm in fpylll. I will describe them here fairly briefly, but have also attached two corresponding Python files reproducing the issues with more extensive comments.

Issue #1:

Babai's algorithm in fpylll is outputting a *coefficient vector*, not a lattice vector. This does not match the fpylll specification, which says that "[Babai returns a] lattice vector close to [the input target vector]."

In particular, fpylll outputs a coefficient vector (and not a lattice vector) in the main fpylll Babai usage example. In fact, as noted in the attached file fpylll-cvp-ex1.py, the vector output in the example is the coefficient vector of the lattice vector output by CVP.closest_vector called on the same lattice and target.

I did not trace how the fplll implementation of Babai, the core of which seems to be here, is pulled through to fpylll.

Issue #2:

I ran into what seems likely to be an overflow/precision issue when running LLL and then Babai on a "knapsack type" integer lattice with some large (presumably greater than 64-bit long) but not ridiculously large (<= 100-bit long) entries. It is not clear where the issue is coming from, but maybe from representing Gram-Schmidt vectors using floating point numbers.

I tried to use mpfr and FPLLL.set_precision to go to higher precision, but am likely not using them correctly. That said, when calling fpylll.LLL.reduction with "float_type=mpfr" and "precision=1000" I get the error message "ValueError: LLL wrapper function requires float_type==None." Whatever else I'm not doing correctly, the documentation makes it seem like this should be allowed, and this error message seems like a potential issue.

Interestingly, CVP.closest_vector works correctly when called on the same lattice and target as Babai and does not seem to have the same issues.

Best wishes,

Huck

[Martin R. Albrecht]

Hi Huck,

Thanks!

# Issue 1

This is now: https://github.com/fplll/fpylll/pull/225

# Issue 2

I think this is because I was lazy. Babai in FPyLLL is just:

cdef Py_ssize_t i, j
cdef list vv = list(v)
for i in range(dimension)[::-1]:
vv[i] = int(round(vv[i]))
for j in range(i):
vv[j] -= self.get_mu(start+i, start+j) * vv[i]
return tuple(vv)

which dumbs everything down to a machine float. Can you open a ticket with a minimal failing example?

Cheers,
Martin

On Mon, May 02 2022, Huck Bennett wrote:
> Dear fp(y)lll developers,
>
> First, thanks a lot for all of your work on this very nice tool!
>
> This email documents two potential issues with documentation and
> implementation of Babai's algorithm in fpylll. I will describe them here
> fairly briefly, but have also attached two corresponding Python files
> reproducing the issues with more extensive comments.
>

> *Issue #1:*

> Babai's algorithm in fpylll is outputting a *coefficient vector*, not a
> lattice vector. This does not match the fpylll specification

> <https://buildmedia.readthedocs.org/media/pdf/fpylll/latest/fpylll.pdf>,

> which says that "[Babai returns a] lattice vector close to [the input
> target vector]."
>
> In particular, fpylll outputs a coefficient vector (and not a lattice
> vector) in the main fpylll Babai usage example

> <https://github.com/fplll/fpylll/blob/master/docs/tutorial.rst#svp-and-cvp-tools>.

> In fact, as noted in the attached file fpylll-cvp-ex1.py, the vector output
> in the example is the coefficient vector of the lattice vector output
> by CVP.closest_vector called on the same lattice and target.
>
> I did not trace how the fplll implementation of Babai, the core of which
> seems to be here

> <https://github.com/fplll/fplll/blob/37bcab0caf510dd7ad49d8a3b277366d7b8b763a/fplll/svpcvp.cpp#L517>,

> is pulled through to fpylll.
>

> *Issue #2:*

> I ran into what seems likely to be an overflow/precision issue when running
> LLL and then Babai on a "knapsack type" integer lattice with some large
> (presumably greater than 64-bit long) but not ridiculously large (<=
> 100-bit long) entries. It is not clear where the issue is coming from, but
> maybe from representing Gram-Schmidt vectors using floating point numbers.
>
> I tried to use mpfr and FPLLL.set_precision to go to higher precision, but
> am likely not using them correctly. That said, when calling
> fpylll.LLL.reduction with "float_type=mpfr" and "precision=1000" I get the
> error message "ValueError: LLL wrapper function requires float_type==None."
> Whatever else I'm not doing correctly, the documentation makes it seem like
> this should be allowed, and this error message seems like a potential issue.

> Interestingly, CVP.closest_vector works correctly when called on the same
> lattice and target as Babai and does not seem to have the same issues.
>
> Best wishes,
> Huck

--

_pgp: https://keybase.io/martinralbrecht
_www: https://malb.io
_prn: he/him or they/them

[Joe Rowell]

Hi Martin, Huck, all,

It might be worth revisiting pushing/exposing an explicit implementation of Babai in fplll: there is an implementation, but it isn't exposed upwards to fpylll.

I appreciate this is tantamount to saying "let's add another load of type checks" as in [0]: I'll have a think to see if I can think of a neater way to

expose what we need from the C++ side in general.

Cheers,

Joe

[0] https://martinralbrecht.wordpress.com/2017/07/23/adventures-in-cython-templating/

--
You received this message because you are subscribed to the Google Groups "fplll-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email to fplll-devel...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/fplll-devel/87ee181596.fsf%40googlemail.com.

[Huck Bennett]

Hi Martin and Joe,

Thanks for the response!

> Babai in FPyLLL is just:

> cdef Py_ssize_t i, j
> cdef list vv = list(v)
> for i in range(dimension)[::-1]:
> vv[i] = int(round(vv[i]))
> for j in range(i):
> vv[j] -= self.get_mu(start+i, start+j) * vv[i]
> return tuple(vv)

Ah! I totally missed that fpylll had a Babai implementation apart from fplll's. I like Joe's idea about exposing fplll's implementation to fpylll. It's of course not for me to call the shots on this, but not replicating core, back-end functionality certainly makes sense from a software engineering standpoint.

> Can you open a ticket with a minimal failing example?

Done. Maybe there's a minimal-er example, but the one I submitted on GitHub is quite simple. It basically shows that running Babai on a knapsack lattice with random 100-bit knapsack values doesn't work.

I'm apparently a GitHub newbie, but I'm amazed that they don't let you attach code files when you open issues. So, I attached the example in a text file there and am attaching the code as a Python file here.

Best,

Huck

[Martin R. Albrecht]

Hi all,

I’ve implemented a simple full precision Babai now:

# FPLLL

code is here: https://github.com/fplll/fplll/pull/492

I suspect both my C++ and my control of precision is naive. Thus, if people more familiar with either could take a quick look, that’d be fab. In particular, the internal Babai implementations in FPLLL seem more complex but I didn’t want to mess with those.

# FPyLLL

interface code here: https://github.com/fplll/fpylll/pull/236

While implementing this I noticed various FP shortcomings in FPLLL.

- Running with qd_real will have lower precision compared to dd_real, see

https://github.com/fplll/fplll/blob/gso-babai/tests/test_babai.cpp#L93

- ZT=long + FT=mpfr will not work
- FT=dpe seems also broken

See commented out blocks here https://github.com/fplll/fpylll/blob/gso-babai/src/fpylll/fplll/gso.pyx#L2295

I started collecting these here: https://github.com/fplll/fplll/issues/493

If combinations are not meant to work (e.g. ZT=long + FT=mpfr?) then we should throw an error.

Cheers,
Martin