Maybe something wrong with SVP.shortest_vector?

[wbohan]

When I use the function "SVP.shortest_vector" like this:

def solve_svp(svp_basis_B):
    B = IntegerMatrix.from_matrix(svp_basis_B)
    v = list(SVP.shortest_vector(B))
    return list(B[1])

#do something
SVP_Lattice_Basis = hnp_to_svp(L_bits,EqualNum,list_Alpha[:EqualNum],list_U[:EqualNum],q)
target_vector = solve_svp(SVP_Lattice_Basis)

Error occurred like this:

AttributeError                            Traceback (most recent call last)
<ipython-input-9-345cb68ad948> in <module>
     76 
     77 SVP_Lattice_Basis = hnp_to_svp(L_bits,EqualNum,list_Alpha[:EqualNum],list_U[:EqualNum],q)
---> 78 target_vector = solve_svp(SVP_Lattice_Basis)
     79 answer = -target_vector[-Integer(2)]
     80 print(answer % q)

<ipython-input-9-345cb68ad948> in solve_svp(svp_basis_B)
     68 def solve_svp(svp_basis_B):
     69     B = IntegerMatrix.from_matrix(svp_basis_B)
---> 70     v = list(SVP.shortest_vector(B))
     71     return list(B[Integer(1)])
     72 print("[*]Start!")

src/fpylll/fplll/svpcvp.pyx in fpylll.fplll.svpcvp.shortest_vector()

src/fpylll/io.pyx in fpylll.io.SuppressStream.__init__()

AttributeError: module 'fpylll.io' has no attribute 'UnsupportedOperation'

I made a few changes to the function hvp_to_cvp,but I promise that the basis Matrix B is a IntegerMatrix and the dimension of the lattice is bigger than 20.

By the way,If I set the parameter with "pruning = None",it runs normally. The program also runs normally if the dimension of the lattice is less than 10.

I need to set pruning = True to solve a high-dimension svp problem,but I don't know how to let it runs normally. Can you help me out?Appreciate a lot!

[quchangle1]

@joerowell

[quchangle1]

@malb

[dvruette]

This is still an issue. Minimal example to reproduce:

from fpylll import LLL, IntegerMatrix, SVP
A = IntegerMatrix.from_matrix([
    [-1, -1,  0, -2,  0,  0, -1,  0,  1,  1, -1],
    [ 2,  0,  0,  0,  1,  0, -1,  1,  0,  2,  1],
    [ 0, -1, -2,  2,  0,  0,  0, -2,  2, -1, -1],
    [-1, -1, -1,  1,  1, -1,  2,  0,  2, -1,  2],
    [-1,  1, -1,  0,  1,  2, -2,  1, -1,  2, -1],
    [-1,  1, -1, -1,  0,  0,  1,  3,  0,  0, -2],
    [ 1,  0,  0,  0,  0,  1, -2,  1,  0, -3, -1],
    [-2, -2,  0,  2, -1,  0,  0,  1,  0,  2,  0],
    [-1,  3,  1,  1,  1, -2,  0,  0,  1,  1,  2],
    [-1,  1,  3,  2,  1,  1,  2,  0,  2,  0, -1],
    [ 0,  2,  1,  0, -3,  3, -1,  1,  3, -1, -1],
])
assert LLL.is_reduced(A)
SVP.shortest_vector(A, pruning=False)
SVP.shortest_vector(A)

The script fails on the last line. Definitely not the result I expect.

[malb]

I can reproduce it, odd error:

fplll: ExternalEnumeration: non-empty pruning vector dimension does not match

This shouldn't happen.

[ThomasGencee]

Hi,

do we have an update on this method ? Because I am obtaining this error :

list_of_f_List = solve_svp(svp_basis_B) File "/Users/thomasgence/Desktop/LABS/Skeleton-Files-LAB3/module_1_ECDSA_Cryptanalysis_Skel.py", line 210, in solve_svp SVP.shortest_vector(svp_basis_B) File "src/fpylll/fplll/svpcvp.pyx", line 124, in fpylll.fplll.svpcvp.shortest_vector RuntimeError: Aborted

[malb]

I just pushed a crude workaround, with that I get that

from fpylll import LLL, IntegerMatrix, SVP
d = 11
for _ in range(100):
    A = IntegerMatrix.random(d, "uniform", bits=2)
    A = LLL.reduction(A)
    print(SVP.shortest_vector(A))

and

from fpylll import LLL, IntegerMatrix, SVP
d = 21
for _ in range(100):
    A = IntegerMatrix.random(d, "uniform", bits=2)
    A = LLL.reduction(A)
    print(SVP.shortest_vector(A))

goes through. Can you test?

[malb]

Closing for now.

[s-v-grebnev]

Still an issue. Fails, for example, on this script: https://github.com/lducas/SchnorrGate

[cmiller73084]

Still an issue. Fails, for example, on this script: https://github.com/lducas/SchnorrGate

I also am encountering this error with the above repo. If I change the call to method='proved' things work fine. Only seems to affect lattice dimensions >20.

Here's a lightweight setup to a similar/identical problem as lducas/SchnorrGate.

import fpylll
from sage.all import *
import numpy as np

def sr(x):
    return np.round(x * 2**5)

num_primes = 20
bits = Integer(20)
p = random_prime(2 **(bits/Integer(2) ), false, Integer(2)**(bits/Integer(2) -Integer(1) ))
q = random_prime(2 **(bits/Integer(2) ), false, Integer(2)**(bits/Integer(2) -Integer(1) ))
N = p*q
A = np.zeros([num_primes+1,num_primes+1],dtype='int')
A[:-1,:-1] = A[:-1,:-1] + sr(N*np.diag(range(1,num_primes+1)))
primes = primes_first_n(num_primes)

A[-1,:-1] = sr(np.array(N*np.log(np.array(primes))))
A[-1,-1] = sr(np.array(N*np.log(N)))

B = fpylll.IntegerMatrix.from_matrix(A.T.tolist())
fpylll.SVP.shortest_vector(B,method='fast')