-
Notifications
You must be signed in to change notification settings - Fork 3
/
Copy pathOKCN-LWE-512.py
176 lines (133 loc) · 5.68 KB
/
OKCN-LWE-512.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
"""Generation of LaTeX tables for the paper and CDFs for the C code.
Based on the paper:
Joppe Bos, Craig Costello, Leo Ducas, Ilya Mironov, Michael Naehrig, Valeria
Nikolaenko, Ananth Raghunathan, Douglas Stebila. Frodo: Take off the ring!
Practical, quantum-secure key exchange from LWE. In ACM Conference on Computer
and Communications Security (CCS) 2016, ACM, October, 2016.
DOI: http://dx.doi.org/10.1145/2976749.2978425
Eprint http://eprint.iacr.org/2016/659
Copyright (c) 2016 Joppe Bos, Leo Ducas, Ilya Mironov, Valeria Nikolaenko,
Ananth Raghunathan, Douglas Stebila
Released under the MIT License; see LICENSE.txt for details.
"""
from math import sqrt, log, ceil
from discrete_distr import dgauss, bits_needed_to_sample, nonnegative_half, pdf_product, distribution_to_C
from renyi import renyi, opt_renyi_bound
from approx_distr import approximate_dgauss
from pqsec import optimize_attack, svp_classical, svp_quantum, svp_plausible, primal_cost, dual_cost
from collections import namedtuple
from failure_prob import noise_failure_prob
def distribution_to_TeX(p):
"""Formats distribution for use in TeX file.
Args:
p: A dictionary with entries for 'distr', 'sigma', 'a', 'D'
Returns:
LaTeX string.
"""
distr, sigma, a, distr_name = p['distr'], p['sigma'], p['a'], p['D']
n = max(distr.iterkeys()) + 1 # range is [0..n)
b = bits_needed_to_sample(distr)
ret = "${}$ & {} & {:.2f} & ".format(distr_name, b + 1, sigma**2)
for i in sorted(distr.iterkeys()):
if i >= 0:
p = int(round(distr[i] * 2**b))
if i == 0:
p *= 2
ret += r" {} &".format(p)
for i in xrange(max(distr.iterkeys()), 6):
ret += "&"
divergence = renyi(distr, nonnegative_half(dgauss(sigma)), a)
ret += " {:.1f} & {:.7f}".format(a, divergence)
return ret + r" \\"
def security_to_TeX(p, nbar, print_sec=True):
"""Formats security estimates for use in TeX file.
Args:
p: A dictionary with entries for 'name', 'n', 'q', 'distr', 'sigma'
nbar: Number of columns in exchanged matrices.
print_sec: If true, output will include security estimates
Returns:
LaTeX string.
"""
name, n, qlog, d, sigma = p['name'], p['n'], p['q'], p['distr'], p['sigma']
samples = 2 * n * nbar + nbar**2
q = 2**qlog
ret = ""
ret += r"\multirow{2}{*}{" + name.capitalize() + "} "
for cost in [primal_cost, dual_cost]:
m_pc, b_pc, cost_pc = optimize_attack( q, n, samples, sigma, cost, svp_classical, verbose=False)
m_pq, b_pq, cost_pq = optimize_attack( q, n, samples, sigma, cost, svp_quantum, verbose=False)
m_pp, b_pp, cost_pp = optimize_attack( q, n, samples, sigma, cost, svp_plausible, verbose=False)
if cost == primal_cost:
ret += "& Primal & "
else:
ret += "& Dual & "
ret += "{} & {} &".format(m_pc, b_pc)
if print_sec:
sym_d = pdf_product(d, {+1: .5, -1: .5})
dg = dgauss(sigma)
_, cost_pc_reduced = opt_renyi_bound(-cost_pc * log(2), sym_d, dg, samples)
_, cost_pq_reduced = opt_renyi_bound(-cost_pq * log(2), sym_d, dg, samples)
_, cost_pp_reduced = opt_renyi_bound(-cost_pp * log(2), sym_d, dg, samples)
ret += "{} & {} & {} & {} & {} & {} \\\\".format(
int(cost_pc),
int(cost_pq),
int(cost_pp),
int(-cost_pc_reduced / log(2)),
int(-cost_pq_reduced / log(2)),
int(-cost_pp_reduced / log(2))) # always round down
else:
ret += "-- & -- & -- & -- & -- & -- \\\\"
ret += "\n"
return ret
def parameters_to_TeX(p, nbar):
"""Formats parameters for use in TeX file.
Args:
p: A dictionary with entries for 'name', 'n', 'q', 'D', 'B', 'distr'
nbar: Number of columns in exchanged matrices.
Returns:
LaTeX string.
"""
name, n, q, dname, B, distr, g = p['name'], p['n'], p['q'], p['D'], p['B'], p['distr'], p['g']
s = name.capitalize()
s += " n = {}".format(n)
s += " q = $2^{{{}}}$".format(q)
s += " distr = ${}$".format(dname)
agreed_bits = B * nbar * nbar
s += " ${}\cdot {}^2 = {}$".format(B, nbar, agreed_bits)
sym_distr = pdf_product(distr, {+1: .5, -1: .5})
failure_prob = noise_failure_prob(sym_distr, 2 ** q, n, B, agreed_bits, g, p['cut'])
s += " err = $2^{{{:.1f}}}$".format(log(failure_prob, 2))
bandwidth = nbar * q * 2 * n + nbar * nbar * ceil(log(g, 2)) # bandwidth in bits
s += " & {:.2f} kB".format(bandwidth / 8000.)
s += r" \\"
return s
def main():
parameters = [
{'name': 'paranoid', 'D': 'D_4', 'sigma': sqrt(1.75), 'n': 700, 'q': 12, 'B': 2, 'g': 2**10, 'bits': 16, 'base': 129, 'cut': 0},
]
for p in parameters:
nbar, mbar = 16, 16
samples = (nbar + mbar) * p['n'] + nbar * mbar
_, p['distr'], p['a'] = approximate_dgauss( p['sigma'], samples, p['base'], None, p['bits'], quiet=True)
print "### C Code ###"
for p in parameters:
suffix = p['D'].replace('_', '')
print distribution_to_C(p['distr'], suffix)
print
print "### TABLE 1 ###"
for p in parameters:
print distribution_to_TeX(p)
print
print "### TABLE 2 ###"
for p in parameters:
print parameters_to_TeX(p, nbar=16)
print
print "### TABLE 3 ###"
for p in parameters:
print security_to_TeX(p, nbar=16, print_sec=p['name'] != 'challenge'),
if p['name'] == 'paranoid':
print r"\bottomrule"
else:
print r"\midrule"
if __name__ == "__main__":
main()