[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 15:26:01 -0400 |
CVSROOT: /cvsroot/gzz
Module name: manuscripts
Changes by: Benja Fallenstein <address@hidden> 03/05/19 15:26:01
Modified files:
Sigs : article.rst
Log message:
update numbers
CVSWeb URLs:
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/manuscripts/Sigs/article.rst.diff?tr1=1.128&tr2=1.129&r1=text&r2=text
Patches:
Index: manuscripts/Sigs/article.rst
diff -u manuscripts/Sigs/article.rst:1.128 manuscripts/Sigs/article.rst:1.129
--- manuscripts/Sigs/article.rst:1.128 Mon May 19 15:03:39 2003
+++ manuscripts/Sigs/article.rst Mon May 19 15:26:00 2003
@@ -32,13 +32,13 @@
a high-security instance with
unlimited use, 160-bit security,
which requires
-a 110 KB signature, 175'072 hash invocations for signing, and
+a 110 KB signature, 201'952 hash function invocations for signing, and
5'568 hash invocations for verification.
On a more practical level, we discuss a
probabilistically valid instance with 56-bit security
if only used for up to XXX signatures.
The probabilistic scheme requires
-a 28 KB sig, 175'096 hash invocations for signing, 1'408 hashes
+a 42 KB sig, 75'732 hash invocations for signing, and 2'088 hashes
for verification.
Introduction
@@ -250,11 +250,16 @@
- impractical; actual numbers below
- - With key_boosting(32, merkle_hashtree(5, merkleI(160, 160)))::
+ - With key_boosting_real(32, 5, 160)::
- (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])
+ (q=2^160.0, b=160, s=110.0 KB,
+ r=20 B, h=20 B,
+ t0=6.31e+03 [~31.555ms],
+ ts=2.02e+05 [~1009.76ms],
+ tv=5.57e+03 [~27.84ms])
+
+The private keys in these schemes is only 160 bits long;
+the random oracle is used to generate all the other private keys.
- Maybe also mention:
@@ -276,18 +281,22 @@
requirements somewhat to obtain more practical schemes.
- For smaller sigs and faster verification,
- key_boosting(8, merkle_hashtree(7, merkleI(160, 160)))::
+ key_boosting_real(8, 7, 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])
+ (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])
- For faster signing,
- key_boosting(12, merkle_hashtree(5, merkleI(160, 160)))::
+ key_boosting_real(12, 5, 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])
+ (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])
This may be ok when using up to a million or so random keys
(XXX chance of a common birthday then?)
@@ -295,11 +304,13 @@
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)))::
+- key_boosting_real(5, 4, 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])
+ (q=2^20.0, b=160, s=17.08984375 KB,
+ r=20 B, h=20 B,
+ t0=3.41e+03 [~17.035ms],
+ ts=1.70e+04 [~85.175ms],
+ 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
- [Gzz-commits] manuscripts/Sigs article.rst, (continued)
- [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/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 <=
- [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/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