Files in this item



application/pdfBB-Sep.pdf (289kB)
(no description provided)PDF


application/pdfBB-Sep.pdf (1MB)
Updated with May 2012 versionPDF


Title:Limits of Random Oracle in Secure Computation
Author(s):Mahmoody, Mohammad; Maji, Hemanta K.; Prabhakaran, Manoj
Subject(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.
Issue Date:2011-02-24
Genre:Technical Report
Publication Status:unpublished
Peer Reviewed:not peer reviewed
Date Available in IDEALS:2011-02-25

This item appears in the following Collection(s)

Item Statistics