gzz-commits
[Top][All Lists]

[Gzz-commits] manuscripts/Sigs article.rst

 From: Benja Fallenstein Subject: [Gzz-commits] manuscripts/Sigs article.rst Date: Sun, 18 May 2003 13:34:04 -0400

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
==========