New answers tagged zero-knowledge-proofs
1
TL,DR: a conjuction of simple $\Sigma$-protocols can prove this compound statement in zero-knowledge. However, the proof is somewhat large.
First, let's break down your compound statement into simpler statements. Observe that essentially you want to prove in zero knowledge for $C_1=m^e$ and $C_2=g^m$ that the following relation $\mathcal{R}(x,\omega)$ ($x$ ...
0
This second challenge $c'$ and second part of the transcript is coming from extractor algorithm, a part of proof of knowledge definition. Extractor algorithm is formally given a power to rewind the prover to the state his first message was sent, so it could pick another challenge. Witness produced by extractor in expected polynomial time is the major ...
1
Is using ZK snark a requirement?
This seems to be the millionaire problem:
https://en.m.wikipedia.org/wiki/Yao%27s_Millionaires%27_problem
This is simpler than doing SNARKS, it's an interactive shared computation, doesn't have any trusted center or assume both inputs are protected by a shared secret (as in Red Sun's answer).
In a bidding scenario, they give ...
3
With zk-snarks, one would verify a proof that "is greater" relation holds for $(a, b)$ plaintext as a private input, and for commitment to $(a, b)$ as a public input. One would split both $a$ and $b$ into bits ("wires" in snarks parlance), and create a circuit with multiplication gates producing "true" or "false". ...
3
Assume there is a common secret $x$ that is used to conceal the value of $a$ and $b$, known only by the actors possessing $a$ and $b$. A verifier $c$ is a randomly picked number, and provided to the two parties possessing $a$ and $b$. Then, they calculate $ax-c$ and $bx-c$, and provide them to the verifier. The verifier then calculate the difference between $...
1
Referring to Vadym Fedyukovych's answer:
Nullifier idea of ZCash could also help.
In this case, a proof is constructed with a nullifier, which is generated and kept by Alice, its hash is provided to Bob and Charlie, as a the Bob/Charlie's side of the authorization. If Alice wants to use this authorization, Alice must provide the nullifier to Bob and ...
0
It think, it can be solved by using structure preserving encryption/signature scheme (I mean schemes which are compatible with the ZK proof system you want to use).
The general idea is that Alice will sign the message and will send the signature $\sigma$ to Bob, then Bob will commit the message $m$, and the signature $\sigma$ and will build ZK proofs that $e$...
0
Yes it's possible, but you need to find equations $E_1, E_2$ which allow you to check:
$$\texttt{Enc}(y)=c \iff E_1(y, c) $$
$$\texttt{Pred}(x) = y \iff E_2 (x,y) $$
Then you have to find a zero-knowledge proof-system which authorize you to prove equations such as $E_1, E_2$. For example, if these equations are in a bilinear group context, then Groth-Sahai ...
0
The section 5.4 "Limited-show certificates" of the book "Rethinking Public Key Infrastructures" by S. Brands could be relevant, ISBN978-0262526302, and may be downloaded from Credentica.
The idea of nullifiers introduced by ZCash may also help.
0
For now, I have gradually understood why the zk-SNARK cannot be suitable for constructing anonymous authentication scheme. That is the performance issue.
According to some references:
[1]Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture;
[2]Comparing General Purpose zk-SNARKs
The zk-SNARK takes seconds to perform a proof operation. ...
1
In most FHE schemes, the ciphertexts contain noise which grows after performing operations. Its growth for additions is usually negligible compared to multiplications. In addition, the cost of operations is different. Therefore, one wants to minimize the multiplicative depth but also the number of multiplications as they are more costly.
For example, in the ...
0
The soundness definition that you are familiar with is the normal soundness definition of proof systems. The soundness definition in this paper is a definition of soundness for "proofs of knowledge", i.e., the goal of the prover is not only to convince the verifier that the statement is true but also that it knows a witness. This can be a much ...
0
Quoting the proposal page 10, just before Theorem 8:
..and carries out a zero-knowledge proof of knowledge $\pi$
(such as the Schnorr’s interactive protocol [Sch90]) of $(m_1, . . . , m_r)$ and $t$ such that..
That means introducing protocol responses $(M_1, \cdots, M_r, T)$
for secrets $(m_1, . . . , m_r)$ and challenge $c$
like $M_i = m_i \cdot c + \xi_i$...
1
In general, AND gates are no big deal. In practice however, many zero-knowledge systems are based on rank-1-constraint systems (R1CS, often "arithmetic circuits" in folklore), and the concern that LowMC tries to address is linked to this practicality. Note that I'm talking from the perspective of ZK, although the principles probably carry over to ...
0
TL,DR: there's already a quite nice proof sketch in the original paper by Feige and Shamir. Check it out here! If you want to see an intuitive explanation then keep reading!
What does witness indistinguishability mean, intuitively?
Witness indistinguishability (WI): The proof system $(P,V)$ is WI over a relation $R$, if for any instance $x$ the verifier with ...
Top 50 recent answers are included
