2
$\begingroup$

Let's say I have a message 0123456789abcdefghijklmnopqrstuvwxyz which gives me the SHA-256 hash 74e7e5bb9d22d6db26bf76946d40fff3ea9f0346b884fd0694920fccfad15e33.

I want to prove to someone that I know a part of the message that hash to the hash, for example xxx34567xxxxxxxxxxxxxxx is it possible to do this? Obviously the counter party should not know what xxxxxxxxx stands for.

Improve this question
$\endgroup$
4
  • $\begingroup$ Are you trying to prove that the part of the input is "34567"? I.e., are you revealing "34567" to the other party? So you actually know the rest of the key? $\endgroup$
    – Maeher
    Commented Jan 9, 2020 at 6:51
  • $\begingroup$ @fgrieu If Maarten interpreted the question correctly, then the prover does not know the witness. Which is indeed a problem. $\endgroup$
    – Maeher
    Commented Jan 9, 2020 at 6:52
  • $\begingroup$ @Maarten - reinstate Monica : I do not get what exactly you deem impossible, nor your reasoning after "And since..". True, the question fails to tell if the verifier initially knows the content of the segment 34567, nor if that can be revealed in the proof. But for all combinations of that, as long as the verifier knows and trusts the hash itself, and the message length is small and not confidential, I see no impossibility. Admitedly that's not possible with a black-box ideal hash, but SHA-256 is a public combinatorial function. $\endgroup$
    – fgrieu ♦
    Commented Jan 10, 2020 at 15:17
  • $\begingroup$ I've removed the comment, but there are still 18 "x"-es in that question, I wonder if that's practical. I guess it's just an example though. Oh, I see that your latest question is about feasibility, and it seems feasible (?). $\endgroup$
    – Maarten Bodewes ♦
    Commented Jan 12, 2020 at 20:16

1 Answer 1

Reset to default
2
$\begingroup$

I'm reading the question as:

  • Prover knows a message (thus its SHA-256 hash, and message length), and position+length of a substring (thus the substring).
  • Verifier knows the hash, the substring and its position (thus length), and message length.

Prover should demonstrate knowledge of a message with such SHA-256 hash and length and with such substring at such position, without revealing more information about such message.

This is possible: we define a variant of SHA-256 with fixed message length and fixed substring at fixed position. The problem then reduces to demonstrating knowledge of input of that hash to a verifier knowing the hash, which is covered in this question.

I do not know exactly how much info must be exchanged between prover and verifier.

A concrete implementation is described by Irene Giacomelli, Jesper Madsen, Claudio Orlandi, ZKBoo: Faster Zero-Knowledge for Boolean Circuits, in proceedings of SEC'2016.

Improve this answer
$\endgroup$
0

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.