Hybrid Sequence:
The starting point is $\lib{sig-real}$.
First, apply the security of signature scheme $\Sigma$. The standard three-hop maneuver is not shown.
Rewrite the check $(X,S) \in \mathcal{S}$ explicitly in terms of equality tests. This will make it easier to apply the collision resistance of $H$ later.
Instead of storing $H(T,\ptxt)$ in $\mathcal{S}$, we can store $\ptxt$ in $\mathcal{S}$ and recompute its hash $H(T,\ptxt)$ later when it is needed.
Now that $\sigver$ is implemented in terms of hash comparisons, we can apply the collision resistance of $H$ (\definitionref{crhf.def.crhf}). The standard three-hop maneuver is not shown.\FORMATTINGHACK{\pagebreak}
The for-loop is just an explicit implementation of the check $(\ptxt,S) \in \mathcal{S}$. Rewriting in this way results in $\lib{sig-fake}$.
$\lib{sig-real}$
$(\pk',\sk) := \Sigma.\KeyGen()$
$T \gets \bits^\secpar$
$\pk := (\pk,T)$
$\sigpk$( ):
return $\pk$
$\sigsign$($\ptxt$):
// $\Sign\bigl( (\sk,T), \ptxt \bigr)$:
$X := H(T,\ptxt)$
$S := \Sigma.\Sign(\sk,X)$
return $S$
$\sigver$($\ptxt,S$):
// $\Verify\bigl( (\pk,T), \ptxt,S \bigr)$:
$X := H(T,\ptxt)$
return $\Sigma.\Verify(\pk',X,S)$