∃CM ⟹ ∃CM<sup>+</sup>

21 March 2022

∃CM ⟹ ∃CM⁺

In this chapter we could finally assemble a full-fledged $\ECM^+$ secure scheme. Compared to a $\ECM$ adversary, the extra power that a $\ECM^+$ adversary gains is his ability to communicate and act dynamically. To counter this extra power, our scheme has to be dynamic as well. Thankfully we have already collected the right idea: We sign each message by a fresh key pair, which is in turn certified by the root key. Here we use the simplest star topology to propagate trust (i.e. the root directly disseminates trust to all new keys), since the root key can be reused in the absence of one-time constraint.

Let $\Sigma = (\gen,\sgn,\vrf)$ be any $\ECM$ secure scheme, and $\Sigma^1 = (\gen^1, \sgn^1, \vrf^1)$ be any $\ECM^1$ secure scheme. (Surely $\Sigma$ itself can serve as $\Sigma^1$, but for optimal performance we might opt for a weaker but faster $\Sigma^1$.) We construct a $\ECM^+$ secure scheme $\Sigma^+ := (\gen, \sgn^+, \vrf^+)$ as follows:

By using fresh keys every time, we essentially enforce the adversary to roll back to a static setting. A formal security proof goes as follows.

Security proof. Let $A$ be any $\ECM^+$ adversary for $\Sigma^+$. Let $\ell = \ell(k)$ be a polynomial upper bound of its running time (technically we require $\ell$ to be time-reconstructable). Suppose that $A$ proposes the forgery $(m, ~pk^1 \Vert \eta \Vert \zeta)$. Define events

\[\begin{align*} E &:= \set{\text{the proposed $pk^1$ was used by the signer before}}, \\ F &:= \set{\vrf(pk, pk', \eta) \land \vrf^1(pk^1, m, \zeta)}. \end{align*}\]

Any given $A$ must fit in exactly one of the two categories:

First Category: $\Pr(E \mid F) \geq 1/2$.

Namely, when this $A$ produces valid forgery, he “prefers” reusing a key that was seen before. Suppose the event $E \cap F$ happens. Then the pair $(m,\zeta)$ is a valid forgery with respect to $pk^1$ – the same $pk^1$ for some previous round, as guaranteed by $E$.

Based on this observation, we may construct a $\ECM^1$ adversary $B$ for $\Sigma^1$ by embedding the attack in a random position $i \in [\ell]$ and running a virtual $A$. We leave the details to the reader. The adversary $B$ succeeds if $E \cap F \cap G$ happens where $G$ denotes the event that he guessed the correct position. Hence

\[P_B \geq \Pr(E \cap F \cap G) =\Pr(E \mid F) \cdot \Pr(F) \cdot \Pr(G) \geq \frac{P_A}{2\ell}.\]

So in this case $P_A$ has to be negligible.

Second Category: $\Pr(E \mid F) < 1/2$.

Namely, when this $A$ produces valid forgery, he “prefers” inventing a fresh key. Suppose the event $\bar{E} \cap F$ happens. Then the pair $(pk^1,\eta)$ is a valid forgery with respect to $pk$, since $pk^1$ is not seen before.

Based on this fact we may construct a $\ECM$ adversary $C$ for $\Sigma$. Again the detail is left to the reader. $C$ succeeds if $\bar{E} \cap F$, hence

\[P_C \geq \Pr(\bar{E} \cap F) = \Pr(\bar{E} \mid F) \cdot \Pr(F) \geq \frac{P_A}{2}.\]

So in this case $P_A$ also need to be negligible.

Combining the two cases we conclude the proof. ∎

Return↩︎