[Gzz-commits] manuscripts ./gzigzag.bib Sigs/article.rst

[Benja Fallenstein]

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 },
+)
+