LWE dual attack

In [ ]:

!pip install "pqlattice[fast]"

!pip install "pqlattice[fast]"

In [1]:

import pqlattice as pq
import numpy as np
import math
pq.settings.set_backend("fast")

import pqlattice as pq import numpy as np import math pq.settings.set_backend("fast")

In [2]:

n = 20
sigma = 2
q = 1000
m = 100
secret_dist = "ternary"

possible_values = []
if secret_dist == "binary":
    possible_values = [0, 1]
elif secret_dist == "ternary":
    possible_values = [-1, 0, 1]

n = 20 sigma = 2 q = 1000 m = 100 secret_dist = "ternary" possible_values = [] if secret_dist == "binary": possible_values = [0, 1] elif secret_dist == "ternary": possible_values = [-1, 0, 1]

In [3]:

lwe = pq.random.LWE(n, q, sigma, secret_dist, 42)
secret = lwe.secret
A, b = lwe.sample_matrix(m)

lwe = pq.random.LWE(n, q, sigma, secret_dist, 42) secret = lwe.secret A, b = lwe.sample_matrix(m)

In [4]:

recovered_secret = []

print("Recovering secret's components")
for i in range(n):
    A_punctured = np.delete(A, i, axis=1)
    G_dual = pq.lattice.embeddings.sis_basis(A_punctured, q)
    target_column = A[:, i]
    v = pq.lattice.bkz(G_dual, 20)[0]
    interaction = np.dot(v, target_column)
    
    best_guess = 0
    max_score = -float('inf')
    
    projection = np.dot(v, b)
    
    for guess in possible_values:
        
        correction = guess * interaction
        z = (projection - correction) % q
        score = math.cos((2 * math.pi * z) / q)
        
        if score > max_score:
            max_score = score
            best_guess = guess
            
    recovered_secret.append(best_guess)
    
    is_correct = (best_guess == secret[i])
    status = "OK" if is_correct else "FAIL"
    print(f"s[{i:2}]: guessed {best_guess:2} (score: {max_score:.4f}) -> {status}")

print()
print("Real secret:")
print(f"{pq.as_integer(secret)}")
print("Recovered secret:")
print(f"{pq.as_integer(recovered_secret)}")
accuracy = (pq.as_integer(recovered_secret) == pq.as_integer(secret)).sum() / len(secret)
print()
print(f"accuracy: {accuracy*100:.2f}")

recovered_secret = [] print("Recovering secret's components") for i in range(n): A_punctured = np.delete(A, i, axis=1) G_dual = pq.lattice.embeddings.sis_basis(A_punctured, q) target_column = A[:, i] v = pq.lattice.bkz(G_dual, 20)[0] interaction = np.dot(v, target_column) best_guess = 0 max_score = -float('inf') projection = np.dot(v, b) for guess in possible_values: correction = guess * interaction z = (projection - correction) % q score = math.cos((2 * math.pi * z) / q) if score > max_score: max_score = score best_guess = guess recovered_secret.append(best_guess) is_correct = (best_guess == secret[i]) status = "OK" if is_correct else "FAIL" print(f"s[{i:2}]: guessed {best_guess:2} (score: {max_score:.4f}) -> {status}") print() print("Real secret:") print(f"{pq.as_integer(secret)}") print("Recovered secret:") print(f"{pq.as_integer(recovered_secret)}") accuracy = (pq.as_integer(recovered_secret) == pq.as_integer(secret)).sum() / len(secret) print() print(f"accuracy: {accuracy*100:.2f}")

Recovering secret's components
s[ 0]: guessed -1 (score: 0.9913) -> OK
s[ 1]: guessed -1 (score: 0.9972) -> OK
s[ 2]: guessed  0 (score: 0.9950) -> OK
s[ 3]: guessed -1 (score: 0.9987) -> OK
s[ 4]: guessed  1 (score: 0.9929) -> OK
s[ 5]: guessed  0 (score: 0.9967) -> OK
s[ 6]: guessed -1 (score: 0.9905) -> OK
s[ 7]: guessed  0 (score: 0.9998) -> OK
s[ 8]: guessed  0 (score: 0.9967) -> OK
s[ 9]: guessed  1 (score: 1.0000) -> OK
s[10]: guessed  1 (score: 0.9961) -> OK
s[11]: guessed  1 (score: 0.9967) -> OK
s[12]: guessed  0 (score: 0.9995) -> OK
s[13]: guessed -1 (score: 0.9834) -> OK
s[14]: guessed  1 (score: 0.9921) -> OK
s[15]: guessed  0 (score: 0.9943) -> OK
s[16]: guessed -1 (score: 1.0000) -> OK
s[17]: guessed  1 (score: 0.9997) -> OK
s[18]: guessed -1 (score: 0.9856) -> OK
s[19]: guessed  1 (score: 0.9686) -> OK

Real secret:
[-1 -1 0 -1 1 0 -1 0 0 1 1 1 0 -1 1 0 -1 1 -1 1]
Recovered secret:
[-1 -1 0 -1 1 0 -1 0 0 1 1 1 0 -1 1 0 -1 1 -1 1]

accuracy: 100.00