3
$\begingroup$

Short version: Is it a common practice (and a valid practice) to hardcode an element $d \in \mathcal{L}$ of a language into a simulator? (making the simulator non-uniform and non-constructive)

Long version:

I have a prover $P$ that does the following: it takes a bit string $d \in \mathcal{L}$ for some languages in $\textsf{NP}$, then it encrypts $d$ using a CPA-secure encryption to obtain an encryption $k$, and it sends a Non-Interactive Zero-Knowledge (NIZK) proof $\pi$ proving that $k$ encrypts a message $d \in \mathcal{L}$. I would like to say now that this scheme does not leak much information on $d$, in the sense that there exists a simulator $Sim$ such that for any malicious non-uniform verifier $V^*$: $$\{Sim(V_\lambda^*)\}_{\lambda,d} \stackrel{comp}{\equiv} \{\textsf{OUT}_{V^*}(P_\lambda(d)\leftrightarrow V^*_\lambda)\}_{\lambda,d}$$

(the $\{X_{\lambda,d}\}_{\lambda,d}\stackrel{comp}{\equiv}\{Y_{\lambda,d}\}_{\lambda,d}$ symbol denotes computational indistinguishability: for any non-uniform distinguisher $D$, there exists a negligible $\mu$ such that for all $\lambda \in \mathbb{N},d \in \mathcal{L}$, $|\Pr[D_\lambda(X_d)]-\Pr[D_\lambda(Y_d)]| < \mu(\lambda)$)

Without the NIZK part, the proof is simple: my simulator would just pick a random $d'$ and encrypt it into $k'$: I can't distinguish $k$ and $k'$ without breaking CPA security. Intuitively, adding a NIZK proof should not leak more information... However I'm not sure how to deal with that case: I have an idea, but it looks quite strange to me (I never saw that kind of method before), and I'm a bit dubious about it.

My main issue is that if I input a random $d'$ to the NIZK, then $d'$ may not belong to $\mathcal{L}$, so I cannot use the NIZK simulator, which expects $k$ to be an encryption of a $d \in \mathcal{L}$. So my idea is to say that if $\mathcal{L}$ is not empty, then there exists a string $d' \in \mathcal{L}$ (which may or may not be equal to $d$). Then, if I encrypt this string into $k'$, $k'$ is now a "valid" element to input to the NIZK simulator. So I could just run the NIZK simulator now with $k'$ to obtain the $Sim$ I wanted: the final proof of indistinguishability would add an intermediate distribution, in which we use $k$ with the NIZK simulator: the first two games should be impossible to distinguish due to the NIZK property, the second two games should be impossible to distinguish due to the CPA property. (I still need to write this sketch of proof formally to verify if it does not contain a stupid mistake).

However, hardcoding an element of $\mathcal{L}$ into $Sim$ looks a bit weird to me (notably because the simulator is not constructive, and non-uniform since for any size of $d$ we need a different $d'$). Is it something common/valid in Zero-Knowledge proofs, or am I missing something?

$\endgroup$
0

1 Answer 1

2
$\begingroup$

In fact I got confused for no reasons (thanks Michael): we can just define two hybrid games (we just sketch the proof here):

  1. in the first game we replace the $\textsf{Proof}(k, (d, r))$ ($r$ is the randomness used in the encryption) with $Sim(k)$: so the message sent is now $(k, Sim(k))$. It is impossible to distinguish from $(k,\textsf{Proof}(k,(d,r)))$ due to the fact that the protocol is ZK, and $k$ is in the appropriate language (i.e. it is an encryption of a $d \in \mathcal{L}$).
  2. Then in a second hybrid we replace $k$ in both the message and the Simulator by a $k'$ coming from a random encrypted $d$ (which may not belong to $\mathcal{L}$): the new message is $(k', Sim(k'))$. It is impossible to distinguish it from $(k, Sim(k))$ or we can use this simulator to break IND-CPA: the idea is simply to ask to the adversary to run $Sim$ on the input encryption $e$, and then send $(e,Sim(e))$ to the distinguisher. Geoffroy also made the remark that we need here IND-CPA against non-uniform adversary (which is the standard definition anyway). The reason is that $\stackrel{comp}{\equiv}$ is formulated for non-uniform distinguishers: therefore if a non-uniform distinguisher can break IND-CPA, then this step is not valid for such non-uniform distinguishers.

Concerning non-uniform simulators (thanks Geoffroy for clarification) the standard definition requires a uniform simulator. However, having a non-uniform simulator does give some guarantees, and most of the time it is fine to have a non-uniform simulator. The reason is that we expect the security to hold even against dishonest non-uniform verifiers, so it makes sense to allow the simulator to also be non-uniform since it is in charge of reproducing the output of the verifier.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.