7
$\begingroup$

Suppose I have a secret 'X'. Which can be use as a seed to a deterministic random number generator to generate a number 'Y'. Is there any way to prove to others, that I have the secret 'X' which generated this number 'Y' without revealing the secret 'X' using zero knowledge proof, such as Schnorr's protocol.

$\endgroup$

migrated from security.stackexchange.com Jun 8 '17 at 13:52

This question came from our site for information security professionals.

  • $\begingroup$ Is deterministic_random_number_generator('X') = 'Y' every time or just the first time? $\endgroup$ – anon Jun 7 '17 at 13:37
  • 3
    $\begingroup$ IMO cryptography or math stack exchange sites will be able to give a better answer to this question. $\endgroup$ – Limit Jun 7 '17 at 16:49
  • $\begingroup$ @anon Yes, deterministic_random_number_generator('X') will give 'Y' every time. $\endgroup$ – prosaad Jun 8 '17 at 13:20
4
$\begingroup$

So let's assume you have the function $f$, which is publicly known, and you publish the value $y = f(x)$. And then you want to prove that you know $x$. You said $f$ is a deterministic random number generator (and I guess you meant a CSPRNG) - but from the given information I guess it's just important that it is one-way?

Anyway, there are two cases for $f$:

  • $f$ is defined in algebraic structures like finite groups/ rings/ fields and can be expressed as a polynomial, has structure preserving properties (like being bijective), etc. Then it might be possible to create an elegant proof of knowledge for that specific function, similar to Schnorr's protocol. But there is no catch-all method for all possible functions $f$, and it's possible that you can't find a proper proof of knowledge without revealing $x$ - it all depends on the function.
  • $f$ is actually non-algebraic, e.g. binary input and binary operations, and it most likely does not preserve structure of any kind, for example the practical hash functions and CSPRNGs. Then the following paper might give you an indication how this could be achieved: Zero-Knowledge Using Garbled Circuits: How To Prove Non-Algebraic Statements Efficiently by Jawurek,Kerschbaum and Orlandi (2013). SHA256 was one of the examples in there - however this is a very different kind of proof of knowledge than Schnorr's identification protocol. And of course, in this case it would also depend entirely on $f$, if this works - and if you are willing to accept its overhead. The example in the paper took around 5 seconds for a single proof of knowledge of a SHA256 preimage.
$\endgroup$
0
$\begingroup$

i think hashes are your answer:

  • Take X
  • H(x) = echo X | sha256sum | awk {print $1}
  • U(x) = echo H(X) | sha256sum | awk {print $1}
  • Display U(x) Publicly
  • Y(H(X))
  • Whatever you do with Y(H(X))
  • After everything is done you release H(X)
  • Anyone with doubts can see the seed's hash does indeed hash to U(H(X))

you only release H(X) when it is of no use to anyone anymore. i.e. the function you needed to keep it secret for is long over. this is the same method that distributed software is done. like ubuntu iso's and such. thats why they give that out, so you can verify the data was the same when they made it, and when you received it.

the seed is never known.

EDIT: i want to clarify that this is not technically "zero knowledge proof" as i don't make any use of probability theory here, but its simpler to accomplish the goals you have. To apply a true zero-knowledge proof, we would need to understand how X is created, and how Y() works since we would need to make sure that someone can determine with 1-probability very near 0 that your seed will result in Y(X) without knowing X somehow.

$\endgroup$
  • 1
    $\begingroup$ What I understand from your answer is, to hash my secret and use hash to generate Y. So that I can share hash of my secret, without sharing actual secret. But the question is then, how will I prove, that I generated this hash. An adversary can copy this hash and say that he/she generated this hash with a valid seed. How will you authenticate then (without the knowledge of actual seed)? $\endgroup$ – prosaad Jun 8 '17 at 13:34
  • 1
    $\begingroup$ This question adresses the problem of proving knowledge of a preimage of a hash function - but that is quite far from the practical approach considered in this answer. $\endgroup$ – tylo Jun 8 '17 at 14:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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