Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Lattice Reduction Crashes with AssertionError #1

Open
bluechen8 opened this issue Jun 22, 2023 · 0 comments
Open

Lattice Reduction Crashes with AssertionError #1

bluechen8 opened this issue Jun 22, 2023 · 0 comments

Comments

@bluechen8
Copy link

bluechen8 commented Jun 22, 2023

I am trying to break Kyber 512 with the assumption of knowing several bits of s, which means that the perfect hints should be basis vector & element of s pairs. However, after hints are integrated and move on to BKZ, the program crashes. Do you know why this could happen? Is there any parameter should be adjusted?
The script I write and the error message is attached.

from lwe_with_hints import *

import numpy as np
from random import randrange

import time
import pdb

A,b,q,s,e = generateLWEInstance("Kyber512")
KYBER_N = 256
n = 512

lattice = LWELattice(A, b, q, verbose=True)

for poly_id in range(2):
    for u64_id in range(4):
        for bit_id in range(15, 48):
            global_id = bit_id + u64_id * 64 + poly_id * KYBER_N
            hint_v = np.array([0]*n)
            hint_v[global_id] = 1
            guess_value = s[global_id]
            print(f"hints -> {global_id}")
            lattice.integratePerfectHint(hint_v, guess_value)

start = time.time()
lattice.reduce()
end = time.time()

print(f"[+] Finishing -> Time consumption: {end-start}")
print(lattice.s)

count = 0
for i in range(len(s)):
    if int(s[i]) == lattice.s[i]:
        count += 1
print(f"Accuracy: {count}/{len(s)}")
```

```
Starting LLL.
Finished LLL. Time: 3736.261560s.
Starting BKZ with blocksize 2.
Traceback (most recent call last):
 File “/home/boru/project/auguryplusplus/rust/kyber_reduction.py”, line 37, in <module>
  lattice.reduce()
 File “/home/boru/project/auguryplusplus/rust/lwe_with_hints/lwe_lattice.py”, line 171, in reduce
  bkz(par)
 File “/home/boru/anaconda3/envs/kyber/lib/python3.10/site-packages/fpylll/algorithms/bkz.py”, line 118, in __call__
  clean = self.tour(params, min_row, max_row, tracer)
 File “/home/boru/anaconda3/envs/kyber/lib/python3.10/site-packages/fpylll/algorithms/bkz.py”, line 152, in tour
  clean &= self.svp_reduction(kappa, block_size, params, tracer)
 File “/home/boru/anaconda3/envs/kyber/lib/python3.10/site-packages/fpylll/algorithms/bkz2.py”, line 108, in svp_reduction
  radius, re, pruning = self.get_pruning(kappa, block_size, params, tracer)
 File “/home/boru/anaconda3/envs/kyber/lib/python3.10/site-packages/fpylll/algorithms/bkz2.py”, line 36, in get_pruning
  return radius, re, strategy.get_pruning(radius, gh_radius * 2**(ge-re))
 File “src/fpylll/fplll/bkz_param.pyx”, line 91, in fpylll.fplll.bkz_param.Strategy.get_pruning
AssertionError
```
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant