Deepmind Alphadev: Faster sorting algorithms discovered using deep RL

Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by Someone on Wednesday June 07, 2023 @05:27PM (#36233786)

> I'm not sure what security properties are really "proven" about existing cryptographic hash functions

AFAIK, we don’t even know whether trapdoor functions exist.

“As of 2004, the best known trapdoor function (family) candidates are the RSA and Rabin families of functions”

Also note that the ‘examples’ section starts with:

“In the following two examples, we always assume it is difficult to factorize a large composite number (see Integer factorization).”

[ Parent | on HN ]

Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by aidenn0 on Wednesday June 07, 2023 @09:52PM (#36236175)

IIRC, if P=NP then trapdoor functions do not exist, so proving that one existed would be a huge deal even outside of cryptography.

[ Parent | on HN ]

Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by Dylan16807 on Thursday June 08, 2023 @02:05AM (#36237853)

Only if your definitions of "easy" and "hard" are based entirely on complexity classes.

If you show me a setup where "easy" is n^3 and "hard" is n^15 I will happily call that a trapdoor function.

[ Parent | on HN ]