Score:1

Zero-knowledge with leakage about the witness

us flag

In Zero-Knowledge (ZK) proofs/arguments of knowledge, the ZK knowledge property informally says that it is possible to simulate the output of a (malicious) verifier interacting with a prover knowing a witness $w$ without using $w$ at all:

$$\{OUT_{V^*_\lambda} \langle P(w,x) , V^*_\lambda(s_\lambda, x) \rangle\}_{\lambda,x,w} \approx_c \{Sim(x, V^*_\lambda, s_\lambda)\}_{\lambda,x,w}$$

where $\lambda$ is a security parameter, $w$ is a witness of $x$ and $s_\lambda$ a non-uniform advice.

However this seems to be too weak for my use-case, as the malicious verifier has a (partial) access to the witness $w$.

Is there a stronger notion of ZK that works for cases where parts of the witness leak to the verifier? If yes, do we have protocols that achieve this stronger notion? (ideally post-quantum secure) What is the status in the non-interactive case (NIZK)?

I just saw in this course a notion of adaptively-secure NIZK that seems quite close to my needs, but it only focuses on NIZK, seems to be even stronger as the instance $(x,w)$ can be maliciously chosen by the adversary (in my case the instance is chosen uniformly at random by the prover) and don't say if there exists protocols achieving this notion.

Geoffroy Couteau avatar
cn flag
What is known about this partial witness? Does the prover also know what part of the witness is known to the verifier? Does the verifier have any choice in what leakage they get? Also, we do have a bunch of adaptively secure NIZKs, including post-quantum candidates. Also, related, you might want to look into leakage-resilient zero-knowledge: https://www.iacr.org/archive/crypto2011/68410293/68410293.pdf. It's for very general notions of leakage, so it might be too strong for your purpose, depending on what you need exactly.
Léo Colisson avatar
us flag
As we discussed offline (added here for reference) it is a quantum state that is provided in the protocol, that contains parts of the witness in superposition.
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.