# -*- coding: utf-8 -*-
"""
Estimate cost of solving LWE using primal attacks.
See :ref:`LWE Primal Attacks` for an introduction what is available.
"""
from functools import partial
from sage.all import oo, ceil, sqrt, log, RR, ZZ, binomial, cached_function
from .reduction import delta as deltaf
from .reduction import cost as costf
from .util import local_minimum
from .cost import Cost
from .lwe_parameters import LWEParameters
from .simulator import normalize as simulator_normalize
from .prob import drop as prob_drop
from .prob import amplify as prob_amplify
from .prob import babai as prob_babai
from .prob import mitm_babai_probability
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
[docs]
class PrimalUSVP:
"""
Estimate cost of solving LWE via uSVP reduction.
"""
@staticmethod
def _xi_factor(Xs, Xe):
xi = RR(1)
if Xs < Xe:
xi = Xe.stddev / Xs.stddev
return xi
@staticmethod
def _solve_for_d(params, m, beta, tau, xi):
"""
Find smallest d ∈ [n,m] to satisfy uSVP condition.
If no such d exists, return the upper bound m.
"""
# Find the smallest d ∈ [n,m] s.t. a*d^2 + b*d + c >= 0
delta = deltaf(beta)
a = -log(delta)
if not tau:
C = log(params.Xe.stddev**2 * (beta - 1)) / 2.0
c = params.n * log(xi) - (params.n + 1) * log(params.q)
else:
C = log(params.Xe.stddev**2 * (beta - 1) + tau**2) / 2.0
c = log(tau) + params.n * log(xi) - (params.n + 1) * log(params.q)
b = log(delta) * (2 * beta - 1) + log(params.q) - C
n = params.n
if a * n * n + b * n + c >= 0: # trivial case
return n
# solve for ad^2 + bd + c == 0
disc = b * b - 4 * a * c # the discriminant
if disc < 0: # no solution, return m
return m
# compute the two solutions
d1 = (-b + sqrt(disc)) / (2 * a)
d2 = (-b - sqrt(disc)) / (2 * a)
if a > 0: # the only possible solution is ceiling(d2)
return min(m, ceil(d2))
# the case a<=0:
# if n is to the left of d1 then the first solution is ceil(d1)
if n <= d1:
return min(m, ceil(d1))
# otherwise, n must be larger than d2 (since an^2+bn+c<0) so no solution
return m
@staticmethod
@cached_function
def cost_gsa(
beta: int,
params: LWEParameters,
m: int = oo,
tau=None,
d=None,
red_cost_model=red_cost_model_default,
log_level=None,
):
delta = deltaf(beta)
xi = PrimalUSVP._xi_factor(params.Xs, params.Xe)
m = min(ceil(sqrt(params.n * log(params.q) / log(delta))), m)
tau = params.Xe.stddev if tau is None else tau
# Account for homogeneous instances
if params._homogeneous:
tau = False # Tau false ==> instance is homogeneous
d = PrimalUSVP._solve_for_d(params, m, beta, tau, xi) if d is None else d
# if d == β we assume one SVP call, otherwise poly calls. This makes the cost curve jump, so
# we avoid it here.
if d == beta and d < m:
d += 1
assert d <= m + 1
if not tau:
lhs = log(sqrt(params.Xe.stddev**2 * (beta - 1)))
rhs = RR(
log(delta) * (2 * beta - d - 1)
+ (log(xi) * params.n + log(params.q) * (d - params.n - 1)) / d
)
else:
lhs = log(sqrt(params.Xe.stddev**2 * (beta - 1) + tau**2))
rhs = RR(
log(delta) * (2 * beta - d - 1)
+ (log(tau) + log(xi) * params.n + log(params.q) * (d - params.n - 1)) / d
)
return costf(red_cost_model, beta, d, predicate=lhs <= rhs)
@staticmethod
@cached_function
def cost_simulator(
beta: int,
params: LWEParameters,
simulator,
m: int = oo,
tau=None,
d=None,
red_cost_model=red_cost_model_default,
log_level=None,
):
delta = deltaf(beta)
if d is None:
d = min(ceil(sqrt(params.n * log(params.q) / log(delta))), m) + 1
xi = PrimalUSVP._xi_factor(params.Xs, params.Xe)
tau = params.Xe.stddev if tau is None else tau
if params._homogeneous:
tau = False
d -= 1 # Remove extra dimension in homogeneous instances
r = simulator(d=d, n=params.n, q=params.q, beta=beta, xi=xi, tau=tau)
if not tau:
lhs = params.Xe.stddev**2 * (beta - 1)
else:
lhs = params.Xe.stddev**2 * (beta - 1) + tau**2
predicate = r[d - beta] > lhs
return costf(red_cost_model, beta, d, predicate=predicate)
[docs]
def __call__(
self,
params: LWEParameters,
red_cost_model=red_cost_model_default,
red_shape_model=red_shape_model_default,
optimize_d=True,
log_level=1,
**kwds,
):
"""
Estimate cost of solving LWE via uSVP reduction.
:param params: LWE parameters.
:param red_cost_model: How to cost lattice reduction.
:param red_shape_model: How to model the shape of a reduced basis.
:param optimize_d: Attempt to find minimal d, too.
: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.
- ``d``: Lattice dimension.
EXAMPLE::
>>> from estimator import *
>>> LWE.primal_usvp(schemes.Kyber512)
rop: ≈2^143.8, red: ≈2^143.8, δ: 1.003941, β: 406, d: 998, tag: usvp
>>> params = LWE.Parameters(n=200, q=127, Xs=ND.UniformMod(3), Xe=ND.UniformMod(3))
>>> LWE.primal_usvp(params, red_shape_model="cn11")
rop: ≈2^87.6, red: ≈2^87.6, δ: 1.006114, β: 209, d: 388, tag: usvp
>>> LWE.primal_usvp(params, red_shape_model=Simulator.CN11)
rop: ≈2^87.6, red: ≈2^87.6, δ: 1.006114, β: 209, d: 388, tag: usvp
>>> LWE.primal_usvp(params, red_shape_model=Simulator.CN11, optimize_d=False)
rop: ≈2^87.6, red: ≈2^87.6, δ: 1.006114, β: 209, d: 400, tag: usvp
The success condition was formulated in [USENIX:ADPS16]_ and studied/verified in
[AC:AGVW17]_, [C:DDGR20]_, [PKC:PosVir21]_. The treatment of small secrets is from
[ACISP:BaiGal14]_.
"""
params = LWEParameters.normalize(params)
# allow for a larger embedding lattice dimension: Bai and Galbraith
m = params.m + params.n if params.Xs <= params.Xe else params.m
if red_shape_model == "gsa":
with local_minimum(40, max(2 * params.n, 41), precision=5) as it:
for beta in it:
cost = self.cost_gsa(
beta=beta, params=params, m=m, red_cost_model=red_cost_model, **kwds
)
it.update(cost)
for beta in it.neighborhood:
cost = self.cost_gsa(
beta=beta, params=params, m=m, red_cost_model=red_cost_model, **kwds
)
it.update(cost)
cost = it.y
cost["tag"] = "usvp"
cost["problem"] = params
return cost.sanity_check()
try:
red_shape_model = simulator_normalize(red_shape_model)
except ValueError:
pass
# step 0. establish baseline
cost_gsa = self(
params,
red_cost_model=red_cost_model,
red_shape_model="gsa",
)
Logging.log("usvp", log_level + 1, f"GSA: {repr(cost_gsa)}")
f = partial(
self.cost_simulator,
simulator=red_shape_model,
red_cost_model=red_cost_model,
m=m,
params=params,
)
# step 1. find β
with local_minimum(
max(cost_gsa["beta"] - ceil(0.10 * cost_gsa["beta"]), 40),
max(cost_gsa["beta"] + ceil(0.20 * cost_gsa["beta"]), 40),
) as it:
for beta in it:
it.update(f(beta=beta, **kwds))
cost = it.y
Logging.log("usvp", log_level, f"Opt-β: {repr(cost)}")
if cost and optimize_d:
# step 2. find d
with local_minimum(params.n, stop=cost["d"] + 1) as it:
for d in it:
it.update(f(d=d, beta=cost["beta"], **kwds))
cost = it.y
Logging.log("usvp", log_level + 1, f"Opt-d: {repr(cost)}")
cost["tag"] = "usvp"
cost["problem"] = params
return cost.sanity_check()
__name__ = "primal_usvp"
primal_usvp = PrimalUSVP()
[docs]
class PrimalHybrid:
[docs]
@classmethod
def babai_cost(cls, d):
return Cost(rop=max(d, 1) ** 2)
[docs]
@classmethod
def svp_dimension(cls, r, D):
"""
Return η for a given lattice shape and distance.
:param r: squared Gram-Schmidt norms
"""
from math import lgamma, log, exp, pi
def ball_log_vol(n):
return (n / 2.0) * log(pi) - lgamma(n / 2.0 + 1)
def gaussian_heuristic_log_input(r):
n = len(list(r))
log_vol = sum(r)
log_gh = 1.0 / n * (log_vol - 2 * ball_log_vol(n))
return exp(log_gh)
d = len(r)
r = [log(x) for x in r]
if d > 4096:
for i, _ in enumerate(r):
# chosen since RC.ADPS16(1754, 1754).log(2.) = 512.168000000000
j = d - 1754 + i
if (j < d) and (gaussian_heuristic_log_input(r[j:]) < D.stddev**2 * (d - j)):
return ZZ(d - (j - 1))
return ZZ(2)
else:
for i, _ in enumerate(r):
if gaussian_heuristic_log_input(r[i:]) < D.stddev**2 * (d - i):
return ZZ(d - (i - 1))
return ZZ(2)
@staticmethod
@cached_function
def cost(
beta: int,
params: LWEParameters,
zeta: int = 0,
babai=False,
mitm=False,
m: int = oo,
d: int = None,
simulator=red_simulator_default,
red_cost_model=red_cost_model_default,
log_level=5,
):
"""
Cost of the hybrid attack.
:param beta: Block size.
:param params: LWE parameters.
:param zeta: Guessing dimension ζ ≥ 0.
:param babai: Insist on Babai's algorithm for finding close vectors.
:param mitm: Simulate MITM approach (√ of search space).
:param m: We accept the number of samples to consider from the calling function.
:param d: We optionally accept the dimension to pick.
.. note :: This is the lowest level function that runs no optimization, it merely reports
costs.
"""
if d is None:
delta = deltaf(beta)
d = min(ceil(sqrt(params.n * log(params.q) / log(delta))), m) + 1
d -= zeta
xi = PrimalUSVP._xi_factor(params.Xs, params.Xe)
tau = 1
# 1. Simulate BKZ-β
# TODO: pick τ as non default value
if params._homogeneous:
tau = False
d -= 1
r = simulator(d, params.n - zeta, params.q, beta, xi=xi, tau=tau, dual=True)
bkz_cost = costf(red_cost_model, beta, d)
# 2. Required SVP dimension η
if babai:
eta = 2
svp_cost = PrimalHybrid.babai_cost(d)
else:
# we scaled the lattice so that χ_e is what we want
eta = PrimalHybrid.svp_dimension(r, params.Xe)
svp_cost = costf(red_cost_model, eta, eta)
# when η ≪ β, lifting may be a bigger cost
svp_cost["rop"] += PrimalHybrid.babai_cost(d - eta)["rop"]
# 3. Search
# We need to do one BDD call at least
search_space, probability, hw = 1, 1.0, 0
# MITM or no MITM
# TODO: this is rather clumsy as a model
def ssf(x):
if mitm:
return RR(sqrt(x))
else:
return x
# e.g. (-1, 1) -> two non-zero per entry
base = params.Xs.bounds[1] - params.Xs.bounds[0]
if zeta:
# the number of non-zero entries
h = ceil(len(params.Xs) * params.Xs.density)
probability = RR(prob_drop(params.n, h, zeta))
hw = 1
while hw < min(h, zeta):
new_search_space = binomial(zeta, hw) * base**hw
if svp_cost.repeat(ssf(search_space + new_search_space))["rop"] >= bkz_cost["rop"]:
break
search_space += new_search_space
probability += prob_drop(params.n, h, zeta, fail=hw)
hw += 1
svp_cost = svp_cost.repeat(ssf(search_space))
if mitm and zeta > 0:
if babai:
probability *= mitm_babai_probability(r, params.Xe.stddev, params.q)
else:
# TODO: the probability in this case needs to be analysed
probability *= 1
if eta <= 20 and d >= 0: # NOTE: η: somewhat arbitrary bound, d: we may guess it all
probability *= RR(prob_babai(r, sqrt(d) * params.Xe.stddev))
ret = Cost()
ret["rop"] = bkz_cost["rop"] + svp_cost["rop"]
ret["red"] = bkz_cost["rop"]
ret["svp"] = svp_cost["rop"]
ret["beta"] = beta
ret["eta"] = eta
ret["zeta"] = zeta
ret["|S|"] = search_space
ret["d"] = d
ret["prob"] = probability
ret.register_impermanent(
{"|S|": False},
rop=True,
red=True,
svp=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(0.99, probability),
)
else:
return Cost(rop=oo)
return ret
[docs]
@classmethod
def cost_zeta(
cls,
zeta: int,
params: LWEParameters,
red_shape_model=red_simulator_default,
red_cost_model=red_cost_model_default,
m: int = oo,
babai: bool = True,
mitm: bool = True,
optimize_d=True,
log_level=5,
**kwds,
):
"""
This function optimizes costs for a fixed guessing dimension ζ.
"""
# step 0. establish baseline
baseline_cost = primal_usvp(
params,
red_shape_model=red_shape_model,
red_cost_model=red_cost_model,
optimize_d=False,
log_level=log_level + 1,
**kwds,
)
Logging.log("bdd", log_level, f"H0: {repr(baseline_cost)}")
f = partial(
cls.cost,
params=params,
zeta=zeta,
babai=babai,
mitm=mitm,
simulator=red_shape_model,
red_cost_model=red_cost_model,
m=m,
**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("bdd", log_level, f"H1: {cost!r}")
# step 2. optimize d
if cost and cost.get("tag", "XXX") != "usvp" and optimize_d:
with local_minimum(
params.n, cost["d"] + cost["zeta"] + 1, log_level=log_level + 1
) as it:
for d in it:
it.update(f(beta=cost["beta"], d=d))
cost = it.y
Logging.log("bdd", log_level, f"H2: {cost!r}")
if cost is None:
return Cost(rop=oo)
return cost
[docs]
def __call__(
self,
params: LWEParameters,
babai: bool = True,
zeta: int = None,
mitm: bool = True,
red_shape_model=red_shape_model_default,
red_cost_model=red_cost_model_default,
log_level=1,
**kwds,
):
"""
Estimate the cost of the hybrid attack and its variants.
:param params: LWE parameters.
:param zeta: Guessing dimension ζ ≥ 0.
:param babai: Insist on Babai's algorithm for finding close vectors.
:param mitm: Simulate MITM approach (√ of search space).
: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 BDD call.
- ``ζ``: Number of guessed coordinates.
- ``|S|``: Guessing search space.
- ``prob``: Probability of success in guessing.
- ``repeat``: How often to repeat the attack.
- ``d``: Lattice dimension.
- When ζ = 0 this function essentially estimates the BDD strategy as given in [RSA:LiuNgu13]_.
- When ζ ≠ 0 and ``babai=True`` this function estimates the hybrid attack as given in
[C:HowgraveGraham07]_
- When ζ ≠ 0 and ``babai=False`` this function estimates the hybrid attack as given in
[SAC:AlbCurWun19]_
EXAMPLES::
>>> from estimator import *
>>> LWE.primal_hybrid(schemes.Kyber512.updated(Xs=ND.SparseTernary(512, 16)), mitm = False, babai = False)
rop: ≈2^91.5, red: ≈2^90.7, svp: ≈2^90.2, β: 178, η: 21, ζ: 256, |S|: ≈2^56.6, d: 531, ...
>>> LWE.primal_hybrid(schemes.Kyber512.updated(Xs=ND.SparseTernary(512, 16)), mitm = False, babai = True)
rop: ≈2^88.7, red: ≈2^88.0, svp: ≈2^87.2, β: 98, η: 2, ζ: 323, |S|: ≈2^39.7, d: 346, ...
>>> LWE.primal_hybrid(schemes.Kyber512.updated(Xs=ND.SparseTernary(512, 16)), mitm = True, babai = False)
rop: ≈2^74.1, red: ≈2^73.7, svp: ≈2^71.9, β: 104, η: 16, ζ: 320, |S|: ≈2^77.1, d: 359, ...
>>> LWE.primal_hybrid(schemes.Kyber512.updated(Xs=ND.SparseTernary(512, 16)), mitm = True, babai = True)
rop: ≈2^85.8, red: ≈2^84.8, svp: ≈2^84.8, β: 105, η: 2, ζ: 366, |S|: ≈2^85.1, d: 315, ...
TESTS:
We test a trivial instance::
>>> params = LWE.Parameters(2**10, 2**100, ND.DiscreteGaussian(3.19), ND.DiscreteGaussian(3.19))
>>> LWE.primal_bdd(params)
rop: ≈2^43.7, red: ≈2^43.7, svp: ≈2^22.1, β: 40, η: 2, d: 1516, tag: bdd
"""
if zeta == 0:
tag = "bdd"
else:
tag = "hybrid"
params = LWEParameters.normalize(params)
# allow for a larger embedding lattice dimension: Bai and Galbraith
m = params.m + params.n if params.Xs <= params.Xe else params.m
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,
babai=babai,
mitm=mitm,
m=m,
log_level=log_level + 1,
)
def find_zeta_max(params, red_cost_model):
usvp_cost = primal_usvp(params, red_cost_model=red_cost_model)["rop"]
zeta_max = 1
while zeta_max < params.n:
# TODO: once support_size() is supported for NTRU, remove the below try/except
try:
if params.Xs.support_size(zeta_max) > usvp_cost:
# double it for mitm
return 2 * zeta_max
zeta_max +=1
except NotImplementedError:
return params.n
return params.n
if zeta is None:
zeta_max = find_zeta_max(params, red_cost_model)
with local_minimum(0, min(zeta_max, params.n), log_level=log_level) as it:
for zeta in it:
it.update(
f(
zeta=zeta,
optimize_d=False,
**kwds,
)
)
# TODO: this should not be required
cost = min(it.y, f(0, optimize_d=False, **kwds))
else:
cost = f(zeta=zeta)
cost["tag"] = tag
cost["problem"] = params
if tag == "bdd":
for k in ("|S|", "prob", "repetitions", "zeta"):
try:
del cost[k]
except KeyError:
pass
return cost.sanity_check()
__name__ = "primal_hybrid"
primal_hybrid = PrimalHybrid()
[docs]
def primal_bdd(
params: LWEParameters,
red_shape_model=red_shape_model_default,
red_cost_model=red_cost_model_default,
log_level=1,
**kwds,
):
"""
Estimate the cost of the BDD approach as given in [RSA:LiuNgu13]_.
:param params: LWE parameters.
:param red_cost_model: How to cost lattice reduction
:param red_shape_model: How to model the shape of a reduced basis
"""
return primal_hybrid(
params,
zeta=0,
mitm=False,
babai=False,
red_shape_model=red_shape_model,
red_cost_model=red_cost_model,
log_level=log_level,
**kwds,
)