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?
Asked By : Ari
Answered By : Yuval Filmus
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/43897
0 comments:
Post a Comment
Let us know your responses and feedback