=============================== 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 $`. All choices produce a *linear* operation from the characteristics of a scheme to the characteristics of the other scheme. Particularly, the signature length increases linearly with `$N$`, and the time to sign grows exponentially with `$n$` and linearly (in the opposite direction!) with `$N$`. - 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