[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: |
Mon, 19 May 2003 18:02:32 -0400 |
CVSROOT: /cvsroot/gzz
Module name: manuscripts
Changes by: Tuomas J. Lukka <address@hidden> 03/05/19 18:02:31
Modified files:
Sigs : article.rst
Log message:
text
CVSWeb URLs:
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/manuscripts/Sigs/article.rst.diff?tr1=1.149&tr2=1.150&r1=text&r2=text
Patches:
Index: manuscripts/Sigs/article.rst
diff -u manuscripts/Sigs/article.rst:1.149 manuscripts/Sigs/article.rst:1.150
--- manuscripts/Sigs/article.rst:1.149 Mon May 19 18:00:46 2003
+++ manuscripts/Sigs/article.rst Mon May 19 18:02:31 2003
@@ -278,9 +278,13 @@
\end{table*}
For example, using the Merkle signature scheme [XXX],
+with X long sigs and X ...
+
+
with `$N=32$` and `$n=5$` and a 160-bit hash,
we obtain a signature scheme
-with 110.0KB signatures and `$2.1\cdot 10^{5}$`
+with 110.0KB signatures and uses
+`$2.1\cdot 10^{5}$`
hash invocations for signing and `$5.6\cdot 10^3$`
hash invocations for verification.
Using SHA-1, we obtained the estimated times 1s and 30ms
@@ -304,26 +308,54 @@
In practice, it may be useful to relax the security
requirements somewhat to obtain more practical schemes.
-- For smaller sigs and faster verification,
- key_boosting_real(8, 7, 160)::
+For smaller signatures and faster verification,
+we can set `$N=8$` and `$n=7$` to obtain a scheme
+with `$2^{56}$` distinct private keys for signing documents,
+which produces
+28KB signatures, and uses
+`$1.9\cdot 10^{5}$`
+hash invocations for signing and `$1.4\cdot 10^3$`
+hash invocations for verification.
+
+
+
+.. key_boosting_real(8, 7, 160)
(q=2^56.0, b=160, s=27.8125 KB,
- r=20 B, h=20 B,
- t0=2.31e+04 [~115.315ms],
- ts=1.85e+05 [~922.52ms],
- tv=1.41e+03 [~7.04ms])
+ r=20 B, h=20 B,
+ t0=2.31e+04 [~115.315ms],
+ ts=1.85e+05 [~922.52ms],
+ tv=1.41e+03 [~7.04ms])
+
+If faster signing is desirable,
+we can set `$N=12$` and `$n=5$` to obtain a scheme
+with `$2^{60}$` distinct private keys.
+This scheme produces
+41KB signatures, and uses
+`$7.6\cdot 10^{4}$`
+hash invocations for signing and `$2.1\cdot 10^3$`
+hash invocations for verification.
-- For faster signing,
- key_boosting_real(12, 5, 160)::
+.. For faster signing,
+ key_boosting_real(12, 5, 160)
(q=2^60.0, b=160, s=41.25 KB,
- r=20 B, h=20 B,
- t0=6.31e+03 [~31.555ms],
- ts=7.57e+04 [~378.66ms],
- tv=2.09e+03 [~10.44ms])
+ r=20 B, h=20 B,
+ t0=6.31e+03 [~31.555ms],
+ ts=7.57e+04 [~378.66ms],
+ tv=2.09e+03 [~10.44ms])
-These may be used freely, bounded only by the birthday
-paradox collision probability within the number of keys
+If the first message hash bits are directly used
+as the bits for the choise of `$x$`, the
+algorithm becomes
+vulnerable to adaptive chosen-message plaintext.
+An easy way around this is to use the private key as salt
+for the selection of `$x$`.
+
+With this caveat, these smaller schemes
+are only bounded by the birthday
+paradox collision probability within the number of distinct
+private keys
defined in the virtual tree.
It is also possible to use key boosting to form `$k$`-time
- [Gzz-commits] manuscripts/Sigs article.rst, (continued)
- [Gzz-commits] manuscripts/Sigs article.rst, Benja Fallenstein, 2003/05/19
- [Gzz-commits] manuscripts/Sigs article.rst, Benja Fallenstein, 2003/05/19
- [Gzz-commits] manuscripts/Sigs article.rst, Tuomas J. Lukka, 2003/05/19
- [Gzz-commits] manuscripts/Sigs article.rst, Benja Fallenstein, 2003/05/19
- [Gzz-commits] manuscripts/Sigs article.rst, Tuomas J. Lukka, 2003/05/19
- [Gzz-commits] manuscripts/Sigs article.rst, Tuomas J. Lukka, 2003/05/19
- [Gzz-commits] manuscripts/Sigs article.rst, Tuomas J. Lukka, 2003/05/19
- [Gzz-commits] manuscripts/Sigs article.rst, Tuomas J. Lukka, 2003/05/19
- [Gzz-commits] manuscripts/Sigs article.rst, Tuomas J. Lukka, 2003/05/19
- [Gzz-commits] manuscripts/Sigs article.rst, Tuomas J. Lukka, 2003/05/19
- [Gzz-commits] manuscripts/Sigs article.rst,
Tuomas J. Lukka <=
- [Gzz-commits] manuscripts/Sigs article.rst, Tuomas J. Lukka, 2003/05/19
- [Gzz-commits] manuscripts/Sigs article.rst, Benja Fallenstein, 2003/05/19
- [Gzz-commits] manuscripts/Sigs article.rst, Tuomas J. Lukka, 2003/05/19
- [Gzz-commits] manuscripts/Sigs article.rst, Benja Fallenstein, 2003/05/19
- [Gzz-commits] manuscripts/Sigs article.rst, Benja Fallenstein, 2003/05/19
- [Gzz-commits] manuscripts/Sigs article.rst, Benja Fallenstein, 2003/05/19
- [Gzz-commits] manuscripts/Sigs article.rst, Tuomas J. Lukka, 2003/05/19
- [Gzz-commits] manuscripts/Sigs article.rst, Tuomas J. Lukka, 2003/05/20
- [Gzz-commits] manuscripts/Sigs article.rst, Tuomas J. Lukka, 2003/05/20