Questions tagged [zero-knowledge]

The tag has no usage guidance.

9 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
18 votes
0 answers

Does Factoring have a Statistical Zero Knowledge Proof?

The title should be pretty self-explanatory, but to be more precise, consider the decision version of factoring, which is given input $(x,k)$, where $x$ and $k$ are binary encodings of integers, to ...
Henry Yuen's user avatar
  • 3,788
11 votes
0 answers

generalizing Ben-Or et al's two-prover bit commitment scheme beyond bits

In "Multi-Prover Interactive Proofs: How to Remove Intractability Assumptions" by Ben-Or, Goldwasser, Kilian, and Wigderson, the authors introduce a bit commitment protocol as a subroutine to their ...
Noam Zeilberger's user avatar
4 votes
0 answers

Is perfect zero knowledge sequentially composable without auxiliary input?

It is known that plain and computational zero knowledge proof systems are not sequentially composable without auxiliary input (see for example
amm's user avatar
  • 41
3 votes
0 answers

(Classical) Zero Knowledge protocol with quantum poly time simulator

We have lower bounds for classical zero-knowledge protocols (eg we cannot have 3-round zero-knowledge protocols for NP, with negligible soundness and black-box simulation). However, some of these ...
vk19's user avatar
  • 31
2 votes
0 answers

Non-interactive proof showing the multiplication of an encrypted matrix with a public vector is as claimed

Consider a "fantasy sports" setting where $m$ contestants each pick $k$ players from a set of $n$ players before a game. The state can be represented by a Boolean matrix $\mathbf{A}$ of size ...
Madhav Jha's user avatar
2 votes
0 answers

concurrent non-malleable *statistical* zero knowledge

According to Huijia Lin and Rafael Pass's "Concurrent Non-Malleable Zero Knowledge with Adaptive Inputs" paper: if collision-resistant hash functions exist, then "there exists a $\omega\left(\log^...
user avatar
2 votes
0 answers

Are there efficient black-box constructions of sigma-protocols for SAT?

Is there a known black-box construction for the following implication? non-interactive string commitment that stretches additively by an amount which does not depend on the string being ...
user avatar
0 votes
0 answers

Is SZK dependent on the verifier’s model of computation?

What if instead of a probabilistic TM, the verifier in the definition of SZK was a quantum TM? How would this affect its relation to other classes? Would Statistical Difference still be a complete ...
Irna Mosa's user avatar
0 votes
0 answers

Is it possible to create an arbitrary $\textsf{NP}$-complete statement of chosen size $n$ and witness in polynomial time?

This questions came in my mind as I was reading the concept of hidden-bits of Feige, Lapidot and Shamir in "Multiple non-interactive zero knowledge proofs based on a single random string". There is ...
Burak's user avatar
  • 161