Message-Recovery variant of Ed25519 signature?

Question

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.

Answer 1

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!)