# 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.

• Comments are not for extended discussion; this conversation has been moved to chat. – e-sushi Jan 29 '18 at 12:57

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:

1. Schnorr signatures are a Fiat-Shamir transformation of the Schnorr identification protocol. Fiat-Shamir transforms an interactive proof of knowledge into a signature.
2. 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$:

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

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

1. Let $R_v=sG+eY'=sG+emY$
2. 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<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<q$.

• It sounds like you can sign $m$ itself to get similar performance, right? – Daniel Jan 30 '18 at 12:36
• Yap, concluded the same, an hour after I wrote this... However, if someone's able to come up with a way that construction of $x'$ requires possession of all of $m$, this may be the way to go. – Ruben De Smet Jan 30 '18 at 14:02

Ok I think I cracked it thanks to Ruben de Smet's hint. The construction goes as follows:

Take $M$ and split it into an array of 32 bytes chunks so that $M$ is the concatenation of $M[0], M[1],\dots, M[n]$. Let $P$ be the private key. We now build a digest of $M$ by heavily incorporating $P$ at every step. For example, let the digest of $M$ be $H(H(M[0]\oplus P)\oplus \dots \oplus H(M[n] \oplus P))$ where $H$ is a hash function such as sha256. Now include a zero knowledge succinct proof (e.g. a SNARK or STARK) that the digest corresponds to $M$ without revealing $P$, and sign the digest plus the zero knowledge proof.

• I think you do not need to do this in zero knowledge, or is this a requirement? – Ruben De Smet Jan 29 '18 at 14:35
• You're right, the "zero knowledge" aspect only needs to guarantee that P stays private. – Randomblue Jan 29 '18 at 15:33

It is not completely clear from your question what exactly you mean by "proof of custody". But it sounds as if you want that the existence of a valid signature $\sigma$ on message $m$ under public key $\mathsf{pk}$ implies that at some point a party was in possession of both $m$ and the signing key $\mathsf{sk}$ corresponding to $\mathsf{pk}$.

I would argue that this is impossible to achieve. We know that (under standard assumptions) there exist secure two-party computation protocols for arbitrary functionalities. I.e., there exist protocols for two parties $A$ and $B$ with inputs $x$ and $y$ such that $A$ and $B$ are capable of jointly computing any functionality $f(x,y)$ without learning any information about the other party's input.

So let us assume that such a protocol exists where only $B$ receives the output $f(x,y)$. Then what we can do is the following: Have $A$ with input $\mathsf{sk}$ and $B$ with input $m$ execute the protocol to compute the functionality $\mathsf{Sign}(\mathsf{sk},m)$. By the correctness of the protocol, the result $\sigma$ received by $B$ is a valid signature on $m$ under $\mathsf{pk}$. But there does not exist a single party that has ever been in possession of both $\mathsf{sk}$ and $m$. (Even if the signature reveals $m$, $A$ does not learn $m$ since they do not receive output in the protocol.)

• I think it suffices to have a protocol in which it is more efficient (terms of used bandwidth, power, ...) to possess both $m$, sk, at a certain time, albeit just for the purpose of calculation, then it is to cheat. Randomblue needs to confirm this though. – Ruben De Smet Jan 29 '18 at 23:10
• @RubenDeSmet Well, from the description it is very unclear what the purpose of such a signature scheme would be. (Since no application is specified.) So it's really no possible to tell. But honestly I cannot think of any scenario where something like you suggest serves any purpose. In what scenario is it a problem that two parties jointly act as a signer? – Maeher Jan 30 '18 at 0:29
• I suppose some kind of blockchain scheme with proof of storage, but that's just what my mind makes of it. I suggest we take further conversation to the chat. – Ruben De Smet Jan 30 '18 at 10:01

The requirements aren't very clear and for different variants we get different answers. It seems the question asks for a non interactive proof that holder of a private key matching a known public key also has a copy of a certain message. This should work even if two adversaries Eve with the private key and Ivan with the message wish to collaborate to forge such a proof.

This is Impossible. Anט $f(P_k,M)$ which can be calculated by a legitimate holder can be calculated using secure multi party computation by two collaborating partners one with the key and one with the message without revealing either.

If you assume only one way communication one party prepares something for the other, my original answer stands: 1. Take message $M$

1. Produce $S = \mathsf{Sign}(\mathsf{digest}(M))$

2. Then $H = \mathsf{hash}(S \Vert M)$

3. Produce $(H,S)$

Optionally sign again

Other answers assume two way communication but with limited size (significantly less than the size of M assuming M is large).

You have two assume some limitation to prevent SMPC based forgery.

• This doesn't work. Both the computation of digest(M) and hash(S || M) are outsourceable. The signer never needs to hold custody of M. – Randomblue Jan 29 '18 at 11:30
• hash(S || M) can't be calculated without M. – Meir Maor Jan 29 '18 at 12:33
• A third party has M. When given S it can compute hash(S || M). We want to prevent outsourcing. – Randomblue Jan 29 '18 at 12:42
• What is the difference between two parties collaborating very closely (back and forth) and a single party. If they insist on being dishonest they can do anything. Even if they have secret data they don't want to share they can still calculate any function together. – Meir Maor Jan 29 '18 at 14:02
• I think the difference would be that the second party would need to have access to the secret key to be able to generate the requested signature. The requirement set by Randomblue is "a signature is valid when both M and the secret key were available to the signer." – Ruben De Smet Jan 29 '18 at 14:09