University of Illinois Urbana-Champaign

Limits of Random Oracle in Secure Computation

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

Content Files
BB-Sep.pdf
BB-Sep.pdf

Permalink

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

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
Date of Ingest
2011-02-25T00:45:31Z
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
Genre of Resource
Technical Report
Language
en
Permalink
http://hdl.handle.net/2142/18698

Owning Collections

Research and Tech Reports - Computer Science PRIMARY