-
Notifications
You must be signed in to change notification settings - Fork 42
/
sis_lattice.py
361 lines (301 loc) · 12.6 KB
/
sis_lattice.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
# -*- coding: utf-8 -*-
"""
Estimate cost of solving SIS using lattice reduction attacks.
See :ref:`SIS Lattice Attacks` for an introduction what is available.
"""
from functools import partial
from sage.all import oo, sqrt, log, RR, floor, cached_function
from .reduction import beta as betaf
from .reduction import cost as costf
from .util import local_minimum
from .cost import Cost
from .sis_parameters import SISParameters
from .simulator import normalize as simulator_normalize
from .prob import gaussian_cdf
from .prob import amplify as prob_amplify
from .io import Logging
from .conf import red_cost_model as red_cost_model_default
from .conf import red_shape_model as red_shape_model_default
from .conf import red_simulator as red_simulator_default
class SISLattice:
"""
Estimate cost of solving SIS via lattice reduction.
"""
@staticmethod
def _solve_for_delta_euclidean(params, d):
# root_volume = params.q**(params.n/d)
# delta = (params.length_bound / root_volume)**(1/(d - 1))
root_volume = (params.n / d) * log(params.q, 2)
log_delta = (1 / (d - 1)) * (log(params.length_bound, 2) - root_volume)
return RR(2**log_delta)
@staticmethod
def _opt_sis_d(params):
"""
Optimizes SIS dimension for the given parameters, assuming the optimal
d ≈ sqrt(n⋅log(q)/log(delta))
"""
log_delta = log(params.length_bound, 2) ** 2 / (4 * params.n * log(params.q, 2))
d = sqrt(params.n * log(params.q, 2) / log_delta)
return d
@staticmethod
@cached_function
def cost_euclidean(
params: SISParameters,
d=None,
red_cost_model=red_cost_model_default,
log_level=None,
**kwds,
):
# Check for triviality
if params.length_bound >= params.q:
raise ValueError("SIS trivially easy. Please set norm bound < q.")
if d is None:
d = min(floor(SISLattice._opt_sis_d(params)), params.m)
# First solve for root hermite factor
delta = SISLattice._solve_for_delta_euclidean(params, d)
# Then derive beta from the cost model(s)
if delta >= 1 and betaf(delta) <= d:
beta = betaf(delta)
reduction_possible = True
else:
beta = d
reduction_possible = False
lb = min(RR(sqrt(params.n * log(params.q))), RR(sqrt(d) * params.q ** (params.n / d)))
return costf(
red_cost_model, beta, d, predicate=params.length_bound > lb and reduction_possible
)
@staticmethod
@cached_function
def cost_infinity(
beta: int,
params: SISParameters,
simulator,
zeta: int = 0,
success_probability: float = 0.99,
d=None,
red_cost_model=red_cost_model_default,
log_level=None,
**kwds,
):
"""
Computes the cost of the attack on SIS using an infinity norm bound.
:param params: SIS parameters
:param beta: Block size used to produce short vectors for reduction
:param simulator: Basis profile simulator
:param zeta: Number of coefficients to set to 0 (ignore)
:param success_probability: The success probability to target
:param red_cost_model: How to cost lattice reduction
.. note :: This function assumes that the instance is normalized. It runs no optimization,
it merely reports costs.
"""
if params.length_bound >= params.q:
raise ValueError("SIS trivially easy. Please set norm bound < q.")
if d is None:
d = params.m
# Calculate the basis shape to aid in both styles of analysis
d_ = d - zeta
if d_ < beta:
return Cost(rop=oo, mem=oo)
r = simulator(d=d_, n=d_ - params.n, q=params.q, beta=beta, xi=1, tau=False)
# Cost the sampling of short vectors.
rho, cost_red, N, sieve_dim = red_cost_model.short_vectors(beta, d_)
bkz_cost = costf(red_cost_model, beta, d_)
if RR(sqrt(d)) * params.length_bound <= params.q: # Non-dilithium style analysis
# Calculate expected vector length using approximation factor on the shortest vector from BKZ
vector_length = rho * sqrt(r[0])
# Find probability that all coordinates meet norm bound
sigma = vector_length / sqrt(d_)
log_trial_prob = RR(d_ * log(1 - 2 * gaussian_cdf(0, sigma, -params.length_bound), 2))
else: # Dilithium style analysis
# Find first non-q-vector in r
if abs(sqrt(r[0]) - params.q) < 1e-8: # q-vectors exist
idx_start = next(i for i, r_ in enumerate(r) if r_ < r[0])
else:
idx_start = 0
if abs(r[-1] - 1) < 1e-8: # 1-vectors exist
# Find first 1 length graham-schmidt vector in r (Zone III)
idx_end = next((i - 1 for i, r_ in enumerate(r) if sqrt(r_) <= 1 + 1e-8), d_ - 1)
else:
idx_end = d_ - 1
vector_length = sqrt(r[idx_start])
gaussian_coords = max(idx_end - idx_start + 1, sieve_dim)
sigma = vector_length / sqrt(gaussian_coords)
log_trial_prob = RR(
log(1 - 2 * gaussian_cdf(0, sigma, -params.length_bound), 2) * (gaussian_coords)
)
log_trial_prob += RR(log((2 * params.length_bound + 1) / params.q, 2) * (idx_start))
probability = 2 ** min(
0, log_trial_prob + RR(log(N, 2))
) # expected number of solutions (max 1)
ret = Cost()
ret["rop"] = cost_red
ret["red"] = bkz_cost["rop"]
ret["sieve"] = max(cost_red - bkz_cost["rop"], 1e-100) # Ensuring non-zero cost here
ret["beta"] = beta
ret["eta"] = sieve_dim
ret["zeta"] = zeta
ret["d"] = d_
ret["prob"] = probability
ret.register_impermanent(
rop=True,
red=True,
sieve=True,
eta=False,
zeta=False,
prob=False,
)
# 4. Repeat whole experiment ~1/prob times
if probability and not RR(probability).is_NaN():
ret = ret.repeat(
prob_amplify(success_probability, probability),
)
else:
return Cost(rop=oo)
return ret
@classmethod
def cost_zeta(
cls,
zeta: int,
params: SISParameters,
ignore_qary: bool = False,
red_shape_model=red_simulator_default,
red_cost_model=red_cost_model_default,
d=None,
log_level=5,
**kwds,
):
"""
This function optimizes costs for a fixed number of coordinates to 'ignore', denoted ζ.
Ignored coordinates are set to 0 in the final SIS solution, so the dimension of the
instance is treated as d-ζ.
"""
# step 0. establish baseline cost using worst case euclidean norm estimate
# length_bound =1 makes sense when norm=∞, but we take logs and divide
params_baseline = params.updated(
norm=2, length_bound=2 if params.length_bound == 1 else params.length_bound
)
baseline_cost = lattice(
params_baseline,
ignore_qary=ignore_qary,
red_shape_model=red_shape_model,
red_cost_model=red_cost_model,
log_level=log_level + 1,
**kwds,
)
Logging.log("sis_infinity", log_level, f"H0: {repr(baseline_cost)}")
f = partial(
cls.cost_infinity,
params=params,
zeta=zeta,
ignore_qary=ignore_qary,
simulator=red_shape_model,
red_cost_model=red_cost_model,
d=d,
**kwds,
)
# step 1. optimize β
with local_minimum(
40, baseline_cost["beta"] + 1, precision=2, log_level=log_level + 1
) as it:
for beta in it:
it.update(f(beta))
for beta in it.neighborhood:
it.update(f(beta))
cost = it.y
Logging.log("sis_infinity", log_level, f"H1: {cost!r}")
if cost is None:
return Cost(rop=oo)
return cost
def __call__(
self,
params: SISParameters,
zeta: int = None,
red_shape_model=red_shape_model_default,
red_cost_model=red_cost_model_default,
log_level=1,
**kwds,
):
"""
Estimate the cost of attacking SIS using lattice reduction
:param params: SIS parameters.
:param zeta: Number of coefficients to set to 0 (ignore)
:return: A cost dictionary
The returned cost dictionary has the following entries:
- ``rop``: Total number of word operations (≈ CPU cycles).
- ``red``: Number of word operations in lattice reduction.
- ``δ``: Root-Hermite factor targeted by lattice reduction.
- ``β``: BKZ block size.
- ``η``: Dimension of the final Sieving call to generate short vectors.
- ``ζ``: Number of ignored coordinates.
- ``|S|``: Guessing search space.
- ``prob``: Probability of success in guessing.
- ``repeat``: How often to repeat the attack.
- ``d``: Lattice dimension.
EXAMPLES::
>>> from estimator import *
>>> SIS.lattice(schemes.Dilithium2_MSIS_WkUnf)
rop: ≈2^152.2, red: ≈2^151.3, sieve: ≈2^151.1, β: 427, η: 433, ζ: 0, d: 2304, prob: 1, ↻: 1, tag: infinity
>>> SIS.lattice(schemes.Dilithium2_MSIS_WkUnf, red_shape_model="lgsa")
rop: ≈2^151.3, red: ≈2^150.2, sieve: ≈2^150.5, β: 423, η: 431, ζ: 0, d: 2304, prob: 1, ↻: 1, tag: infinity
>>> params = SIS.Parameters(n=113, q=2048, length_bound=512, norm=2)
>>> SIS.lattice(params)
rop: ≈2^47.0, red: ≈2^47.0, δ: 1.011391, β: 61, d: 276, tag: euclidean
>>> SIS.lattice(params.updated(norm=oo, length_bound=16), red_shape_model="lgsa")
rop: ≈2^61.0, red: ≈2^59.9, sieve: ≈2^60.1, β: 95, η: 126, ζ: 0, d: 2486, prob: 1, ↻: 1, tag: infinity
>>> SIS.lattice(params.updated(norm=oo, length_bound=16), red_shape_model="cn11")
rop: ≈2^65.9, red: ≈2^64.9, sieve: ≈2^64.9, β: 113, η: 142, ζ: 0, d: 2486, prob: 1, ↻: 1, tag: infinity
>>> SIS.lattice(params.updated(norm=oo, length_bound=1), red_shape_model="cn11")
rop: ≈2^246.2, red: ≈2^245.2, sieve: ≈2^245.2, β: 764, η: 751, ζ: 0, d: 2486, prob: 1, ↻: 1, tag: infinity
The success condition for euclidean norm bound is derived by determining the root hermite factor required for
BKZ to produce the required output. For infinity norm bounds, the success conditions are derived using a
probabilistic analysis. Vectors are assumed to be short as in [MATZOV22]_ P.18, or [Dilithium21]_ P.35.
.. note :: When using euclidean norm bounds and the length bound is too small, this function returns
β = d, and rop: inf
"""
if params.norm == 2:
tag = "euclidean"
elif params.norm == oo:
tag = "infinity"
else:
raise NotImplementedError(
"SIS attack estimation currently only supports euclidean and infinity norms"
)
if tag == "infinity":
red_shape_model = simulator_normalize(red_shape_model)
f = partial(
self.cost_zeta,
params=params,
red_shape_model=red_shape_model,
red_cost_model=red_cost_model,
log_level=log_level + 1,
)
if zeta is None:
with local_minimum(0, params.m, log_level=log_level) as it:
for zeta in it:
it.update(
f(
zeta=zeta,
**kwds,
)
)
# TODO: this should not be required
cost = min(it.y, f(0, **kwds))
else:
cost = f(zeta=zeta)
else:
cost = self.cost_euclidean(
params=params,
red_cost_model=red_cost_model,
log_level=log_level + 1,
)
cost["tag"] = tag
cost["problem"] = params
if tag == "euclidean":
for k in ("sieve", "prob", "repetitions", "zeta"):
try:
del cost[k]
except KeyError:
pass
return cost.sanity_check()
__name__ = "lattice"
lattice = SISLattice()