Mixing
Are there deterministic and/or non-interactive zero-knowledge proofs?
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
The Wikipedia page on zero-knowledge proof says
Zero-knowledge proofs are not proofs in the mathematical sense of the term because there is some small probability, the soundness error, that a cheating prover will be able to convince the verifier of a false statement. In other words, zero-knowledge proofs are probabilistic "proofs" rather than deterministic proofs. However, there are techniques to decrease the soundness error to negligibly small values.
Is it possible to prove that no zero-knowledge proof can be deterministic? What about non-interactive?
complexity-theory interactive-proof-systems
asked 4 hours ago
tparker
362112
add a comment |Â
up vote
2
down vote
favorite
The Wikipedia page on zero-knowledge proof says
Zero-knowledge proofs are not proofs in the mathematical sense of the term because there is some small probability, the soundness error, that a cheating prover will be able to convince the verifier of a false statement. In other words, zero-knowledge proofs are probabilistic "proofs" rather than deterministic proofs. However, there are techniques to decrease the soundness error to negligibly small values.
Is it possible to prove that no zero-knowledge proof can be deterministic? What about non-interactive?
complexity-theory interactive-proof-systems
asked 4 hours ago
tparker
362112
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
The Wikipedia page on zero-knowledge proof says
Zero-knowledge proofs are not proofs in the mathematical sense of the term because there is some small probability, the soundness error, that a cheating prover will be able to convince the verifier of a false statement. In other words, zero-knowledge proofs are probabilistic "proofs" rather than deterministic proofs. However, there are techniques to decrease the soundness error to negligibly small values.
Is it possible to prove that no zero-knowledge proof can be deterministic? What about non-interactive?
complexity-theory interactive-proof-systems
asked 4 hours ago
tparker
362112
The Wikipedia page on zero-knowledge proof says
Zero-knowledge proofs are not proofs in the mathematical sense of the term because there is some small probability, the soundness error, that a cheating prover will be able to convince the verifier of a false statement. In other words, zero-knowledge proofs are probabilistic "proofs" rather than deterministic proofs. However, there are techniques to decrease the soundness error to negligibly small values.
Is it possible to prove that no zero-knowledge proof can be deterministic? What about non-interactive?
complexity-theory interactive-proof-systems
complexity-theory interactive-proof-systems
asked 4 hours ago
tparker
362112
asked 4 hours ago
tparker
362112
asked 4 hours ago
tparker
362112
asked 4 hours ago
tparker
362112
asked 4 hours ago
tparker
362112
362112
add a comment |Â
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
1
down vote
At the very core of Zero Knowledge proof systems, lies the fact that proofs are published by asking the party to prove the correctness of its knowledge, via any one of many methods to verify a solution.
Since knowing the question in advance allows a party to forge another proof, the only way to get a reliable proof is via asking a random question out of a pre-determined set of questions, multiple times enough so that the chances of a cheat to pass through are practically impossible.
The probabilistic behaviour becomes inevitable from the fact that any question asked at random can be predicted with a non-zero probability, since it comes from a pre-determined set of questions. If the question to be asked was not from a set of pre-determined questions, current Zero Knowledge proofs would be deterministic.
answered 1 hour ago
RandomPerfectHashFunction
693
New contributor
RandomPerfectHashFunction is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |Â
up vote
1
down vote
Goldreich and Oren, in their paper Definitions and properties of zero-knowledge proof systems, show that if the verifier is deterministic then interactive proofs trivialize to RP, whereas if the prover is deterministic then interactive proofs trivialize to BPP. See Section 4 of their paper.
Blum, de Santis, Micali and Persiano constructed noninteractive zero-knowledge proofs in their classic work Noninteractive zero-knowledge. The two parties do have to agree on a random key beforehand. Noninteractive zero-knowledge proofs have found many applications, for example to cryptocurrencies. See Wikipedia for many references.
answered 13 mins ago
Yuval Filmus
182k12171331
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
At the very core of Zero Knowledge proof systems, lies the fact that proofs are published by asking the party to prove the correctness of its knowledge, via any one of many methods to verify a solution.
Since knowing the question in advance allows a party to forge another proof, the only way to get a reliable proof is via asking a random question out of a pre-determined set of questions, multiple times enough so that the chances of a cheat to pass through are practically impossible.
The probabilistic behaviour becomes inevitable from the fact that any question asked at random can be predicted with a non-zero probability, since it comes from a pre-determined set of questions. If the question to be asked was not from a set of pre-determined questions, current Zero Knowledge proofs would be deterministic.
answered 1 hour ago
RandomPerfectHashFunction
693
New contributor
RandomPerfectHashFunction is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |Â
up vote
1
down vote
At the very core of Zero Knowledge proof systems, lies the fact that proofs are published by asking the party to prove the correctness of its knowledge, via any one of many methods to verify a solution.
Since knowing the question in advance allows a party to forge another proof, the only way to get a reliable proof is via asking a random question out of a pre-determined set of questions, multiple times enough so that the chances of a cheat to pass through are practically impossible.
The probabilistic behaviour becomes inevitable from the fact that any question asked at random can be predicted with a non-zero probability, since it comes from a pre-determined set of questions. If the question to be asked was not from a set of pre-determined questions, current Zero Knowledge proofs would be deterministic.
answered 1 hour ago
RandomPerfectHashFunction
693
New contributor
RandomPerfectHashFunction is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |Â
up vote
1
down vote
up vote
1
down vote
At the very core of Zero Knowledge proof systems, lies the fact that proofs are published by asking the party to prove the correctness of its knowledge, via any one of many methods to verify a solution.
Since knowing the question in advance allows a party to forge another proof, the only way to get a reliable proof is via asking a random question out of a pre-determined set of questions, multiple times enough so that the chances of a cheat to pass through are practically impossible.
The probabilistic behaviour becomes inevitable from the fact that any question asked at random can be predicted with a non-zero probability, since it comes from a pre-determined set of questions. If the question to be asked was not from a set of pre-determined questions, current Zero Knowledge proofs would be deterministic.
answered 1 hour ago
RandomPerfectHashFunction
693
New contributor
RandomPerfectHashFunction is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
At the very core of Zero Knowledge proof systems, lies the fact that proofs are published by asking the party to prove the correctness of its knowledge, via any one of many methods to verify a solution.
Since knowing the question in advance allows a party to forge another proof, the only way to get a reliable proof is via asking a random question out of a pre-determined set of questions, multiple times enough so that the chances of a cheat to pass through are practically impossible.
The probabilistic behaviour becomes inevitable from the fact that any question asked at random can be predicted with a non-zero probability, since it comes from a pre-determined set of questions. If the question to be asked was not from a set of pre-determined questions, current Zero Knowledge proofs would be deterministic.
answered 1 hour ago
RandomPerfectHashFunction
693
New contributor
RandomPerfectHashFunction is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered 1 hour ago
RandomPerfectHashFunction
693
New contributor
RandomPerfectHashFunction is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered 1 hour ago
RandomPerfectHashFunction
693
answered 1 hour ago
RandomPerfectHashFunction
693
693
New contributor
RandomPerfectHashFunction is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
RandomPerfectHashFunction is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
RandomPerfectHashFunction is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |Â
add a comment |Â
up vote
1
down vote
Goldreich and Oren, in their paper Definitions and properties of zero-knowledge proof systems, show that if the verifier is deterministic then interactive proofs trivialize to RP, whereas if the prover is deterministic then interactive proofs trivialize to BPP. See Section 4 of their paper.
Blum, de Santis, Micali and Persiano constructed noninteractive zero-knowledge proofs in their classic work Noninteractive zero-knowledge. The two parties do have to agree on a random key beforehand. Noninteractive zero-knowledge proofs have found many applications, for example to cryptocurrencies. See Wikipedia for many references.
answered 13 mins ago
Yuval Filmus
182k12171331
add a comment |Â
up vote
1
down vote
Goldreich and Oren, in their paper Definitions and properties of zero-knowledge proof systems, show that if the verifier is deterministic then interactive proofs trivialize to RP, whereas if the prover is deterministic then interactive proofs trivialize to BPP. See Section 4 of their paper.
Blum, de Santis, Micali and Persiano constructed noninteractive zero-knowledge proofs in their classic work Noninteractive zero-knowledge. The two parties do have to agree on a random key beforehand. Noninteractive zero-knowledge proofs have found many applications, for example to cryptocurrencies. See Wikipedia for many references.
answered 13 mins ago
Yuval Filmus
182k12171331
add a comment |Â
up vote
1
down vote
up vote
1
down vote
Goldreich and Oren, in their paper Definitions and properties of zero-knowledge proof systems, show that if the verifier is deterministic then interactive proofs trivialize to RP, whereas if the prover is deterministic then interactive proofs trivialize to BPP. See Section 4 of their paper.
Blum, de Santis, Micali and Persiano constructed noninteractive zero-knowledge proofs in their classic work Noninteractive zero-knowledge. The two parties do have to agree on a random key beforehand. Noninteractive zero-knowledge proofs have found many applications, for example to cryptocurrencies. See Wikipedia for many references.
answered 13 mins ago
Yuval Filmus
182k12171331
Goldreich and Oren, in their paper Definitions and properties of zero-knowledge proof systems, show that if the verifier is deterministic then interactive proofs trivialize to RP, whereas if the prover is deterministic then interactive proofs trivialize to BPP. See Section 4 of their paper.
Blum, de Santis, Micali and Persiano constructed noninteractive zero-knowledge proofs in their classic work Noninteractive zero-knowledge. The two parties do have to agree on a random key beforehand. Noninteractive zero-knowledge proofs have found many applications, for example to cryptocurrencies. See Wikipedia for many references.
answered 13 mins ago
Yuval Filmus
182k12171331
answered 13 mins ago
Yuval Filmus
182k12171331
answered 13 mins ago
Yuval Filmus
182k12171331
answered 13 mins ago
Yuval Filmus
182k12171331
182k12171331
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f97367%2fare-there-deterministic-and-or-non-interactive-zero-knowledge-proofs%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password