Create a gist now

Instantly share code, notes, and snippets.

Embed
What would you like to do?
BKZ Cost Esimates
# -*- coding: utf-8 -*-
"""
Estimate the cost of BKZ 2.0 using Pruner/Simulator
.. moduleauthor: Martin R. Albrecht <martinralbrecht@royalholloway.ac.uk>
"""
from collections import OrderedDict
from fpylll import IntegerMatrix, GSO, BKZ, Pruning, LLL
from fpylll.tools.bkz_simulator import simulate as bkz_simulate
from fpylll.util import gaussian_heuristic
from math import log
from pickle import dump
def lll_cost(d):
"""
Some rough cost of LLL in dimension d in enumeration nodes.
NOTE:: We are ignoring the bit-size of the input here.
"""
return d**3
def sample_r(d):
"""
Sample squared Gram-Schmidt norms of an LLL reduced q-ary lattice in dimension d.
"""
A = LLL.reduction(IntegerMatrix.random(d, "qary", bits=30, k=d//2))
M = GSO.Mat(A)
M.update_gso()
return M.r()
def preprocess(r, block_size, strategies):
"""
Simulate preprocessing algorithm.
:param r: squared Gram-Schmidt norms.
:param block_size: preprocessing block size
:param strategies: strategies computed so far for cost.
"""
d = len(r)
# NOTE we hardcode two tours. FPLLL uses 1 tour, but it also applies recursive preprocessing.
r, _ = bkz_simulate(r, BKZ.EasyParam(block_size, max_loops=2))
cost = lll_cost(block_size)
for kappa in range(d-1):
cost += strategies[min(d-kappa, block_size)][0]
return r, cost
def enum_cost(r, preproc_cost):
"""
Return cost of computing shortest vector on basis r.
:param r: squared Gram-Schmidt norms.
:param preproc_cost: cost of achieving basis of quality similar to r.
"""
d = len(r)
target_norm = gaussian_heuristic(r)
for float_type in ("d", "dd", "qd"):
try:
pruner = Pruning.Pruner(target_norm, preproc_cost, [r], target=0.51, float_type="dd")
coefficients = pruner.optimize_coefficients([1. for _ in range(d)])
cost = pruner.repeated_enum_cost(coefficients)
cost_single = pruner.single_enum_cost(coefficients)
return preproc_cost + cost, cost_single
except RuntimeError:
pass
raise RuntimeError
def strategize(max_block_size=80):
strategies = OrderedDict()
strategies[2] = (0, 2, 0)
for block_size in range(3, max_block_size+1):
r = sample_r(block_size)
start = strategies[block_size-1][1]
# HACK We skip over the last few blocks because somehow those make the pruner go BOOM
stop = max(strategies[block_size-1][1]+1, block_size-8)
for preproc in range(start, stop):
cost, cost_single = enum_cost(*preprocess(r, preproc, strategies))
if block_size not in strategies or cost < strategies[block_size][0]:
strategies[block_size] = cost, preproc, cost_single
if preproc > 40 and cost > 2*strategies[block_size][0]:
break
print "d: %3d, log(enum cost): %5.1f, preprocessing block size: %2d"%(block_size,
log(strategies[block_size][0], 2),
strategies[block_size][1])
dump(strategies, open("strategies.sobj", "wb"))
return strategies
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment