gzz-commits
[Top][All Lists]

## [Gzz-commits] manuscripts/Sigs article.rst kbmhtrade.tex poss.py

 From: Tuomas J. Lukka Subject: [Gzz-commits] manuscripts/Sigs article.rst kbmhtrade.tex poss.py Date: Mon, 19 May 2003 12:18:08 -0400

CVSROOT:        /cvsroot/gzz
Module name:    manuscripts
Changes by:     Tuomas J. Lukka <address@hidden>        03/05/19 12:18:08

Modified files:

Log message:

CVSWeb URLs:
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/manuscripts/Sigs/article.rst.diff?tr1=1.111&tr2=1.112&r1=text&r2=text
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/manuscripts/Sigs/poss.py.diff?tr1=1.13&tr2=1.14&r1=text&r2=text

Patches:
Index: manuscripts/Sigs/article.rst
diff -u manuscripts/Sigs/article.rst:1.111 manuscripts/Sigs/article.rst:1.112
--- manuscripts/Sigs/article.rst:1.111  Mon May 19 11:58:31 2003
+++ manuscripts/Sigs/article.rst        Mon May 19 12:18:08 2003
@@ -200,10 +200,33 @@

..  raw:: latex

+    \begin{table*}
\begin{tabular}{rr|rrrr}
-    $N$ & $n$ & $s$ & $t_0$ & $t_s$ & $t_v$ \\
+    $N$ & $n$ & \multicolumn{1}{c}{$s'$} &
+               \multicolumn{1}{c}{$t_0'$} &
+               \multicolumn{1}{c}{$t_s'$} &
+               \multicolumn{1}{c}{$t_v'$} \\
+    \hline
+    \hline
\end{tabular}
+    \caption{The tradeoff between rounds of key boosting
+    and branching factor when using key boosting
+    and Merkle hash trees to
+    obtain the full digital signature feature set
+    for 160 bits.
+    Notation: $N$ is the number of rounds of key boosting,
+    and $n$ is the merkle hash tree degree;
+    $s$ is the length of a signature in the underlying
+    algorithm, $k$ is the length of a public key in the underlying
+    algorithm, and $h$ is the number of bits in a hash (i.e. 160).
+    and $t_0$, $t_s$ and $t_v$ are the times
+    to generate a public key, to sign and to verify a signature
+    in the underlying scheme, respectively.
+    The primed symbols signify the same things for the derived
+    scheme.
+    }
+    \end{table*}

For example,

--- manuscripts/Sigs/kbmhtrade.tex:1.1  Mon May 19 11:58:31 2003
+++ manuscripts/Sigs/kbmhtrade.tex      Mon May 19 12:18:08 2003
@@ -1,23 +1,23 @@
-2 & 80 & $2 s' + 2 k' + 162 h$ & $1208925819614629174706176 t_0' + 2417851639229258349412351$ & $2417851639229258349412352 t_0' + 2 t_s' + 4835703278458516698824702$ & $2 t_v' + 162$ \
-3 & 54 & $3 s' + 3 k' + 165 h$ & $18014398509481984 t_0' + 36028797018963967$
& $54043195528445952 t_0' + 3 t_s' + 108086391056891901$ & $3 t_v' + 165$ \
-4 & 40 & $4 s' + 4 k' + 164 h$ & $1099511627776 t_0' + 2199023255551$ &
$4398046511104 t_0' + 4 t_s' + 8796093022204$ & $4 t_v' + 164$ \
-5 & 32 & $5 s' + 5 k' + 165 h$ & $4294967296 t_0' + 8589934591$ &
$21474836480 t_0' + 5 t_s' + 42949672955$ & $5 t_v' + 165$ \
-6 & 27 & $6 s' + 6 k' + 168 h$ & $134217728 t_0' + 268435455$ & $805306368 t_0' + 6 t_s' + 1610612730$ & $6 t_v' + 168$ \
-7 & 23 & $7 s' + 7 k' + 168 h$ & $8388608 t_0' + 16777215$ & $58720256 t_0' + 7 t_s' + 117440505$ & $7 t_v' + 168$ \
-8 & 20 & $8 s' + 8 k' + 168 h$ & $1048576 t_0' + 2097151$ & $8388608 t_0' + 8 t_s' + 16777208$ & $8 t_v' + 168$ \
-9 & 18 & $9 s' + 9 k' + 171 h$ & $262144 t_0' + 524287$ & $2359296 t_0' + 9 t_s' + 4718583$ & $9 t_v' + 171$ \
-10 & 16 & $10 s' + 10 k' + 170 h$ & $65536 t_0' + 131071$ & $655360 t_0' + 10 t_s' + 1310710$ & $10 t_v' + 170$ \
-11 & 15 & $11 s' + 11 k' + 176 h$ & $32768 t_0' + 65535$ & $360448 t_0' + 11 t_s' + 720885$ & $11 t_v' + 176$ \
-12 & 14 & $12 s' + 12 k' + 180 h$ & $16384 t_0' + 32767$ & $196608 t_0' + 12 t_s' + 393204$ & $12 t_v' + 180$ \
-13 & 13 & $13 s' + 13 k' + 182 h$ & $8192 t_0' + 16383$ & $106496 t_0' + 13 t_s' + 212979$ & $13 t_v' + 182$ \
-14 & 12 & $14 s' + 14 k' + 182 h$ & $4096 t_0' + 8191$ & $57344 t_0' + 14 t_s' + 114674$ & $14 t_v' + 182$ \
-15 & 11 & $15 s' + 15 k' + 180 h$ & $2048 t_0' + 4095$ & $30720 t_0' + 15 t_s' + 61425$ & $15 t_v' + 180$ \
-16 & 10 & $16 s' + 16 k' + 176 h$ & $1024 t_0' + 2047$ & $16384 t_0' + 16 t_s' + 32752$ & $16 t_v' + 176$ \
-18 & 9 & $18 s' + 18 k' + 180 h$ & $512 t_0' + 1023$ & $9216 t_0' + 18 t_s' + 18414$ & $18 t_v' + 180$ \
-20 & 8 & $20 s' + 20 k' + 180 h$ & $256 t_0' + 511$ & $5120 t_0' + 20 t_s' + 10220$ & $20 t_v' + 180$ \
-23 & 7 & $23 s' + 23 k' + 184 h$ & $128 t_0' + 255$ & $2944 t_0' + 23 t_s' + 5865$ & $23 t_v' + 184$ \
-27 & 6 & $27 s' + 27 k' + 189 h$ & $64 t_0' + 127$ & $1728 t_0' + 27 t_s' + 3429$ & $27 t_v' + 189$ \
-32 & 5 & $32 s' + 32 k' + 192 h$ & $32 t_0' + 63$ & $1024 t_0' + 32 t_s' + 2016$ & $32 t_v' + 192$ \
-40 & 4 & $40 s' + 40 k' + 200 h$ & $16 t_0' + 31$ & $640 t_0' + 40 t_s' + 1240$ & $40 t_v' + 200$ \
-54 & 3 & $54 s' + 54 k' + 216 h$ & $8 t_0' + 15$ & $432 t_0' + 54 t_s' + 810$ & $54 t_v' + 216$ \
-80 & 2 & $80 s' + 80 k' + 240 h$ & $4 t_0' + 7$ & $320 t_0' + 80 t_s' + 560$
& $80 t_v' + 240$ \
+2 & 80 & $2 s + 2 k + 164 h$ & $1.21\cdot 10^{24} t_0 + 2.42\cdot 10^{24}$ &
$2.42\cdot 10^{24} t_0 + 2 t_s + 4.84\cdot 10^{24}$ & $2 t_v + 162$ \\
+3 & 54 & $3 s + 3 k + 168 h$ & $1.8\cdot 10^{16} t_0 + 3.6\cdot 10^{16}$ &
$5.4\cdot 10^{16} t_0 + 3 t_s + 1.08\cdot 10^{17}$ & $3 t_v + 165$ \\
+4 & 40 & $4 s + 4 k + 168 h$ & $1.1\cdot 10^{12} t_0 + 2.2\cdot 10^{12}$ &
$4.4\cdot 10^{12} t_0 + 4 t_s + 8.8\cdot 10^{12}$ & $4 t_v + 164$ \\
+5 & 32 & $5 s + 5 k + 170 h$ & $4.29\cdot 10^{9} t_0 + 8.59\cdot 10^{9}$ &
$2.15\cdot 10^{10} t_0 + 5 t_s + 4.29\cdot 10^{10}$ & $5 t_v + 165$ \\
+6 & 27 & $6 s + 6 k + 174 h$ & $1.34\cdot 10^{8} t_0 + 2.68\cdot 10^{8}$ &
$8.05\cdot 10^{8} t_0 + 6 t_s + 1.61\cdot 10^{9}$ & $6 t_v + 168$ \\
+7 & 23 & $7 s + 7 k + 175 h$ & $8.39\cdot 10^{6} t_0 + 1.68\cdot 10^{7}$ &
$5.87\cdot 10^{7} t_0 + 7 t_s + 1.17\cdot 10^{8}$ & $7 t_v + 168$ \\
+8 & 20 & $8 s + 8 k + 176 h$ & $1.05\cdot 10^{6} t_0 + 2.1\cdot 10^{6}$ &
$8.39\cdot 10^{6} t_0 + 8 t_s + 1.68\cdot 10^{7}$ & $8 t_v + 168$ \\
+9 & 18 & $9 s + 9 k + 180 h$ & $262144 t_0 + 524287$ & $2.36\cdot 10^{6} t_0 + 9 t_s + 4.72\cdot 10^{6}$ & $9 t_v + 171$ \\
+10 & 16 & $10 s + 10 k + 180 h$ & $65536 t_0 + 131071$ & $655360 t_0 + 10 t_s + 1.31\cdot 10^{6}$ & $10 t_v + 170$ \\
+11 & 15 & $11 s + 11 k + 187 h$ & $32768 t_0 + 65535$ & $360448 t_0 + 11 t_s + 720885$ & $11 t_v + 176$ \\
+12 & 14 & $12 s + 12 k + 192 h$ & $16384 t_0 + 32767$ & $196608 t_0 + 12 t_s + 393204$ & $12 t_v + 180$ \\
+13 & 13 & $13 s + 13 k + 195 h$ & $8192 t_0 + 16383$ & $106496 t_0 + 13 t_s + 212979$ & $13 t_v + 182$ \\
+14 & 12 & $14 s + 14 k + 196 h$ & $4096 t_0 + 8191$ & $57344 t_0 + 14 t_s + 114674$ & $14 t_v + 182$ \\
+15 & 11 & $15 s + 15 k + 195 h$ & $2048 t_0 + 4095$ & $30720 t_0 + 15 t_s + 61425$ & $15 t_v + 180$ \\
+16 & 10 & $16 s + 16 k + 192 h$ & $1024 t_0 + 2047$ & $16384 t_0 + 16 t_s + 32752$ & $16 t_v + 176$ \\
+18 & 9 & $18 s + 18 k + 198 h$ & $512 t_0 + 1023$ & $9216 t_0 + 18 t_s + 18414$ & $18 t_v + 180$ \\
+20 & 8 & $20 s + 20 k + 200 h$ & $256 t_0 + 511$ & $5120 t_0 + 20 t_s + 10220$ & $20 t_v + 180$ \\
+23 & 7 & $23 s + 23 k + 207 h$ & $128 t_0 + 255$ & $2944 t_0 + 23 t_s + 5865$ & $23 t_v + 184$ \\
+27 & 6 & $27 s + 27 k + 216 h$ & $64 t_0 + 127$ & $1728 t_0 + 27 t_s + 3429$
& $27 t_v + 189$ \\
+32 & 5 & $32 s + 32 k + 224 h$ & $32 t_0 + 63$ & $1024 t_0 + 32 t_s + 2016$
& $32 t_v + 192$ \\
+40 & 4 & $40 s + 40 k + 240 h$ & $16 t_0 + 31$ & $640 t_0 + 40 t_s + 1240$ &
$40 t_v + 200$ \\
+54 & 3 & $54 s + 54 k + 270 h$ & $8 t_0 + 15$ & $432 t_0 + 54 t_s + 810$ &
$54 t_v + 216$ \\
+80 & 2 & $80 s + 80 k + 320 h$ & $4 t_0 + 7$ & $320 t_0 + 80 t_s + 560$ &
$80 t_v + 240$ \\
Index: manuscripts/Sigs/poss.py
diff -u manuscripts/Sigs/poss.py:1.13 manuscripts/Sigs/poss.py:1.14
--- manuscripts/Sigs/poss.py:1.13       Mon May 19 11:58:31 2003
+++ manuscripts/Sigs/poss.py    Mon May 19 12:18:08 2003
@@ -41,7 +41,7 @@

def merkle_hashtree(n, S):
return (2L**n * S[0], S[1],
-               S[2] + S[3] + n * S[4],
+               S[2] + S[3] + (n+1) * S[4],
S[4],
S[4],
2L**n * S[5] + 2L**(n+1) - 1,