[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Gzz-commits] manuscripts/Sigs article.rst
From: |
Benja Fallenstein |
Subject: |
[Gzz-commits] manuscripts/Sigs article.rst |
Date: |
Mon, 19 May 2003 20:18:02 -0400 |
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
- [Gzz-commits] manuscripts/Sigs article.rst, (continued)
- [Gzz-commits] manuscripts/Sigs article.rst, Tuomas J. Lukka, 2003/05/19
- [Gzz-commits] manuscripts/Sigs article.rst, Tuomas J. Lukka, 2003/05/19
- [Gzz-commits] manuscripts/Sigs article.rst, Tuomas J. Lukka, 2003/05/19
- [Gzz-commits] manuscripts/Sigs article.rst, Tuomas J. Lukka, 2003/05/19
- [Gzz-commits] manuscripts/Sigs article.rst, Tuomas J. Lukka, 2003/05/19
- [Gzz-commits] manuscripts/Sigs article.rst, Tuomas J. Lukka, 2003/05/19
- [Gzz-commits] manuscripts/Sigs article.rst, Tuomas J. Lukka, 2003/05/19
- [Gzz-commits] manuscripts/Sigs article.rst, Benja Fallenstein, 2003/05/19
- [Gzz-commits] manuscripts/Sigs article.rst, Tuomas J. Lukka, 2003/05/19
- [Gzz-commits] manuscripts/Sigs article.rst, Benja Fallenstein, 2003/05/19
- [Gzz-commits] manuscripts/Sigs article.rst,
Benja Fallenstein <=
- [Gzz-commits] manuscripts/Sigs article.rst, Benja Fallenstein, 2003/05/19
- [Gzz-commits] manuscripts/Sigs article.rst, Tuomas J. Lukka, 2003/05/19
- [Gzz-commits] manuscripts/Sigs article.rst, Tuomas J. Lukka, 2003/05/20
- [Gzz-commits] manuscripts/Sigs article.rst, Tuomas J. Lukka, 2003/05/20