[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Gzz-commits] manuscripts/Sigs article.rst internal.rst
From: |
Tuomas J. Lukka |
Subject: |
[Gzz-commits] manuscripts/Sigs article.rst internal.rst |
Date: |
Mon, 19 May 2003 11:06:00 -0400 |
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