0
$\begingroup$

Assume that Prover have $n$ pedersen commitments ($V_{a_1},V_{a_2},\cdots,V_{a_n}$ where $V_{a_i}=G \cdot a_i + H \cdot r_{a_i}$) of $n$ elements $a_1,a_2,\cdots,a_n$. The Prover have another element $\theta$.

The verifier is provided with these $n$ pedersen commitments ($V_{a_1},V_{a_2},\cdots,V_{a_n}$) and $\theta$.

How can the Prover prove that the sum of $\textbf{only one}$ subset of these elements $a_1,a_2,\cdots,a_n$ can equal to $\theta$ and don't reveal these elements to verifier? (the size of this set is a constant witch smaller than $n$)

$\endgroup$
5
  • $\begingroup$ Ignoring the cryptography part, this sounds like the knapsack problem but in reverse. Proving a specific subset satisfies the sum is straightforward, proving no other subsets do will depend on how you would prove this in the non-zero-knowledge case. This depends on how you choose $a_n$ values to guarantee this property. If the values are powers of 2, it's obvious that your condition holds (only one sum possible) and there are approaches to doing the proof. Arbitrary sets will be harder. $\endgroup$ Jul 30, 2023 at 22:51
  • $\begingroup$ If you're trying to do this for arbitrary sets, you might need to ask on math.stackexchange.com what the non-zero knowledge proof would look like. $\endgroup$ Jul 30, 2023 at 22:52
  • $\begingroup$ @Richard Thiessen:Thankyou!How can I proof only one sum possible if the values are powers of 2? $\endgroup$
    – user105684
    Jul 31, 2023 at 2:20
  • $\begingroup$ If you don't care about revealing what values are in the original list, You can something like mental poker to show the list is a set of non-repeated 2^i powers but shuffled. Then just do a sigma-or proof to accumulate some number of the shuffled commitments and that's that. $\endgroup$ Aug 1, 2023 at 19:13
  • $\begingroup$ For an arbitrary list, if the list is small and proof size can be O(2^n), you can do 2^n inequality proofs with a single backdoor to allow falsifying one of them and something ring signature like to ensure one of them is actually false. $\endgroup$ Aug 1, 2023 at 19:19

1 Answer 1

0
$\begingroup$

Let $a_i=2^{u_i}$ $i=1,\ldots,n$ with $u_i$ nonnegative integers. If the values $u_i$ are distinct, and $$ \theta=\sum_{i \in J} 2^{u_i} $$ then the subset $J\in \{1,\ldots,n\}$ is uniquely determined by $\theta$ by the uniqueness of writing $\theta$ in base $2.$

If they are not unique, then the decomposition is not necessarily unique since e.g., the repeated values $u_i,u_i$ could be replaced by $u_j=u_i+1.$

So if $u_i$ appears twice in the list then the list should not contain $u_i+1.$ This is because $2^3+2^3=2^4,$ for example. Define the condition $$ \textrm{Do}~u_i,u_i,u_{i}+1~ \textrm{appear in the list?}\quad (*) $$ If (*) does not hold the expression is unique. If it does hold then a new list with $n-1$ members should be formed with $u_i+1$ replacing the pair $u_i,u_i$ in the original list and the condition checked again recursively. Obviously if $u_i$ appeared $f_i\geq 2$ times in the original list it would appear $f_i-2$ times in the new list.

Then the condition $(*)$ needs to be applied to the new list, and this needs to be repeated again and again if $(*)$ holds until it no longer holds finally confirming uniqueness.

$\endgroup$
1
  • $\begingroup$ Thanks for your reply!I still have a problem because prover cannot reveal all values. Given pedersen commitments of all values, how can the prover prove they are powers of 2? $\endgroup$
    – user105684
    Jul 31, 2023 at 6:29

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.