[Gzz-commits] manuscripts/Sigs article.rst

[Benja Fallenstein]

CVSROOT:        /cvsroot/gzz
Module name:    manuscripts
Changes by:     Benja Fallenstein <address@hidden>      03/05/19 20:18:02

Modified files:
        Sigs           : article.rst 

Log message:
        possibly-final readthrough

CVSWeb URLs:
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/manuscripts/Sigs/article.rst.diff?tr1=1.156&tr2=1.157&r1=text&r2=text

Patches:
Index: manuscripts/Sigs/article.rst
diff -u manuscripts/Sigs/article.rst:1.156 manuscripts/Sigs/article.rst:1.157
--- manuscripts/Sigs/article.rst:1.156  Mon May 19 19:47:22 2003
+++ manuscripts/Sigs/article.rst        Mon May 19 20:18:02 2003
@@ -41,7 +41,8 @@
 by [rabin78digitalized]_ and [lamport79constructing]_. Since then, numerous 
variations
 and improvements have been published 
 
[merkle80protocols-andalso-merkle87digital-andalso-bleichenbacheroptimal-andalso-perrig01biba-andalso-reyzin02better]_.
-Despite their limitations, one-way signatures have
+
+Despite their limitations, one-time signatures have
 attracted considerable interest because
 their operation does not rely on
 trapdoor functions, whose strength is based on
@@ -57,18 +58,16 @@
 The alternative, digital timestamping 
 [haber91timestamp-andalso-bayer92improving]_,
 adds additional complication because
-it needs a secure, trusted timestamping service.
+it requires a secure, trusted timestamping service.
 
 In this article, we introduce a new signature scheme,
 based on one-time signatures and a random oracle,
 that can be used any number of times without keeping track
 of private keys that have already been used.
-In the following Sections, we first 
+In the following sections, we first 
 review one-time signatures, and subsequently
 describe our algorithm. 
-Then, we analyze the tradeoffs in it and other one-time signature
-schemes. 
-After this, we discuss the different variants of our
+Then, we discuss the different variants of our
 algorithm based on how the path through the key tree
 is selected, and finally conclude.
 
@@ -79,7 +78,7 @@
 One-time signature schemes are based 
 on one-way functions, i.e., functions `$y=f(x)$` such
 as block ciphers or cryptographic hashes so that
-that given `$y$` it is infeasible to find `$x$`.
+given `$y$` it is infeasible to find `$x$`.
 Generally, given a one-way function f, the signer generates a set
 of (pseudo)random numbers and and publishes `$f(x)$` for each
 `$x$` in the set. This is the public key. To sign a message,
@@ -95,7 +94,7 @@
 published numbers to sign a different message,
 the deterministic algorithm is chosen so that no set
 in its range is a true subset of any other set in its range,
-or that finding such a pair of sets is infeasible.
+or that finding such a pair of sets is computationally infeasible.
 
 Private keys in one-time signature schemes can generally
 only be used to sign a single message. If the same key 
@@ -107,10 +106,10 @@
 becoming completely insecure 
 [perrig01biba-andalso-mitzenmacher-bounds-andalso-reyzin02better]_.
 
-Another way to allow n messages to be signed with the
-same public key is to create n different key pairs,
+Another way to allow `$q$` messages to be signed with the
+same public key is to create `$q$` different key pairs,
 and then compute a hash tree over the public keys.
-This is only practical for relatively small n.
+This is only practical for relatively small `$q$`.
 
 Yet another approach is to sign one or more new public keys
 as the last message signed with the old key. This way,
@@ -132,14 +131,16 @@
 Other choices such as BiBa [perrig01biba]_
 are possible, but not evaluated in this article.
 
-The private key for this scheme is simply a private key
-for the underlying one-time-signature primitive,
-and the public key is the corresponding one-time-signature 
+The private key for this scheme is a random number
+from which a private key for the underlying 
+one-time-signature primitive can be generated
+using the random oracle.
+The public key is the corresponding one-time-signature 
 public key.
 
 To generate a signature for the message `$m$`, 
-start by setting `$p$` to the
-private key.
+we first set `$p$` to the first private key
+generated by the random oracle.
 Then, we iterate over the following steps `$N$` times:
 
 1. Choose the tree branch `$x \\in [1,q]$`. 
@@ -148,7 +149,7 @@
    below.
 
 2. Use the random oracle to generate the `$x$th` new private key
-   `$p_x$` from `$p$`.
+   `$p_x$`, based on `$p$`.
 
 3. Sign the corresponding public key with `$p$`. This does
    not present
@@ -160,24 +161,27 @@
 4.  `$p \\leftarrow p_x$`
 
 After the last iteration, `$p$` contains the private key to be used to sign
-the actual message `$m$` using the one-time-signature primitive.
-The signature consists of this signature and the whole chain
-of signatures connecting this to the original public key.
+the actual message `$m$` with the one-time-signature primitive.
+Our scheme's signature consists of this signature, and the whole chain
+of signatures and public keys connecting this to the original public key.
 To verify a signature, the verifier only needs to traverse the
 chain of signatures from the public key to the last signature.
 
-As long as the algorithm for choosing `$x$` does not yield the same
-chain for two messages, the signatures will be no weaker than normal
-one-time signatures of the underlying scheme.
+The virtual tree has `$q^N$` one-time keys at the leaves 
+which can be used to sign individual messages.
 
 The length of the signature will be `$N$` times the length
-of a signatures and a public key in the underlying scheme.
+of a signature and a public key in the underlying scheme.
 The time to sign is also `$N$` times the time to generate a public
 key and sign in the
 underlying scheme, plus the accesses to the random oracle.
 The time to verify is also equal to the time of verifying `$N$` 
 signatures in the underlying scheme.
 
+As long as the algorithm for choosing `$x$` does not yield the same
+chain for two messages, the signatures will be no weaker than normal
+one-time signatures of the underlying scheme.
+
 *Security.* Assume that the underlying signature scheme
 is resistant against a `$q$`-time chosen message attack.
 Within the tree, each private key is only used to sign
@@ -199,12 +203,11 @@
 Our scheme has no time limits for private keys
 because its security
 is not based on complexity of inverting trapdoor functions;
-the scheme requires only that one-way functions and 
-random oracles exist.
+it requires only a hash function in the random oracle model.
 
 To our knowledge, this is has not previously been possible without
 remembering things about
-previously signed documents or changing to a new
+previously signed documents and changing to a new
 private key after a given number of signatures.
 Our scheme only requires the private key to be remembered; no other
 state is required.
@@ -216,9 +219,11 @@
 a unique private key for each 160-bit hash. 
 This is done by requiring that `$q^N \\ge 2^{160}$` and choosing
 `$x$` based on the bits of the hash to be signed.
+
 If we use Merkle hash trees to obtain the underlying `$q$`-time scheme
 from a one-time scheme, we have for the parameters of the two algorithms
 the inequality `$ nN \\ge 160 $`.
+
 Obtaining the minimal integral solutions of this inequality 
 gives us a tradeoff where the length of the signature is approximately
 linear with `$N$` and the time to sign grows exponentially with `$n$`.
@@ -249,7 +254,8 @@
     $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
+    and $t_0$, $t_s$ and $t_v$ are the number of 
+    hash function invocations necessary
     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
@@ -293,8 +299,9 @@
     ts=2.02e+05 [~1009.76ms], 
     tv=5.57e+03 [~27.84ms])
 
-The private keys in these schemes need only be 160 bits long;
-the random oracle can be used to generate all the other private keys.
+The private key in this scheme need only be 160 bits long;
+the random oracle can be used to generate 
+all the private keys of the Merkle signature scheme.
 
 
 Variants
@@ -378,16 +385,24 @@
 We have presented a new signature scheme with several benefits
 which, as far as we know, have not been embodied in the same
 algorithm so far.
+
+The key idea of the scheme is to use 
+a deterministic random oracle
+to define a huge virtual tree of private keys,
+of which one path is traversed to find the private key to
+use to sign a particular document.
+
 Our scheme uses
-no trapdoor funcs, so its security does not rely on 
+no trapdoor functions, so its security does not rely on 
 hardness of factoring or some other such problem.
 There is 
-no need for expiration of key or signature - keys don't
+no need for expiration of keys or signatures - keys don't
 degrade with use and cracking a signature seems to require
-a full search through the key space;
-there is also
+a full search through the key space.
+
+There is also
 no state beyond the private key: there is no need to keep track
-of signed documents.
+of the number of documents already signed.
 The scheme is existentially
 unforgeable with an adaptive chosen message attack since a different
 private key produced by the random oracle
@@ -400,16 +415,17 @@
 are inconvenient.
 
 The downsides of the present scheme are that
-signatures are relatively large and signing
-and verifying require considerably more time
+signatures are large and signing
+requires considerably more time
 than with other schemes. 
 While the presented instances of
 schemes are certainly feasible, and
 may be practical for some applications, 
-they are currently no replacement for normal digital signature
+they are currently no replacement for more usual digital signature
 algorithms.
-Additionally,
-considerable algorithmic improvements may be possible.
+
+.. Additionally,
+   considerable algorithmic improvements may be possible.
 
 Naturally, this scheme is not foolproof. Weaknesses in cryptographic
 hash functions may be found. Also, while
@@ -417,12 +433,6 @@
 signatures in practice do depend on a hash function for
 long messages, our demands for are stricter: the hash
 function must also be a random oracle.
-
-The key idea of the scheme is to use 
-a deterministic random oracle
-to define a huge virtual tree of private keys,
-of which one path is traversed to find the private key to
-use to sign a particular document.
 
 We believe that as long as the random oracle, 
 used to generate the new private keys