The strange thing about using AI for analysing cryptography - ciphers, hash functions, digital signatures, etc. - is that getting ideas is not the hard part. Getting rid of bad ideas is.
I don’t have a PhD in cryptography, nor math. Okay, I do have a PhD in computer science, but I somehow followed it up with op-eds and an LL.M. in IT law rather than a career proving theorems about lattices. Yet AI has made it possible for me to explore the fascinating areas of lattice cryptography and others, and sufficiently understand the machinery to generate attack ideas, test them, discard most of them, and get results. Breaking cryptography, invalidating proofs, and the such.
Lukasz Olejnik on Cyber, Privacy and Tech Policy Critique is a reader-supported publication. To receive new posts and support my work, consider becoming a free or paid subscriber.
One example is especially illustrative. A paper on Chinese Remainder Theorem (CRT)-based fully homomorphic encryption (allowing to make computation on encrypted data) had been submitted in May and was published by IACRCommunications in Cryptology in August. Same August I started examining it with the workflow I had been developing. The failure surfaced the same day.
Broken stuff
The construction relies on mathematical noise to hide secret information. But that noise passes through a particular CRT encoding. The natural question was simple: what happens to the noise after that map? For a whole family of error distributions allowed by the construction’s stated conditions, the answer is: it disappears.
Once that happens, relations that are supposed to be noisy become exact. In the usual invertible case, the secret key can be computed directly from the public key. Furthermore, the paper’s claimed transformation from ordinary Ring-LWE does not preserve the error distribution it says it does. The claimed reduction therefore does not work as stated.
Many other examples followed. I am sure there are tons more. Let’s consider two.
In a lattice e-voting protocol, privacy against coercion depends on voters being able to fabricate convincing fake receipts. The simulator generating those fake receipts has a statistical fingerprint that differs from genuine receipts for every permitted parameter. A coercer holding the transcript can tell them apart.
In a Ring-LWR commitment scheme, the verification rule allows a multiplier equal to zero. Set it to zero and the cryptographic equation becomes, well, 0 = 0. The same commitment can be opened to any message. Pushing that observation further breaks the soundness of the associated proof systems. By this point I already joined forces with Bartosz Naskrecki, who absolutely knows more about algebra than I do. We refined both papers, works, and grinded AI. Bartosz did it on vacation, and let me not even mention where I was doing my parts.
AI Grinding
These results, and several others, led us to formalise the workflow we had been using. We call it AI grinding. The idea is to let AI generate hypotheses aggressively but trust none of them. Most ideas die. Many do not. Sometimes AI is able to nail it nearly immediately, especially when results are verifiable, and many are. At other times human judgment might be of help. This is the future of math, cryptography, and whatnot. We formalise the approach and make a specific workflow. I expect that plenty of unexpected results will be unearthed about all the research papers published in previous years.
Algebraic structures generate hidden relations and edge cases. LLM agents are remarkably good at exploring those by trying many mathematical tricks and counterexamples humans might never test.
AI can be fluent, fast and wrong. It also makes exploration cheap. Including for researchers entering areas outside their original background. It’s a boon for inter and multidisciplinary work.