## 5 A Novel Signature Scheme
Definition 2: The scheme \(\mathcal{PS}\) is a secure Pre-Signature scheme if and only if it satisfies the following properties:  
Correctness: _Completed signatures succed verification iff valid, i.e., given \((k,S_{P})=\mathrm{register}(P,n)\),_  
\[\mathrm{verify}(\mathrm{complete}(\mathrm{pre-sign}(m,P),b),v)=\mathrm{True} \iff\exists(b,v)\in S_{P}.\]  
_In other words, given a message_ \(m\)_, a valid Pre-Signature_ \(\sigma\) _on_ \(m\)_, and a valid completed signature_ \(\overline{\sigma}\) _on_ \(m\) _and_ \(\sigma\) _using_ \(b_{i}\)_, the verification_ \(\mathrm{verify}(\overline{\sigma},m,v_{i})\) _succeeds if and only if_ \((b_{i},v_{i})\) _is a pair of blinding key, verification code in_ \(S_{P}\)_._  
Unforgeability: _For a malicious prover_ \(\tilde{P}\)_, creating a valid completed signature for_ \(m^{*}\) _using any_ \((b^{*},v^{*})\in S_{P}\)_without_ \(\mathrm{pre-sign}(m^{*},\tilde{P})\) _is_ hard_._  
Non-transferability: _For a malicious prover_ \(\tilde{P}\) _knowing any_ \(\mathrm{pre-sign}(m^{*},\tilde{P})\) _and_ \(\mathrm{pre-sign}(m^{*},\)__\(P^{\prime}\
eq\tilde{P})\)_, creating a valid completed signature for_ \(m^{*}\) _and a target_ \((b^{\prime},v^{\prime})\in S_{P^{\prime}}\) _is_ hard_._  
Indistinguishability: _Let_ \(\sigma_{0}=\mathrm{pre-sign}(m_{0},P_{0})\)_,_ \(\sigma_{0}=\mathrm{complete}(\sigma_{0},b_{0})\)_,_ \(v_{0}\) _the associated verification code, and_ \(k_{0}\)_,_ \(P_{0}\)_'s hidden key. Similarly for_ \(P_{1}\)_,_ \(\sigma_{1}\)_,_ \(\bar{\sigma}_{1}\)_,_ \(b_{1}\)_,_ \(v_{1}\)_, and_ \(k_{1}\)_. Given only_ \(pk\)_,_ \((m_{0},\bar{\sigma}_{0},v_{0})\) _and_ \((m_{1},\bar{\sigma}_{1},v_{1})\)_, determining whether_ \(P_{0}=P_{1}\) _(or, equivalently, whether_ \(k_{0}=k_{1}\)_) is hard._  
We propose below a construction of \(\mathcal{PS}_{\mathrm{RSA}}\), a Pre-Signature scheme based on the RSA encryption/signature scheme:  
* keygen: \(pk=(e,N)\) and \(sk=(d,N)\) with \((e,d,N)=\mathrm{keygen}_{\mathrm{RSA}}(\ell)\);
* register: \(k\) and \((b_{i})_{i=1}^{n}\) are chosen at random in \(\mathbb{Z}_{N}\), and \(v_{i}=(kb_{i})^{e}\pmod{N}\);
* pre-sign: \(\sigma=h(m)^{d}k\pmod{N}\), with \(k\) the hidden key associated with \(P\), and \(h\) a secure hash function;  
Figure 7: Sequence Diagram for Typical Operation of a Pre-Signature Scheme. complete: \(\vartheta=\sigma b\pmod{N}\);  verify: returns True if and only if \(\vartheta^{\varepsilon}\equiv h(m)\upsilon\pmod{N}\). **Theorem 1**. : \(\mathcal{PS}_{RSA}\) _is a secure Pre-Signature scheme._  
Proof. : The four properties from Definition 2 are satisfied:  
**Correctness**: \(\vartheta^{\varepsilon}\equiv(\sigma b)^{\varepsilon}\equiv(h(m)^{d}kb)^{ \varepsilon}\equiv h(m)(kb)^{\varepsilon}\equiv h(m)\upsilon\pmod{N}\). **Unforgeability**: Without knowing \(\sigma^{*}\) or its own hidden key \(k\), for \(\hat{P}\) to compute a valid completed signature \(\vartheta^{*}\equiv(h(m^{*})\upsilon^{*})^{d}\pmod{N}\) would require computing the \(e\)th root of \(h(m^{*})\upsilon^{*}\). This reduces to the RSA problem. **Non-transferability**: Creating a completed signature for \(m^{*}\) and a target \((b^{\prime},b^{\prime})\in S_{P^{\prime}}\) requires knowing the blinding key \(b^{\prime}\) associated with the target verification code \(\upsilon^{\prime}\). The blinding key can be isolated by \(\bar{P}\) as \(\upsilon^{\prime}/\upsilon(b\sigma/\sigma^{\prime})^{\varepsilon}\equiv(k^{ \prime}b^{\prime})^{\varepsilon}/(kb)^{\varepsilon}(bk/k^{\prime})^{ \varepsilon}\equiv(b^{\prime})^{\varepsilon}\pmod{N}\) using known quantities. Computing \(b^{\prime}\) from \(\upsilon^{\prime}/\upsilon(b\sigma/\sigma^{\prime})^{\varepsilon}\pmod{N}\) reduces to the RSA problem. **Indistinguishability**: The problem of determining \(r\) and \(s\) from \(rs\pmod{N}\) (given \(r\) and \(s\) randomly distributed in \(\mathbb{Z}_{N}\)) solves integer factorization. Under this reduction, since the blinding keys are randomly selected (in advance, by \(I\)), one cannot determine the blinding key or the Pre-Signature from a completed signature.