CS276 Lecture 21 (draft)


Today we show how to construct an inefficient (but efficiently verifiable) signature scheme starting from a one-time signature scheme.

Next time we shall see how to make it efficient using a pseudorandom function.

From One-Time Signatures to Fully Secure Signatures

Assume we have a {(t,\epsilon)}-secure one-time signature scheme {(G,S,V)} such that if {m} is the length of messages that can be signed by {S}, then the length of public keys generated by {G()} is at most {m/2}.

(Lamport’s signatures do not satisfy the second property, but in Lecture 20 we described how to use a collision-resistant hash function to turn Lamport’s scheme into a scheme that can sign longer messages. We can arrange the parameters of the construction so that the hash-and-sign scheme can sign messages at least twice as long as the public key.)

We describe a scheme in which the key generation and signing have exponential complexity; later we will see how to reduce their complexity.

  • Key Generation: run {G()} {2^{m+1}-1} times, once for every string {a\in \{ 0,1 \}^*} of length at most {m}, and produce a public key / secret key pair {(pk_a,sk_a)}.

    It is convenient to think of the strings {a} of length at most {m} as being arranged in a binary tree, with {a} being the parent of {a0} and {a1}, and the empty string {\epsilon} being the root.

    • Public Key: {pk_\epsilon} (where {\epsilon} is the empty string)
    • Secret Key: the set of all pairs {(pk_a,sk_a)} for all {a} of length {\leq m}.
  • Sign: given a message {M} of length {m}, denote by {M_{|i}} the string {M_1,\ldots,M_i} made of the first {i} bits of {M}. Then the signature of {M} is composed of {m+1} parts:
    • {pk_M, S(sk_M,M)}: the signature of {M} using secret key {sk_M}, along with the value of the matching public key {pk_M}
    • {pk_{M_{|m-1}} , pk_{M_{|m-1}0} || pk_{M_{|m-1}1}, S(sk_{M_{|m-1}} , pk_{M_{|m-1}0} || pk_{M_{|m-1}1} )} the signature of the public keys corresponding to {M} and its sibling, signed using the secret key corresponding to the parent of {M}, along with the matching public key
    • {\cdots}

    • {pk_{M_{|i}} , pk_{M_{|i}0} || pk_{M_{i}1}, S(sk_{M_{|i}} , pk_{M_{|i}0} || pk_{M_{i}1} )}
    • {\cdots}
    • {pk_0, pk_1 , S(sk_\epsilon, pk_0 || pk_1 )}
  • Verify. The verification algorithm receives a public key {pk_\epsilon}, a message {M}, and a signature made of {m+1} pieces: the first piece is of the form {(pk_m,\sigma_m)}, the following {m-1} pieces are of the form {(pk_j,pk'_j,pk''_j,\sigma_j)}, for {j=1,\ldots,m-1}, and the last piece is of the form {(pk'_0,pk''_0,\sigma_0)}.

    The verification algorithm:

    1. checks {V(pk_m,M,\sigma_m)} is valid;
    2. For {j=1,\ldots,m}, if {M_j=0} it checks that {pk_j = pk'_{j+1}}, and if {M_j=1} it checks that {pk_j = pk''_{j+1}};
    3. For {j=0,\ldots,m}, it checks that {V(pk_j,pk'_j||pk''_j,\sigma_j)} is valid. (For the case {j=0}, we take {pk_0 := pk_\epsilon}.)

Theorem 1 Suppose that the scheme described in this section is not {(t,\epsilon)} existentially unforgeable against a chosen message attack.

Then {(G,S,V)} is not a {(t\cdot O(r \cdot m),\epsilon \cdot (2tn+1))}-secure one time signature scheme, where {r} is the running time of {S}.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s