Revision #3 Authors: Iftach Haitner, Eran Omri, Hila Zarosim

Accepted on: 14th January 2013 22:24

Downloads: 844

Keywords:

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 assumption). 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, Impagliazzo and

Rudich [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 the above 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 essentially that 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 the existence of one-way functions.

Revision #2 Authors: Iftach Haitner, Eran Omri, Hila Zarosim

Accepted on: 14th January 2013 21:48

Downloads: 876

Keywords:

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 assumption). 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, Impagliazzo and

Rudich [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 the above 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 essentially that 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 the existence of one-way functions.

The name of the paper was changed from ``On the Power of Random Oracles" to ``Limits on the Usefulness of Random Oracles"

Revision #1 Authors: Iftach Haitner, Eran Omri, Hila Zarosim

Accepted on: 14th January 2013 21:44

Downloads: 876

Keywords:

In the random oracle model, the parties are given oracle access to a random member of

a (typically huge) function family, 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 assumption). The random oracle model is also

used to show that a given cryptographic primitive cannot be used in a black-box way to construct

another primitive; in their seminal work, Impagliazzo and Rudich [STOC ’89] showed that in the

random function model – when the function family is the set of all functions – it is impossible

to construct (secure) key-agreement protocols, 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, in the more general sense, the following fundamental question remained open:

What is the exact power of the random oracle model, and more specifically, of the

random function model?

We make progress towards answering the above question, showing that any (no private input)

semi-honest two-party functionality that can be securely implemented in the random function

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.

To exhibit the power of our result, 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

function model; yielding that protocols for computing these functionalities cannot be black-box

reduced to the existence of one-way functions.

The name of the paper was changed from ``On the Power of Random Oracles" to ``Limits on the Usefulness of Random Oracles"

TR12-129 Authors: Iftach Haitner, Eran Omri, Hila Zarosim

Publication: 9th October 2012 15:26

Downloads: 1180

Keywords:

In the random oracle model, the parties are given oracle access to a random member of

a (typically huge) function family, 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 assumption). The random oracle model is also

used to show that a given cryptographic primitive cannot be used in a black-box way to construct

another primitive; in their seminal work, Impagliazzo and Rudich [STOC ’89] showed that in the

random function model – when the function family is the set of all functions – it is impossible

to construct (secure) key-agreement protocols, 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, in the more general sense, the following fundamental question remained open:

What is the exact power of the random oracle model, and more specifically, of the

random function model?

We make progress towards answering the above question, showing that any (no private input)

semi-honest two-party functionality that can be securely implemented in the random function

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.

To exhibit the power of our result, 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

function model; yielding that protocols for computing these functionalities cannot be black-box

reduced to the existence of one-way functions.