Generic case complexity and One-Way functions

Details Generic case complexity and One-Way functions Generic case complexity and One-Way functions

2008-02-26

arxiv.org/abs/0802.3734v1

Computer Science

Computational Complexity

Scientific paper

The goal of this paper is to introduce ideas and methodology of the generic case complexity to cryptography community. This relatively new approach allows one to analyze the behavior of an algorithm on ''most'' inputs in a simple and intuitive fashion which has some practical advantages over classical methods based on averaging. We present an alternative definition of one-way function using the concepts of generic case complexity and show its equivalence to the standard definition. In addition we demonstrate the convenience of the new approach by giving a short proof that extending adversaries to a larger class of partial algorithms with errors does not change the strength of the security assumption.

Affiliated with

Also associated with

No associations

Rating

Generic case complexity and One-Way functions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Generic case complexity and One-Way functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Generic case complexity and One-Way functions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-606443