[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Gzz-commits] manuscripts/Sigs article.rst poss.py reyzin.py
From: |
Tuomas J. Lukka |
Subject: |
[Gzz-commits] manuscripts/Sigs article.rst poss.py reyzin.py |
Date: |
Mon, 19 May 2003 07:47:04 -0400 |
CVSROOT: /cvsroot/gzz
Module name: manuscripts
Changes by: Tuomas J. Lukka <address@hidden> 03/05/19 07:47:04
Modified files:
Sigs : article.rst poss.py reyzin.py
Log message:
More
CVSWeb URLs:
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/manuscripts/Sigs/article.rst.diff?tr1=1.104&tr2=1.105&r1=text&r2=text
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/manuscripts/Sigs/poss.py.diff?tr1=1.8&tr2=1.9&r1=text&r2=text
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/manuscripts/Sigs/reyzin.py.diff?tr1=1.1&tr2=1.2&r1=text&r2=text
Patches:
Index: manuscripts/Sigs/article.rst
diff -u manuscripts/Sigs/article.rst:1.104 manuscripts/Sigs/article.rst:1.105
--- manuscripts/Sigs/article.rst:1.104 Sun May 18 17:11:59 2003
+++ manuscripts/Sigs/article.rst Mon May 19 07:47:04 2003
@@ -325,20 +325,24 @@
\parbox{\sw}{Lamport\cite{XXX}\\$(h,b)$}
& $1$ & $b$ & $bh$ & $2bh$ & $h$ & $2b$ & $0$ & $b$ \\
\parbox{\sw}{Merkle I $(h,b)$}
- & $1$ & $b$ & $h(b+\lceil \log{2} b \rceil)$ & $h$ & $h$ &
- $b+\lceil \log{2} b \rceil + 1$ & $0$ &
+ & $1$ & $b$ & $(b+\lceil \log_2 b \rceil)h$ & $h$ & $h$ &
+ $b+\lceil \log_2 b \rceil + 1$ & $0$ &
$\le b$ \\
\parbox{\sw}{Merkle-Winternitz\cite{XXX} $(h,b,n)$ }
- & $1$ & $b$ & $\frac{b}{n}h+h$ & $h$ & $h$ &
+ & $1$ & $b$ & $(\frac{b}{n}+1)h$ & $h$ & $h$ &
$2\frac{b}{n}(2^n-1)+1$ & $\frac{b}{n}(2^n-1)$ &
$\frac{b}{n}(2^n-1)+1$ \\
- \parbox{\sw}{BiBa $(h,b,q,n,t,w)$}
- & $q$ & $b$ & $th$ & $wh$ & $h$ & $t$ & $?+wh$ & $w$ \\
- \parbox{\sw}{PowerBall $(?)$}
- \\
- \parbox{\sw}{Reyzin subset-resilient $(h,b,t,k)$ }
+ \parbox{\sw}{BiBa $(h,b,q,n,t,k)$}
+ & $q$ & $b$ & $kh$ & $th$ & $h$ & $t$ & $1+t+k$ & $1+t+k$ \\
+ \parbox{\sw}{BiBa-Merkle $(h,b,q,n,t,k)$}
+ & $q$ & $b$ & $k\lceil \log_2 t \rceil h$
+ & $h$ & $h$ & $2t$ & $1+t+k $
+ & $1+t+k+ k\lceil \log_2 t
\rceil$ \\
+ \parbox{\sw}{Reyzin $(h,b,t,k)$ }
& $1$ & $b$ & $kh$ & $th$ & $h$ & $t$ & $1$ & $1+k$ \\
-
+ \parbox{\sw}{Reyzin-Merkle$(h,b,t,k)$ }
+ & $1$ & $b$ & $k\lceil \log_2 t \rceil h$
+ & $h$ & $h$ & $t$ & $1$ & $1+k+k \lceil \log_2 t
\rceil$ \\
\parbox{\sw}{Bleichenbacher-Maurer\cite{XXX(ASIACRYPT)}
(h, n)
}
@@ -355,7 +359,7 @@
% XXX check this again
($n, S'$) }
& ${2^n}q'$
- & $b$ & $s'+r'+hn+h$
+ & $b$ & $s'+r'+(n+1)h$
& $h$ & $h$ &
${2^n}c_0' + 2(2^n)-1$ &
$c_s'$ &
@@ -369,11 +373,16 @@
Characterizations of existing one-time signature schemes.
The symbols are explained in the text. $n$ is a freely chosen
positive integer.
- In BiBa, $t$ is the number of balls, $n$ the number of bins,
- and $w$ the number of balls needed in a single bin
- in order to form a signature.
- In Reyzin and Reyzin's scheme, $t$ and $k$
- must be chosen so that ${t \choose k} \ge 2^b$.
+ The Biba and Reyzin schemes (also the Merkle variants) are
+ probabilistic and the parameters must be chosen to obtain
+ sufficient security.
+ Even in the non-probabilistic alternative
+ of the Reyzin scheme, $t$ and $k$
+ must be chosen so that ${t \choose k} \ge 2^b$; in that alternative,
+ the running time of signing and verifying is more complicated and
+ not taken into account in the table.
+ In Biba, the invocations of the random oracle that throws the balls
+ into bins are counted as single hash function invocations.
For Bleichenbacher-Maurer, XXX
`$\eta=\log 51 / \log 2$`.
The derived schemes use
@@ -420,6 +429,8 @@
Merkle (?)
----------
+
+
This scheme is an improvement over Lamport, needing
only `$k=b+\\lceil \\log{2} b \\rceil$` hashes.
@@ -492,30 +503,56 @@
their hashes as the public key. A hash function maps each ball
to one of `$n$` *bins*, depending on the signed message
and a counter, initially zero.
-If `$w$` balls fall into the same bin, they are published
-as the signature. If no bin contains at least `$w$` balls,
+If `$k$` balls fall into the same bin, they are published
+as the signature. If no bin contains at least `$k$` balls,
the counter is increased and the procedure is repeated
-until a '`$w$`-time collision' is found.
+until a '`$k$`-time collision' is found.
- private key: the `$t$` random numbers
- public key: the hashes of the random numbers
- sign: apply the hash function to all balls
- until a `$w$`-time collision is found
+ until a `$k$`-time collision is found
- verify: verify that the hash function maps the published balls
into the same bin; verify that the balls match the public key
(i.e., that the public key contains their hashes).
-Octuplet: `$(q, b, th, wh, h, t, ?+wh, w)$` XXX check
+Octuplet: `$(q, b, kh, th, h, t, 1+C(t)+k, 1+C(t)+k)$` XXX check
Probability for successful forgery at one attempt
after `$r$` signatures:
`$ {rk \\over k} (n-1)^{(r-1)k} / n^{rk-1} $`
+Because only a small number of the hashes in the public key need to be
+revealed and checked when signing, a Merkle hash tree may be used
+for the public key as described in the appendix of [XXX].
+However, in the usual course of things this is impractical because
+of the increased signature size. However, here the situation is different
+since both public key size and signature size
+of the underlying algorithm add to the
+
+Never more than `$k \\lceil \\log_2 t \\rceil$` hashes need to be provided
+Worst-case estimate octuplet:
+`$(q, b, k\\lceil \\log_2 t \\rceil h, h, h, 2t, 1+C(t)+k, 1+C(t)+k+ k\\lceil
\\log_2 t \\rceil)$` XXX check
+
MERKLE HASH TREE VARIANT!!! REDUCE PUBLIC KEY + SIG SIZE!!!
+ In BiBa, $t$ is the number of balls, $n$ the number of bins,
+ and $w$ the number of balls needed in a single bin
+ in order to form a signature.
+
+Powerball
+---------
+
+Like BiBa, except that instead of looking for a `$k$`-way collision,
+the public key is used to generate patterns in which each bin must
+be filled.
+
+Not included in table: detailed analysis of probability of forgery
+not found in literature, and is beyond the scope of this article..
+
Reyzin
------
@@ -542,11 +579,15 @@
?
-- serious vulnerabilities with chosen-message multiple signatures,
-
-Octuplet: `$(1, b, kh, th, h, t, 1, 1+k)$` XXX check
-
-MERKLE HASH TREE VARIANT!!! REDUCE PUBLIC KEY + SIG SIZE!!!
+- serious vulnerabilities with adaptive chosen-message multiple signatures,
+- however, not a problem in our current context, as different key will be used
+ for each signature
+
+Octuplet: `$(1, b, kh, th, h, t, 1, 1+k)$`
+
+Additionally, a Merkle hash tree can be applied as in BiBa:
+Octuplet: `$(1, b, k\\lceil \\log_2 t \\rceil h, h, h, 2t, 1, 1+k+k\\lceil
\\log_2 t \\rceil)$`
+XXX check
Bleichenbacher-Maurer
---------------------
@@ -570,7 +611,7 @@
public key - calculate some less than `$9n+2$` hashes
Octuplet: `$(1, \\lfloor\\eta n\\rfloor,
-3(n+1)h, h, h, 9n+2, 0, 9n+2)$` XXX check
+3(n+1)h, h, h, 9n+2, 0, 9n+2)$`
Merkle hash trees
@@ -624,6 +665,7 @@
Tradeoffs in deterministic key boosting
---------------------------------------
+
- we demand security level `$2^{-160}$` for our underlying schemes
- biba:
@@ -648,7 +690,8 @@
`$t=175$`, `$k=62$`
- Bleichenbacher-Maurer.
- To sign 160 bits, we need `$n=29$`
+ To sign 160 bits, we need `$n=29$`.
+ Signatures are 90 hashes
Conclusion
Index: manuscripts/Sigs/poss.py
diff -u manuscripts/Sigs/poss.py:1.8 manuscripts/Sigs/poss.py:1.9
--- manuscripts/Sigs/poss.py:1.8 Sun May 18 17:11:59 2003
+++ manuscripts/Sigs/poss.py Mon May 19 07:47:04 2003
@@ -33,6 +33,8 @@
def reyzin(h,b,t,k):
return 1, b, k*h, t*h, h, t, 1, 1+k
+def reyzin_merkled(h, b, t, k):
+ return 1, b, k*ceil(log2(t)), h, h, t, 1, 1 + k + ceil(log2(t))
def times(j, S):
return (j*S[0], S[1], S[2], j*S[3], S[4], j*S[5], S[6], S[7])
@@ -77,38 +79,60 @@
schemes = []
+def scheme(p, n, s):
+ if p:
+ print n
+ printscheme(s)
+ schemes.append((n,s))
+
if __name__ == '__main__':
- for t in range(1, 40):
+ ts = []
+ ts.extend(range(1, 50))
+ ts.append(80)
+ ts.append(160)
+ for t in ts:
n = ceil(160.0 / t )
#print "\n N = ",t, " n = ", n
#print "MW:"
for mn in range(1,17):
- s = (key_boosting(t,
+ scheme(0,
+ "KB%(t)sM%(n)sMW(160,160,%(mn)s)" % locals(),
+ key_boosting(t,
merkle_hashtree(n,
merkle_winternitz(160, 160, mn))))
- schemes.append( (
- "KB%(t)sM%(n)sMW(160,160,%(mn)s)" % locals(),
- s
- ))
#printscheme(s)
- s = (key_boosting(t,
+ scheme(0,
+ "KB%(t)sM%(n)sBM(160,29)" % locals(),
+ key_boosting(t,
merkle_hashtree(n,
bleichenbacher_maurer(160, 29))))
- schemes.append( (
- "KB%(t)sM%(n)sBM(160,29)" % locals(),
- s
- ))
-
- #print "Lamport:"
- s = (key_boosting(t,
+
+ scheme(1,
+ "KB%(t)sM%(n)sRZ(160,160,168,69)" % locals(),
+ key_boosting(t,
+ merkle_hashtree(n,
+ reyzin(160, 160, 168, 69))))
+
+ for rt, rk in (
+ (256, 42),
+ (512, 30),
+ (1024, 24),
+ (2048, 21),
+ (4096, 18),
+ (8192, 16),
+ (16384, 15)):
+ scheme(1,
+ "KB%(t)sM%(n)sRZM(160,160,8192,16)" % locals(),
+ key_boosting(t,
+ merkle_hashtree(n,
+ reyzin_merkled(160, 160, rt, rk))))
+
+ scheme(0,
+ "KB%(t)sM%(n)sL(160,160)" % locals(),
+ key_boosting(t,
merkle_hashtree(n,
lamport(160, 160))))
- schemes.append( (
- "KB%(t)sM%(n)sL(160,160)" % locals(),
- s
- ))
- #printscheme(s)
f = open("m.dat", "w")
for s in schemes:
@@ -117,17 +141,43 @@
for criteria in (
(1, 0),
+ (1, 0.00001),
+ (1, 0.0001),
+ (1, 0.001),
(1, 0.01),
(1, 0.1),
(1, 1),
(1, 10),
(1, 100),
- (1, 1000)):
+ (1, 110),
+ (1, 120),
+ (1, 130),
+ (1, 140),
+ (1, 150),
+ (1, 160),
+ (1, 170),
+ (1, 180),
+ (1, 190),
+ (1, 200),
+ (1, 300),
+ (1, 400),
+ (1, 500),
+ (1, 600),
+ (1, 700),
+ (1, 800),
+ (1, 900),
+ (1, 1000),
+ (1, 10000),
+ (1, 100000),
+ (1, 1000000L),
+ (1, 10000000L),
+ (1, 100000000L),
+ (0, 1)):
m = None
mv = 0
def critf(s):
- return criteria[0] * log2(s[1][2]) + \
- criteria[1] * log10(sum(s[1][5:]))
+ return criteria[0] * (s[1][2]) + \
+ criteria[1] * (sum(s[1][5:]))
for s in schemes:
if m == None or critf(s)<mv:
m = s
Index: manuscripts/Sigs/reyzin.py
diff -u manuscripts/Sigs/reyzin.py:1.1 manuscripts/Sigs/reyzin.py:1.2
--- manuscripts/Sigs/reyzin.py:1.1 Mon May 19 00:42:15 2003
+++ manuscripts/Sigs/reyzin.py Mon May 19 07:47:04 2003
@@ -1,4 +1,5 @@
from poss import *
+from math import *
def securitybits(t, k, r=1):
return k*(log2(t)-log2(k) - log2(r))
@@ -6,28 +7,34 @@
def signbits(t, k):
return log2(choose(t, k))
+def msignaturebits(t, k):
+ # Merkled signature bits
+ lt = ceil(log2(t))
+ return k * lt
+
# for t in (128, 256, 512, 1024, 2048):
-print "Reyzin tradeoff: probabilistic, with security req"
-for t in range(300, 330):
- r = 1
- for k in range(1, t/2):
- if signbits(t, k) >= 160 and securitybits(t, k, r) >= 160:
- print t, k, signbits(t, k), securitybits(t, k, r)
- r += 1
- if r > 4:
- break
+if 0:
+ print "Reyzin tradeoff: probabilistic, with security req"
+ for t in range(300, 330):
+ r = 1
+ for k in range(1, t/2):
+ if signbits(t, k) >= 160 and securitybits(t, k, r) >= 160:
+ print t, k, signbits(t, k), securitybits(t, k, r)
+ r += 1
+ if r > 4:
+ break
-print "Reyzin tradeoff: probabilistic, with security req"
-for t in range(300, 330):
+print "Reyzin tradeoff: with security req"
+for t in [2**i for i in range(1,15)]:
for k in range(1, t/2):
if signbits(t, k) >= 160 and securitybits(t, k) >= 160:
- print t, k, signbits(t, k), securitybits(t, k)
+ print t, k, msignaturebits(t, k), signbits(t, k), securitybits(t, k)
break
print "Reyzin tradeoff: hash only"
-for t in range(100, 200):
+for t in [2**i for i in range(1,15)]:
for k in range(1, t/2):
if signbits(t, k) >= 160:
- print t, k, signbits(t, k)
+ print t, k, msignaturebits(t, k), signbits(t, k)
break
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [Gzz-commits] manuscripts/Sigs article.rst poss.py reyzin.py,
Tuomas J. Lukka <=