Zero-Knowledge proof for data being decryptable to a given hash preimage

[Oded Leiba]

Hi all,

I have posted a question on Cryptography stack exchange: https://crypto.stackexchange.com/questions/54481/zero-knowledge-proof-for-data-being-decryptable-to-a-given-hash-preimage.

TL;DR
I am interested in ZK proving

SHA256(Dec(Ex, SHA256^-1(Hr)) == Hx

where prover passes Ex, Hr and Hx to the verifier.

1) Is it generally ZK-provable? My intuition is yes, because this statement can be verified in polynomial time, hence is an NP statement.
2) Assuming answer to (1) is true, can it be implemented using zk-SNARKs and libsnark? If so, can I have some lead to how to approach this with libsnark?

Thanks for this library, highly appreciated project!
Oded

[Kobi Gurkan]

Hi Oded,

Your intuition is correct, that is indeed possible!

It's common these days to reason about zkSNARKs in the form of gadgets, which are, roughly, building blocks that embody both the description of variables and constraints needed to be satisfied and the method through which you assign values to the variables in order the satisfy the constraints.

In these case, you could use the combination of a SHA256 gadget and a symmetric decryption gadget to define the following constraints (given Ex, Hr and Hx as public inputs and r as a private input):

1. SHA256(r) == Hr

2. SHA256(Dec(Ex, r)) == Hx

Take note that a zkSNARK circuit has a fixed size, so your "r" and Dec(Ex, r) are not easily made to be of arbitrary size.

Practically, you have in libsnark the sha256_compression_gadget, which, by using Merkle-Damgård, you can hash inputs of any specific size (if you only need 512 bits - you're set, it will cover you).

For symmetric encryption, you could either use the method described here: https://github.com/zcash-hackworks/pay-to-sudoku/blob/master/snark/snark.tcc, a sha256-based stream cipher.

Alternatively, you have the Speck128 cipher in https://github.com/akosba/jsnark and also a SHA256 gadget there.

Keep in mind I don't evaluate the security of the different encryption methods here, but listing relatively easily attainable possibilities.

Since you're also in Israel, feel free to drop by our office in Rise Tel Aviv to discuss more :-)

Kobi

--
You received this message because you are subscribed to the Google Groups "libsnark" group.
To unsubscribe from this group and stop receiving emails from it, send an email to libsnark+unsubscribe@googlegroups.com.
To post to this group, send email to libs...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/libsnark/43afc4fd-3ed5-4f69-9802-6b9fa1387132%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--

----------

Kobi Gurkan

Core Team Lead

(+972)-549743033

[Daira Hopwood]

On 07/01/18 15:25, Oded Leiba wrote:
> Hi all,
>
> I have posted a question on Cryptography stack
> exchange: https://crypto.stackexchange.com/questions/54481/zero-knowledge-proof-for-data-being-decryptable-to-a-given-hash-preimage.
>
> TL;DR
> I am interested in ZK proving
>
> SHA256(Dec(Ex,SHA256^-1(Hr))==Hx
>
> where prover passes Ex, Hr and Hx to the verifier.

SHA256^-1(Hr) is not strictly speaking well-defined, since there may be multiple
preimages of Hr. I guess you mean, using Camenisch-Stadler notation:

{(k): SHA256(Dec(Ex, k)) == Hx and SHA256(k) == Hr}

If so, yes that's provable using zk-SNARKs and libsnark. The SHA256 gadget
is already implemented; you'll probably need to implement Dec yourself,
depending on which algorithm it is.

--
Daira Hopwood ⚧Ⓐ

[Oded Leiba]

Wow!
Thank you both for taking the time and replying so fast!

 

I'm glad both of you agreed this is in the zk-provable space :)

Kobi:

Take note that a zkSNARK circuit has a fixed size, so your "r" and Dec(Ex, r) are not easily made to be of arbitrary size.

Practically, you have in libsnark the sha256_compression_gadget, which, by using Merkle-Damgård, you can hash inputs of any specific size (if you only need 512 bits - you're set, it will cover you).

 

Well "r" is of fixed size (say 256 bit), but for "Dec(Ex, r)" I actually currently don't have (or prefer not to have) boundaries on size... Can I use this sha256_compression_gatget to help me out?
Will it have serious practical implications (let's say, MBs of data)?

Please recall that I need to prove something on the entire decryption (its hash)...
One of the reasons I was not confident in the feasibility of this idea is this quote from paper Efficient Zero-Knowledge Contingent Payments in Cryptocurrencies Without Scripts (BanasikStefan, Dziembowski, Malinowski 2016):
"the protocol of Zero-Knowledge Contingent Payment uses generic zero knowledge protocols, or can be used only for very simple problems (like selling the sudoku solution)"
- I'd love to get your take on that.

 Keep in mind I don't evaluate the security of the different encryption methods here, but listing relatively easily attainable possibilities.

Isn't there something similar to AES? I guess that's secure enough, no (or I missed your point here)?... :)

Since you're also in Israel, feel free to drop by our office in Rise Tel Aviv to discuss more :-)

That's great! I will definitely love that!

Daira:

SHA256^-1(Hr) is not strictly speaking well-defined, since there may be multiple 
preimages of Hr. I guess you mean, using Camenisch-Stadler notation: 

  {(k): SHA256(Dec(Ex, k)) == Hx and SHA256(k) == Hr} 

 

Yes, that's exactly what I meant :)

If so, yes that's provable using zk-SNARKs and libsnark. The SHA256 gadget 
is already implemented; you'll probably need to implement Dec yourself, 
depending on which algorithm it is. 

I'm surprised that you say Dec is not supported, wasn't it used in the ZKCP protocol in https://github.com/zcash-hackworks/pay-to-sudoku in Maxwell's transactions in 2016?
BTW, I just need it to be a strong symmetric encryption, AES will do great for that intention.

Thanks!
Oded

[Kobi Gurkan]

Hi Oded,

In general - a zkSNARK circuit has a fixed size, so, if done directly, you can define a maximum size of the decrypted data and will be able to handle any amount below that. The sha256_compression_gadget needs to be executed for each 512-block in your data, so that also adds to your cost around, roughly, 27k constraints per execution (data_size/512 executions) and also some constraints for the combination of different blocks. So, naively, handling arbitrary amounts of data is not trivial for a zkSNARK circuit.

Regarding their quote - I don't have access to the paper, but I'm guessing that they mean is that their specific constructions don't allow to easily express complex logic, which may be a reasonable description of some of the constructions. In libsnark, or generally, in zkSNARK-style constructions, you can express complex statements using arithmetic circuits which allow good flexibility.

Kobi

--
You received this message because you are subscribed to the Google Groups "libsnark" group.
To unsubscribe from this group and stop receiving emails from it, send an email to libsnark+unsubscribe@googlegroups.com.
To post to this group, send email to libs...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/libsnark/d2e31f74-8af4-4c55-8baf-dfa3f274de11%40googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

[Moran Shwartz]

Hi,

I am implementing the ZKP as described by Oded.

I am trying to understand how to do it using the Speck128 cipher and SHA256 gadgets in jsnark?

What I don't understand is if and how a circuit generator follows the zk-SNARK algorithm (KeyGen, Prove, Verify)? 

Or is it just a JAVA library for building circuits/constraints and the whole prove-verify is done in libsnark when calling runLibsnark?

What am I missing?

Thanks and regards,

Moran

בתאריך יום שלישי, 9 בינואר 2018 בשעה 18:36:56 UTC+2, מאת kobi:

To unsubscribe from this group and stop receiving emails from it, send an email to libsnark+u...@googlegroups.com.

To post to this group, send email to libs...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/libsnark/d2e31f74-8af4-4c55-8baf-dfa3f274de11%40googlegroups.com.

For more options, visit https://groups.google.com/d/optout.