[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Gzz-commits] manuscripts/Sigs article.rst
From: |
Tuomas J. Lukka |
Subject: |
[Gzz-commits] manuscripts/Sigs article.rst |
Date: |
Sat, 17 May 2003 11:51:42 -0400 |
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
===================================
- [Gzz-commits] manuscripts/Sigs article.rst, (continued)
- [Gzz-commits] manuscripts/Sigs article.rst, Tuomas J. Lukka, 2003/05/17
- [Gzz-commits] manuscripts/Sigs article.rst, Tuomas J. Lukka, 2003/05/17
- [Gzz-commits] manuscripts/Sigs article.rst, Tuomas J. Lukka, 2003/05/17
- [Gzz-commits] manuscripts/Sigs article.rst, Tuomas J. Lukka, 2003/05/17
- [Gzz-commits] manuscripts/Sigs article.rst, Tuomas J. Lukka, 2003/05/17
- [Gzz-commits] manuscripts/Sigs article.rst, Tuomas J. Lukka, 2003/05/17
- [Gzz-commits] manuscripts/Sigs article.rst, Tuomas J. Lukka, 2003/05/17
- [Gzz-commits] manuscripts/Sigs article.rst, Tuomas J. Lukka, 2003/05/17
- [Gzz-commits] manuscripts/Sigs article.rst, Tuomas J. Lukka, 2003/05/17
- [Gzz-commits] manuscripts/Sigs article.rst, Tuomas J. Lukka, 2003/05/17
- [Gzz-commits] manuscripts/Sigs article.rst,
Tuomas J. Lukka <=
- [Gzz-commits] manuscripts/Sigs article.rst, Benja Fallenstein, 2003/05/17
- [Gzz-commits] manuscripts/Sigs article.rst, Benja Fallenstein, 2003/05/17
- [Gzz-commits] manuscripts/Sigs article.rst, Benja Fallenstein, 2003/05/17
- [Gzz-commits] manuscripts/Sigs article.rst, Tuomas J. Lukka, 2003/05/17
- [Gzz-commits] manuscripts/Sigs article.rst, Benja Fallenstein, 2003/05/17
- [Gzz-commits] manuscripts/Sigs article.rst, Benja Fallenstein, 2003/05/17
- [Gzz-commits] manuscripts/Sigs article.rst, Benja Fallenstein, 2003/05/17
- [Gzz-commits] manuscripts/Sigs article.rst, Tuomas J. Lukka, 2003/05/17
- [Gzz-commits] manuscripts/Sigs article.rst, Tuomas J. Lukka, 2003/05/17
- [Gzz-commits] manuscripts/Sigs article.rst, Tuomas J. Lukka, 2003/05/17