Questions tagged [zero-knowledge-proofs]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
1 answer
21 views

How does the sumcheck protocol help solving the #SAT (circuit satisfiability) problem?

I am going through Justin Thaler's book - https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf - "Proofs, Arguments, and Zero-Knowledge" He presents the Sumcheck protocol & then ...
user93353's user avatar
  • 125
1 vote
2 answers
62 views

Is this a zero knowledge proof algorithm (security)

Suppose we have a website and you log in the website with a username and a password.During registration your computer downloads a file containing a random 32 digit number.Now when you try to log in , ...
Cerise's user avatar
  • 153
-1 votes
1 answer
30 views

(Zero-knowledge?) Proof of Connection

I have a conundrum to solve but am not knowledgeable enough about cryptography to know whether it's possible to do, and if so, what method to use. I am a Provider and my task is to prove to some ...
Yellow's user avatar
  • 99
2 votes
1 answer
29 views

Interactive ZKP of possession of a signed message

Suppose Alice has a verifiable (message, signature) pair from Cedric, who would not cooperate and routinely uses an algo (ecdsa, eddsa, rsa, or insert yours here) to sign messages. Alice wants to ...
wick's user avatar
  • 123
0 votes
1 answer
59 views

What is a witness string in a zero knowledge proof?

I had earlier asked the question What is a witness string? I unable to understand the concept From the answers I got, it seems that a witness is more or less the answer. For e.g. in the padlock ...
user93353's user avatar
  • 125
1 vote
0 answers
42 views

Reference for the formal definition of sigma protocol

I'm looking for a book that contains the formal definition of sigma protocol (something like: A sigma protocol for a relation $R$ and a challenge space $C$ is... that satisfies the properties of ...
H5brick's user avatar
  • 11
26 votes
7 answers
8k views

How can you convince your colour-blind friend that two balls have the same colour?

I was reading about zero-knowledge proofs. I understand how one can convince their colour-blind friend that the two chosen balls have different colours. Now what happens if the two chosen balls have ...
Dmitry Kamenetsky's user avatar
0 votes
1 answer
62 views

What is the use or how can we implement zero-knowledge proof system in Elections?

I recently heard about the concept of zero-knowledge proof. However, I still do not get how it is possible to make it a solution to some real-world problems. One thing I heard is that zero-knowledge ...
Aidre Cabrera's user avatar
1 vote
2 answers
227 views

Why exactly is Zero Knowledge Proof used here?

"The Ali Baba cave" example of ZKP is pictured below. There is no need for a probabilistic ZKP protocol to prove to the verifier of the statement (that the prover has the key to the door). ...
Anon's user avatar
  • 11
0 votes
0 answers
47 views

Is this an example of a zero-knowledge proof?

I want to prove to a verifier that I know the passcode of a system. The system contains data/information of the verifier of which is only contained with this system. Since I know the passcode to the ...
Anon's user avatar
  • 1
1 vote
1 answer
88 views

Prove 2 cups contain the same number of marbles without revealing quantity

I have seen proofs of this particular problem in a few articles/papers (which lead to a ZKP 2 nuclear warheads are similar), but I find a problem in the proof with the marbles - surely the proof doesn'...
Shuri2060's user avatar
  • 111
1 vote
1 answer
30 views

Is it possible to have a zero knowledge proof with a P Prover?

In the literature, when reading about zero knowledge proofs, the prover (prover/verifier) is always given an unlimited computational power or just capacity to solve NP. Is it necessary for the prover ...
Rafael's user avatar
  • 21
0 votes
1 answer
126 views

Zero knowledge proof - case of graph 3-coloring (not understanding the concept)

In zero knowledge, in the context of graph 3-coloring, I do not understand how the prover is actually showing that he solved the problem. The context: both know the graph (the prover and the verifier)...
Rafael's user avatar
  • 21
5 votes
2 answers
1k views

Is there a Zero-Knowledge proof for SAT?

I know that SAT can be reduced to (3 vertex) Graph colouring, and there is a Zero-knowlegde protocol (ZKP) for graph colouring. However, I am interested in a ZKP that can be performed directly on a ...
StackMachine's user avatar
1 vote
2 answers
142 views

Zero-knowledge proof of intractibility of NP-complete problems

I am not an expert in Zero-knowledge proofs and I am interested in its applicability to general mathematical proofs. Suppose we're willing to assume that NP-complete problems are intractable and ...
Mohammad Al-Turkistany's user avatar