[Gzz-commits] manuscripts/Sigs article.rst poss.py reyzin.py

[Tuomas J. Lukka]

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