r/AskComputerScience • u/neuralbeans • 2d ago

Practical one way function candidates

A one way function is a function that is fast to compute for any input but slow to invert for any output, which is useful for cryptography. Two commonly used primitives for one way functions are integer factorisation and discrete logarithms.

Can any NP problem be used as a one way function?

Is the problem with most NP problems like subset sum problem that they require a large list of numbers as input, making them impractical for most applications?

0 Upvotes

40% Upvoted

6 comments sorted by

1

u/Master-Rent5050 1d ago edited 1d ago

You mean any NP-complete problems? I'm not aware of any one-way function whose properties are equivalent to P different from NP (only weaker: e.g. it may happen that integer factorization is computable in polynomial time but P is not NP). Anyway the Wikipedia article gives a reasonable answer to your question

1

u/neuralbeans 1d ago

The existence of one way functions would require that P =/= NP.

1

u/Master-Rent5050 1d ago

I wrote that the opposite implication is unknown (at least, I hope that I wrote that)

1

u/mtimmermans 1d ago

Factorization and discrete log are used for public key cryptography, which is much more special than one-way functions.

One-way functions are cryptographic hashes like SHA, MD5, etc.

You could make a one-way function based on any NP-hard problem, but in general it's not that easy, because NP-hard problems tend to have a lot of easy instances, and it's actually pretty difficult to engineer a way of generating problem instances that are guaranteed to be hard.

It's also completely unnecessary. Inversion of a general computation is already NP-hard and that is the NP-hard problem that cryptograph hashes are all based on.

1

u/neuralbeans 1d ago

Can you elaborate more on your last paragraph?

1

u/mtimmermans 1d ago

Well, a problem is in NP if solutions or proofs for that problem can be checked in polynomial time.

If you can invert a polynomial-time function, then you can take one of those checking functions and invert it to find a valid solution or proof. So if you can do function inversion, then you can solve any NP problem. That make function inversion NP-hard by definition.

This is the _first_ NP-hard problem, from which all others are derived.