21–30 of 86 posts
Does anyone know if all provable things are zero-knowledge provable? As an example: given a chess position, would you be able to construct a zero-knowledge proof that you can force checkmate in N moves or less without revealing anything about the particular moves involved? If so, what would such a proof look like?
"Prove it!" - Me
"aec070645fe53ee3b3763059376134f058cc337247c978add178b6ccdfb0019f" - God
I'm not an expert, but coming from a logic background, I always think that ZK proofs are fudging the idea of "completeness" (and "soundness," for that matter). For example, in [1] (Definition 1.1): > We note that the constants 2/3 and 1/3 are arbitrarily chosen for simplicity. We can always amplify the completeness probability to 1 − negl(λ) and the soundness probability to negl(λ) with repetition. But that's not com…
Earlier quoted context omitted.
The main type of zero-knowledge proofs are a subset (potentially proper subset) of interactive proofs. All problems that have an interactive proof form a complexity class called IP, and IP is currently believed to be a subset of PSPACE. So no, not all provable statements are zero-knowledge provable if by zero-knowledge proof you mean an interactive proof where no information is transferred. Of course it's possible th…
> IP is currently believed to be a subset of PSPACE. IP is _known_ to be _equal_ to PSPACE
Thanks for your correction.
In the Waldo example, if Bob has watermarked the back of the puzzle and Alice shows him the cutout Waldo, what prevents Bob from comparing the portion of the watermark on the back of the cutout Waldo (provided by Alice) with the original watermark (say Bob chose the watermark to be a grid of cells where each cell is trivially identifiable and small enough to be contained on the back of the cutout), thus deriving Wald…
In the Waldo example, if Bob has watermarked the back of the puzzle and Alice shows him the cutout Waldo, what prevents Bob from comparing the portion of the watermark on the back of the cutout Waldo (provided by Alice) with the original watermark (say Bob chose the watermark to be a grid of cells where each cell is trivially identifiable and small enough to be contained on the back of the cutout), thus deriving Wald…
Alice should properly reject that proposal, and only accept pages with totally uniform watermarks.
In the sudoku exapmle how can Bob be sure that the three face down cards in a cell are three identcal card? Without this knowledge, it is easy to pass the final validations without a correct solution.
> Starting with each row, Bob randomly chooses one card in each cell, from the top, the middle, or the bottom
The random assignment of solutions from each pile to each of the three problems means that the only way to consistently pass the test is to have the three solutions in each pile be identical.
In the sudoku exapmle how can Bob be sure that the three face down cards in a cell are three identcal card? Without this knowledge, it is easy to pass the final validations without a correct solution.