7 Spend authorisation

Let $E$ be the event that the observer queries $𝖧$ at $T\parallel w$. In a second experiment, $𝖧(T\parallel w)$ is replaced, in the computation of $\alpha$ only, by a uniform $64$-byte string $U$ independent of all else. In the lazy realisation of the random oracle (Crypto Guide, §“The random oracle model”, Definition “Random oracle”) the answers at inputs other than $T\parallel w$ are independent of $𝖧(T\parallel w)$, so the two experiments are identical until $E$ occurs; $E$ has the same probability in both, and their outputs are within statistical distance $\mathrm{Pr}[E]$ (Crypto Guide, §“Security as a game”, Remark “Game-hopping”). In the second experiment the observer’s view is independent of $T$, so each query agrees with $T\parallel w$ in its first $80$ bytes with probability at most $2^{-640}$, and $\mathrm{Pr}[E]\le q_h\cdot 2^{-640}$ by the union bound. There $U$ is independent of $𝖧$, of $T$ and of the observer’s coins, and the pair of view and $\alpha$ is a function of $\alpha =\mathrm{ToScalar}(U)$ and of them. Replacing $\alpha$ by a uniform scalar changes the pair by at most ${\delta }_{512}$ (Assumption 7.3; Math Guide, §“Statistical distance”, Theorem “Properties of statistical distance”, part (4)). The triangle inequality, part (2) of the same theorem, gives (5). □

(i) For each $i$ this is the Crypto Guide’s Theorem “Perfect unlinkability of re-randomised keys” (§“Key re-randomisation and unlinkability”). The base $G^{\mathrm{𝖲𝗉𝖾𝗇𝖽𝖠𝗎𝗍𝗁}}$ generates the Pallas group, of prime order $p_{\mathrm{𝖵𝖾𝗌𝗍𝖺}}$ (§7.1), so $\alpha \mapsto [\alpha ]G^{\mathrm{𝖲𝗉𝖾𝗇𝖽𝖠𝗎𝗍𝗁}}$ is a bijection from ${𝔽}_{p_{\mathrm{𝖵𝖾𝗌𝗍𝖺}}}$ onto the group, and translation by ${\mathrm{𝖺𝗄}}_i^{\mathbb{P}}$ is a bijection of the group; hence ${\mathrm{𝗋𝗄}}_i$ is uniform whatever ${\mathrm{𝖺𝗄}}_i^{\mathbb{P}}$ is, and the independence of the ${\alpha }_i$ gives the product distribution. The scalar ${\mathrm{𝖺𝗌𝗄}}_i+{\alpha }_i$ is uniform for every fixed ${\mathrm{𝖺𝗌𝗄}}_i$ because ${\alpha }_i$ is, and ${\mathrm{𝗋𝗄}}_i=[{\mathrm{𝖺𝗌𝗄}}_i+{\alpha }_i]G^{\mathrm{𝖲𝗉𝖾𝗇𝖽𝖠𝗎𝗍𝗁}}$. Equal distributions give every distinguisher advantage zero (Math Guide, §“Statistical distance”, Theorem “Properties of statistical distance”, part (3)).

(ii) The randomisers are replaced by independent uniform scalars one at a time, for $i=1,\mathrm{\dots },n$. At step $i$ the lemma on the distance of $\mathrm{𝖦𝖾𝗇𝖱𝖺𝗇𝖽𝗈𝗆}$ from uniform applies, with $w=\epsilon$, to the observer extended by the rest of the experiment: it holds the points and ${\alpha }_1,\mathrm{\dots },{\alpha }_{i-1}$, already uniform; it draws $T_{i+1},\mathrm{\dots },T_n$ itself and queries $𝖧$ at them; it receives ${\alpha }_i$, computes the tuple and runs the given observer. It makes at most $q_h+n-i$ queries, and the given observer’s view and the tuple are a function of its view and ${\alpha }_i$. By (5) and part (4) of the same theorem, step $i$ changes the pair of view and tuple by at most ${\delta }_{512}+(q_h+n-i)\cdot 2^{-640}$. By the triangle inequality, the $n$ steps together change it by at most

After the last step the ${\alpha }_i$ are uniform, independent and independent of $𝖧$, so by (i) the tuple is uniform and independent of $𝖧$, for every assignment of the points. The triangle inequality through that common distribution gives the factor $2$ for two assignments. □

The argument is route (ii) of the Crypto Guide’s Remark “Unforgeability under re-randomised keys, and the key-prefixing subtlety” (§“Key re-randomisation and unlinkability”), with the bound of its Theorem “EUF-CMA security of Schnorr signatures in the ROM” (§“Security in the random oracle model and the forking lemma”), which applies to RedPallas with the generator replaced by the base $G^{\mathrm{𝖲𝗉𝖾𝗇𝖽𝖠𝗎𝗍𝗁}}$ (Construction “RedDSA”). The Orchard steps are made in place; write $G:=G^{\mathrm{𝖲𝗉𝖾𝗇𝖽𝖠𝗎𝗍𝗁}}$.

(1) Idealisation. First, the nonce $r_i$ of each oracle answer is replaced by a uniform scalar. By the lemma on the distance of $\mathrm{𝖦𝖾𝗇𝖱𝖺𝗇𝖽𝗈𝗆}$ from uniform, with $w=\underset{¯}{{\mathrm{𝗋𝗄}}_i}\parallel M_i$ and the rest of the experiment as observer, each of the at most $q_s$ replacements costs at most ${\delta }_{512}+(q_h+2q_s)\cdot 2^{-640}$: apart from this nonce query, the experiment queries $𝖧$ at most $q_h$ times for $𝒜$, $q_s-1$ times for other nonces, $q_s$ times for challenges and once for validating the forgery. Second, the answers of $𝖧$ to the queries of $𝒜$ and to the validation query are replaced by uniform preimages, under $\mathrm{ToScalar}$, of uniform scalars, so that their values under ${𝖧}^{⊛}$ are uniform on ${𝔽}_{p_{\mathrm{𝖵𝖾𝗌𝗍𝖺}}}$. Each of these at most $q_h+1$ replacements costs at most ${\delta }_{512}$, because in both distributions an answer, conditioned on its reduction, is uniform on the preimages of that reduction. The forging probability thus drops by at most $\eta$ (Math Guide, §“Statistical distance”, Theorem “Properties of statistical distance”, part (3)).

(2) Embedding. The reduction receives a discrete-logarithm challenge $Y=[x]G$ with $x$ uniform and gives $𝒜$ the key ${\mathrm{𝖺𝗄}}^{\mathbb{P}}:=Y$.

(3) Signing. It answers the $i$-th query $({\alpha }_i,M_i)$ without $x$, under ${\mathrm{𝗋𝗄}}_i:={\mathrm{𝖺𝗄}}^{\mathbb{P}}+[{\alpha }_i]G$, by the simulator of the Crypto Guide’s Lemma “Signature simulation” (§“Security in the random oracle model and the forking lemma”): it draws $u_i$ uniform on the $64$-byte strings and $S_i$ uniform on ${𝔽}_{p_{\mathrm{𝖵𝖾𝗌𝗍𝖺}}}$, sets $c_i:=\mathrm{ToScalar}(u_i)$ and $R_i:=[S_i]G-[c_i]{\mathrm{𝗋𝗄}}_i$, programs $𝖧$ at $\underset{¯}{R_i}\Vert \underset{¯}{{\mathrm{𝗋𝗄}}_i}\Vert M_i$ to $u_i$, aborting if that entry is already defined, and returns ${\sigma }_i:=\underset{¯}{R_i}\parallel {\mathrm{𝖨𝟤𝖫𝖤𝖮𝖲𝖯}}_{256}(S_i)$. After step (1) a real answer has a uniform nonce $r_i$ and, at a fresh input, the challenge $c_i=\mathrm{ToScalar}(u_i)$ for a uniform $u_i$; then $S_i=r_i+c_i(x+{\alpha }_i)$ is uniform given $u_i$, and $R_i=[S_i]G-[c_i]{\mathrm{𝗋𝗄}}_i$, which is the simulated distribution (Crypto Guide, §“The Schnorr identification protocol”, Theorem “Special honest-verifier zero knowledge”). The point $R_i$ is uniform, so the reduction aborts with probability at most $q_s(q_h+q_s)/p_{\mathrm{𝖵𝖾𝗌𝗍𝖺}}$, as in the lemma. Key prefixing places $\underset{¯}{{\mathrm{𝗋𝗄}}_i}$ in every programmed input: entries programmed under distinct keys have distinct inputs, and the simulation needs no relation among the ${\mathrm{𝗋𝗄}}_i$.

(4) Critical query. Let $({\mathrm{𝗋𝗄}}^{\ast },M^{\ast },{\sigma }^{\ast })$ be a forgery, with ${\sigma }^{\ast }={\overline{R}}^{\ast }\parallel {\overline{S}}^{\ast }$ decoding to $R^{\ast }\ne \perp$ and . If ${\mathrm{𝗋𝗄}}^{\ast }=𝒪$, the scalar ${\mathrm{𝗋𝗌𝗄}}^{\ast }:=0$ satisfies (i), and in (ii) $x=-{\alpha }^{\ast }$; the reduction outputs these. Let ${\mathrm{𝗋𝗄}}^{\ast }\ne 𝒪$. The validation input ${\overline{R}}^{\ast }\Vert \underset{¯}{{\mathrm{𝗋𝗄}}^{\ast }}\Vert M^{\ast }$ is not a programmed entry. Its first $32$ bytes, its next $32$ bytes and its remainder would otherwise give ${\overline{R}}^{\ast }=\underset{¯}{R_i}$, ${\mathrm{𝗋𝗄}}^{\ast }={\mathrm{𝗋𝗄}}_i$ and $M^{\ast }=M_i$ for some $i$, the second by injectivity of $P\mapsto \underset{¯}{P}$, and the challenge would be $c_i$. Then $R^{\ast }=R_i$, and (4) gives $[S^{\ast }]G=R_i+[c_i]{\mathrm{𝗋𝗄}}_i=[S_i]G$. Since $G$ generates the group, of prime order $p_{\mathrm{𝖵𝖾𝗌𝗍𝖺}}$, and , this forces $S^{\ast }=S_i$, so ${\sigma }^{\ast }={\sigma }_i$ and the triple is an oracle answer. The input was queried by $𝒜$, except with probability at most $1/p_{\mathrm{𝖵𝖾𝗌𝗍𝖺}}$: otherwise its value under ${𝖧}^{⊛}$ is a uniform scalar drawn at validation, and, since ${\mathrm{𝗋𝗄}}^{\ast }\ne 𝒪$ generates the group, at most one scalar satisfies (4). This guessing term is part of the term $Q/p_{\mathrm{𝖵𝖾𝗌𝗍𝖺}}$ of the cited theorem.

(5) Fork. The reduction wraps $𝒜$ as the algorithm of the Crypto Guide’s Theorem “General forking lemma” (§“Security in the random oracle model and the forking lemma”), with challenge set ${𝔽}_{p_{\mathrm{𝖵𝖾𝗌𝗍𝖺}}}$, $Q$ prepared challenges $c_1,\mathrm{\dots },c_Q$, and coins that include those of $𝒜$ and of the simulator. The wrapper answers the $j$-th distinct unprogrammed query to $𝖧$, of $𝒜$ or of validation, with a uniform preimage of $c_j$ under $\mathrm{ToScalar}$, and returns the index of the critical query with $𝒜$’s output. The two runs of the forking algorithm share the coins and the challenges before that index, so $𝒜$ makes the same critical query in both, with the same ${\overline{R}}^{\ast }$, the same ${\mathrm{𝗋𝗄}}^{\ast }$, since key prefixing makes ${\mathrm{𝗋𝗄}}^{\ast }$ part of the critical input, and the same $M^{\ast }$. In (ii) they also share ${\alpha }^{\ast }$, which ${\mathrm{𝗋𝗄}}^{\ast }$ determines because $G$ generates the group. The runs receive distinct challenges $c\ne c^{\prime }$ at the critical index and return responses $S^{\ast }$ and $S^{\prime \ast }$.

(6) Extraction. The transcripts $(R^{\ast },c,S^{\ast })$ and $(R^{\ast },c^{\prime },S^{\prime \ast })$ are accepting for ${\mathrm{𝗋𝗄}}^{\ast }$ with $c\ne c^{\prime }$, so the Crypto Guide’s Theorem “2-special soundness” (§“The Schnorr identification protocol”) gives

the discrete logarithm of ${\mathrm{𝗋𝗄}}^{\ast }$, which is (i). For (ii) the reduction outputs ${\mathrm{𝗋𝗌𝗄}}^{\ast }-{\alpha }^{\ast }=x$. The probability bound follows as in the cited theorem, from the forking bound

with $\mathrm{𝑎𝑐𝑐}$ at least $ϵ-\eta$ less the abort and guessing terms of steps (3) and (4). □