AI Grinding for Fun and Cryptanalysis
Lukasz Olejnik, Bartosz Naskrecki
cs.CR
2026-08-22
Agents dump attack hypotheses at volume; exact checks decide what counts. Eight published constructions fail at their own stated parameters, each with a reproducible witness.
A language model can read a crypto paper and dump candidate attacks by the dozen. Almost none survive an exact test, and the errors lean one way: fluent overclaim, mixing a proof gap with a real break. The expensive step is deciding which candidate is real.
Olejnik and Naskrecki call the arrangement grinding. Generation is deliberately high-volume and low-precision. Model output is never evidence. Exact arithmetic, a control whose expected outcome is fixed before the run, and the source version decide admission. Every survivor is then pushed at its own limitation until it either breaks a property the paper promises or hits a wall that can be proved.
Cryptanalysis has always rewarded one person carrying one idea a long way. Nothing here replaces that. What the workflow returns is a reproducible candidate; a researcher assigns its status.
Search aims at joins in the argument: a change of algebra, a change of encoding, a distribution carried through a map, rounding or CRT, a quotient, an exceptional value such as zero, a quantifier that widens from one object to a family, a parameter dropped into a script instead of the theorem it came from. At each join, two questions.
Which efficiently computable map still lives on the published objects and makes the hidden relation trivial or enumerable. Which distribution actually comes out, versus the law the proof claims. Neither question needs a full reading of the construction, so a generator that has seen one paper can be pointed at them.
The loop is short: an idea becomes an exact witness, the witness usually carries an "only works when" clause, that clause is the next target, and the exit is either a stronger attack or a boundary that will not move. Admission is a short deterministic program plus a precommitted control. The machine supplies breadth of conjecture; consequence, scope, and provenance stay with the researcher.
Eight published constructions fail at parameters or claims their authors state. A group-ring decision claim and a multivariate MinRank hardening stop at the assumption or accounting layer and are kept out of the "broken construction" count on purpose. Three further targets yielded no attack; they only show that a generic reading of Sparse, Tensor, and Succinct LWE is wider than the theorem.
| Target | Claim defeated | Number |
| Ring-LWR commitment | Binding, and soundness of three protocols | The accepted multipliers include d=0, so the zero commitment opens to every message with probability 1; the extractor divides by a zero divisor on about half of challenge pairs |
| Spinel signature hash | Collision and second-preimage resistance | 244 of 255 nonzero bytes have an immediate second preimage; printable equal-length pair "(y" and "y(" share one digest |
| Middle-product PKE at printed t=9 | IND-CPA | One ciphertext recovers all 2313 binary masks with success at least 0.999999730074; recovery holds through t=24 and collapses at t=25; the schemes' own lemmas need t≥98 |
| Lattice e-voting | Receipt-freeness | Simulator total variation is at least 1/15 at every permitted ternary parameter; at d=4096, p=1/3 the zero-count test has advantage 0.999999804160 |
| Hollow-LWE updatable encryption | IND-CR-CPA of pre-update ciphertexts | After the published permutation recovery, linear algebra yields a valid old decryption key, 12/12 at three reduced dimensions; repairing both defects grows ciphertexts and update tokens by 1.24 to 1.54 times |
| Two-limb CRT-RLWE | Malicious rerandomiser limited to denial of service | The accept bit is a threshold oracle on decryption noise; at n=4096 at most 131072 adaptive reactions recover the key |
| Function-field Normal Ring-LPN | Search hardness of the printed degree-63 basis | X^63+X^7+1 splits into seven degree-nine irreducibles; 3584 candidate tests replace 2^63 |
| Semidirect group-ring LWE | Decision hardness on full rings and selected quotients | Two-sample false-accept bound 64 N^{-7} log^2 N; an assumption defect, not a scheme break |
Every failure sits one level above the hardness assumption it rests on. Lattice reduction is never required. A zero multiplier, a variable-length encoding without boundaries, the two ends of a polynomial product, or a wrong simulator marginal is already enough.
For people who write and review schemes, the prescription is narrow. When a construction adds an algebraic setting or a representation layer, the argument should list the efficiently computable images of its published objects and say, for each, why the secret is not enumerable there and why the projected error is not distinguishable. An input encoding must be shown injective or uniquely decodable before hash security is transferred through it. Binding and soundness have to be proved for the exact set the verifier accepts, not for the honest element of that set. A parameter script must call the estimator at the dimension the reduction actually supplies.
For people building AI-assisted research, the useful split is generator reliability versus evidence reliability. Generation can be noisy if the admission boundary is exact, controlled, and reproducible. The model does not have to be reliable for the research to stand. That is a methods contribution, not a new primitive.
The Hollow-LWE runs assume the permutation and only check the post-permutation algebra at reduced dimension. They are not a benchmark of the published full-size recovery, which is other authors' work. The MinRank numbers live inside the source's own cost formula; no key recovery was executed. Whether Spinel yields a signature forgery depends on whether Hmsg uses the same defective hash, which the specification does not pin down. The CRT-RLWE attack needs an observable accept/reject bit. The group-ring results recover only images of the secret; the source also supplies no Type-II parameter generator or message encoding, so no fully specified encryption scheme is attacked.
Grinding returns reproducible candidates. Classification stays with the human. Coverage gaps and failed strengthenings are recorded on purpose, so a list of breaks is not an unknown filter.