Git Product home page Git Product logo

lwe_with_hints's Introduction

LWE with Hints

An efficient Python library for attacking LWE with hints, accompanying the paper

Too Many Hints – When LLL Breaks LWE.

Requirements

We note that all required libraries ship with Sage. (However, fpylll can be very slow in Sage, when not upgrading to the latest fpylll version, see fplll/fpylll#239.)

If you want to run the library in Sage, then you have run Sage in its Python mode. For instance, to run tutorial.py in Sage, simply execute the following command:

sage --python tutorial.py

The code is written for Python 3.x / Sage 9.x.

Tutorial

Getting started

We import the library and load an LWE instance from tutorial/lwe_instance.json.

>>> from lwe_with_hints import *
>>> A,b,q = loadLWEInstanceFromFile("tutorial/lwe_instance.json")

As the following code snippet shows, our LWE instance has parameters n = 70, m = 80, q = 521.

>>> A.shape
(70,80)
>>> q
521

Let us first attack the LWE instance without hints. To this end, we create an LWELattice object and run the (progressive) BKZ lattice reduction algorithm on it.

>>> lattice = LWELattice(A,b,q)
>>> lattice.reduce()

Executing the above code should take roughly 1 - 2 minutes on a laptop.

When execution is finished, the LWE secret is stored in lattice.s.

>>> lattice.s
array([ 0,  0,  2,  1,  2, -1, -1,  0, -1,  1,  1,  1,  0,  1,  1, -3, -2,
       -2, -3, -1,  1,  1, -1,  2, -1,  0, -2,  0,  1,  0,  0,  0,  1,  0,
        1,  0,  0,  0,  0,  0,  1,  0,  0,  0, -1,  0, -1, -1, -1,  1,  1,
        1,  0,  0,  0,  0,  2,  1,  0, -1,  1, -2,  0,  0, -2,  0,  1,  0,
       -1,  0])

The shortest vector, that was recovered by lattice reduction, is stored in lattice.shortestVector.

>>> lattice.shortestVector
array([ 2, -1,  1,  1,  0, -2,  2,  2,  0, -1,  1, -1,  0,  0,  0,  0,  1,
       -2,  0, -2,  2, -3,  0, -1,  0,  0, -1, -1, -1, -1, -1,  1, -1, -2,
        2,  1,  1,  1,  0,  0, -1,  0, -1,  2,  2,  1,  0, -1,  0,  0, -1,
       -1, -1, -1, -1,  1,  1,  1,  1, -1,  1,  1,  1,  1,  0,  3,  0,  1,
        1,  0,  0, -2, -1,  0,  0,  1,  2, -2, -1,  1,  0,  0, -2, -1, -2,
        1,  1,  0,  1, -1, -1, -1,  0, -1, -1,  3,  2,  2,  3,  1, -1, -1,
        1, -2,  1,  0,  2,  0, -1,  0,  0,  0, -1,  0, -1,  0,  0,  0,  0,
        0, -1,  0,  0,  0,  1,  0,  1,  1,  1, -1, -1, -1,  0,  0,  0,  0,
       -2, -1,  0,  1, -1,  2,  0,  0,  2,  0, -1,  0,  1,  0,  1])

The BKZ blocksize, at which the LWE secret was successfully recovered, is stored in lattice.successBlocksize.

>>> lattice.successBlocksize
5

Integrating hints

Now let us attack the LWE instance again, but this time with hints.

Let us first reset the LWELattice object.

>>> lattice = LWELattice(A,b,q)

Suppose we obtain the following hints via some side channel.

  1. The first four coordinates of the LWE secret are 0, 0, 2 and 1.
  2. The inner product between the LWE secret and the following two vectors equals -1670 and 2381, respectively:
(-459, -441, 107, -207, 30, 358, -221, -483, 457, 96, 118, -241, 400, -478, 374, -46, -376, 415, 213, 476, -195, 25, -486, 444, 228, 313, -252, -182, -314, 105, -248, 163, 489, -388, 222, 110, -493, -491, 378, 213, 493, 48, 497, 138, 441, 140, 351, 135, -123, 414, -7, -344, -320, 54, 400, 230, -80, -85, -76, -475, 342, 276, 340, 1, 477, 158, -378, 146, 274, -355)
(-315, 212, 432, 236, 423, -389, 67, -313, 365, 416, -180, -121, -472, 56, -468, -234, -305, 173, 444, -348, 261, -120, 249, -466, 491, -349, -140, 49, 99, 383, -321, 127, 447, -199, 443, -89, -384, -102, -106, 253, 495, 500, 8, -354, 115, 488, -88, 471, -291, 323, 349, 68, -253, -35, 34, -175, 172, -162, 123, -266, -6, 321, 481, -116, -60, 227, 163, -24, 56, 114)
  1. The sum over all coordinates of the LWE secret is an even number.

We integrate the hints as follows. (Note: vec is simply an alias for numpy.array)

>>> n = 70
>>> v_1 = vec( [1] + [0]*(n-1) )
>>> v_2 = vec( [0] + [1] + [0]*(n-2) )
>>> v_3 = vec( [0]*2 + [1] + [0]*(n-3) )
>>> v_4 = vec( [0]*3 + [1] + [0]*(n-4) )
>>> v_5 = vec( [-459, -441, 107, -207, 30, 358, -221, -483, 457, 96, 118, -241, 400, -478, 374, -46, -376, 415, 213, 476, -195, 25, -486, 444, 228, 313, -252, -182, -314, 105, -248, 163, 489, -388, 222, 110, -493, -491, 378, 213, 493, 48, 497, 138, 441, 140, 351, 135, -123, 414, -7, -344, -320, 54, 400, 230, -80, -85, -76, -475, 342, 276, 340, 1, 477, 158, -378, 146, 274, -355] )
>>> v_6 = vec( [-315, 212, 432, 236, 423, -389, 67, -313, 365, 416, -180, -121, -472, 56, -468, -234, -305, 173, 444, -348, 261, -120, 249, -466, 491, -349, -140, 49, 99, 383, -321, 127, 447, -199, 443, -89, -384, -102, -106, 253, 495, 500, 8, -354, 115, 488, -88, 471, -291, 323, 349, 68, -253, -35, 34, -175, 172, -162, 123, -266, -6, 321, 481, -116, -60, 227, 163, -24, 56, 114] )
>>> v_7 = vec( [1]*n )
>>> 
>>> lattice.integratePerfectHint( v_1, 0 ) #Coordinates
>>> lattice.integratePerfectHint( v_2, 0 )
>>> lattice.integratePerfectHint( v_3, 2 )
>>> lattice.integratePerfectHint( v_4, 1 )
>>> lattice.integratePerfectHint( v_5, -1670 ) #Inner products
>>> lattice.integratePerfectHint( v_6, 2381 )
>>> lattice.integrateModularHint( v_7, 0, 2 ) #Sum over all coordinates is even

Integrating the hints reduces the security of our LWE instance. When now running BKZ on the lattice, the secret will be recovered significantly faster. The required runtime on a laptop is roughly half a minute, and the required BKZ blocksize is 3.

>>> lattice.reduce()
>>> lattice.successBlocksize
3
>>> lattice.s
array([ 0,  0,  2,  1,  2, -1, -1,  0, -1,  1,  1,  1,  0,  1,  1, -3, -2,
       -2, -3, -1,  1,  1, -1,  2, -1,  0, -2,  0,  1,  0,  0,  0,  1,  0,
        1,  0,  0,  0,  0,  0,  1,  0,  0,  0, -1,  0, -1, -1, -1,  1,  1,
        1,  0,  0,  0,  0,  2,  1,  0, -1,  1, -2,  0,  0, -2,  0,  1,  0,
       -1,  0])

Generating LWE instances

Our library implements key generation algrotihms for various LWE-/NTRU-based schemes. To generate an LWE instance (A,b,q) with secret s and error e, simply run

>>> A,b,q,s,e = generateLWEInstance(scheme)

where scheme can be any of the following strings:

  • "Kyber512", "Kyber768", "Kyber1024",
  • "Dilithium2", "Dilithium3", "Dilithium5",
  • "Falcon2", "Falcon4", "Falcon8", "Falcon16", "Falcon32", "Falcon64", "Falcon128", "Falcon256", "Falcon512", "Falcon1024",
  • "NTRU-HPS-509", "NTRU-HPS-677", "NTRU-HPS-821", "NTRU-HRSS".

Additionally, one can generate Kyber-like toy instances, where both secret and error follow a binomial distribtuion with parameter eta, as follows:

A,b,q,s,e = generateToyInstance(n,m,q,eta)

Disclaimer: Our key generation algorithms are not suitable for production enviroments!

Reproducing experiments from the paper

To recreate our experiments for perfect hints, please run the following commands:

python3 experiments.py Kyber512 -hints="192:256:1" -trials=32
python3 experiments.py Kyber512 -hints="220:256:1" -trials=32 -centered
python3 experiments.py Kyber768 -hints="359:390:1" -trials=32
python3 experiments.py Falcon512 -hints="220:256:1" -trials=32
python3 experiments.py NTRU-HRSS -hints="310:350:1" -trials=32
python3 experiments.py Dilithium2 -hints="440:503:4" -trials=16

To recreate our experiments for modular hints, please run the following commands:

python3 experiments.py Kyber512 -hints="440:455:1" -trials=16 -modular
python3 experiments.py Falcon512 -hints="440:455:1" -trials=16 -modular
python3 experiments.py NTRU-HRSS -hints="610:625:1" -trials=16 -modular
python3 experiments.py Kyber768 -hints="690:705:1" -trials=16 -modular
python3 experiments.py Dilithium2 -hints="870:885:1" -trials=16 -modular

If you want to run the experiments in verbose mode, simply add the flag -verbose to the above commands.

Acknowledgments

For generating Falcon keys we use Thomas Prest's great falcon.py library.

lwe_with_hints's People

Contributors

juliannowakowski avatar

Stargazers

avatar Mingyao Shao avatar avatar Shouran MA avatar avatar Millie Solem avatar IE11 avatar Boru Chen avatar Matthias Steiner avatar Alex avatar sh1kaku avatar avatar tl2cents avatar avatar cccorz avatar thuguz15 avatar Yansong Feng avatar Nour-eddine Rahmani avatar Tong Liu avatar avatar Ryota Sakai avatar Joseph Surin avatar maple avatar

Watchers

avatar Nour-eddine Rahmani avatar

Forkers

sh1k4ku qianguo

lwe_with_hints's Issues

Lattice Reduction Crashes with AssertionError

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
```

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.