Cryptology ePrint Archive: Report 2000/001

On Security Preserving Reductions -- Revised Terminology

Oded Goldreich

Abstract: Many of the results in Modern Cryptography are actually transformations of a basic computational phenomenon (i.e., a basic primitive, tool or assumption) to a more complex phenomenon (i.e., a higher level primitive or application). The transformation is explicit and is always accompanied by an explicit reduction of the violation of the security of the former phenomenon to the violation of the latter. A key aspect is the efficiency of the reduction. We discuss and slightly modify the hierarchy of reductions originally suggested by Levin.

Category / Keywords: foundations / Complexity, Reductions

Date: received 6 Mar 2000

Contact author: oded at wisdom weizmann ac il

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

Version: 20000307:201901 (All versions of this report)

Short URL: ia.cr/2000/001

Discussion forum: Show discussion | Start new discussion