Non-outsourceable digest-free signature scheme Given a message $M$, I am looking for a signature scheme that does not involve first computing the digest $H(M)$ and then signing $H(M)$. Signature schemes on digests are outsourceable in the sense that the private key holder does not need custody of $M$ while signing (the digest $H(M)$ suffices and can be generated by a third party).

For context, I am trying to build a "proof of custody" scheme, where some private key holder proves he also had the original message $M$ in full at the point of signing.
I will be basing this construction on Schnorr signatures, since I am most familiar with those. I will also use elliptic curve, for the same reason; see ECDH.

Recall:


Schnorr signatures are a Fiat-Shamir transformation of the Schnorr identification protocol. Fiat-Shamir transforms an interactive proof of knowledge into a signature.
The Schnorr identification protocol (interactively) proves the knowledge of a discrete logarithm; i.e., Alice (who signs $m$) has access to a secret key $x$, with corresponding public key $Y=xG$. Now $x$ is said to be the discrete logarithm of $Y$.


Applying this terminology to your question, I would say we want to prove that Alice has access to $m$ and $x$. Alice can, for example, prove that she knows the discrete logarithm $ms$ of $mxG=mY$. She can do this by applying a regular Schnorr signature using public key $Y'=mY$ and secret key $x'=mx$:


Let $k$ be a random field element; set $R = kG$.
Let $e=\mathcal{H}(R)$
Let $s=k-x'e=k-mxe$


The signature is $(s,e)$. Bob verifies:


Let $R_v=sG+eY'=sG+emY$
Let $e_v=\mathcal{H}(R_v)$


The signature is valid iff $e=e_v$, since $R_v=sG+eY'=(k-mxe)G+emY=kG-mxeG+emxG=kG$.

Of course, this supposes that it is feasible to multiple your (potentially large) message $m$ with the secret key. This also assumes that $m&lt;q$ (smaller than the order of the field $\mathbb{F}_q$, since Eve can otherwise compress $|m| \bmod q$. You can circumvent this by signing in blocks of size $m_i&lt;q$.