Randomized encoding

A randomized encoding of a function is a randomized function , typically of much lower complexity than , whose output determines and reveals nothing else about : it can be decoded to and simulated from alone — IK00, AIK06.

Syntax

A randomized encoding of is a function together with two efficient algorithms:

  • a deterministic decoder ,
  • a randomized simulator that takes and outputs a string in .

For a family of functions , the encodings, decoders and simulators form families computable in time polynomial in . The complexity of an encoding is that of : its degree, its locality (the number of input bits, of and together, on which each output bit depends) or its depth — AIK06; for succinct encodings, its running time as a function of the time, space and output length of the encoded computation — BGLPT15.

Properties

Correctness

The encoding is perfectly correct if for all and ,

Randomized encodings are required to be perfectly correct.

Privacy

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{re}}_{\hat f,\Sim,\calA}(\secpar)$}
\begin{algorithmic}
\State $(x, \stA) \gets \calA(1^\secpar)$; $b \getsr \bits$
\State $r \getsr \bits^{\rho}$; $y_0 := \hat f_\secpar(x; r)$
\State $y_1 \gets \Sim(1^\secpar, f_\secpar(x))$
\State $b' \gets \calA(\stA, y_b)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

The encoding is private if there is a simulator such that for all efficient ,

is negligible. It is statistically private if the advantage is negligible for all, possibly unbounded, , and perfectly private if and are identically distributed for every — AIK06. An encoding that is private is also called a computational randomized encoding; the garbled circuit of with the input labels of is one for — AIK06b.

Variations

Perfect randomized encodings

A perfect randomized encoding is perfectly correct and perfectly private, and in addition balanced, is uniform on , and stretch-preserving, — AIK06. Balance and stretch preservation let the encoding inherit pseudorandomness, so that a perfect randomized encoding of a PRG is a PRG (PRG in NC1 ⇒ PRG in NC0) — AIK06.

Succinct randomized encodings

A succinct randomized encoding, for a space bound and an output length fixed in advance, is a randomized encoding of the output of a program on an input , given a time bound such that halts on within steps using space at most and outputs bits; it is computable in time , and its privacy hides as well as — BGLPT15. Such encodings exist assuming iO and one-way functions — BGLPT15. One-time succinct garbling of RAM programs, with garbled programs of size proportional to the maximum space of the program up to polylogarithmic factors and a factor in , follows from iO and injective one-way functions — CHJV15. With a non-parallelizing language, succinct randomized encodings give time-lock puzzles — BGJ+16.

TODO: the syntax and privacy game of BGLPT15, stated from the paper: whether the encoder takes as input; whether a single polynomial, independent of , bounds the encoding time; the range of ; the running time of the decoder, which the base syntax requires to be ; and what the simulator receives (, and which of , , , and ). Register the notion as a variant once the game is encoded.

Other results

  • Functions with polynomial-size branching programs, among them every function in , have randomized encodings in which every output is a polynomial of degree in over a finite field — IK00.
  • Every function in , which contains , has a perfect randomized encoding of locality — AIK06. Hence one-way functions and PRGs computable in have counterparts in , where each output bit depends on at most four input bits (PRG in NC1 ⇒ PRG in NC0), and public-key encryption whose encryption algorithm is in has a counterpart whose encryption algorithm is in — AIK06.
  • Assuming a pseudorandom generator in , every polynomial-time computable function has a computationally private randomized encoding of degree , hence of locality ; the construction combines Yao’s garbled circuits with the information-theoretic encodings above — AIK06b.
  • A randomized encoding of degree reduces secure multiparty computation of to secure computation of degree- polynomials, which with degree gives constant-round protocols — IK00.