[Gzz-commits] manuscripts/Sigs article.rst

[Tuomas J. Lukka]

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