3
$\begingroup$

Alice wants to share a secret $S$ with Bob so she encrypts it with Bob's public key.

Bob is not online at the moment so Victor will keep it safe for him in the meantime.

Victor the verifier would like to verify the ciphertext is indeed the secret $S$ without actually knowing the secret $S$ himself. Victor can reliably know the hash of the secret $S$ (details of how he can rely on the hash are not relevant here). Victor could also have any other kind of commitment, it need not be a hash, provided he can never deduce the secret in plain text.

Alice does this

encryptedSecret = encrypt(secret, bobsPublicKey)

Victor does this

verify(encryptedSecret, hashOfSecret) => true
verify("anything else", hashOfSecret) => false

Does such a verify function exist?

$\endgroup$
13
  • $\begingroup$ Does it have to be a hash, or could it be a different kind of commitment? $\endgroup$
    – knaccc
    Dec 16, 2021 at 14:25
  • $\begingroup$ it could be a different commitment, provided Victor can never get to the secret $\endgroup$ Dec 16, 2021 at 14:49
  • 1
    $\begingroup$ Can your question therefore be simplified as: If Victor is aware of a commitment to a secret, how can Alice non-interactively provide that secret to Bob via Victor, including proof to Victor that the secret has been provided without Victor being able to learn the secret? Please also specify who needs to be the one that provides the commitment, as this makes a difference to the answer. $\endgroup$
    – knaccc
    Dec 16, 2021 at 16:09
  • $\begingroup$ Alice needs to provide the commitment as Bob is offline $\endgroup$ Dec 16, 2021 at 16:19
  • $\begingroup$ But then how does Victor know that the commitment (whether a hash or otherwise) is a commitment to the correct secret? Alice could provide a commitment to a different secret, and provide proof that the different secret has been given to Bob. Victor would have no idea whether the correct secret has been provided. $\endgroup$
    – knaccc
    Dec 16, 2021 at 16:20

3 Answers 3

1
$\begingroup$

At a high level, we know that a zksnark can be created so that it proves that a publicly known output $z$ is the result of applying a publicly known function $\text{f}$ to a sef of private (i.e., secret) inputs $x_1, x_2, ...$, namely $z= \text{f}(x_1,x_2,...)$.

Under the hood, what the zksnark is actually doing is prove a set of constraints (each constraint is a simple arithmetic statement that is true or false), so that the full set of constraints is true if and only if the public output is correctly calculated from the private input.

So the machinery of the zksnark (e.g., a zksnark circuit compiler such as Circom) makes it simple for us to add additional constraints that implement the desired logic of the full problem to be solved. Here, we want to also prove that the secret $S$ hashes to a publicly known value for the hash of the secret, $H = \text{Hash}(S)$. For example, maybe $S$ is the private key for a blockchain wallet, $H$ is the publicly known wallet address owned by that private key, and $\text{Hash}$ is the method to compute the wallet address from the private key.

So the zksnark should have a system of constraints that implement the following: $$H - \text{Hash}(S) == 0 \\ \text{encryptedSecret} - \text{f}(S, \text{salt}) == 0 $$

Here, the function $f$ is the encryption function that encrypts the secret using Bob's public key, and $\text{salt}$ is the salt/nullifier that could be optionally included to prevent replay attacks, double spends, etc.

In a possible implementation, $\text{f}$ and $\text{Hash}$ are published functions, $H$ is a public input to the zksnark and is known to be the correct hash of the secret $S$, $S$ and $\text{salt}$ are private inputs to the zksnark, and $\text{encryptedSecret}$ is the public output of the zksnark. The zksnark is configured to prove that the constraints above are satisfied, which means that Alice knows a secret $S$ and a $\text{salt}$ which satisfy the constraints and produce the encrypted output $\text{encryptedSecret}$.

Victor the verifier can then run the standard verifier algorithm for the zksnark, to verify that the full logic has been satisfied.

(Note: the original question had a typo in "Alice wants to share a secret 𝑆 with Bob so she encrypts it with Bob's private key", as it should say "encrypts it with Bob's public key".)

$\endgroup$
2
  • $\begingroup$ I'm not sure this works because the encryption function is not deterministic. There will be a salt for every encryption so the encryptedSecret will be different every time f is run... Thanks for the correction $\endgroup$ Jul 5 at 10:29
  • $\begingroup$ Thanks, I edited the answer to incorporate an optional salt in the encryption. It's ok that the encryption output changes depending on the salt. The zksnark just takes the salt as an additional private input. $\endgroup$ Jul 7 at 7:13
0
$\begingroup$

Private verification of a Sudoku solution, Bowe-Maxwell talk and a bitcoin transaction at Financial Crypto 2016 workshop.

The problem solved with verification was:

  1. buyer is reluctant to sent his coins first, at risk of receiving random bits;
  2. seller is reluctant to send his solution to the puzzle first, at risk of receiving no reward.

A non-interactive proof was introduced and implemented to verify that:

  1. the plaintext is a valid Sudoku solution to the puzzle at hand;
  2. the ciphertext was produced with a key;
  3. the key is a pre-image to the hash value, that was sent to the buyer with the ciphertext.

This hash could be used to create HTLC transaction so that the seller would claim his coins only by publishing the key on the blockchain. Well actually a script was used, but lets stick to HTLC as a simplification.

The short practical answer is: one would verify a hash preimage with a zkSNARK proof. Another (general) answer is, an interactive proof system exists for any NP language.

A shameless ad: an alternative Sudoku solution verification circuit was designed, starting from polynomial set representation and "playing cards" solution of Naor, presented at IEEE ATIT 2019.

https://github.com/vadym-f/Sudoku_solvability_proof/tree/master/IEEE_ATIT_2019

$\endgroup$
2
  • $\begingroup$ Hey thank you! Sounds promising but not sure how relevant sudoku is to my problem. Could you spell it out a little more about how zkSNARK can be applied to my problem ie in terms of Alice and Bob thanks $\endgroup$ Dec 19, 2021 at 15:26
  • $\begingroup$ HTLC transaction and the snark proof of a proper secret hashed seems relevant. $\endgroup$ Dec 19, 2021 at 18:45
0
$\begingroup$

There is a ZK-STARK that proves you know the preimage to a value. "The Rescue-Hash statement proven by the prover given in this code is:

"I know a sequence of n + 1 inputs {w_i} such that H(...H(H(w_0, w_1), w_2) ..., w_n) = p"

where:

H is the Rescue hash function.
Each w_i is a 4-tuple of field elements. These are private inputs, known only to the prover.
p is the public output of the hash (which also consists of 4 field elements).

" https://github.com/starkware-libs/ethSTARK/tree/ziggy

$\endgroup$
3
  • $\begingroup$ this sounds very promising but is a little over my head, could you explain to me like I'm 5? I don't get what the "inputs" are and I don't get what P is. In terms of Alice, Bob etc how does this work? $\endgroup$ Dec 19, 2021 at 15:24
  • $\begingroup$ While a little late, the key to a result of this form is that the particular hash being used (Rescue) is "advanced crypto friendly", meaning has "low multiplicative complexity" by some metric, and therefore is suitable for usage with advanced crypto primitives (such as MPC, FHE, or ZKProofs --- all have slightly different cost metrics, but roughly speaking have "cheap addition" and "expensive multiplication"). If the hash itself is expressible as a relatively low (multiplicative) depth circuit, you can hope getting a ZK proof of a hash preimage "directly", e.g. treating it as... $\endgroup$
    – Mark
    Jan 18 at 10:02
  • $\begingroup$ a generic statement that you want to prove, and using off-the-shelf techniques for this. Note that this generic technique will perform much worse on other hash functions that are not "advanced crypto friendly", say SHA variants (or really "most" hash functions not designed for this particular goal). $\endgroup$
    – Mark
    Jan 18 at 10:03

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.