Create a gist now

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Shortest vector distribution in "ntrulike" basis matrices
# -*- coding: utf-8 -*-
import argparse
from fpylll import IntegerMatrix
from multiprocessing import Pool
def ntru_like(d, bits=30, q=1073741789):
A = IntegerMatrix.random(d, "ntrulike", bits=bits, q=q)
return A
def my_ntru_like(d, bits=30, q=1073741789):
A = IntegerMatrix.random(d, "ntrulike", bits=bits, q=q)
B = IntegerMatrix.random(d, "uniform", bits=bits)
for i in range(d):
for j in range(d):
k = (i+j)%d
A[i, d+k] = B[0, j]
return A
def q_array(d, bits=30, q=1073741789):
A = IntegerMatrix.random(d, "ntrulike", bits=bits, q=q)
B = IntegerMatrix.random(d, "uniform", bits=bits)
for i in range(d):
for j in range(d):
A[i, d+j] = B[i, j]
return A
def lll_it(A):
from fpylll import LLL
LLL.reduction(A)
return A
def bkz_it(A):
from fpylll import BKZ
for k in range(10, A.nrows, 10):
BKZ.reduction(A, BKZ.Param(block_size=k, flags=BKZ.AUTO_ABORT|BKZ.GH_BND))
return A
def norm_it(v):
from math import sqrt
n = 0.0
for i in range(len(v)):
n += v[i]*v[i]
return sqrt(n)
def svp_it(A):
from fpylll import SVP
A = bkz_it(lll_it(A))
v = SVP.shortest_vector(A)
return norm_it(v)
parser = argparse.ArgumentParser("NTRU-like stuff")
parser.add_argument("-d", "--dimension", help="dimension", type=int)
parser.add_argument("-w", "--workers", help="number of worker processes", type=int)
parser.add_argument("-t", "--tasks", help="number of tasks", type=int)
args = parser.parse_args()
d = args.dimension
workers = args.workers
tasks = args.tasks
print "d: %d, workers: %d, tasks: %d"%(d, workers, tasks)
Ar = [ntru_like(d) for _ in range(tasks)]
Am = [my_ntru_like(d) for _ in range(tasks)]
Aq = [q_array(d) for _ in range(tasks)]
pool = Pool(workers)
norms_a = [A[0].norm() for A in Ar]
def run_it(p, f, A, prefix=""):
import sys
r = []
for i, retval in enumerate(p.imap_unordered(f, A, 1)):
r.append(retval)
sys.stderr.write('\r{0} done: {1:.2%}'.format(prefix, float(i)/len(A)))
sys.stderr.flush()
sys.stderr.write('\r{0} done {1:.2%}\n'.format(prefix, float(i+1)/len(A)))
return r
norms_r = run_it(pool, svp_it, Ar, "rot")
norms_m = run_it(pool, svp_it, Am, "mne")
norms_q = run_it(pool, svp_it, Aq, "rnd")
print(u"λ_1(rot):: min: %12.2f, avg: %12.2f, max: %12.2f"%(min(norms_r), sum(norms_r)/tasks, max(norms_r)))
print(u"λ_1(mne):: min: %12.2f, avg: %12.2f, max: %12.2f"%(min(norms_m), sum(norms_m)/tasks, max(norms_m)))
print(u"λ_1(rnd):: min: %12.2f, avg: %12.2f, max: %12.2f"%(min(norms_q), sum(norms_q)/tasks, max(norms_q)))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment