[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Gzz-commits] manuscripts/Sigs article.rst poss.py internal.rst
|
From: |
Tuomas J. Lukka |
|
Subject: |
[Gzz-commits] manuscripts/Sigs article.rst poss.py internal.rst |
|
Date: |
Mon, 19 May 2003 09:35:55 -0400 |
CVSROOT: /cvsroot/gzz
Module name: manuscripts
Changes by: Tuomas J. Lukka <address@hidden> 03/05/19 09:35:55
Modified files:
Sigs : article.rst poss.py
Added files:
Sigs : internal.rst
Log message:
restart article
CVSWeb URLs:
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/manuscripts/Sigs/internal.rst?rev=1.1
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/manuscripts/Sigs/article.rst.diff?tr1=1.106&tr2=1.107&r1=text&r2=text
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/manuscripts/Sigs/poss.py.diff?tr1=1.10&tr2=1.11&r1=text&r2=text
Patches:
Index: manuscripts/Sigs/article.rst
diff -u manuscripts/Sigs/article.rst:1.106 manuscripts/Sigs/article.rst:1.107
--- manuscripts/Sigs/article.rst:1.106 Mon May 19 09:18:32 2003
+++ manuscripts/Sigs/article.rst Mon May 19 09:35:54 2003
@@ -1,735 +1,3 @@
===============================
One-time Signature Key Boosting
===============================
-
-.. raw:: latex
-
- \begin{abstract}
- We propose an unlimited-time digital signature scheme based
- on a one-time signature scheme and a random oracle.
- The random oracle is used to map a private key deterministically
- to a
- set of new private keys.
- The original private key is used (through a hash tree)
- to sign the new
- private keys.
- For each message, one of the new keys is chosen,
- and this process is iterated for a number
- of times to obtain the final private key used to sign
- the actual message. The signature consists of
- the chain of signatures from the original public key
- to the final signature.
-
- On a theoretical level, our scheme allows the construction
- of a feasible algorithm with the full digital signature feature
- set without using a trapdoor function, i.e. without
- relying on
- number-theoretic assumptions such as the hardness
- of factoring or discrete logs.
-
- This scheme is existentially
- unforgeable with an adaptive chosen message attack.
- As long as the random oracle, used to generate the new private keys
- and to implement the one-time signatures,
- isn't broken, an exhaustive
- key search is the only way to break the scheme.
- \end{abstract}
-
-.. The detailed characteristics of the algorithm are determined
- by the one-time signature scheme used,
- the number of iterations,
- and the algorithm for choosing which private key to use.
-
-.. Additionally, rejecting invalid signatures can be
- significantly faster than in RSA-like systems.
- On the other hand, signing is comparatively slow
- and signatures can be large.
-
-
-Introduction
-============
-
-One-time signatures were originally proposed independently
-by [XXX] and [XXX]. Since then, numerous variations
-and improvements have been published [XXX].
-Despite their limitations, one-way signatures have
-attracted considerable interest because
-their operation
-does not
-rely on
-trapdoor functions, whose strength is based on
-unproven number-theoretic assumptions such as the
-difficulty of factoring large integers [XXX].
-
-This is important for, e.g., long-term digital publishing
-where the usual recommended digital signature expiration
-time of two years[XXX] is inconvenient.
-
-
-In this article, we introduce a new signature scheme,
-based on one-time signatures and a random oracle,
-that can be used any number of times without keeping track
-of private keys that have already been used.
-In the following Sections, we first
-review one-time signatures, and subsequently
-describe our algorithm.
-Then, we analyze the tradeoffs in it and other one-time signature
-schemes.
-After this, we discuss the different variants of our
-algorithm based on how the path through the key tree
-is selected, and finally conclude.
-
-One-time Signatures
-===================
-
-.. Also, in practice,
- a cryptographic hash function is used in most
- signature schemes anyway to map messages to a
- fixed-length digest, which is then signed. As
- cryptographic hash functions are one-way, also using them
- as the basis for signature avoids introducing additional
- cryptographic primitives into the system.
- Additionally, operations on one-way signatures
- may be orders of magnitude faster than operations
- in schemes like DSA or RSA.
-
-One-time signature schemes [XXX] are based
-on one-way functions, i.e., functions `$y=f(x)$` such
-as block ciphers or cryptographic hashes so that
-that given `$y$` it is infeasible to find `$x$`.
-Generally, given a one-way function f, the signer generates a set
-of (pseudo)random numbers and and publishes `$f(x)$` for each
-`$x$` in the set. This is the public key. To sign a message,
-the signer employs a deterministic algorithm to select
-a subset of the random numbers, and publishes them
-as the signature. The signature can be verified by running
-the same deterministic algorithm, checking that the
-resultant set of numbers has been published, and comparing
-f(x) for each published number x against the values
-in the public key.
-
-To prevent an attacker from using a subset of the
-published numbers to sign a different message,
-the deterministic algorithm is chosen so that no set
-in its range is a true subset of any other set in its range,
-or that finding such a pair of sets is infeasible.
-
-Private keys in one-time signature schemes can generally
-only be used to sign a single message. If the same key
-were used to sign multiple messages, an attacker might
-be able to combine the random numbers published in each
-signature to find a new valid signature.
-However, some schemes have been recently proposed that
-allow a small number of messages to be signed without
-becoming completely insecure [BiBa-andalso-betterthanbiba]_.
-
-Another way to allow n messages to be signed with the
-same public key is to create n different key pairs,
-and then compute a hash tree over the public keys.
-This is only practical for relatively small n.
-
-Yet another approach is to sign one or more new public keys
-as the last message signed with the old key. This way,
-an arbitrary number of messages can be signed.
-However, verification time increases, and the signer
-still needs to keep track of which private keys
-have already been used in order not to compromise security.
-
-In section XXX, we give a description of existing
-one-time signature algorithms with their different
-tradeoffs.
-
-One-time Signature Key Boosting
-===============================
-
-This scheme is based on two primitives: 1) A `$q$`-time-signature
-algorithm which takes a random number as its private key, and
-2) a random oracle which generates an apparently random
-bitstring from a given number.
-
-The private key for this scheme is simply a private key
-for the underlying one-time-signature primitive,
-and the public key is the corresponding one-time-signature
-public key.
-
-To generate a signature for the message `$m$`,
-we start by setting `$p$` to the
-private key.
-Then, we iterate over the following steps `$N$` times:
-
-1. Choose `$x \\in [1,q]$`. The exact algorithm for making this
- choice parametrizes the algorithm; possible choices are discussed
- below.
-
-2. Use the random oracle to generate the `$x$th` new private key
- `$p_x$` from `$p$`.
-
-3. Sign the corresponding public key with `$p$`. This does
- not present
- a problem for the `$q$`-time signature algorithm, since
- the random oracle is deterministic and
- no more than `$q$` strings will therefore be signed
- with any given `$p$`.
-
-4. `$p \\leftarrow p_x$`
-
-After the last iteration, `$p$` contains the private key to be used to sign
-the actual message `$m$` using the one-time-signature primitive.
-The signature consists of this signature and the whole chain
-of signatures connecting this to the original public key.
-
-To verify a signature, the verifier only needs to traverse the
-chain of signatures
-
-As long as the algorithm for choosing `$x$` does not yield the same
-chain for two messages, the signatures XXX
-The effects of this algorithm and the parameters `$q$` and `$N$`
-are analyzed in the next section.
-
-Security of this construction
-
-
-.. If *p* is a private key, let *pub(p)* be
- the public key corresponding to it. For a message m, let
- *sign(p,m)* be the signature of *m* with private key *p*.
- Let *verify(pub(p),m,s)* be true for a signature *s*
- if *sign(p,m)=s*. Assume the above only if *sign(p,m)*
- is not publicized for more than one *m*.
-
- Further, let *R* be a random oracle which
- deterministically maps a private key
- to a pair of other private keys.
-
- To generate a private/public key pair in our scheme,
- generate a random number *p* as the private key
- and use *pub(p)* as the public key.
-
- 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
-
- - feasible
-
- - impractical; actual numbers below
-
-
-
- - 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.
-
-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.
-
-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.
-
-Analysis: Characterizing one-time signature schemes
-===================================================
-
-To compare possible one-time signature schemes for use
-with our algorithm, we
-
-We shall characterize the underlying one-time signature scheme by
-a octuplet `$(q, b, s, r, h, c_0, c_s, c_v)$`, where
-`$q$` is the number of messages a single private key can be used to sign,
-`$b$` is the number of bits in a single signed message.
-`$s$` is the number of bits in a signature,
-`$r$` is the number of bits in a public key,
-`$h$` is the number of bits a in the hash function used,
-`$c_0$` is the number of invocations of the hash function off-line at key
generation,
-`$c_s$` is the number of invocations of the hash function when signing,
-and
-`$c_v$` is the number of invocations of the hash function when verifying.
-
-.. raw:: latex
-
- \begin{table*}\def\sw{2.5cm}
- \raggedright
- \begin{tabular}{lccccccccc}
- \parbox{\sw}{Scheme (params) }
- & $q$ & $b$ & $s$ & $r$ & $h$ & $c_0$ & $c_s$ & $c_v$ \\
- \hline
- \multicolumn{4}{l}{\hskip 2cm Primitives} \\
- \hline
- \parbox{\sw}{Lamport\cite{XXX}\\$(h,b)$}
- & $1$ & $b$ & $bh$ & $2bh$ & $h$ & $2b$ & $0$ & $b$ \\
- \parbox{\sw}{Merkle I $(h,b)$}
- & $1$ & $b$ & $(b+\lceil \log_2 b \rceil)h$ & $h$ & $h$ &
- $b+\lceil \log_2 b \rceil + 1$ & $0$ &
- $\le b$ \\
- \parbox{\sw}{Merkle-Winternitz\cite{XXX} $(h,b,n)$ }
- & $1$ & $b$ & $(\frac{b}{n}+1)h$ & $h$ & $h$ &
- $2\frac{b}{n}(2^n-1)+1$ & $\frac{b}{n}(2^n-1)$ &
- $\frac{b}{n}(2^n-1)+1$ \\
- \parbox{\sw}{BiBa $(h,b,q,n,t,k)$}
- & $q$ & $b$ & $kh$ & $th$ & $h$ & $t$ & $1+t+k$ & $1+t+k$ \\
- \parbox{\sw}{BiBa-Merkle $(h,b,q,n,t,k)$}
- & $q$ & $b$ & $k\lceil \log_2 t \rceil h$
- & $h$ & $h$ & $2t$ & $1+t+k $
- & $1+t+k+ k\lceil \log_2 t
\rceil$ \\
- \parbox{\sw}{Reyzin $(h,b,t,k)$ }
- & $1$ & $b$ & $kh$ & $th$ & $h$ & $t$ & $1$ & $1+k$ \\
- \parbox{\sw}{Reyzin-Merkle$(h,b,t,k)$ }
- & $1$ & $b$ & $k\lceil \log_2 t \rceil h$
- & $h$ & $h$ & $t$ & $1$ & $1+k+k \lceil \log_2 t
\rceil$ \\
- \parbox{\sw}{Bleichenbacher-Maurer\cite{XXX(ASIACRYPT)}
- (h, n)
- }
- & $1$ & $\lfloor\eta n\rfloor$
- & $3(n+1)h $
- & $h$
- & $h$
- & $9n+2$ & 0 & $9n+2 $
- \\
- \hline
- \multicolumn{4}{l}{\hskip 2cm Derived schemes} \\
- \hline
- \parbox{\sw}{Merkle hash tree \cite{XXX}
- % XXX check this again
- ($n, S'$) }
- & ${2^n}q'$
- & $b$ & $s'+r'+(n+1)h$
- & $h$ & $h$ &
- ${2^n}c_0' + 2(2^n)-1$ &
- $c_s'$ &
- $c_v'+n+1$ \\
- \parbox{\sw}{Key boosting $(N, S')$ }
- & ${q'}^N$ & $b$ & $N(r'+s')$ & $r'$ & $h$ &
- $c_0'$ & $N(c_0'+c_s')$ & $Nc_v$ \\
- \hline
- \end{tabular}
- \caption{
- Characterizations of existing one-time signature schemes.
- The symbols are explained in the text. $n$ is a freely chosen
- positive integer.
- The Biba and Reyzin schemes (also the Merkle variants) are
- probabilistic and the parameters must be chosen to obtain
- sufficient security.
- Even in the non-probabilistic alternative
- of the Reyzin scheme, $t$ and $k$
- must be chosen so that ${t \choose k} \ge 2^b$; in that alternative,
- the running time of signing and verifying is more complicated and
- not taken into account in the table.
- In Biba, the invocations of the random oracle that throws the balls
- into bins are counted as single hash function invocations.
- For Bleichenbacher-Maurer, XXX
- `$\eta=\log 51 / \log 2$`.
- The derived schemes use
- as their basis another one-time signature scheme
- $S'$ with the parameter octuplet
- $(q',b,s',r',h,c_0',c_s',c_v')$.
- }
- \end{table*}
-
-Table XXX shows the tradeoffs possible in various one-time signature
algorithms.
-The formulas for key boosting follow trivially from
-the description of the algorithm.
-
-In order to work, key boosting requires the
-hash tree as a basis to obtain an basis algorithm
-with `$q' \\ne 1$`.
-
-The values for Bleichenbacher and Maurer's algorithm
-
-
-- given `$N$` and `$q$`, there are `$q^N$`
- possible private keys for signing messages.
-
-
-- the first levels of signatures may be given in the public key,
- giving a tradeoff between public key size and signature size.
-
-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
-
-Octuplet: `$(1, b, bh, 2bh, h, 2b, 0, b)$`
-
-
-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.
-
- At most `$b$` numbers are revealed (if all bits
- in the message are zero).
-
- The signature consists of the revealed numbers,
- plus the hashes of the numbers that were not revealed.
-
-- verify:
-
-Octuplet: `$(1, b, h(b+\\lceil \\log{2} b \\rceil), h, h,
-b+\\lceil \\log{2} b \\rceil + 1, 0, \\le b$`
-
-
-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^{k(2^n-1)}(R_0)$`, and
- `$P_i=H^{2^n-1}(R_i)$` for `$i>0$`. The hash of
- `$(P_0,...,P_k)$` is the public key.
-
- Needs `$2k(2^n-1) + 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^n-1)k-\\sum{k_i}}(R_0)$`. The tuple
- `$(S_0,...,S_k)$` is the signature.
-
- Signing requires `$k(2^n-1)$` 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-1-k_i}(S_i)$` for `$i>0$`.
- Check that the hash of `$(V_0,...,V_i)$`
- equals the public key.
-
- Verification requires `$k(2^n-1) + 1$` invocations
- of the hash function.
-
-Octuplet: `$(1, b, kh + h, h, h,
-2k(2^n-1)+1, k(2^n-1)+1, k(2^n-1)+1)$`
-
-
-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 `$k$` balls fall into the same bin, they are published
-as the signature. If no bin contains at least `$k$` balls,
-the counter is increased and the procedure is repeated
-until a '`$k$`-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 `$k$`-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).
-
-Octuplet: `$(q, b, kh, th, h, t, 1+C(t)+k, 1+C(t)+k)$` XXX check
-
-Probability for successful forgery at one attempt
-after `$r$` signatures:
-`$ {rk \\over k} (n-1)^{(r-1)k} / n^{rk-1} $`
-
-Because only a small number of the hashes in the public key need to be
-revealed and checked when signing, a Merkle hash tree may be used
-for the public key as described in the appendix of [XXX].
-However, in the usual course of things this is impractical because
-of the increased signature size. However, here the situation is different
-since both public key size and signature size
-of the underlying algorithm add to the
-
-Never more than `$k \\lceil \\log_2 t \\rceil$` hashes need to be provided
-Worst-case estimate octuplet:
-`$(q, b, k\\lceil \\log_2 t \\rceil h, h, h, 2t, 1+C(t)+k, 1+C(t)+k+ k\\lceil
\\log_2 t \\rceil)$` XXX check
-
-MERKLE HASH TREE VARIANT!!! REDUCE PUBLIC KEY + SIG SIZE!!!
-
- In BiBa, $t$ is the number of balls, $n$ the number of bins,
- and $w$ the number of balls needed in a single bin
- in order to form a signature.
-
-Powerball
----------
-
-Like BiBa, except that instead of looking for a `$k$`-way collision,
-the public key is used to generate patterns in which each bin must
-be filled.
-
-Not included in table: detailed analysis of probability of forgery
-not found in literature, and is beyond the scope of this article..
-
-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$`
-
-?
-
-- serious vulnerabilities with adaptive chosen-message multiple signatures,
-- however, not a problem in our current context, as different key will be used
- for each signature
-
-Octuplet: `$(1, b, kh, th, h, t, 1, 1+k)$`
-
-Additionally, a Merkle hash tree can be applied as in BiBa:
-Octuplet: `$(1, b, k\\lceil \\log_2 t \\rceil h, h, h, 2t, 1, 1+k+k\\lceil
\\log_2 t \\rceil)$`
-XXX check
-
-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
-
-Octuplet: `$(1, \\lfloor\\eta n\\rfloor,
-3(n+1)h, h, h, 9n+2, 0, 9n+2)$`
-
-
-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.
-
- The branches in the hash tree are stored for use
- when signing.
-
-- 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.
-
-Octuplet: `$({2^n}q', b, s'+r'+hn+h, h, h,
-{2^n}c_0' + 2(2^n)-1, c_s', c_v'+n+1)$`
-
-Efficiency of key boosting
-==========================
-
-- general analysis as appears in table
-
-- given different choices for the underlying scheme,
- and for choosing x
-
-- maybe recommendations
-
-Octuplet: `${q'}^N, b, N(r'+s'), r', h,
-c_0', N(c_0'+c_s'), Nc_v)$`
-
-
-Tradeoffs in deterministic key boosting
----------------------------------------
-
-Supporting multiple signatures is possible e.g. in BiBa,
-but inefficient. Merkle hash trees better
-
-we want the full deterministic
-algorithm,
-that, which requires `$ nN = 160 $`
-
-2, 80
-3, 54
-4, 40
-5, 32
-6, 27
-7, 23
-8, 20
-9, 18
-10, 16
-11, 15
-12, 14
-13, 13
-...
-
-
-
-
-- we demand security level `$2^{-160}$` for our underlying schemes
-
- - biba:
-
- - Reyzin subset-resilient. The security requirement,
- for a single signature signing 160 bits, this means that
- `$\\log t \ge {160-\log k \over k}$`.
- The choice with smallest `$t+k$` and (with less priority)
- `$t$` is XXX SMALLEST K?
- `$t=308$`, `$k=91$`
- `$t=316$`, `$k=83$`
-
- - Reyzin pure.
- the Reyzin theoretical construction may be used,
- where the time spent is somewhat more but security depends
- only on hashes
- Here, we only need the ability to sign 160 bits,
- which we get at the cheapest (where sum of bits
- in signature plus public key is smallest, and
- with smallest `$t$` at
- `$t=168$`, `$k=69$`
- `$t=175$`, `$k=62$`
-
- - Bleichenbacher-Maurer.
- To sign 160 bits, we need `$n=29$`.
- Signatures are 90 hashes
-
-
-Conclusion
-==========
-
-- key idea: using the deterministic bit string for each privkey
-
-In long-term digital publishing, the time limits on normal digital signatures
-are
-
-- we expect our methods to be improved on considerably; we have shown it is
*feasible*,
- now someone needs to show it's *practical*
-
-- hashes *do* get broken, REF
-
-foo
-
-.. bibliography:: gzigzag
Index: manuscripts/Sigs/poss.py
diff -u manuscripts/Sigs/poss.py:1.10 manuscripts/Sigs/poss.py:1.11
--- manuscripts/Sigs/poss.py:1.10 Mon May 19 09:18:32 2003
+++ manuscripts/Sigs/poss.py Mon May 19 09:35:54 2003
@@ -45,8 +45,8 @@
S[4],
S[4],
2L**n * S[5] + 2L**(n+1) - 1,
- S[6] + n,
- S[7] + n)
+ S[6],
+ S[7] + n + 1)
def key_boosting(N, S):
return (S[0] ** N,
@@ -116,16 +116,23 @@
if 1:
- def pzip(names, arrs):
+ def pzip(names, arrs, zeros):
res = []
for i in range(0, len(arrs[0])):
- res.append(" + ".join([
- "%s %s" % (arrs[name][i], names[name])
+ s = [
+ "%s %s" % (arrs[name][i]-zeros[i], names[name])
for name in range(0, len(names))
- if arrs[name][i] != 0]))
+ if arrs[name][i]-zeros[i] != 0]
+ if(zeros[i] != 0):
+ s.append(" %s" % zeros[i])
+ s = " + ".join(s)
+ res.append(s)
return res
for N,n in tks:
+ z = key_boosting(N,
+ merkle_hashtree(n,
+ (0, 0, 0, 0, 0, 0, 0, 0)))
ss = key_boosting(N,
merkle_hashtree(n,
(0, 0, 1, 0, 0, 0, 0, 0)))
@@ -145,8 +152,8 @@
merkle_hashtree(n,
(0, 0, 0, 0, 0, 0, 0, 1)))
print "\n\n",N,n
- print "S,R:", pzip(("s'", "r'", "h'"), (ss, sr, sh)) [2:4]
- print "C0,Cs,Cv:", pzip(("C0'", "Cs'", "Cv'"), (sc0, scs, scv)) [5:]
+ print "S,R:", pzip(("s'", "r'", "h'"), (ss, sr, sh), z) [2:4]
+ print "C0,Cs,Cv:", pzip(("C0'", "Cs'", "Cv'"), (sc0, scs, scv), z)
[5:]
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- [Gzz-commits] manuscripts/Sigs article.rst poss.py internal.rst,
Tuomas J. Lukka <=