[Gzz-commits] manuscripts/Sigs article.rst internal.rst

[Tuomas J. Lukka]

CVSROOT:        /cvsroot/gzz
Module name:    manuscripts
Changes by:     Tuomas J. Lukka <address@hidden>        03/05/19 11:06:00

Modified files:
        Sigs           : article.rst internal.rst 

Log message:
        more

CVSWeb URLs:
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/manuscripts/Sigs/article.rst.diff?tr1=1.108&tr2=1.109&r1=text&r2=text
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/manuscripts/Sigs/internal.rst.diff?tr1=1.1&tr2=1.2&r1=text&r2=text

Patches:
Index: manuscripts/Sigs/article.rst
diff -u manuscripts/Sigs/article.rst:1.108 manuscripts/Sigs/article.rst:1.109
--- manuscripts/Sigs/article.rst:1.108  Mon May 19 09:40:36 2003
+++ manuscripts/Sigs/article.rst        Mon May 19 11:05:59 2003
@@ -1,6 +1,6 @@
-===============================
-One-time Signature Key Boosting
-===============================
+==============================================================================================
+One-time Signature Key Boosting: Full Digital Signature Feature Set without 
Trapdoor Functions
+==============================================================================================
 
 ..  Benja: I'm restarting the writing.
 
@@ -11,18 +11,219 @@
 
     I'm sure the referees will tell us if we should review them...
 
+Abstract:
+
+- Full DS feature set
+
+- unlimited time
+
+- hash function strength, no unproven complexity results
+
+- In conjunction with Merkle hash trees, used to generate
+  a family of trade-offed schemes whose time and space characteristics
+  depend linearly on the underlying schemes'.
+
+- recursive application of 
+
+
 
 Introduction
 ============
 
+One-time signatures were originally proposed independently
+by [XXX] and [XXX]. Since then, numerous variations
+and improvements have been published [XXX].
+Despite their limitations, one-way signatures have
+attracted considerable interest because
+their operation 
+does not
+rely on
+trapdoor functions, whose strength is based on
+unproven number-theoretic assumptions such as the
+difficulty of factoring large integers [XXX]. 
+
+This is important for, e.g., long-term digital publishing
+where the usual recommended digital signature expiration 
+time of two years[XXX] is inconvenient.
+
+
+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 
+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
+algorithm based on how the path through the key tree
+is selected, and finally conclude.
+
+
 One-time Signatures
 ===================
 
+One-time signature schemes [XXX] 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$`.
+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,
+the signer employs a deterministic algorithm to select
+a subset of the random numbers, and publishes them
+as the signature. The signature can be verified by running
+the same deterministic algorithm, checking that the
+resultant set of numbers has been published, and comparing
+f(x) for each published number x against the values
+in the public key.
+
+To prevent an attacker from using a subset of the
+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.
+
+Private keys in one-time signature schemes can generally
+only be used to sign a single message. If the same key 
+were used to sign multiple messages, an attacker might
+be able to combine the random numbers published in each
+signature to find a new valid signature.
+However, some schemes have been recently proposed that
+allow a small number of messages to be signed without
+becoming completely insecure [BiBa-andalso-betterthanbiba]_.
+
+Another way to allow n messages to be signed with the
+same public key is to create n different key pairs,
+and then compute a hash tree over the public keys.
+This is only practical for relatively small n.
+
+Yet another approach is to sign one or more new public keys
+as the last message signed with the old key. This way,
+an arbitrary number of messages can be signed.
+However, verification time increases, and the signer
+still needs to keep track of which private keys
+have already been used in order not to compromise security.
+
+
 One-time Signature Key Boosting
 ===============================
 
-Full Digital Signature Feature Set without Trapdoors
-====================================================
+
+- based on underlying $q$-time scheme --- usually Merkle hash tree
+  of one-time scheme.
+
+- req. also random oracle
+
+
+
+
+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 
+public key.
+
+To generate a signature for the message `$m$`, 
+start by setting `$p$` to the
+private key.
+Then, we iterate over the following steps `$N$` times:
+
+1. Choose the tree branch `$x \\in [1,q]$`. 
+   The exact algorithm for making this
+   choice parametrizes the algorithm; possible choices are discussed
+   below.
+
+2. Use the random oracle to generate the `$x$th` new private key
+   `$p_x$` from `$p$`.
+
+3. Sign the corresponding public key with `$p$`. This does
+   not present
+   a problem for the `$q$`-time signature algorithm, since
+   the random oracle is deterministic and
+   no more than `$q$` strings will therefore be signed
+   with any given `$p$`.
+
+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.
+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 length of the signature will be `$N$` times the length
+of a signatures 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.
+
+Full Digital Signature Feature Set without Trapdoor Functions
+=============================================================
+
+In this Section, we describe our central theoretical result:
+a feasible scheme for general 160-bit digital signatures.
+Our scheme has no time limits for private keys
+because it is not based on complexity of inverting trapdoor functions.
+The scheme requires only that one-way functions and random oracles exist.
+To our knowledge, this is has not previously been possible without
+remembering all previously signed documents or 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.
+
+In key boosting, the choise of the tree branch `$x$` to follow at each 
+node is crucial to the nature of the algorithm.
+In order to be able to sign 160-bit hashes securely, we generate
+a unique private key for each 160-bit hash. 
+This is done by requiring that `$q^N > 2^{160}$` and choosing
+`$x$` based on the bits of the hash to be signed.
+- however, we *can* use OTS algorithms with chosen-message attacks since final 
pubkey
+  not known
+
+we want the full deterministic
+algorithm, for 160-bit hashes
+that, which requires `$ nN = 160 $`.
+
+All choices produce a *linear* operation from the characteristics
+of a scheme to the characteristics of the other scheme.
+Particularly, the signature length increases linearly with `$N$`,
+and the time to sign grows exponentially with `$n$` and
+linearly (in the opposite direction!) with `$N$`.
+
+
+    - feasible
+
+    - 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$`.
+
+        Formally, this is:
+        Key boosting(16, Merkle hash tree(10, Merkle-Winternitz(160,160,2), 
10))
+
+       and has the octuplet??
+
+- Security not straightforward:
+  There is a large number of hashes used, and a collision
+  between any two could allow forging of signatures.
+  birthday attacks, ...
+
+  - Bleichenbacher-Maurer. 
+    To sign 160 bits, we need `$n=29$`.
+    Signatures are 90 hashes
+
+Supporting multiple signatures is possible e.g. in BiBa,
+but inefficient. Merkle hash trees better
+
 
 Practical Variants
 ==================
Index: manuscripts/Sigs/internal.rst
diff -u manuscripts/Sigs/internal.rst:1.1 manuscripts/Sigs/internal.rst:1.2
--- manuscripts/Sigs/internal.rst:1.1   Mon May 19 09:35:54 2003
+++ manuscripts/Sigs/internal.rst       Mon May 19 11:06:00 2003
@@ -49,36 +49,6 @@
 Introduction
 ============
 
-One-time signatures were originally proposed independently
-by [XXX] and [XXX]. Since then, numerous variations
-and improvements have been published [XXX].
-Despite their limitations, one-way signatures have
-attracted considerable interest because
-their operation 
-does not
-rely on
-trapdoor functions, whose strength is based on
-unproven number-theoretic assumptions such as the
-difficulty of factoring large integers [XXX]. 
-
-This is important for, e.g., long-term digital publishing
-where the usual recommended digital signature expiration 
-time of two years[XXX] is inconvenient.
-
-
-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 
-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
-algorithm based on how the path through the key tree
-is selected, and finally conclude.
-
 One-time Signatures
 ===================
 
@@ -93,52 +63,6 @@
     may be orders of magnitude faster than operations
     in schemes like DSA or RSA.
 
-One-time signature schemes [XXX] 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$`.
-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,
-the signer employs a deterministic algorithm to select
-a subset of the random numbers, and publishes them
-as the signature. The signature can be verified by running
-the same deterministic algorithm, checking that the
-resultant set of numbers has been published, and comparing
-f(x) for each published number x against the values
-in the public key.
-
-To prevent an attacker from using a subset of the
-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.
-
-Private keys in one-time signature schemes can generally
-only be used to sign a single message. If the same key 
-were used to sign multiple messages, an attacker might
-be able to combine the random numbers published in each
-signature to find a new valid signature.
-However, some schemes have been recently proposed that
-allow a small number of messages to be signed without
-becoming completely insecure [BiBa-andalso-betterthanbiba]_.
-
-Another way to allow n messages to be signed with the
-same public key is to create n different key pairs,
-and then compute a hash tree over the public keys.
-This is only practical for relatively small n.
-
-Yet another approach is to sign one or more new public keys
-as the last message signed with the old key. This way,
-an arbitrary number of messages can be signed.
-However, verification time increases, and the signer
-still needs to keep track of which private keys
-have already been used in order not to compromise security.
-
-In section XXX, we give a description of existing
-one-time signature algorithms with their different
-tradeoffs.
-
 One-time Signature Key Boosting
 ===============================
 
@@ -147,45 +71,6 @@
 2) a random oracle which generates an apparently random
 bitstring from a given number.
 
-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 
-public key.
-
-To generate a signature for the message `$m$`, 
-we start by setting `$p$` to the
-private key.
-Then, we iterate over the following steps `$N$` times:
-
-1. Choose `$x \\in [1,q]$`. The exact algorithm for making this
-   choice parametrizes the algorithm; possible choices are discussed
-   below.
-
-2. Use the random oracle to generate the `$x$th` new private key
-   `$p_x$` from `$p$`.
-
-3. Sign the corresponding public key with `$p$`. This does
-   not present
-   a problem for the `$q$`-time signature algorithm, since
-   the random oracle is deterministic and
-   no more than `$q$` strings will therefore be signed
-   with any given `$p$`.
-
-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.
-
-To verify a signature, the verifier only needs to traverse the
-chain of signatures
-
-As long as the algorithm for choosing `$x$` does not yield the same
-chain for two messages, the signatures XXX
-The effects of this algorithm and the parameters `$q$` and `$N$`
-are analyzed in the next section.
-
 Security of this construction
 
 
@@ -214,43 +99,6 @@
 Deterministic: a Full Digital Signature Algorithm Feature Set
 -------------------------------------------------------------
 
-- Arbitrary (pseudo-infinite, i.e. infinite wouldn't help any more) 
-  number of keys, if for each *hash* its own private key for signing it!
-  This means that `$N \\log k \\ge h$`
-
-    - this is a nice theoretical result: it *is* possible to sign anything
-      without trapdoors - full feature set of normal (non-one-time) DSs
-
-    - feasible
-
-    - 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$`.
-
-        Formally, this is:
-        Key boosting(16, Merkle hash tree(10, Merkle-Winternitz(160,160,2), 
10))
-
-       and has the octuplet??
-
-- Security not straightforward:
-  There is a large number of hashes used, and a collision
-  between any two could allow forging of signatures.
-  birthday attacks, ...
-
-- AAAGH We can't use 80-bit hashes inside the tree, and it's
-  questionable whether we can even use 160-bit! 
-  Reason: if you sign a lot of docs, chances are 
-  you get a common birthday: two instances
-  of the same key used at two different branches.
-
-  Especially since we use N primitive signatures for each sig.
-
-  This needs to be reasoned out carefully.
-
 Probabilistic limited
 ---------------------
 
@@ -661,25 +509,23 @@
 Octuplet: `${q'}^N, b, N(r'+s'), r', h,
 c_0', N(c_0'+c_s'), Nc_v)$`
 
+- We can't use 80-bit hashes inside the tree, 
 
-Tradeoffs in deterministic key boosting
----------------------------------------
+  Reason: if you sign a lot of docs, chances are 
+  you may a common birthday: two instances
+  of the same key used at two different branches.
+  An accidental attack ;)
 
-Supporting multiple signatures is possible e.g. in BiBa,
-but inefficient. Merkle hash trees better
+  Especially since we use N primitive signatures for each sig.
 
-we want the full deterministic
-algorithm, 
-that, which requires `$ nN = 160 $`.
-
-All choices produce a *linear* operation from the characteristics
-of a scheme to the characteristics of the other scheme.
-Particularly, the signature length increases linearly with `$N$`,
-and the time to sign grows exponentially with `$n$` and
-linearly (in the opposite direction!) with `$N$`.
+  This needs to be reasoned out carefully.
 
 
 
+Tradeoffs in deterministic key boosting
+---------------------------------------
+
+
 
 - we demand security level `$2^{-160}$` for our underlying schemes
 
@@ -704,23 +550,9 @@
     `$t=168$`, `$k=69$`
     `$t=175$`, `$k=62$`
 
-  - Bleichenbacher-Maurer. 
-    To sign 160 bits, we need `$n=29$`.
-    Signatures are 90 hashes
-
 
 Conclusion
 ==========
-
-- key idea: using the deterministic bit string for each privkey
-
-In long-term digital publishing, the time limits on normal digital signatures
-are 
-
-- we expect our methods to be improved on considerably; we have shown it is 
*feasible*,
-  now someone needs to show it's *practical*
-
-- hashes *do* get broken, REF
 
 foo