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

[Tuomas J. Lukka]

CVSROOT:        /cvsroot/gzz
Module name:    manuscripts
Changes by:     Tuomas J. Lukka <address@hidden>        03/05/18 17:11:59

Modified files:
        Sigs           : article.rst poss.py 

Log message:
        Important idea from biba article: we can reduce public key size 
considerably by using the merkle hash tree since we are revealing a small 
fraction of the nodes

CVSWeb URLs:
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/manuscripts/Sigs/article.rst.diff?tr1=1.103&tr2=1.104&r1=text&r2=text
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/manuscripts/Sigs/poss.py.diff?tr1=1.7&tr2=1.8&r1=text&r2=text

Patches:
Index: manuscripts/Sigs/article.rst
diff -u manuscripts/Sigs/article.rst:1.103 manuscripts/Sigs/article.rst:1.104
--- manuscripts/Sigs/article.rst:1.103  Sun May 18 16:30:44 2003
+++ manuscripts/Sigs/article.rst        Sun May 18 17:11:59 2003
@@ -334,6 +334,8 @@
                $\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)$ }
            & $1$ & $b$ & $kh$ & $th$ & $h$ & $t$ & $1$ & $1+k$ \\
 
@@ -508,6 +510,11 @@
 
 Octuplet: `$(q, b, th, wh, h, t, ?+wh, w)$` XXX check
 
+Probability for successful forgery at one attempt
+after `$r$` signatures:
+`$ {rk \\over k} (n-1)^{(r-1)k} / n^{rk-1} $`
+
+MERKLE HASH TREE VARIANT!!! REDUCE PUBLIC KEY + SIG SIZE!!!
 
 Reyzin
 ------
@@ -539,6 +546,7 @@
 
 Octuplet: `$(1, b, kh, th, h, t, 1, 1+k)$` XXX check
 
+MERKLE HASH TREE VARIANT!!! REDUCE PUBLIC KEY + SIG SIZE!!!
 
 Bleichenbacher-Maurer
 ---------------------
@@ -640,6 +648,7 @@
     `$t=175$`, `$k=62$`
 
   - Bleichenbacher-Maurer. 
+    To sign 160 bits, we need `$n=29$`
 
 
 Conclusion
Index: manuscripts/Sigs/poss.py
diff -u manuscripts/Sigs/poss.py:1.7 manuscripts/Sigs/poss.py:1.8
--- manuscripts/Sigs/poss.py:1.7        Sun May 18 15:47:11 2003
+++ manuscripts/Sigs/poss.py    Sun May 18 17:11:59 2003
@@ -2,8 +2,13 @@
 import math
 from math import log, log10, ceil
 
+factorials = {}
 def fact(x):
-    return reduce(lambda a, b: a*b, range(1, x+1), 1L)
+    a = factorials.get(x, None)
+    if a == None:
+       a = reduce(lambda a, b: a*b, range(1, x+1), 1L)
+       factorials[x] = a
+    return a
 
 def choose(n, k):
     return fact(n) / (fact(k)*fact(n-k))