Our "estimator_hybrid.py" sage module estimates the bit-security of the hybrid MITM attack, given LWE parameters. We uses functions in "estimator.py" made by Albrecht et al [APS15] and the high-level structure of our estimator "estimator_hybrid.py" is from "estimator.py".
The current version is somewhat unstable for estimating small parameters such as n < 1000 and log(q) < 30.
We recommend to use our MITM_estimator function in "estimator_hybrid.py". This function estimates the cost of ring operations, given a bounded memory capacity 2^80.
EXAMPLE :
> sage: from estimator_hybrid import *
> sage: n = 8192; q = next_prime(2^125); alpha = 8/q; h = 64;
> sage: MITM_estimator(n, alpha, q, h, reduction_cost_model=BKZ.sieve)
Chosen Parameters :
n = 8192, log(q) = 125.0, stddev = 3.19, HW(s) = 64
Start Estimation . . .
Optimizing with beta = 268 . . .
Optimizing with beta = 276 . . .
Optimizing with beta = 272 . . .
Optimizing with beta = 244 . . .
== Bit-security : 131.2 with optimal parameters
k = 4606, h1 = 7, h2 = 11, beta = 268, mem = 72.9
(For simplicity, we set k1 = k2 = k/2)
== Details
rop: 2^131.2
m: 2^12.9
red: 2^110.5
delta_0: 1.005218
beta: 268
repeat: 1.031899
d: 2^12.9
c: 23.890
post: 2^108.6
prob_inv: 2^20.3
k: 2^12.2
h1: 7
h2: 11
mem: 2^72.9
"mitm.py" is an attack code for Sage. This is just for a proof-of-concept of the hybrid attack, and hence it is definitely not optimized.
> sage: from Mitm import *
> sage: n = 45; q = next_prime(2^14); h = 6; beta = 20; k = 30; tau = 30;
> sage: A, c, u, s = gen_instance(n, q, h, m = tau * n)
(A, c) is n-dim LWE samples (with secret s) / (A, u) is uniform samples
> sage: A_k, c_k, u_k, B = dim_error_tradeoff(A, c, u, beta, h, k)
(A_k, c_k) is k-dim LWE samples (with secret s[-k:]) / (A_k, u_k) is uniform samples.
> sage: Mitm_on_LWE(A_k, c_k, u_k, B, h)
Table size = 34281
** Mitm on (A_k, c_k) **
Number of noisy searches = 193
- Input is LWE with secret
(0, -1, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1)
** Mitm on (A_k, u_k) **
Number of noisy searches = 34281
- Input is uniform
> sage: s[-k:]
(0, -1, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1)