Threat to PKE from AI

There is a plausible threat to public key encryption from advances in AI:

(a) AI may find new exploitable structures in RSA, elliptic curves, finite-field discrete log, or lattices. This could mean faster classical attacks on any of them, or an efficient quantum algorithm for lattices.

(b) AI will accelerate large scale quantum computers, both by advancing hardware (and improvements to error correction), and improvements to Shor’s algorithm.

And hashes cannot save the day, because, while discounting that they themselves are structured & vulnerable to advances in AI albeit being more conservative, it’s impossible to construct PKE from only one-way functions & random oracle (ie hash functions).

Others provide better evidence for (b) than I can. For (a) it’s well known that an attack exploits a structure. The primtives standing today have survived decades of scrutiny, albeit with limited effort of the ones that could afford ¹. And overtime we’ve settled onto a few structures that the primitives are allowed. However, the times they are a-changin'.

LLMs have all of humanity’s knowledge and can search over it faster than any cryptoanalyst. If there exists a attacks discoverable by effectively traversing the search tree using all known knowledge, then frontier models will find them. Even in the case where attacks require new insights, I think, frontier models are likely to score them. Either by learning to create new knowledge or by the virtue of step-change insights often researchers leak to LLMs over the course of a conversation. They will not only score, they will score fast. Previosuly, key insights did not always immediately translate into attacks but now they do².

It’s likely that any damaging attack will first be discovered by a frontier lab. I suspect the labs will play the closed-door game to avoid causing large, imminent damage to the world. This is a very sensible move. But they can’t expect the game to last more than ~6 months, a year at most, because open-source models catch up with frontier models fast!

If you care about public key encryption, there are enough reasons not to ignore the threat. Find some way to accelerate the development of new alternative primitives for PKE (AI can help us speedrun this!). While, no one wishes to need them soon, but for better or worse, the chances of us needing them in a few years are not slim.

I don’t have a clear idea of what properties the new primitives must have to be safe against more powerful AI. But being conservative and demanding little to no structure seems reasonable. And since I’m writing this, I’ll mention local-mixing, to which I was fortunate to make small contributions wherever I could help. It started as an approach to indistinguishability obfuscation, which I think is still its main objective. But over time it became clear to me (& others) that it’s also a new low-level primitive for constructing cryptographic tools. For example, Ran and his students are developing PKE with local-mixing as the base assumption.