Limits of Random Oracle in Secure Computation

Mahmoody, Mohammad; Maji, Hemanta K.; Prabhakaran, Manoj

Permalink

https://hdl.handle.net/2142/18698 Copy

Description

Title

Limits of Random Oracle in Secure Computation

Author(s)

• Mahmoody, Mohammad
• Maji, Hemanta K.
• Prabhakaran, Manoj

Issue Date

2011-02-24

Keyword(s)

• Secure Function Evaluation
• Random Oracle Model
• One-way Function
• Random Permutation Oracle
• Ideal Cipher
• Symmtric Primitives
• Black-box Separation

Abstract

Random Oracles have proven to be extremely powerful constructs in cryptography and they can be used to realize several useful cryptographic primitives which are, otherwise, impossible in the plain model. In this work, we explore the usefulness of random oracles for two-party semi-honest secure computation when parties have unbounded computational power, i.e. protocols which are information theoretically secure. In the plain model, where we have no setup, only extremely simple functions, namely decomposable functions, can be semi-honest securely realized against adversaries with unbounded computational power. In fact, decomposable functions have perfectly semi-honest secure round-optimal protocols in the plain model. The random oracle model, where parties are provided access to a common random oracle but are restricted to performing polynomially many queries to it, raises the optimism of securely realizing additional functions. But we show that random oracles are useless for information theoretic semi-honest secure realization of functions. When considering information theoretic security, a function is semi-honest trivial in the random oracle model if and only if it is semi-honest trivial in the plain model, i.e. it is decomposable.

Type of Resource

other

Language

en

Permalink

http://hdl.handle.net/2142/18698

Owning Collections