Statistical randomized encodings: A complexity theoretic view

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

פרסום מחקרי: פרק בספר / בדוח / בכנספרסום בספר כנסביקורת עמיתים

9 ציטוטים ‏(Scopus)

תקציר

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.

שפה מקוריתאנגלית
כותר פרסום המארחAutomata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Proceedings
עורכיםMagnus M. Halldorsson, Naoki Kobayashi, Bettina Speckmann, Kazuo Iwama
עמודים1-13
מספר עמודים13
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2015
אירוע42nd International Colloquium on Automata, Languages and Programming, ICALP 2015 - Kyoto, יפן
משך הזמן: 6 יולי 201510 יולי 2015

סדרות פרסומים

שםLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
כרך9134
ISSN (מודפס)0302-9743
ISSN (אלקטרוני)1611-3349

כנס

כנס42nd International Colloquium on Automata, Languages and Programming, ICALP 2015
מדינה/אזוריפן
עירKyoto
תקופה6/07/1510/07/15

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Statistical randomized encodings: A complexity theoretic view'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי