[Gzz-commits] manuscripts/Sigs article.rst

[Benja Fallenstein]

CVSROOT:        /cvsroot/gzz
Module name:    manuscripts
Changes by:     Benja Fallenstein <address@hidden>      03/05/18 10:58:15

Modified files:
        Sigs           : article.rst 

Log message:
        Merkle-Winternitz

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

Patches:
Index: manuscripts/Sigs/article.rst
diff -u manuscripts/Sigs/article.rst:1.76 manuscripts/Sigs/article.rst:1.77
--- manuscripts/Sigs/article.rst:1.76   Sun May 18 08:28:33 2003
+++ manuscripts/Sigs/article.rst        Sun May 18 10:58:15 2003
@@ -152,7 +152,36 @@
 Merkle-Winternitz
 -----------------
 
-?
+This scheme relies on recursive application of the hash function.
+Let `$n$` be a positive integer and `$k=\\frac{b}{n}$`.
+Let `$H$` donate the hash function, with `$H^2(x)=H(H(x))$` etc.
+
+- private key: A list of random numbers `$(R_0,...,R_k)$`.
+
+- public key: Compute `$P_0=H^{k2^n}(R_0)$`, and
+  `$P_i=H^{2^n}(R_i)$` for `$i>0$`. The hash of
+  `$(P_0,...,P_k)$` is the public key.
+
+  Needs `$2k2^n + 1$` hash function invocations.
+
+- signature: Split the `$b$`-bit message into `$k$` 
+  parts of `$n$` bits each. Interpreted each part
+  as an integer `$k_i$` for `$0 < i \\le k$`.
+  Compute `$S_i=H^{k_i}(R_i)$` for `$i>0$`
+  and `$S_0=H^{2^nk-\\sum{k_i}}(R_0)$`. The tuple
+  `$(S_0,...,S_k)$` is the signature.
+
+  Signing requires `$k2^n$` invocations
+  of the hash function.
+
+- verification: Compute `$k_i$` as above.
+  Compute `$V_0=H^{\\sum{k_i}}(S_0)$`
+  and `$V_i=H^{2^n-k_i}(S_i)$` for `$i>0$`.
+  Check that the hash of `$(V_0,...,V_i)$`
+  equals the public key.
+
+  Verification requires `$k2^n + 1$` invocations
+  of the hash function.
 
 BiBa
 ----