[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Gzz-commits] manuscripts/Sigs article.rst
From: |
Benja Fallenstein |
Subject: |
[Gzz-commits] manuscripts/Sigs article.rst |
Date: |
Mon, 19 May 2003 14:35:30 -0400 |
CVSROOT: /cvsroot/gzz
Module name: manuscripts
Changes by: Benja Fallenstein <address@hidden> 03/05/19 14:35:30
Modified files:
Sigs : article.rst
Log message:
skeleton of practical variants section
CVSWeb URLs:
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/manuscripts/Sigs/article.rst.diff?tr1=1.119&tr2=1.120&r1=text&r2=text
Patches:
Index: manuscripts/Sigs/article.rst
diff -u manuscripts/Sigs/article.rst:1.119 manuscripts/Sigs/article.rst:1.120
--- manuscripts/Sigs/article.rst:1.119 Mon May 19 14:08:02 2003
+++ manuscripts/Sigs/article.rst Mon May 19 14:35:30 2003
@@ -52,7 +52,7 @@
- with p XXX safe to sign up to XXX docs
- - 28 KB sig, 175'096 hashes to create, 1408 hashes to verify
+ - 28 KB sig, 175'096 hashes to create, 1'408 hashes to verify
- we discuss applications
@@ -265,18 +265,52 @@
- impractical; actual numbers below
- - Works with `$k=10$`, `$N=16$` for SHA-1; sig length
- is about `$16(r'+s')$`; realistically, about
- 25KB using Merkle-Winternitz with `$n=2$`.
+ - With key_boosting(32, merkle_hashtree(5, merkleI(160, 160)))::
- Formally, this is:
- Key boosting(16, Merkle hash tree(10, Merkle-Winternitz(160,160,2),
10))
-
- and has the octuplet??
+ (q=2^160.0, b=160, s=110.0 KB, r=20 B, h=20 B,
+ t0=5.47e+03 [~27.355ms], ts=1.75e+05 [~875.36ms],
+ tv=5.57e+03 [~27.84ms])
Practical Variants
==================
+
+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(8, merkle_hashtree(7, merkleI(160, 160)))::
+
+ (q=2^56.0, b=160, s=27.8125 KB, r=20 B, h=20 B,
+ t0=2.19e+04 [~109.435ms], ts=1.75e+05 [~875.48ms],
+ tv=1.41e+03 [~7.04ms])
+
+- For faster signing,
+ key_boosting(12, merkle_hashtree(5, merkleI(160, 160)))::
+
+ (q=2^60.0, b=160, s=41.25 KB, r=20 B, h=20 B,
+ t0=5.47e+03 [~27.355ms], ts=6.57e+04 [~328.26ms],
+ tv=2.09e+03 [~10.44ms])
+
+This may be ok when using up to a million or so random keys
+(XXX chance of a common birthday then?)
+
+It is also possible to use key boosting to form `$k$`-time
+signature schemes for large `$k$`. For example, for `$k=2^20$`:
+
+- key_boosting(5, merkle_hashtree(4, merkleI(160, 160)))::
+
+ (q=2^20.0, b=160, s=17.08984375 KB, r=20 B, h=20 B,
+ t0=2.74e+03 [~13.675ms], ts=1.37e+04 [~68.375ms],
+ tv=8.65e+02 [~4.325ms])
+
+Of course, there is the common technique to create a tree
+of one-time signatures, where each key at the top signs
+a number of keys below it. Using our scheme is only a variant,
+which may be somewhat more convenient sometimes because
+it only requires storing the number of keys already used,
+not a whole tree of private keys.
+
Conclusion
==========
- [Gzz-commits] manuscripts/Sigs article.rst, (continued)
- [Gzz-commits] manuscripts/Sigs article.rst, Tuomas J. Lukka, 2003/05/18
- [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, 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, Benja Fallenstein, 2003/05/19
- [Gzz-commits] manuscripts/Sigs article.rst,
Benja Fallenstein <=
- [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, 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