4
votes
State of the art for Graph Isomorphism
Goldreich and Krawczyk proved the following theorem:
Theorem 6.2: A language L has a three-round interactive proof which is black-box simulation zero-knowledge if and only if L ∈ BPP
So unless GI is ...
- 340
4
votes
Accepted
Statistics-heavy crypto papers
I am afraid your search for Annals of Stats etc. level of purely statistical theoretical papers in cryptology may not yield too many examples.
The field is very applied and the role of statistics is ...
- 21k
1
vote
Zero Knowledge Argument for Elliptic Curve Multiplication/Inverse Multiplication Correctness?
how could Alice convince him that the multiplication done to compute $B′$ was the inverse of the multiplication done to compute $A′$ without revealing $x$, or ideally any information about $x$?
If ...
- 143k
1
vote
Accepted
Amplifying the completeness and soundness of a proof scheme
I will assume that at least $\delta$ is known. $c$ can be estimated by running the proof many times on true statements and $s$ can be set as $c-\delta$. The strategy to make completeness close to $1$ ...
- 632
1
vote
Accepted
State of the art for Graph Isomorphism
The G&K impossibility you mention in your answer only concerns black-box simulation ZK. For weaker flavors of zero-knowledge, it can be circumvented. For example, it is well known that HVZK $\...
- 632
1
vote
Accepted
Unbounded distinguishers and statistical indistinguishability
Statistical indistinguishability implies computational indistinguishability, and in fact this describes a tight upper bound on any distinguishers advantage, unbounded or not. So a distinguisher may ...
- 413
Only top scored, non community-wiki answers of a minimum length are eligible