[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: |
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
==========
- [Gzz-commits] manuscripts/Sigs article.rst, (continued)
- [Gzz-commits] manuscripts/Sigs article.rst, Benja Fallenstein, 2003/05/18
- [Gzz-commits] manuscripts/Sigs article.rst, Tuomas J. Lukka, 2003/05/18
- [Gzz-commits] manuscripts/Sigs article.rst, Benja Fallenstein, 2003/05/18
- [Gzz-commits] manuscripts/Sigs article.rst, Benja Fallenstein, 2003/05/18
- [Gzz-commits] manuscripts/Sigs article.rst, Benja Fallenstein, 2003/05/18
- [Gzz-commits] manuscripts/Sigs article.rst, Benja Fallenstein, 2003/05/18
- [Gzz-commits] manuscripts/Sigs article.rst, Tuomas J. Lukka, 2003/05/18
- [Gzz-commits] manuscripts/Sigs article.rst, Tuomas J. Lukka, 2003/05/18
- [Gzz-commits] manuscripts/Sigs article.rst, Tuomas J. Lukka, 2003/05/18
- [Gzz-commits] manuscripts/Sigs article.rst, Benja Fallenstein, 2003/05/18
- [Gzz-commits] manuscripts/Sigs article.rst,
Benja Fallenstein <=
- [Gzz-commits] manuscripts/Sigs article.rst, Benja Fallenstein, 2003/05/18
- [Gzz-commits] manuscripts/Sigs article.rst, Benja Fallenstein, 2003/05/18
- [Gzz-commits] manuscripts/Sigs article.rst, Benja Fallenstein, 2003/05/18
- [Gzz-commits] manuscripts/Sigs article.rst, Tuomas J. Lukka, 2003/05/18
- [Gzz-commits] manuscripts/Sigs article.rst, Benja Fallenstein, 2003/05/18
- [Gzz-commits] manuscripts/Sigs article.rst, Benja Fallenstein, 2003/05/18
- [Gzz-commits] manuscripts/Sigs article.rst, Benja Fallenstein, 2003/05/18
- [Gzz-commits] manuscripts/Sigs article.rst, Benja Fallenstein, 2003/05/18
- [Gzz-commits] manuscripts/Sigs article.rst, Benja Fallenstein, 2003/05/18
- [Gzz-commits] manuscripts/Sigs article.rst, Benja Fallenstein, 2003/05/18