Limits on the usefulness of random oracles

Iftach Haitner, Eran Omri, Hila Zarosim

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

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

תקציר

In the random oracle model, parties are given oracle access to a random function (i.e., a uniformly chosen function from the set of all functions), and are assumed to have unbounded computational power (though they can only make a bounded number of oracle queries). This model provides powerful properties that allow proving the security of many protocols, even such that cannot be proved secure in the standard model (under any hardness assumptions). The random oracle model is also used for showing that a given cryptographic primitive cannot be used in a black-box way to construct another primitive; in their seminal work, ImpagliazzoRu89 [STOC '89] showed that no key-agreement protocol exists in the random oracle model, yielding that key-agreement cannot be black-box reduced to one-way functions. Their work has a long line of followup works (Simon [EC '98], Gertner et al. [STOC '00] and Gennaro et al. [SICOMP '05], to name a few), showing that given oracle access to a certain type of function family (e.g., the family that "implements" public-key encryption) is not sufficient for building a given cryptographic primitive (e.g., oblivious transfer). Yet, the following question remained open: What is the exact power of the random oracle model? We make progress towards answering this question, showing that essentially, any no private input, semi-honest two-party functionality that can be securely implemented in the random oracle model, can be securely implemented information theoretically (where parties are assumed to be all powerful, and no oracle is given). We further generalize the above result to function families that provide some natural combinatorial property. Our result immediately yields that essentially the only no-input functionalities that can be securely realized in the random oracle model (in the sense of secure function evaluation), are the trivial ones (ones that can be securely realized information theoretically). In addition, we use the recent information theoretic impossibility result of McGregor et al. [FOCS '10], to show the existence of functionalities (e.g., inner product) that cannot be computed both accurately and in a differentially private manner in the random oracle model; yielding that protocols for computing these functionalities cannot be black-box reduced to one-way functions.

שפה מקוריתאנגלית
כותר פרסום המארחTheory of Cryptography - 10th Theory of Cryptography Conference, TCC 2013, Proceedings
עמודים437-456
מספר עמודים20
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - מרץ 2013
אירוע10th Theory of Cryptography Conference, TCC 2013 - Tokyo, יפן
משך הזמן: 3 מרץ 20136 מרץ 2013

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

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

כנס

כנס10th Theory of Cryptography Conference, TCC 2013
מדינה/אזוריפן
עירTokyo
תקופה3/03/136/03/13

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Limits on the usefulness of random oracles'. יחד הם יוצרים טביעת אצבע ייחודית.

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