I know that if one-way functions exist then there are certain universal one-way functions that exist, but to my knowledge they are too impractical to implement (which is the main reason why they are not being used in modern cryptographic protocols). However, if one-way functions exist are the modern implementations (like RSA and its computational equivalents) definitely one-way? Conversely, if it can be shown that these cryptosystems are insecure, do one-way functions definitely not exist?

  • $\begingroup$ What research have you done? Have you looked on Crypto.SE? This is covered in standard courses on the theory of cryptography; they discuss what does and doesn't follow from the assumption that one-way functions exist. Short version: No, RSA needs stronger assumptions. $\endgroup$
    – D.W.
    Jun 24 '15 at 18:44
  • $\begingroup$ @D.W. Thank you for letting me know. I didn't know that crypto.SE existed. I did look through previous questions on cs.SE but didn't see anything similar. $\endgroup$
    – Ari
    Jun 24 '15 at 18:49

One-way functions are an asymptotic concept. A function such as modular exponentiation with specific parameters doesn't qualify for being a one-way function since it only exists for a specific size. The same can be said about hash functions such as SHA1. In order to ask the question, you will need to specify an infinite family of functions of the type you're interested in.

Once you've specified your infinite family of functions, the answer to both of your questions is negative: even conditional on the existence of one-way functions, we don't know whether these particular families are one-way, and conversely, it could well be that one-way functions exist, but these families are not one-way.

Should we care? Probably not. Even if a family of functions is one-way, that doesn't mean that using one of these functions is secure. One-way functions is an asymptotic concept, and a family of one-way functions can have significant weaknesses unless the key length is $10^{100}$, and still be one-way. What we need is more concrete guarantees.

In practice, functions we use are deemed secure since generations of researchers have tried to break them and failed (or at least failed to let us know that they succeeded). There is no relation to theoretical cryptography.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.