16
$\begingroup$

If I have committed to a number x by revealing g^x mod p, can I prove that 0 < x mod (p-1) < (p-1)/2, i.e. that x is positive, without leaking any more information about x?

My bounty is ending in 4 days and I am unsatisfied with the current answers so I would like to provide more context and also expand the question for the limited time remaining. Consider the following situation:

Paul and Quentin are wealthy and competitive with each other and they frequently settle their account with great variance: one week Paul is ahead by a million dollars, the next week Quentin is ahead by a billion, the next week Paul is ahead by only a thousand. Paul and Quentin have a wealthy rival Raul, whom they shun, but all 3 persons patronize the same accountant Verne. Verne is honest and discreet and frugal and he will never make a payment to a client on credit, but he will pay an owed amount to a client on demand. Raul can profit from information about Paul's account, indirectly costing Paul, and everyone knows this. How can Verne manage his accounts without having to buy insurance against Paul's legal accusation of a conflict of interest?

$\endgroup$
16
  • 1
    $\begingroup$ I am just talking about mod (p-1) in a signed sense... e.g. if p=7 and g=3, then the possible values for x mod 6 are (-3,-2,-1,0,1,2), corresponding to g^x values (6,4,5,1,3,2). In this case I want to create a zero-knowledge proof that x is either 1 or 2. $\endgroup$ Aug 14, 2010 at 11:51
  • 5
    $\begingroup$ If one-way functions exist, every problem in NP has a computational zero-knowledge interactive proof system (Goldreich, Micali and Wigderson, JACM 1991). Therefore, the answer is yes assuming one-way functions. Are you looking for an unconditional result? $\endgroup$ Aug 14, 2010 at 12:06
  • 1
    $\begingroup$ Tsuyoshi Ito, thank you for the reference, if you write this as an answer I may accept it. However it seems like to use this fact directly I would first have to transform the discrete-log-based decision problem into Graph 3-Colorability and I'm not sure exactly how to do this nor how practical it would be (e.g. would such a transformation multiply the problem size by a large constant?) I would prefer an answer that describes a simple protocol. $\endgroup$ Aug 14, 2010 at 23:35
  • 1
    $\begingroup$ @jdb19937: That sounds like a much more interesting question, but I do not know the answer. (But I am no expert in cryptography, so I may be missing something that is simple to those who work on cryptography.) A straightforward way to reduce your problem to 3-colorability is to compose several reductions including Cook’s reduction, and the reduction constructed this way incurs a polynomial blowup (instead of linear) in the instance size. $\endgroup$ Aug 15, 2010 at 11:31
  • 2
    $\begingroup$ This does not seem to answer your question completely, but I found an interesting paper: Oded Goldreich and Eyal Kushilevitz: A perfect zero-knowledge proof system for a problem equivalent to the discrete logarithm, Journal of Cryptology, 6(2):97–116, June 1993 (springerlink.com/content/u567k88h3g5rw31r). In this paper, the authors construct a perfect zero-knowledge interactive proof system for a problem of deciding whether x mod (p−1) is less than (p−1)/2 under the promise that x mod (p−1)/2 is not too close to (p−1)/2. Their result is unconditional. $\endgroup$ Aug 22, 2010 at 22:38

4 Answers 4

11
$\begingroup$

This answer combines my three comments to the question and expands them a little.

Following [BM84], let’s call the integers $g^x \bmod p$ for $0 < (x \bmod (p−1)) < (p−1)/2$ principal square roots. We call the problem of deciding, given $p$, $g$ and $y$, whether an integer $y$ is a principal square root or not the principal square root problem.

For the original question, the answer is positive assuming one-way functions. This is because if one-way functions exist, every problem in NP has a computational zero-knowledge interactive proof system [GMW91]. Note that the principal square root problem is clearly in NP.

As the questioner pointed out, this construction has a drawback that it requires a reduction from the principal square root problem to the $3$-colorability problem, which involves Cook’s reduction and blows up the instance size (polynomially). In addition, this construction requires the assumption that one-way functions exist.

I do not know a direct way to construct a zero-knowledge interative proof system for the principal square root problem. However, [GK93] shows an interesting result related to the question: the principal square root problem under a promise that $(x \bmod (p−1)/2)$ is not too close to $(p−1)/2$ has a perfect zero-knowledge interactive proof system. The construction is direct and does not use any cryptographic assumptions.

References

[BM84] Manuel Blum and Silvio Micali. How to generate cryptographically strong sequences of pseudorandom bits. SIAM Journal on Computing, 13(4):850–864, Nov. 1984. DOI 10.1137/0213053. Zbl 0547.68046

[GK93] Oded Goldreich and Eyal Kushilevitz. A perfect zero-knowledge proof system for a problem equivalent to the discrete logarithm. Journal of Cryptology, 6(2):97–116, June 1993. DOI 10.1007/BF02620137. Zbl 0783.68039

[GMW91] Oded Goldreich, Silvio Micali and Avi Wigderson. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. Journal of the ACM, 38(3):690–728, July 1991. DOI 10.1145/116825.116852. Zbl 0799.68101

$\endgroup$
1
$\begingroup$

It seems the answer to the question is "no", since the positivity of $x$ is a hard predicate for the exponentiation function (on a primitive element) modulo a prime $p$. In other word, being able to compute this positivity is as hard as computing $x$. This is proven by Blum and Micali in "How to generate cryptographically strong sequences of pseudo-random bits", SIAM Journal on Computing, Volume 13, Issue 4 (November 1984). See also Fact 3.84 in the Handbook of Applied Cryptography.

$\endgroup$
3
  • 2
    $\begingroup$ Something can be hard to compute and still have a short witness. The question is whether Dan, who knows what $x$ is, can convince me that $x$ is positive without revealing it; not whether I can determine whether $x$ is positive without computing it. $\endgroup$ Aug 19, 2010 at 16:44
  • $\begingroup$ I think the same is true for any other bit of x as long as p and g are chosen carefully. The lowest bit (parity) has a short witness (g^(x/2)), is the same true for the highest bit (sign)? $\endgroup$ Aug 19, 2010 at 21:37
  • $\begingroup$ Actually I am wrong about that, according to Gerard's reference QR is efficiently solvable for any prime modulus. However, Fact 3.84 confirms that finding the sign of x is just as hard as finding the entirety of x. I was already assuming this so it doesn't really answer the question. $\endgroup$ Aug 20, 2010 at 7:29
0
$\begingroup$

If I understand your expanded question correctly, it is now about Verne the accountant committing to the participants' account balances by publishing them in encrypted form. So Verne can encode all positive balances n as the even number 2n, and all negative balances -n as the odd number 2n+1. And you already know how to commit to a proof that a number is even. Does this fit the bill?

$\endgroup$
5
  • 1
    $\begingroup$ Sorry, that is not the interpretation I had in mind. Verne wants to be able to do his job without even knowing Paul's account balance, only that it is positive. Even though Verne is honest and Paul trusts him, there will never arise any situation where Paul accuses Verne of giving information to Raul. [continued] $\endgroup$ Aug 22, 2010 at 22:59
  • 1
    $\begingroup$ The idea is that Verne knows g^x_p, g^x_q, and g^x_r and is convinced at all times that they all have positive logarithms. If Paul asks Verne to make a payment y to Quentin, Verne only needs to know g^y, with which he can compute g^(x_p-y) g^(x_q+y). But Verne won't do this unless Paul can prove that g^(x_p-y) has a positive logarithm, because Paul is the only one who knows x_p or y. $\endgroup$ Aug 22, 2010 at 23:01
  • 1
    $\begingroup$ ... Quentin presumably also knows y in this case, but not x_p. $\endgroup$ Aug 22, 2010 at 23:02
  • $\begingroup$ So P, Q, and R use the same g? That looks wrong. $\endgroup$
    – TonyK
    Aug 22, 2010 at 23:24
  • $\begingroup$ Yes, everybody knows the same g and p. $\endgroup$ Aug 22, 2010 at 23:28
0
$\begingroup$

Short answer is, integer commitment scheme (a group of a hidden order) and four squares Lagrange theorem.

With a group of a known prime order, it is not quite convenient to handle integers, unless breaking them into bits. A group of a composite order (example: RSA) is useful here, provided group order is unknown to (that is, hidden from) Prover.

For any non-negative integer committed, one would always find four integers (a witness) that fits sum-of-four-squares theorem. Follow a Schnorr-like protocol, extended to verification equation of second degree (square) in challenge.

$\endgroup$
5
  • $\begingroup$ How does this capture the non-negativity constraint? E.g. $1^2+1^2+1^2+1^2=-1 \bmod 5$? $\endgroup$ Dec 9, 2014 at 15:04
  • $\begingroup$ Integer commitment scheme means no modular reduction over group order, which is not known to Prover. "Positivity" relation is tested over integers, not residue classes modulo some order. $\endgroup$ Dec 10, 2014 at 13:09
  • $\begingroup$ Could you outline the steps in more detail? I'm afraid I'm still confused. $\endgroup$ Dec 12, 2014 at 1:59
  • $\begingroup$ Original query was for "positivity", a natural relation over integers. However, it was instantiated with a commitment scheme for residue classes (remainders), with a half of modulus. To achieve an efficient protocol, one better pick proper commitment scheme first. Major point with such a scheme for integers is avoiding reduction modulo group order, doable with groups of unknown order (think RSA) such that factorization is not available to Prover. For example: (2,3,3,5) is a witness for 47, but no witness exists for -47. Theorem is, one can compute such a witness for any non-negative integer. $\endgroup$ Dec 12, 2014 at 8:06
  • $\begingroup$ It's a late answer, no bounty expected. Major point is, one need to soften assumption on commitment scheme to achieve some progress. That is, Lagrange thm needs integers (not residues modulo a prime divisor of p-1), and integers assume a group of a hidden order. $\endgroup$ Jan 7, 2015 at 19:26

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.