A computational randomized encoding scheme $(\textrm{RE.Encode}, \textrm{RE.Decode})$ works as follows:

  • $\textrm{RE.Encode}(1^\lambda, C, x, r)$: takes as input the security parameter $\lambda$ in unary, a circuit $C$, the input string $x$, and the randomness $r$. It outputs a randomized encoding $\widetilde{C}(x,r)$.

  • $\textrm{RE.Decode}(\widetilde{C}(x,r))$: it outputs a value $y = C(x)$

The security property of computational randomized encoding requires that there exists a PPT simulator $\textrm{Sim}$ that takes input $C(x)$ and security parameter $\lambda$, then it output $\textrm{SimOut}_{C(x)}$ such that the the distribution $\{\textrm{SimOut}_{C(x)}\}$ is indistinguishable from the distribution $\{\widehat{C}(x,r)\}$ for any PPT adversaries.

Consider the following scenario: If we prove something using this randomized encoding in the hybrid argument, it is nature we replace $\widehat{C}(x,r)$ with $\textrm{SimOut}_{C(x)}$ due to the security of randomized encoding in the hybrid. However, if we use it to prove, for example, function (circuit) privacy, the first step which is also nature is to replace $\widehat{C_0}(x,r)$ with $\textrm{SimOut}_{C_0(x)}$.

My question is the second step, can we change $\textrm{SimOut}_{C_0(x)}$ into $\textrm{SimOut}_{C_1(x)}$ immediately and in turn into $\widehat{C_1}(x,r)$ ? where $C_0$ and $C_1$ are functionally equivalent.

  • 1
    $\begingroup$ You should provide (or link to) a specific definition that you have in mind. Unless you see a security definition that explicitly considers the output of RE.Encode on two different circuits, then the scheme is not required to hide anything about the choice of circuit. And in general, a computational randomized encoding (based on garbled circuits) will not hide the choice of circuit. $\endgroup$
    – Mikero
    Jul 20 '16 at 2:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.