[Gzz-commits] manuscripts/Sigs article.rst

[Tuomas J. Lukka]

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

Modified files:
        Sigs           : article.rst 

Log message:
        more

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

Patches:
Index: manuscripts/Sigs/article.rst
diff -u manuscripts/Sigs/article.rst:1.29 manuscripts/Sigs/article.rst:1.30
--- manuscripts/Sigs/article.rst:1.29   Sat May 17 11:27:28 2003
+++ manuscripts/Sigs/article.rst        Sat May 17 11:51:42 2003
@@ -188,6 +188,9 @@
 Analysis
 ========
 
+Characterizing one-time signature schemes
+-----------------------------------------
+
 We shall characterize the underlying one-time signature scheme by
 a octuplet `$(q, b, s, r, h, c_0, c_s, c_v)$`, where
 `$q$` is the number of messages a single private key can be used to sign,
@@ -200,11 +203,6 @@
 and
 `$c_v$` is the number of invocations of the hash function when verifying.
 
-There are three parameters to the one-time signature key boosting algorithm:
-`$N$`, the number of levels in the private key tree,
-`$k$`, the branching factor of the tree, and
-the algorithm for choosing `$x$`.
-
 ..  raw:: latex
 
     \begin{table*}
@@ -221,6 +219,14 @@
     }
     \end{table*}
 
+Effect of boosting
+------------------
+
+There are three parameters to the one-time signature key boosting algorithm:
+`$N$`, the number of levels in the private key tree,
+`$k$`, the branching factor of the tree, and
+the algorithm for choosing `$x$`.
+
 - given `$N$` and `$k$`, there are `$k^N$` 
   possible private keys for signing messages.
 
@@ -236,15 +242,41 @@
 
     - hash of hashes, publish one public key and hashes of others:
       contributes `$s + r + (k-1)h$` bits to sig and 
-      `$k+1$` extra hashes to `$c_s$` and `$c_v$`.
+      `$k+1$` extra hashes to `$c_s$` and two to `$c_v$`.
 
     - tree of hashes, publish one public key and hashes of tree branches:
       contributes `$s + r + h \\log k$` bits to sig and
-      `$2k-1$` extra hashes to `$c_s$` and `$c_v$`.
+      `$2k-1$` extra hashes to `$c_s$` and `$k-1$` to `$c_v$`.
+
+
+- Our scheme, in the third alternative, maps a scheme 
+  `$(1, b,   s,                        r, h, c_0, c_s,           c_v)$` to
+  `$(k^N, b, s + N(s + r + h \\log k), r, h, c_0, c_s + N(2k-1), c_v + 
N(k-1))$`
+
+- the first levels of signatures may be given in the public key,
+  giving a tradeoff between public key size and signature size.
+
+Choice of `$x$`
+---------------
+
+- Arbitrary (pseudo-infinite, i.e. infinite wouldn't help any more) 
+  number of keys, if for each *hash* its own private key for signing it!
+  This means that `$N \\log k \ge h$`
+
+    - this is a nice theoretical result: it *is* possible to sign anything
+      without trapdoors
+
+    - realistic? How much does this need?
+
+- If less, cannot use information from hash directly, otherwise can attack
+  by giving close relatives
+
+  - except! Algorithm for choosing `$x$` need not be public. If we hash
+    a different private key plus the content hash or content of the 
information,
+    we *can* use it here; random oracle 
 
+    - birthday paradox; if collision, someone can forge a signature
 
-Also, the first levels of signatures may be given in the public key,
-giving a tradeoff between public key size and signature size.
 
 Applicability to Digital Publishing
 ===================================