[Gzz-commits] manuscripts/Sigs article.rst

[Benja Fallenstein]

CVSROOT:        /cvsroot/gzz
Module name:    manuscripts
Changes by:     Benja Fallenstein <address@hidden>      03/05/18 12:50:02

Modified files:
        Sigs           : article.rst 

Log message:
        merkle's other scheme

CVSWeb URLs:
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/manuscripts/Sigs/article.rst.diff?tr1=1.79&tr2=1.80&r1=text&r2=text

Patches:
Index: manuscripts/Sigs/article.rst
diff -u manuscripts/Sigs/article.rst:1.79 manuscripts/Sigs/article.rst:1.80
--- manuscripts/Sigs/article.rst:1.79   Sun May 18 12:35:05 2003
+++ manuscripts/Sigs/article.rst        Sun May 18 12:50:02 2003
@@ -151,6 +151,26 @@
 - verify: check that the revealed RNs hashes to right hash in public key - 
   calculate `$b$` hashes
 
+Merkle (?)
+----------
+
+This scheme is an improvement over Lamport, needing
+only `$k=b+\\lceiling \\log{2} b \\rceiling$` hashes.
+
+Let `$m_i$` be the `$i$`-th bit of the message.
+
+- private key: A list of `$k$` random numbers `$R_i$`.
+
+- public key: Compute a list of `$k$` hashes `$P_i=H(R_i)$`;
+  the hash of this list is the public key.
+
+- sign: Reveal the `$R_i$` for `$i \\le b$` if the
+  `$m_i=0$`. Compute the checksum `$c=\\sum{m_i}$`,
+  and interpret as a bitstring. Reveal `$R_{b+i}$`
+  if the `$i$`-th bit of the bitstring is zero.
+
+- verify:
+
 Merkle-Winternitz
 -----------------
 
@@ -385,8 +405,6 @@
                $\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}{Reyzin 1st $(h,b,t,k)$ }
-           & $1$ & $b$ & $kh$ & $th$ & $h$ & $t$ & $?$ (XXX) & $?+k$ (XXX) \\
        \parbox{\sw}{Reyzin 2nd $(h,b,t,k)$ }
            & $1$ & $b$ & $kh$ & $th$ & $h$ & $t$ & $1$ (XXX) & $1+k$ (XXX) \\