Committing to Obsolescence

A technique to generate a secret-public key pair bound to an arbitrary verifying key, so that the verifying key may certify a key rotation.

I first found this idea in a musing. The basic principle laid out here is the same, but somewhat generalized. The rest of the page is an extract from the draft paper.

To be abundantly clear, this has not been checked by anyone but myself, and there are no formally verified proofs. I am fairly confident that it is correct, and there are some informal proofs in the paper. If you find anything wrong, please let me know.

Definitions

The target cryptosystem has a set of secret keys, $S$, a set of public keys, $P$, and a projection from secret keys to public keys $\textrm{Pub} : S \to P$. $\textrm{Pub}$ must be infeasible to reverse.

There must be another pair of functions, adding in the set $Q$, $* : P \to Q \to P$ and $\cdot : S \to Q \to S$, with the property that for all $x\in S$ and $y\in Q$, $\textrm{Pub}(x\cdot y) = \textrm{Pub}(x) * y$. That is to say, values in $Q$ must be able to be used to derive subkeys in $S$ and $P$. These operations must take a uniform distribution on $Q$ and an arbitrary distribution on $S$ and $P$ to a uniform distribution on $S$ and $P$. In typical case $S$ and $\cdot$ are the set and operation of a group, and $*$ is a group action on $P$ that uses $S$, but such structure is not required.

The signing cryptosystem has sets $S_s$ as secret keys and $P_s$ as public keys, and producing signatures in some set $\Sigma$, from messages in $\{0,1\}^*$. $\textrm{Pub}_s : S_s \to P_s$, $\textrm{Sign} : S_s \to \{0,1\}^* \to \Sigma$, and $\textrm{Verify} : P_s \to \{0,1\}^* \to \Sigma \to \{T,F\}$. Any typical signature scheme will do.

Finally, this scheme requires a random oracle, typically approximated by a cryptographic hash function, from a tuple of the signing and target public keys to $Q$, $H : P_s \to P \to Q$.

There are two roles in this system, the user and certification agents. In practice both are likely to be under the control of the same user, but the certification agent might be embedded in a hardware security module, or simply a different software module with distinct access control.

Setup

The certification agent generates a signing key, $s_s$, and deriving the corresponding verifying key $p_s$. This signing-verifying key-pair may be reused for multiple target public keys.

$$s_s \stackrel{R}\leftarrow S_s\quad p_s := \textrm{Pub}_s(s_s)$$

Key Generation

The user agent generates a secret key, $s_c \in S$, and derives its corresponding public key, the committed value.

$$s_c \stackrel{R}\leftarrow S\quad p_c := \textrm{Pub}(s_c)$$

Either the user agent sends $p_c$ to the certification agent or the certification agent sends the verification key $p_s$ to the user agent. The recipient then calculates the hash of the certificate verifying key and the committed value, and, if that’s the certification agent, sends that hash to user agent.

$$h := H(p_s, p_c)$$

The user agent then derives the target secret and public keys using the related functions on the generated secret and public keys:

$$s := s_c \cdot h$$ $$p := \textrm{Pub}(s) = \textrm{Pub}(s_c \cdot h) = \textrm{Pub}(s_c) * h = p_c * h$$

The user agent or certification agent stores the committed value $p_c$, and the user agent proceeds to use $s$ and $p$.

Certificate Issuance

To issue a certificate concerning the target public key, the certification agent requires the committed value, $p_c$. Assuming it does not have it already, the user agent sends $p_c$ to the certification agent who signs a certificate containing it and any other claims about the public key $p$.

$$\sigma \leftarrow \textrm{Sign}(s_s, p_c || …)$$

The certificate $(p_s, \sigma, p_c, …)$ may then be distributed publicly.

Certificate Verification

Any recipient may then verify the signature on the certificate and that $p = p_c * H(p_s, p_c)$.

$$\textrm{Verify}(p_s, \sigma, p_c || …)\quad p \stackrel?= p_c * H(p_s, p_c)$$

If both checks pass, the certificate is valid.