# Message-Recovery variant of Ed25519 signature?

What would be a Message-Recovery variant of the Ed25519 signature scheme?

Ed25519-MR should be simple to use, fast, with a strong security argument, and striving to stay out of the patent minefield, as the original does.

[Ed25519] is a signature scheme with appendix: it adds a signature of 512 bits to the message that it signs, for 128-bit conjectured security. A Message-Recovery variant would embed some of the signed message into the signature, with that so-called recoverable part of the message a byproduct of successful verification, that needs not be explicitly transmitted. We wish to minimize the overall signed message size.

Signatures schemes with message recovery of the Elliptic Curve Discrete Logarithm family have been proposed, patented and standardized (see bibliography), including ECNR (Nyberg-Rueppel), ECMR (Miyaji), ECAO (Abe-Okamoto), ECPV (Pintsov-Vanstone, aka ECPVS, PVSSR, ECSSR-PV), ECKNR (KCDSA/Nyberg-Rueppel) per their name in [ISO 9796-3].

Addition: I'm puzzled at the achievable gain over a signature scheme with appendix. My reading of [PV1999] and [AO1999] is that for $$b$$-bit security and arbitrary message, ECPV and ECAO embed $$b$$ bits into a $$4b$$-bit signature; when my limited understanding of other schemes is that some aim at embedding $$2b$$ bits.

Bibliography on (possibly Elliptic Curve) Discrete Logarithm Signatures with Message Recovery.

[NR1993]: Kaisa Nyberg and Rainer A. Rueppel, A new signature scheme based on the DSA giving message recovery, in proceedings of CCS 1993;
[NR1994]: id., Message recovery for signature schemes based on the Discrete Logarithm problem, in proceedings of EuroCrypt 1994;
[US'725]: Rainer A. Rueppel and Kaisa Nyberg, Digital signature method and key agreement method, US 5,600,725.

[M1995a] and [M1995b]: Atsuko Miyaji, Weakness in message recovery signature schemes based on discrete logarithm problems (continued), in IEICE TF;
[Mi1996a]: id., Signature equation suitable for message recovery schemes in IEICE TF;
[Mi1996b]: id., A message recovery signature scheme equivalent to DSA over elliptic curves, in proceedings of AsiaCrypt 1996;
[Mi1997]: id., Another countermeasure to forgeries over message recovery signature in IEICE TF;
[JP'357]: Miyaji Mitsuko, Message decoding type signature system, JP Pub.# H09-034357 ;
[JP'492]: id., Signature system, JP Pub.# H09-160492 .

[AO1999]: Masayuki Abe and Tatsuaki Okamoto, A Signature Scheme with Message Recovery as Secure as Discrete Logarithm in proceedings of AsiaCrypt 1999;
[AO2001] id., id., in IEICE TF;
[JP'178]: id., Message recovery type signature system and program storage medium therefor, JP Pub.# 2001-134178 .

[PV1999]: Leon A. Pintsov and Scott A. Vanstone, Postal Revenue Collection in the Digital Age, in proceedings of FC 2000;
[PV2000]: id., submissions to IEEE P1363a, including [PVSSR-D2] and [PVSSR-D3].

[BJ2001]: Daniel R. L. Brown, Don B. Johnson, Formal Security Proofs for a Signature Scheme with Partial Message Recovery, in proceedings of CT-RSA 2001; drafts: [BJ2000-02], [BJ2000-06].

[P1363a]: IEEE Standard 1363a-2004 - Specifications for Public-Key Cryptography - Amendment 1: Additional Techniques.

[ISO ISO9796-3]: ISO/IEC 9796-3:2006, Information technology — Security techniques — Digital signature schemes giving message recovery — Part 3: Discrete logarithm based mechanisms. Free previews in HTML and PDF.

[X9.92-1]: ANS X9.92-1-2009 (reaffirmed 2017, reportedly without change). Public Key Cryptography for the Financial Services Industry - Digital Signature Algorithms Giving Partial Message Recovery - Part 1: Elliptic Curve Pintsov-Vanstone Signatures (ECPVS).

[Ed25519]: Daniel J. Bernstein, Niels Duif, Tanja Lange, Peter Schwabe, Bo-Yin Yang, High-speed high-security signatures, in proceedings of CHES 2011.

• One might be able to trim the state size of Keccak down to 512 bits, maintain the 64 bit width, index for theta and chi would change from mod 5 to mod 3, phi and rho would need to get reduced with justification, iota could go unchanged, reversible domain extension might be possible by removing XOR and replacing with a modified theta (via bit twisted theta definition) and inserting previous value into IV (That part that should be checked). Or save time and say 1600 bit signature is acceptable. Output is never truncated (entire state only) ,whole message recovery a possibility! – Q-Club Sep 12 '17 at 6:14
• @back_seat_driver: How exactly does that work as a public-key signature scheme with separate signing and verification keys? – Squeamish Ossifrage Sep 13 '17 at 17:55
• @SqueamishOssifrage I'm not sure, it sounded like the goal was to hash a message that would produce a digest that at the very least matched a part of the message? I muddled through the problem poorly. – Q-Club Sep 14 '17 at 3:34
• Does this recent paper perhaps answer your question? It's based on [AO1999], but the patent you mention as [JP'178] has expired in the meantime. – xorhash May 3 '20 at 13:57

Fix finite fields $k$ and $k'$, say $k = \mathbb F_p$ and $k' = \mathbb F_{p^2}$ represented by $\mathbb F_p[i]/(i^2 + 1)$ where $$p = 36 u^4 + 36 u^3 + 24 u^2 + 6 u + 1$$ for $u = -2^{62} - 2^{55} - 1$. Fix a group $G$ written multiplicatively, say $(\mathbb F_{p^{12}})^\times$. Fix elliptic curves $E/k$ and $E'/k'$, say $E/k : y^2 = x^3 + 2$ and $E'/k' : y^2 = x^3 + 2/(1 + i)$, with a bilinear map $e\colon E(k) \times E'(k') \to G$, say the Tate pairing. Fix a random function $H\colon \{0,1\}^* \to E(k)$, say $m \mapsto {+}x^{-1}(\operatorname{SHA256}(m))$, where ${+}x^{-1}(x_0)$ is the point on $E(k)$ with $x$ coordinate $x_0$ and the lexicographically smallest $y$ coordinate. Fix a point $G \in E'(k')$ of large prime order. (This choice of curve $E/k$ and its twist $E'(k')$ is more popularly known as BN(2, 254).)

A public key is the byte encoding $\underline A$ of a point $A$ on $E'(k')$. A signature of a message $m$ under $\underline A$ is the byte encoding $\underline\sigma$ of an element $\sigma \in E(k)$ satisfying $$e(\sigma, G) = e(H(\underline A \mathbin\Vert m), A).$$

A private key is the byte encoding $\underline a$ of a secret scalar $a$; the corresponding public key is $\underline A = \underline{[a]G}$. To sign a message $m$ with private key $\underline a$, the signer computes $\sigma = [a]H(A \mathbin\Vert m)$. This yields a signature because \begin{align*} e(\sigma, G) &= e([a]H(\underline A \mathbin\Vert m), G) \\ &= e(H(\underline A \mathbin\Vert m), G)^a \\ &= e(H(\underline A \mathbin\Vert m), [a]G) \\ &= e(H(\underline A \mathbin\Vert m), A) \end{align*} by the bilinearity of $e$.

Note that in the choice of parameters above, a signature can be encoded in 32 bytes, or even a mere 255 bits, by combining a 254-bit encoding of an $x$ coordinate with a single bit to discriminate between the two possible $y$ coordinates. (Further compression of the curve points may be possible with techniques like Decaf, left as an exercise for the reader.)

Thus, you have 32 bytes and 1 bit left in your budget for a 64-byte Ed25519 signature to encode a part of the message, thereby enabling message recovery of 32 bytes (plus 1 bit) in 64-byte signatures!

Let us then define a Mr. Signature as a 64-byte string $\underline \sigma \mathbin\Vert m$ satisfying $$e(\sigma, G) = e(H(\underline A \mathbin\Vert m), A),$$ which admits message recovery by $\underline \sigma \mathbin\Vert m \mapsto m$.

(Am I joking? Maybe!)

• I'll need to think over the details in the security reduction. But I fully get the message recovery procedure, and the super-elasticity of the conception of variant. From a meta standpoint: I up-voted, but it is a dangerous slope. – fgrieu Sep 12 '17 at 4:32
• I'm a vulture. I circle dangerous slopes for breakfast! – Squeamish Ossifrage Sep 13 '17 at 17:39
• BN* and Ed25519, huh? How are these combined? An $e(\cdot, \cdot)$ exists for ed25519? AFAIK Curve/Ed25519 is not pairing friendly. – cypherfox May 7 '18 at 16:23
• @cypherfox It was a joke. The only relation is that there are elliptic curves involved. – Squeamish Ossifrage May 7 '18 at 16:25
• @SqueamishOssifrage Aww. No new magic. :( – cypherfox May 7 '18 at 16:26