Cryptography from One-Way Communication: On Completeness of Finite Channels

Shweta Agrawal, Yuval Ishai, Eyal Kushilevitz, Varun Narayanan, Manoj Prabhakaran, Vinod Prabhakaran, Alon Rosen

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء

ملخص

Garg et al. (Crypto 2015) initiated the study of cryptographic protocols over noisy channels in the non-interactive setting, namely when only one party speaks. A major question left open by this work is the completeness of finite channels, whose input and output alphabets do not grow with the desired level of security. In this work, we address this question by obtaining the following results: 1.Completeness of Bit-ROT with Inverse Polynomial Error. We show that bit-ROT (i.e., Randomized Oblivious Transfer channel, where each of the two messages is a single bit) can be used to realize general randomized functionalities with inverse polynomial error. Towards this, we provide a construction of string-ROT from bit-ROT with inverse polynomial error.2.No Finite Channel is Complete with Negligible Error. To complement the above, we show that no finite channel can be used to realize string-ROT with negligible error, implying that the inverse polynomial error in the completeness of bit-ROT is inherent. This holds even with semi-honest parties and for computational security, and is contrasted with the (negligible-error) completeness of string-ROT shown by Garg et al.3.Characterization of Finite Channels Enabling Zero-Knowledge Proofs. An important instance of secure computation is zero-knowledge proofs. Noisy channels can potentially be used to realize truly non-interactive zero-knowledge proofs, without trusted common randomness, and with non-transferability and deniability features that cannot be realized in the plain model. Garg et al. obtain such zero-knowledge proofs from the binary erasure channel (BEC) and the binary symmetric channel (BSC). We complete the picture by showing that in fact any non-trivial channel suffices.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفAdvances in Cryptology – ASIACRYPT 2020 - 26th International Conference on the Theory and Application of Cryptology and Information Security, 2020, Proceedings
المحررونShiho Moriai, Huaxiong Wang
ناشرSpringer Science and Business Media Deutschland GmbH
الصفحات653-685
عدد الصفحات33
رقم المعيار الدولي للكتب (المطبوع)9783030648398
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2020
الحدث26th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2020 - Daejeon, كوريا الجنوبيّة
المدة: ٧ ديسمبر ٢٠٢٠١١ ديسمبر ٢٠٢٠

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

الاسمLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
مستوى الصوت12493 LNCS

!!Conference

!!Conference26th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2020
الدولة/الإقليمكوريا الجنوبيّة
المدينةDaejeon
المدة٧/١٢/٢٠١١/١٢/٢٠

All Science Journal Classification (ASJC) codes

  • !!Theoretical Computer Science
  • !!General Computer Science

بصمة

أدرس بدقة موضوعات البحث “Cryptography from One-Way Communication: On Completeness of Finite Channels'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا