[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: |
Sun, 18 May 2003 06:33:04 -0400 |
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$ \\
- [Gzz-commits] manuscripts/Sigs article.rst, (continued)
- [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, 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
- [Gzz-commits] manuscripts/Sigs article.rst, Benja Fallenstein, 2003/05/17
- [Gzz-commits] manuscripts/Sigs article.rst, Tuomas J. Lukka, 2003/05/18
- [Gzz-commits] manuscripts/Sigs article.rst,
Tuomas J. Lukka <=
- [Gzz-commits] manuscripts/Sigs article.rst, Benja Fallenstein, 2003/05/18
- [Gzz-commits] manuscripts/Sigs article.rst, Tuomas J. Lukka, 2003/05/18
- [Gzz-commits] manuscripts/Sigs article.rst, Benja Fallenstein, 2003/05/18
- [Gzz-commits] manuscripts/Sigs article.rst, Benja Fallenstein, 2003/05/18
- [Gzz-commits] manuscripts/Sigs article.rst, Benja Fallenstein, 2003/05/18
- [Gzz-commits] manuscripts/Sigs article.rst, Benja Fallenstein, 2003/05/18
- [Gzz-commits] manuscripts/Sigs article.rst, Tuomas J. Lukka, 2003/05/18
- [Gzz-commits] manuscripts/Sigs article.rst, Tuomas J. Lukka, 2003/05/18
- [Gzz-commits] manuscripts/Sigs article.rst, Tuomas J. Lukka, 2003/05/18
- [Gzz-commits] manuscripts/Sigs article.rst, Benja Fallenstein, 2003/05/18