TY - GEN

T1 - Statistical randomized encodings

T2 - 42nd International Colloquium on Automata, Languages and Programming, ICALP 2015

AU - Agrawal, Shweta

AU - Ishai, Yuval

AU - Khurana, Dakshita

AU - Paskin-Cherniavsky, Anat

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2015.

PY - 2015

Y1 - 2015

N2 - A randomized encoding of a function f(x) is a randomized function f(x, r), such that the “encoding” 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 SRE of languages (or boolean functions) that admit an efficient statistical randomized encoding. That is, 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.

AB - A randomized encoding of a function f(x) is a randomized function f(x, r), such that the “encoding” 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 SRE of languages (or boolean functions) that admit an efficient statistical randomized encoding. That is, 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.

UR - http://www.scopus.com/inward/record.url?scp=84950113617&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84950113617&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-47672-7_1

DO - 10.1007/978-3-662-47672-7_1

M3 - Conference contribution

AN - SCOPUS:84950113617

SN - 9783662476710

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 1

EP - 13

BT - Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Proceedings

A2 - Halldorsson, Magnus M.

A2 - Kobayashi, Naoki

A2 - Speckmann, Bettina

A2 - Iwama, Kazuo

PB - Springer

Y2 - 6 July 2015 through 10 July 2015

ER -