Statistical Randomized Encodings: A Complexity Theoretic View

A randomized encoding of a function

f

(

x

) is a randomized function

$$\hat{f}(x,r)$$

f

^

(

x

,

r

)

, such that the “encoding”

$$\hat{f}(x,r)$$

f

^

(

x

,

r

)

reveals

f

(

x

) and essentially no additional information about

x

. Randomized encodings of functions have found many applications in different areas of cryptography, including secure multiparty computation, efficient parallel cryptography, and verifiable computation.

We initiate a complexity-theoretic study of the class

$$\mathsf {SRE} $$

SRE

of languages (or boolean functions) that admit an efficient statistical randomized encoding. That is,

$$\hat{f}(x,r)$$

f

^

(

x

,

r

)

can be computed in time poly(|

x

|), and its output distribution on input

x

can be sampled in time poly(|

x

|) given

f

(

x

), up to a small statistical distance.

We obtain the following main results.

Separating

$$\mathsf {SRE} $$

SRE

from efficient computation:

We give the first examples of promise problems and languages in

$$\mathsf {SRE} $$

SRE

that are widely conjectured to lie outside

$$\mathsf {P/poly}$$

P

/

poly

. Our candidate promise problems and languages are based on the standard Learning with Errors (LWE) assumption, a non-standard variant of the Decisional Diffie Hellman (DDH) assumption and the “Abelian Subgroup Membership problem” (which generalizes Quadratic-Residuosity and a variant of DDH).

Separating

$$\mathsf {SZK} $$

SZK

from

$$\mathsf {SRE} $$

SRE

:

We explore the relationship of

$$\mathsf {SRE} $$

SRE

with the class

$$\mathsf {SZK} $$

SZK

of problems possessing statistical zero knowledge proofs. It is known that

$$\mathsf {SRE} \subseteq \mathsf {SZK} $$

SRE

⊆

SZK

. We present an oracle separation which demonstrates that a containment of

$$\mathsf {SZK} $$

SZK

in

$$\mathsf {SRE} $$

SRE

cannot be proved via relativizing techniques.