[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Gzz-commits] manuscripts/Sigs article.rst poss.py
From: |
Tuomas J. Lukka |
Subject: |
[Gzz-commits] manuscripts/Sigs article.rst poss.py |
Date: |
Sun, 18 May 2003 17:11:59 -0400 |
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))
- [Gzz-commits] manuscripts/Sigs article.rst poss.py, Tuomas J. Lukka, 2003/05/18
- [Gzz-commits] manuscripts/Sigs article.rst poss.py, Tuomas J. Lukka, 2003/05/18
- [Gzz-commits] manuscripts/Sigs article.rst poss.py, Benja Fallenstein, 2003/05/18
- [Gzz-commits] manuscripts/Sigs article.rst poss.py, Benja Fallenstein, 2003/05/18
- [Gzz-commits] manuscripts/Sigs article.rst poss.py, Tuomas J. Lukka, 2003/05/18
- [Gzz-commits] manuscripts/Sigs article.rst poss.py,
Tuomas J. Lukka <=
- [Gzz-commits] manuscripts/Sigs article.rst poss.py, Tuomas J. Lukka, 2003/05/19