[Gzz-commits] manuscripts/Sigs article.rst

[Tuomas J. Lukka]

CVSROOT:        /cvsroot/gzz
Module name:    manuscripts
Changes by:     Tuomas J. Lukka <address@hidden>        03/05/18 06:33:04

Modified files:
        Sigs           : article.rst 

Log message:
        Morealgs

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

Patches:
Index: manuscripts/Sigs/article.rst
diff -u manuscripts/Sigs/article.rst:1.72 manuscripts/Sigs/article.rst:1.73
--- manuscripts/Sigs/article.rst:1.72   Sun May 18 05:05:37 2003
+++ manuscripts/Sigs/article.rst        Sun May 18 06:33:04 2003
@@ -133,6 +133,87 @@
 still needs to keep track of which private keys
 have already been used in order not to compromise security.
 
+XXX Following descriptions not into article, maybe into tech report?
+We need these to make sure our numbers are right
+
+Lamport
+-------
+
+- private key: `$2b$` random numbers
+
+- public key: hashes of private key - calculate `$2b$` hashes
+
+- sign: reveal one of each pair of RNs in private key corresponding to signing 
0 or 1
+  Signature contains `$b$` of the random numbers
+
+- verify: check that the revealed RNs hashes to right hash in public key - 
+  calculate `$b$` hashes
+
+Merkle-Winternitz
+-----------------
+
+?
+
+BiBa
+----
+
+?
+
+Reyzin
+------
+
+?
+
+Bleichenbacher-Maurer
+---------------------
+
+ASIACRYPTO construction
+
+- Construction for `$H_n$`: a binary tree,
+  at each node 2 hashes combined into one
+
+- private key: `$3(n+1)$` hash values of tree leaves.
+  Calculate `$9n+2$` hashes. This can sign
+  `$\\lfloor {\\log 51 \\over \\log 2} n \\rfloor$` bits.
+  (XXX Some were not allowable because not minimal???)
+
+- public key: one hash, the one calculated for the root of the tree
+
+- sign: message determines which nodes of the tree to reveal; 
+  Signature contains `$3(n+1)$` hashes.
+
+- verify: check that right nodes revealed, and that tree computes right
+  public key - calculate some less than `$9n+2$` hashes
+
+Merkle hash trees
+-----------------
+
+Sign `$2^n$` new public keys by signing one hash.
+
+Assume underlying algorithm using same hash.
+
+Signature using new public key will not need to contain all new public keys,
+only the tree.
+
+- private key: `$2^n + 1$` private keys of the underlying algorithm
+
+- public key: original public key. Also calculate off-line 
+  hashes of the `$2^n$` public keys, and a hash tree from them,
+  i.e. `$2^{n+1} - 1$` hashes in addition to calculating public
+  keys in the underlying algorithm.
+  Sign the original hash.
+  Altogether, calculate `$(2^n + 1) c_0' + c_s' + 2^{n+1}-1 $`
+  hashes
+  Signature contains the hashes and the new public key and the signature with 
it,
+  and the signature of the original hash.
+
+- sign using one key: Sign with that private key, and provide
+  hashes in the chain to the original signature with the
+  underlying public key in the signature.
+  Only hash invocations in the signing using the underlying algorithm.
+
+- verify: verify signature with new public key, verify hash chain and verify 
+  signature of hash tree root.
 
 
 One-time Signature Key Boosting
@@ -228,7 +309,7 @@
        \multicolumn{4}{l}{\hskip 2cm Primitives} \\
        \hline
        \parbox{\sw}{Lamport\cite{XXX}\\$(h,b)$} 
-           & $1$ & $b$ & $bh$ & $2bh$ & $h$ & $2b$ & $0$ &  $2b$ \\
+           & $1$ & $b$ & $bh$ & $2bh$ & $h$ & $2b$ & $0$ &  $b$ \\
        \parbox{\sw}{Merkle-Winternitz\cite{XXX} $(h,b,n)$ }
            & $1$ & $b$ & $\frac{bh}{n}+h$ & $h$ & $h$ &
                $2\frac{b}{n}(2^n-1)+1$ & $\frac{b}{n}(2^n-1)+1$ &
@@ -252,8 +333,12 @@
        \parbox{\sw}{Merkle hash tree \cite{XXX} 
        % XXX check this again
        ($n, S'$) }
-           & ${2^n}q'$ & $b$ & $s'+r'+hn$ & $h$ & $h$ & 
-               ${2^n}c_0'+2^{n+1}-1$ & $c_s'+n$ & $c_v'+n$ \\
+           & ${2^n}q'$ 
+               & $b$ & $2s'+r'+hn$ 
+                           & $h$ & $h$ & 
+                                       $({2^n}+1)c_0'+c_s' + 2^{n+1}-1$ & 
+                                                $c_s'$ &
+                                                       $2c_v'+n$ \\
        \parbox{\sw}{Key boosting $(N, S')$ }
            & ${q'}^N$ & $b$ & $N(r'+s')$ & $r'$ & $h$ &
                $c_0'$ & $N(c_0'+c_s')$ & $Nc_v$ \\