Statistical randomized encodings: A complexity theoretic view

Shweta Agrawal, Yuval Ishai, Dakshita Khurana, Anat Paskin-Cherniavsky

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationAutomata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Proceedings
EditorsMagnus M. Halldorsson, Naoki Kobayashi, Bettina Speckmann, Kazuo Iwama
PublisherSpringer-Verlag
Pages1-13
Number of pages13
ISBN (Print)9783662476710
DOIs
StatePublished - Jan 1 2015
Externally publishedYes
Event42nd International Colloquium on Automata, Languages and Programming, ICALP 2015 - Kyoto, Japan
Duration: Jul 6 2015Jul 10 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9134
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other42nd International Colloquium on Automata, Languages and Programming, ICALP 2015
CountryJapan
CityKyoto
Period7/6/157/10/15

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Statistical randomized encodings: A complexity theoretic view'. Together they form a unique fingerprint.

Cite this