[Gzz-commits] manuscripts/Sigs article.rst

[Benja Fallenstein]

CVSROOT:        /cvsroot/gzz
Module name:    manuscripts
Changes by:     Benja Fallenstein <address@hidden>      03/05/18 13:34:04

Modified files:
        Sigs           : article.rst 

Log message:
        large-scale reorg

CVSWeb URLs:
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/manuscripts/Sigs/article.rst.diff?tr1=1.85&tr2=1.86&r1=text&r2=text

Patches:
Index: manuscripts/Sigs/article.rst
diff -u manuscripts/Sigs/article.rst:1.85 manuscripts/Sigs/article.rst:1.86
--- manuscripts/Sigs/article.rst:1.85   Sun May 18 13:14:19 2003
+++ manuscripts/Sigs/article.rst        Sun May 18 13:34:04 2003
@@ -138,173 +138,6 @@
 XXX Following descriptions not into article, maybe into tech report?
 We need these to make sure our numbers are right
 
-Lamport
--------
-
-- private key: `$2b$` random numbers
-
-- public key: hashes of private key - calculate `$2b$` hashes
-
-- sign: reveal one of each pair of RNs in private key corresponding to signing 
0 or 1
-  Signature contains `$b$` of the random numbers
-
-- verify: check that the revealed RNs hashes to right hash in public key - 
-  calculate `$b$` hashes
-
-Merkle (?)
-----------
-
-This scheme is an improvement over Lamport, needing
-only `$k=b+\\lceil \\log{2} b \\rceil$` hashes.
-
-Let `$m_i$` be the `$i$`-th bit of the message.
-
-- private key: A list of `$k$` random numbers `$R_i$`.
-
-- public key: Compute a list of `$k$` hashes `$P_i=H(R_i)$`;
-  the hash of this list is the public key.
-
-- sign: Reveal the `$R_i$` for `$i \\le b$` if the
-  `$m_i=0$`. Compute the checksum `$c=\\sum{m_i}$`,
-  and interpret as a bitstring. Reveal `$R_{b+i}$`
-  if the `$i$`-th bit of the bitstring is zero.
-
-- verify:
-
-Merkle-Winternitz
------------------
-
-This scheme relies on recursive application of the hash function.
-Let `$n$` be a positive integer and `$k=\\frac{b}{n}$`.
-Let `$H$` donate the hash function, with `$H^2(x)=H(H(x))$` etc.
-
-- private key: A list of random numbers `$(R_0,...,R_k)$`.
-
-- public key: Compute `$P_0=H^{k2^n}(R_0)$`, and
-  `$P_i=H^{2^n}(R_i)$` for `$i>0$`. The hash of
-  `$(P_0,...,P_k)$` is the public key.
-
-  Needs `$2k2^n + 1$` hash function invocations.
-
-- signature: Split the `$b$`-bit message into `$k$` 
-  parts of `$n$` bits each. Interpreted each part
-  as an integer `$k_i$` for `$0 < i \\le k$`.
-  Compute `$S_i=H^{k_i}(R_i)$` for `$i>0$`
-  and `$S_0=H^{2^nk-\\sum{k_i}}(R_0)$`. The tuple
-  `$(S_0,...,S_k)$` is the signature.
-
-  Signing requires `$k2^n$` invocations
-  of the hash function.
-
-- verification: Compute `$k_i$` as above.
-  Compute `$V_0=H^{\\sum{k_i}}(S_0)$`
-  and `$V_i=H^{2^n-k_i}(S_i)$` for `$i>0$`.
-  Check that the hash of `$(V_0,...,V_i)$`
-  equals the public key.
-
-  Verification requires `$k2^n + 1$` invocations
-  of the hash function.
-
-BiBa
-----
-
-The signer generates `$t$` random numbers (balls) and publishes
-their hashes as the public key. A hash function maps each ball
-to one of `$n$` *bins*, depending on the signed message 
-and a counter, initially zero.
-If `$w$` balls fall into the same bin, they are published
-as the signature. If no bin contains at least `$w$` balls,
-the counter is increased and the procedure is repeated
-until a '`$w$`-time collision' is found.
-
-- private key: the `$t$` random numbers
-
-- public key: the hashes of the random numbers
-
-- sign: apply the hash function to all balls
-  until a `$w$`-time collision is found
-
-- verify: verify that the hash function maps the published balls
-  into the same bin; verify that the balls match the public key
-  (i.e., that the public key contains their hashes).
-
-
-Reyzin
-------
-
-We discuss only the second algorithm, based on subset-intractable
-functions.
-
-To sign `$b$` bits, choose `$t$` and `$k$` such that
-`$ {t \\choose k} \\ge b $`
-
-Parameters `$t$` and `$k$`.
-
-- private key: `$t$` random numbers
-
-- public key: hashes of the random numbers. Calculate `$t$` hashes
-
-- sign: Hash the message, split hash to `$k$` strings of `$\\log t$` bits.
-  use these as indices to say which numbers to reveal in the signature.
-  Calculate one hash.
-
-- verify: same deterministic part, check that revealed numbers hash right.
-
-Probability for successful forgery after `$r$` signatures:
-`$(rk/t)^k$` 
-
-?
-
-Bleichenbacher-Maurer
----------------------
-
-ASIACRPTO construction
-
-- Construction for `$H_n$`: a binary tree,
-  at each node 2 hashes combined into one
-
-- private key: `$3(n+1)$` hash values of tree leaves.
-  Calculate `$9n+2$` hashes. This can sign
-  `$\\lfloor {\\log 51 \\over \\log 2} n \\rfloor$` bits.
-  (XXX Some were not allowable because not minimal???)
-
-- public key: one hash, the one calculated for the root of the tree
-
-- sign: message determines which nodes of the tree to reveal; 
-  Signature contains `$3(n+1)$` hashes.
-
-- verify: check that right nodes revealed, and that tree computes right
-  public key - calculate some less than `$9n+2$` hashes
-
-Merkle hash trees
------------------
-
-Assume an underlying one-time signature scheme `$S'$`.
-Generate `$2^n$` public keys through `$S'$`, 
-compute a hash tree over them, publish the root 
-of the tree as the actual public key.
-
-Assume underlying algorithm using same hash.
-
-Signature using new public key will not need to contain 
-all the public keys, just path through the tree.
-
-- private key: `$2^n$` private keys of the underlying algorithm.
-
-- public key: Calculate the `$2^n$` public keys; hash each
-  public key (if it is longer than a single hash); compute
-  the hash tree. Calculating the public key takes
-  `$2^n c_0$` and calculating the hash tree takes
-  `$2^{n+1}-1$` hash function invocations.
-
-- sign using one key: Sign with that private key, provide the
-  corresponding public key, and provide the chain of hashes
-  from the hash tree's root to the public key.
-  Only hash invocations in the signing using the underlying algorithm.
-
-- verify: verify signature with new public key, verify hash chain.
-
-
 One-time Signature Key Boosting
 ===============================
 
@@ -370,6 +203,90 @@
 
     To sign a *b*-bit message *m*, 
 
+Variants: Choosing the Tree Branch
+==================================
+
+Choice of `$x$`
+
+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
+
+    - realistic? How much does this need?
+
+      - 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.
+
+Ordered
+-------
+
+- Keep count of number of signatures made
+
+- use bits of count for choosing
+
+- this is basically a k-time signature made feasible
+  for large k
+
+- mustn't lose count! 
+
+- can't copy key or restore from backup!
+
+- any scheme mapping the *action* of signing uniquely to a number between 0 
and `$q$`
+  will work.
+
+Probabilistic limited
+---------------------
+
+Shorter signatures
+
+- If less, cannot use information from hash directly, otherwise can attack
+  by giving close relatives
+
+  - except! Algorithm for choosing `$x$` need not be public. If we hash
+    a different private key plus the content hash or content of the 
information,
+    we *can* use it here; random oracle 
+
+    - birthday paradox; if collision, someone can forge a signature
+      (relevant if a large number of chosen message attacks)
+
+  - can use random number; if we sign only 2**20 messages total,
+    choosing randomly from 2**60 keys should be enough, since
+    we expect collisions only at about 2**30 messages signed
+
+    - birthday paradox again: must not allow the attacker to have
+      2**30 messages being signed
+
+- however, collisions *only* invalidate one leaf of the key tree, so 
+  it *is* possible to 
+  revoke only that leaf, not the whole key.
+
 Analysis: Characterizing one-time signature schemes
 ===================================================
 
@@ -474,89 +391,173 @@
 - the first levels of signatures may be given in the public key,
   giving a tradeoff between public key size and signature size.
 
-Variants: Choosing the Tree Branch
-==================================
+Lamport
+-------
 
-Choice of `$x$`
+- private key: `$2b$` random numbers
 
-Deterministic: a Full Digital Signature Algorithm Feature Set
--------------------------------------------------------------
+- public key: hashes of private key - calculate `$2b$` hashes
 
-- 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$`
+- sign: reveal one of each pair of RNs in private key corresponding to signing 
0 or 1
+  Signature contains `$b$` of the random numbers
 
-    - this is a nice theoretical result: it *is* possible to sign anything
-      without trapdoors - full feature set of normal (non-one-time) DSs
+- verify: check that the revealed RNs hashes to right hash in public key - 
+  calculate `$b$` hashes
 
-    - realistic? How much does this need?
+Merkle (?)
+----------
 
-      - 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$`.
+This scheme is an improvement over Lamport, needing
+only `$k=b+\\lceil \\log{2} b \\rceil$` hashes.
 
-        Formally, this is:
-        Key boosting(16, Merkle hash tree(10, Merkle-Winternitz(160,160,2), 
10))
+Let `$m_i$` be the `$i$`-th bit of the message.
 
-       and has the octuplet??
+- private key: A list of `$k$` random numbers `$R_i$`.
 
-- Security not straightforward:
-  There is a large number of hashes used, and a collision
-  between any two could allow forging of signatures.
-  birthday attacks, ...
+- public key: Compute a list of `$k$` hashes `$P_i=H(R_i)$`;
+  the hash of this list is the public key.
 
-- 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.
+- sign: Reveal the `$R_i$` for `$i \\le b$` if the
+  `$m_i=0$`. Compute the checksum `$c=\\sum{m_i}$`,
+  and interpret as a bitstring. Reveal `$R_{b+i}$`
+  if the `$i$`-th bit of the bitstring is zero.
 
-  Especially since we use N primitive signatures for each sig.
+- verify:
 
-  This needs to be reasoned out carefully.
+Merkle-Winternitz
+-----------------
 
-Ordered
--------
+This scheme relies on recursive application of the hash function.
+Let `$n$` be a positive integer and `$k=\\frac{b}{n}$`.
+Let `$H$` donate the hash function, with `$H^2(x)=H(H(x))$` etc.
 
-- Keep count of number of signatures made
+- private key: A list of random numbers `$(R_0,...,R_k)$`.
 
-- use bits of count for choosing
+- public key: Compute `$P_0=H^{k2^n}(R_0)$`, and
+  `$P_i=H^{2^n}(R_i)$` for `$i>0$`. The hash of
+  `$(P_0,...,P_k)$` is the public key.
 
-- this is basically a k-time signature made feasible
-  for large k
+  Needs `$2k2^n + 1$` hash function invocations.
 
-- mustn't lose count! 
+- signature: Split the `$b$`-bit message into `$k$` 
+  parts of `$n$` bits each. Interpreted each part
+  as an integer `$k_i$` for `$0 < i \\le k$`.
+  Compute `$S_i=H^{k_i}(R_i)$` for `$i>0$`
+  and `$S_0=H^{2^nk-\\sum{k_i}}(R_0)$`. The tuple
+  `$(S_0,...,S_k)$` is the signature.
 
-- can't copy key or restore from backup!
+  Signing requires `$k2^n$` invocations
+  of the hash function.
 
-- any scheme mapping the *action* of signing uniquely to a number between 0 
and `$q$`
-  will work.
+- verification: Compute `$k_i$` as above.
+  Compute `$V_0=H^{\\sum{k_i}}(S_0)$`
+  and `$V_i=H^{2^n-k_i}(S_i)$` for `$i>0$`.
+  Check that the hash of `$(V_0,...,V_i)$`
+  equals the public key.
 
-Probabilistic limited
+  Verification requires `$k2^n + 1$` invocations
+  of the hash function.
+
+BiBa
+----
+
+The signer generates `$t$` random numbers (balls) and publishes
+their hashes as the public key. A hash function maps each ball
+to one of `$n$` *bins*, depending on the signed message 
+and a counter, initially zero.
+If `$w$` balls fall into the same bin, they are published
+as the signature. If no bin contains at least `$w$` balls,
+the counter is increased and the procedure is repeated
+until a '`$w$`-time collision' is found.
+
+- private key: the `$t$` random numbers
+
+- public key: the hashes of the random numbers
+
+- sign: apply the hash function to all balls
+  until a `$w$`-time collision is found
+
+- verify: verify that the hash function maps the published balls
+  into the same bin; verify that the balls match the public key
+  (i.e., that the public key contains their hashes).
+
+
+Reyzin
+------
+
+We discuss only the second algorithm, based on subset-intractable
+functions.
+
+To sign `$b$` bits, choose `$t$` and `$k$` such that
+`$ {t \\choose k} \\ge b $`
+
+Parameters `$t$` and `$k$`.
+
+- private key: `$t$` random numbers
+
+- public key: hashes of the random numbers. Calculate `$t$` hashes
+
+- sign: Hash the message, split hash to `$k$` strings of `$\\log t$` bits.
+  use these as indices to say which numbers to reveal in the signature.
+  Calculate one hash.
+
+- verify: same deterministic part, check that revealed numbers hash right.
+
+Probability for successful forgery after `$r$` signatures:
+`$(rk/t)^k$` 
+
+?
+
+Bleichenbacher-Maurer
 ---------------------
 
-Shorter signatures
+ASIACRPTO construction
 
-- If less, cannot use information from hash directly, otherwise can attack
-  by giving close relatives
+- Construction for `$H_n$`: a binary tree,
+  at each node 2 hashes combined into one
 
-  - except! Algorithm for choosing `$x$` need not be public. If we hash
-    a different private key plus the content hash or content of the 
information,
-    we *can* use it here; random oracle 
+- private key: `$3(n+1)$` hash values of tree leaves.
+  Calculate `$9n+2$` hashes. This can sign
+  `$\\lfloor {\\log 51 \\over \\log 2} n \\rfloor$` bits.
+  (XXX Some were not allowable because not minimal???)
 
-    - birthday paradox; if collision, someone can forge a signature
-      (relevant if a large number of chosen message attacks)
+- public key: one hash, the one calculated for the root of the tree
 
-  - can use random number; if we sign only 2**20 messages total,
-    choosing randomly from 2**60 keys should be enough, since
-    we expect collisions only at about 2**30 messages signed
+- sign: message determines which nodes of the tree to reveal; 
+  Signature contains `$3(n+1)$` hashes.
+
+- verify: check that right nodes revealed, and that tree computes right
+  public key - calculate some less than `$9n+2$` hashes
+
+Merkle hash trees
+-----------------
+
+Assume an underlying one-time signature scheme `$S'$`.
+Generate `$2^n$` public keys through `$S'$`, 
+compute a hash tree over them, publish the root 
+of the tree as the actual public key.
+
+Assume underlying algorithm using same hash.
+
+Signature using new public key will not need to contain 
+all the public keys, just path through the tree.
+
+- private key: `$2^n$` private keys of the underlying algorithm.
+
+- public key: Calculate the `$2^n$` public keys; hash each
+  public key (if it is longer than a single hash); compute
+  the hash tree. Calculating the public key takes
+  `$2^n c_0$` and calculating the hash tree takes
+  `$2^{n+1}-1$` hash function invocations.
+
+- sign using one key: Sign with that private key, provide the
+  corresponding public key, and provide the chain of hashes
+  from the hash tree's root to the public key.
+  Only hash invocations in the signing using the underlying algorithm.
+
+- verify: verify signature with new public key, verify hash chain.
 
-    - birthday paradox again: must not allow the attacker to have
-      2**30 messages being signed
 
-- however, collisions *only* invalidate one leaf of the key tree, so 
-  it *is* possible to 
-  revoke only that leaf, not the whole key.
 
 Conclusion
 ==========