0
$\begingroup$

I understand the Zero Proof Knowledge Protocol concept but find it tricky to implement sometimes for real world cases.

What I would need is, given a file with some key/value (numbers mainly) pairs, the verifier to verify that some values are within a certain range without knowing the information in the file.

Would that be possible with Zero the Proof Knowledge Protocol?

Thanks

$\endgroup$
  • $\begingroup$ Kinda sounds like Yao's millionaire's problem to me. Also see this related question. $\endgroup$ – SEJPM Nov 3 '16 at 11:11
  • $\begingroup$ Here is a list of publications regarding zero knowledge and what can be done with it. What you're looking for is called "range proof" (or similar), is loosely related to Yao's millionaire's problem and private set membership. An example for this is Efficient Protocols for Set Membership and Range Proofs (Camenisch et al. , 2008). However, this adresses conditions on values themselves. How this related to files and what security you want, has to be analyzed separately. $\endgroup$ – tylo Nov 3 '16 at 12:53
2
$\begingroup$

Your question actually demonstrates a quite common misconception when it comes to zero knowledge. Unfortunately, you will need some basic complexity background to understand what I'm going to answer. Note: I am not going to talk here about practical and efficiency sides of zero knowledge, but rather the theoretical question of what can be proven.

The famous GMW theorem for zero knowledge is often quoted to say that "anything" can be proven in zero knowledge. However, this is a misconception: rather, it says that any language in $\cal NP$ can be proven in zero knowledge. (I am not going to relate to languages in $IP\setminus NP$ since they do not have efficient provers.) Now, this means that in order to apply zero knowledge, you have to make sure that the statement is in $\cal NP$.

Let's say that a prover $P$ holds a database, and wants to prove to the verifier that certain values are in a range. First, you need to define the $\cal NP$ statement. What would it be here? One option is to say "there exists a database $D$ such that it contains the values in the range...". Well, that's actually a trivial language since for a fixed definition of the values the answer is always yes (and irrespective of any input statement $x$). Basically, the problem here is that there is no statement of reference related to your database, and so this is meaningless.

Therefore, the way to solve this is to have the verifier hold a commitment to the file. This can come in many forms, but consider a public-key encryption scheme with key pairs $(pk,sk)$ and denote the database by $D$. Then, the statement is $c=Enc_{pk}(D)$ and the $\cal NP$-witness is the secret key $sk$. The language is all of the pairs $(pk,c)$ where $c$ is an encryption of $D$ under $pk$ (with the specified public key encryption scheme) and $D$ contains values in the range as defined. Note that $pk$ must be included in the statement since otherwise $c$ doesn't uniquely define $D$.

$\endgroup$
1
$\begingroup$

To complement prof. Lindell answer, assume by now that you are in the setting he suggested: the verifier knows encryptions of the content of the database, and the prover holds the database and the random coins used to encrypt (or, alternatively, the secret key). In this setting, proving that some value (committed, or encrypted) belongs to a public interval is called a range proof. There are many solutions to this problem. It essentially consists of two class of protocols:

-If the interval considered is very large (say, $[0,2^{1000}]$), then one method is to use a proof of constant size, based on the fact that positive numbers are exactly those that can be written as a sum of four squares (see e.g. this article). As this requires to use some groups of hidden order, it involves quite large constants.

-For small intervals, the simplest solution remains to encrypt each bit of the plaintext, and prove in parallel that each ciphertext encrypts a bit (a simple OR proof). The verifier is guaranteed that the content remains lower than $2^l$, where $l$ is the number of ciphertexts to encrypt all the bits of a value.

Note that there are also more involved solutions, e.g. this article, which constructs a proof of size $O((\log n)^{1/3})$ with rather small constants, for intervals of size $n$.

$\endgroup$
  • $\begingroup$ One would OR-combine range proofs (like Lipmaa' 4-squares verifiable with a commitment in a group of a hidden order) for all entries in the database. $\endgroup$ – Vadym Fedyukovych Nov 4 '16 at 9:04
  • 1
    $\begingroup$ Indeed, I interpreted the word "some" in the statement "verify that some values are within a certain range" as "some well defined element in the database" (e.g. "the $i$th entry"). If one wants to prove that "there exists some element in the database which is in the correct range", then OR proofs or variants theoreof are required. $\endgroup$ – Geoffroy Couteau Nov 8 '16 at 14:23

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.