[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Gzz-commits] manuscripts ./gzigzag.bib Sigs/article.rst
From: |
Benja Fallenstein |
Subject: |
[Gzz-commits] manuscripts ./gzigzag.bib Sigs/article.rst |
Date: |
Mon, 19 May 2003 19:47:22 -0400 |
CVSROOT: /cvsroot/gzz
Module name: manuscripts
Changes by: Benja Fallenstein <address@hidden> 03/05/19 19:47:22
Modified files:
. : gzigzag.bib
Sigs : article.rst
Log message:
more
CVSWeb URLs:
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/manuscripts/gzigzag.bib.diff?tr1=1.113&tr2=1.114&r1=text&r2=text
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/manuscripts/Sigs/article.rst.diff?tr1=1.155&tr2=1.156&r1=text&r2=text
Patches:
Index: manuscripts/Sigs/article.rst
diff -u manuscripts/Sigs/article.rst:1.155 manuscripts/Sigs/article.rst:1.156
--- manuscripts/Sigs/article.rst:1.155 Mon May 19 18:28:58 2003
+++ manuscripts/Sigs/article.rst Mon May 19 19:47:22 2003
@@ -9,41 +9,24 @@
\begin{abstract}
We propose a digital signature scheme based on
recursive application of an underlying
- one-time signature scheme to sign
- nodes along a single path through a virtual tree of
- keys deterministically
- generated by random oracle from the parent private keys.
- In conjunction with Merkle hash trees, our scheme
- is used to generate
- a family of schemes with a tradeoff between
- time and space characteristics, which for all separate values
- of the tradeoff parameter
- depend linearly on the characteristics
- of the underlying one-time signature scheme.
-
- Our scheme has several advantages:
- signatures are
- existentially unforgeable in adaptive chosen message attack,
- and because the security of the scheme is based only on
- one-way functions and a random oracle, i.e.
- no trapdoor functions are used,
+ one-time signature scheme, allowing a single private key
+ to sign an unlimited number of messages.
+ Our scheme uses a virtual tree of key pairs, where each parent node
+ signs the public keys of its children.
+ The childrens' private keys are generated by a random oracle
+ from the parent's private key. There are as many leaves
+ in the tree as possible messages, allowing every message
+ to be signed by a different key.
+
+ Signatures in our scheme are
+ existentially unforgeable under an adaptive chosen message attack,
+ and because no trapdoor functions are used,
the keys and signatures remain valid
- for an
- unlimited time.
+ for an unlimited time.
- We discuss two example instances:
- a high-security instance with
- unlimited use, 160-bit security,
- which requires
- a 110 KB signature, 201'952 hash function invocations for signing, and
- 5'568 hash invocations for verification.
- On a more practical level, we discuss a
- probabilistically valid instance
- which can be used for any number of signatures
- within the bounds of the 56-bit birthday paradox.
- The probabilistic scheme requires
- a 42 KB sig, 75'732 hash invocations for signing, and 2'088 hashes
- for verification.
+ In an instance using a 160 bit hash, signatures are 110 KB large;
+ signing needs `$2.1\\cdot 10^{5}$` and verification needs
+ `$5.6\\cdot 10^3$` hash function invocations.
\end{abstract}
\renewcommand{\baselinestretch}{1.7}
@@ -70,7 +53,7 @@
cryptoanalytic attack; keys therefore need not
expire after a small number of years.
This is important for e.g. long-term
-digital publishing [anderson98eternal]_.
+digital publishing [anderson98erl]_.
The alternative, digital timestamping
[haber91timestamp-andalso-bayer92improving]_,
adds additional complication because
@@ -142,7 +125,7 @@
Our scheme is a construction based on 1) a `$q$`-time signature
scheme, and 2) a random oracle function. We generally assume
-that the random oracle is the same hash function (e.g. SHA-1)
+that the random oracle is the same hash function (e.g. SHA-1 [fips-sha1]_)
as in the underlying signature scheme. Usually, this scheme
will be a Merkle hash tree [merkle80protocols]_ of Merkle
one-time signatures [merkle87digital]_.
@@ -298,7 +281,9 @@
hash invocations for signing and `$5.6\\cdot 10^3$`
hash invocations for verification.
Using SHA-1, we obtained the estimated times 1s and 30ms
-for signing and verifying on a P4 Mobile 1.6GHz.
+for signing and verifying on a P4 Mobile 1.6GHz;
+on this system, the verification times are competitive
+with DSA [fips-dsa]_.
.. com
Index: manuscripts/gzigzag.bib
diff -u manuscripts/gzigzag.bib:1.113 manuscripts/gzigzag.bib:1.114
--- manuscripts/gzigzag.bib:1.113 Mon May 19 18:05:53 2003
+++ manuscripts/gzigzag.bib Mon May 19 19:47:22 2003
@@ -1832,17 +1832,6 @@
publisher = {ACM Press},
}
address@hidden(anderson98erl,
-author = {Ross J. Anderson and Vaclav Matyas Jr. and Fabien A.P. Petitcolas},
-title = {The Eternal Resource Locator: An Alternative Means of Establishing
Trust on the World Wide Web},
-booktitle = {Proceedings of the 3rd USENIX Workshop on Electronic Commerce},
-year = 1998,
-pages = {141--154},
-location = {Boston, Massachusetts},
-url =
{http://www.usenix.org/publications/library/proceedings/ec98/full_papers/anderson/anderson_html/anderson.html},
-)
-
-
@article(markup-systems-future-scholarly,
author = { James H. Coombs and Allen H. Renear and Steven J. DeRose },
title = { Markup Systems and the Future of Scholarly Text Processing },
@@ -1913,12 +1902,6 @@
@comment howpublished =
{\url{http://www.ietf.org/html.charters/urn-charter.html}}
@comment )
address@hidden(fips-sha-1,
-title = { FIPS PUB 180-1: Secure Hash Standard },
-organization = { NIST },
-year = { 1995 },
-)
-
@inproceedings{ giles98citeseer,
author = "C. Lee Giles and Kurt Bollacker and Steve Lawrence",
@@ -5872,22 +5855,6 @@
bibsource = {DBLP, http://dblp.uni-trier.de}
}
address@hidden application of one-time sigs:
address@hidden very interesting in relation to Storm, do read!
address@hidden anderson98eternal,
- author = {Ross J. Anderson and Maty\'{a}\v{s}, Jr., V\'{a}clav and
- Fabien A. P. Petitcolas},
- title = {The Eternal Resource Locator: An Alternative Means of
- Establishing Trust on the World Wide Web},
- booktitle = {Third Usenix Workshop on Electronic Commerce},
- year = 1998,
- address = {Boston, Massachusetts, U.S.A.},
- month = {31 } # aug # {--3 } # sep,
- pages = {141--153},
- isbn = {1-880-446-97-9},
- url = {citeseer.nj.nec.com/365389.html}
-}
-
@article{ haber91timestamp,
author = "Stuart Haber and W. Scott Stornetta",
title = "How to Time-Stamp a Digital Document",
@@ -5906,4 +5873,29 @@
year = "1992",
publisher = "Springer-Verlag",
url = "citeseer.nj.nec.com/bayer93improving.html"
-}
\ No newline at end of file
+}
+
address@hidden application of one-time sigs:
address@hidden very interesting in relation to Storm, do read!
address@hidden(anderson98erl,
+author = {Ross J. Anderson and Vaclav Matyas Jr. and Fabien A.P. Petitcolas},
+title = {The Eternal Resource Locator: An Alternative Means of Establishing
Trust on the World Wide Web},
+booktitle = {Proceedings of the 3rd USENIX Workshop on Electronic Commerce},
+year = 1998,
+pages = {141--154},
+location = {Boston, Massachusetts},
+url =
{http://www.usenix.org/publications/library/proceedings/ec98/full_papers/anderson/anderson_html/anderson.html},
+)
+
address@hidden(fips-sha-1,
+title = { FIPS PUB 180-1: Secure Hash Standard },
+organization = { NIST },
+year = { 1995 },
+)
+
address@hidden(fips-dsa,
+title = { FIPS PUB 186: DIGITAL SIGNATURE STANDARD },
+organization = { NIST },
+year = { 1994 },
+)
+