13.77934
i’ve been wanting a good way to migrate signature keys in converge. ideally a migrating key pair that:
- signatures can be verified correct with merely the signing public key
- the migrating secret cannot be derived from the signing secret key
- even if the migrating public key is known
schnorr signatures use a scalar secret key, $sk_s$, and a public key $pk_s = B * sk_s$, where $B$ is an agreed upon group member and $*$ repeated application of the group operation, which must be hard to reverse. suppose you have a cryptographic hash function that turns group members to scalars, $H(x)$. if the secret signing key is the product of the secret migration key and the hash of the public migration key, $sk_s = sk_m * H(pk_m)$, the public signing key would be the product of the public migration key and its hash, $pk_s = pk_m * H(pk_m)$,
it seems obviously difficult to derive either migration key from the signing keys. the combination of reversing the hard problem of the group and the hash function. however, once the public migration key is known, the secret migration key can be quickly derived from the secret signing key via the inverse of the hash of the public migration key, $sk_m = sk_s * H(pk_m)^{\ell-2}$, where $\ell$ is the group order.
what about $sk_s = H(pk_m)$?
it certainly fulfills our criteria, though it also reveals the signing secret key.
it’d be nice to not need to do that.
maybe $sk_s = sk_m^{H(pk_m)}$?
finding roots in finite fields appears to take time linear in the degree of the root, so we can’t recover the migration secret key. however, there doesn’t appear to be a straight-forward relationship on the public key side.
$$pk_s = B * sk_m^{H(pk_m)} = B*sk_m * sk_m^{H(pk_m)-1} = pk_m * sk_m^{H(pk_m)-1}$$
we can’t reveal $sk_m^{H(pk_m)-1}$, because that would also reveal $sk_s$.
actually, suppose we generate a pair of migration keys, and have a hash function from a pair of keys to a scalar. the secret signing key is the hash of both public keys times one secret key.
$$h = H(pk_m, pk_n)$$ $$sk_s = sk_m * h, pk_s = pk_m * h$$
when we sign, we sign with both migration keys. this reveals one of the migration keys to anyone with the signing secret, but the other one is still secret. and the hash function prevents anyone from coming up with a different pair of migration keys.
so, specifically:
we have a set, $G$, with prime order $\ell$, and an element in that set, $B : G$. then we have an operation on that set $* : G → Z/\ell → G$, such that $A * x * y = A * x·y$, where $A$ is any element of the set and $x$ and $y$ are elements of $Z/\ell$.
we have a one-way function $H : G → G → Z/\ell$, which transforms two group elements to a scalar.
we generate two scalars, our secret migration keys, $s_m$ and $s_n$, and derive their corresponding group elements $P_m = B * s_m$ and $P_n = B * s_n$.
we then derive the scalar $h = H(P_m, P_n)$ via the one-way function.
our final scalar is the secret signing key, $s_s = s_m·h$, which hash a corresponding group element / public key, $P_s = B * s_s = B * s_m·h = B * s_m * h = P_m * h$.
finally we have a signature scheme, with a signer $S : Z/\ell → M → Σ$, using a secret scalar to turn a message into a signature, and a verifier $V : G → M → Σ → Bool$, which checks whether a signature was made on that message with the scalar corresponding to the group element.
for some time we use the signature scheme with the secret and public signing keys. we distribute the signing keys to various software agents, so they can sign things for us. then, for some reason, we want to migrate to a new signing key pair.
we construct a message, $m$, indicating the old public key and the new public key. and produce two signatures, $σ_m = S(s_m, m)$ and $σ_n = S(s_n, m)$, and broadcast $(P_m, P_n, σ_m, σ_n, m)$.
anyone with the old public key can check both signatures and $P_s = P_m * H(P_m, P_n)$ to verify that they should migrate. anyone with access to the old secret key can additionally derive $S_m = s_s * H(P_m, P_n)^{\ell-2}$, but they cannot derive $s_n$, and so cannot issue false key migrations.
nice.