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
374 views

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
190 views

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
105 views

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 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1....
amm's user avatar
  • 41
3 votes
0 answers
28 views

(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
99 views

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
119 views

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
202 views

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
35 views

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
146 views

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