LWE dual attack
In [ ]:
Copied!
!pip install "pqlattice[fast]"
!pip install "pqlattice[fast]"
In [1]:
Copied!
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]:
Copied!
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]:
Copied!
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]:
Copied!
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