5
$\begingroup$

Most signature schemes first hash the data and than sign the hash. Correct me if I am wrong: The signature does not prove that the signatory was in possession of the document itself? In cases where the document hash but not the document itself is public, anyone could create a signature for the document without having access to the document data itself. Is there any well known signature scheme that gives a proof of data possession?

I am interested on any hints to existing signature schemes that provide proof of data possession at time of signature creations.

My question is if there are any existing well known/reviewed signature schemes that provide proof of data possession. I am not asking how to "roll your own".

Improve this question
$\endgroup$
3
  • $\begingroup$ Have you read about proofs of ownership? (not in a cryptocurrency context) $\endgroup$
    – Daniel
    Commented Jan 30, 2018 at 12:08
  • 1
    $\begingroup$ Possible duplicate of Non-outsourceable digest-free signature scheme $\endgroup$
    – dade
    Commented Jan 30, 2018 at 12:15
  • $\begingroup$ I did some rough searching. But I could only find challenge based interactive protocols in the cloud storage context. $\endgroup$
    – Titusz
    Commented Jan 30, 2018 at 12:17

1 Answer 1

Reset to default
4
$\begingroup$

If the document is short enough, then its ISO/IEC 9796-2 signature proves data possession, for a simple reason: in so-called total recovery mode, signature verification recovers the document as a byproduct.

ISO/IEC 9796-2 is an RSA or Rabin signature scheme, also requiring a hash. Depending on options, the "recoverable" message (that is, embedded in the signature) can be up to about $n-h-16$ bits, for $n$-bit public modulus and $h$-bit hash. For example, with 4096-bit RSA and SHA-256, the message can be up to 478-octet, embedded in a 512-octet signature.

ISO/IEC 9796-2 mode 1 is in wide use in Smart Cards. However, beware that it has a near-practical weakness allowing forgery from the signature of chosen messages. ISO/IEC 9796-2 mode 3 is functionally compatible with mode 1, and cures that. Both are deterministic, and maximize the size of the embedded message. ISO/IEC 9796-2 mode 2 is randomized, like RSASSA-PSS, which allows a stronger security argument, at the expense of reducing maximum message size for total recovery.

Independently: for any signature scheme with appendix signing a hash, including RSASSA-PSS and (EC)DSA, changing $\mathcal S_\text{priv}(\operatorname H(M))$ to $$\mathcal S_\text{priv}(\operatorname H(M))\|\mathcal S_\text{priv}(\operatorname{HMAC-H}(\mathcal S_\text{priv}(\operatorname H(M)),M))$$proves possession of $M$ as well as a static signature can do. That has the advantage of working with large messages. This is not standardized, but is a straightforward combination of standardized things.

Addition per comment: this is out of my head. However, the security argument (not proof) is simple:

  • $\operatorname{HMAC-H}$ is a standard Message Authentication Code construction from a hash.
  • A standard single-pass interactive proof of data possession is using $\operatorname{MAC}(R,M)$ where $R$ is a random challenge used as key of the MAC.
  • Signing that gives insurance that the signer is involved.
  • Replacing $R$ with the signature of the hash makes it non-interactive and invoking the signer before the HMAC could be computed, yet verifiable.

Still, a dishonest signer can offload all hashing to a third party, but that seems inevitable. And an imprudent signer hashing-and-signing any message can be abused into signing a proof of possession of something s/he did not keep (because HMAC's result is a hash).

Note: I chose this, at the price of requiring two signatures, rather than $$\mathcal S_\text{priv}(\operatorname H(M))\|\operatorname{HMAC-H}(\mathcal S_\text{priv}(\operatorname H(M)),M)$$ because:

  • The security argument of the former is more straightforward.
  • The later succumbs if $H$ turns out not to be collision-resistant: an attacker could find $M$ and $M'$ with $H(M)=H(M')$, give $M'$ to signer, obtain $\mathcal S_\text{priv}(\operatorname H(M'))$ as part of proof of possession of $M'$ by honest signer, and turn that into a (different) forged proof of possession of $M$, when the honest signer never knew that $M$.
  • Involving the signer at beginning and end of preparation of the proof of possession arguably makes repudiation harder.
Improve this answer
$\endgroup$
3
  • $\begingroup$ One problem with RSA is that it allows 'blinding'; if you do that, then the guy with the RSA private key doesn't actually see the value being signed (which would appear to be in conflict with the goal 'proof of data possession'). I don't know of a why to do blinding with ECDSA; however I also don't know of a proof that there isn't a way either... $\endgroup$
    – poncho
    Commented Jan 30, 2018 at 14:13
  • $\begingroup$ I was looking for short signatures without total recovery mode. The signature mixing-rehashing you propose is very much what I was looking for and is close to what I had in mind. Any further references that add credibility to this? $\endgroup$
    – Titusz
    Commented Jan 30, 2018 at 14:19
  • $\begingroup$ @poncho: whatever is doing $x\to x^d\bmod N$ in ISO/IEC 9796-2 signature restricted to total recovery can check that no blinding occurs, because $x$ has built-in redundancy resisting blinding (much like in RSASSA-PSS, or RSASSA-PKCS1-V1_5, the thing doing the modexp could check that the corresponding padding is used). $\endgroup$
    – fgrieu ♦
    Commented Jan 30, 2018 at 14:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.