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
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2020
אירוע26th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2020 - Daejeon, קוריאה הדרומית
משך הזמן: 7 דצמ׳ 202011 דצמ׳ 2020

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

שםLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
כרך12493 LNCS

כנס

כנס26th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2020
מדינה/אזורקוריאה הדרומית
עירDaejeon
תקופה7/12/2011/12/20

ASJC Scopus subject areas

  • ???subjectarea.asjc.2600.2614???
  • ???subjectarea.asjc.1700.1700???

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Cryptography from One-Way Communication: On Completeness of Finite Channels'. יחד הם יוצרים טביעת אצבע ייחודית.

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