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
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2015
الحدث42nd International Colloquium on Automata, Languages and Programming, ICALP 2015 - Kyoto, اليابان
المدة: ٦ يوليو ٢٠١٥١٠ يوليو ٢٠١٥

سلسلة المنشورات

الاسمLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
مستوى الصوت9134
رقم المعيار الدولي للدوريات (المطبوع)0302-9743
رقم المعيار الدولي للدوريات (الإلكتروني)1611-3349

!!Conference

!!Conference42nd International Colloquium on Automata, Languages and Programming, ICALP 2015
الدولة/الإقليماليابان
المدينةKyoto
المدة٦/٠٧/١٥١٠/٠٧/١٥

بصمة

أدرس بدقة موضوعات البحث “Statistical randomized encodings: A complexity theoretic view'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا