Source-linked AI summary
AI Grinding for Fun and Cryptanalysis
Lukasz Olejnik, Bartosz Naskrecki
TL;DR
The paper addresses how to turn abundant but unreliable machine-generated cryptanalytic hypotheses into evidence suitable for review. It presents a workflow that generates, tests, and repeatedly refines candidates with exact witnesses and controls before human classification. Across the analyzed constructions, it reports eight failures at stated parameters or claims, alongside narrower boundaries and targets yielding no attack.
Problem
Machine-generated cryptanalytic candidates are plentiful but usually unreliable, so deciding which hypotheses constitute real findings is the central research problem.
Method
The workflow uses high-volume candidate generation, exact arithmetic and executable witnesses, discriminating controls, reproducible run records, repeated limitation attacks, and human review.
Results
Eight published constructions fail at stated parameters or claims, while three further targets yield no attack and support narrower guarantees than a generic reading suggests.
Takeaways & Limitations
The workflow separates construction breaks from assumption defects and coverage gaps while producing reproducible evidence and proved boundaries.
Takeaways & Limitations
The axes impose a narrow classification, and some reported attacks remain conditional on observable acceptance or on particular constructed bases.
Abstract
from arXiv · showhide
We present an autonomous cryptanalysis workflow in which agents generate, test, and refine hypotheses before human review. The autonomous stage returns reproducible candidates with exact witnesses, controls, code, and run records. A researcher then decides whether the evidence establishes a break, defect, or coverage gap. Two failure modes recur. First, a public algebraic map or input representation erases or exposes a relation that a construction must hide. Examples include multiplication by zero, boundary coefficients of a polynomial product, quotients, characters, Schur squares, and variable-length byte encodings without boundaries. Second, a simulator, error law, or parameter certification uses a distribution different from the one claimed. Several targets fail in both ways. Every result has an exact witness and a discriminating control; every stated boundary has a proof. Three further targets yielded no attack but support narrower guarantees than a generic reading suggests. Eight published constructions fail at stated parameters or claims. A Ring-LWR commitment opens to every message with probability one. One ciphertext reveals two middle-product encryption rows. A lattice e-voting protocol loses receipt-freeness. A permutation-recovery attack against updatable encryption extends by linear algebra to the old decryption key. An explicit normal basis splits a degree-63 instance into seven degree-nine instances. A signature hash outside the lattice setting maps two printable equal-length messages to the same digest. A rerandomisable scheme's accept bit is a threshold oracle on its decryption noise. Separately, a group-ring decision claim and a multivariate MinRank hardening fail at the assumption or accounting level rather than as complete construction breaks. Each failure occurs one level above its supporting assumption.
1 Grinding: a direction for machine-assisted cryptanalysis
The paper proposes “grinding”: high-volume hypothesis generation followed by exact, controlled testing, human classification, and repeated escalation of verified limitations. This workflow produces reproducible candidate findings while distinguishing breaks, boundaries, and unsupported claims.
- Motivation: AI-generated attack ideas are numerous but usually fail exact testing, making candidate validation the costly research step.The workflow treats generation as low-precision and never treats generator output as evidence.
- Grinding: Grinding repeatedly attacks each verified limitation until it yields a stronger result or a proved boundary.A boundary that moves strengthens the attack; one that holds becomes a maximality result.
- Grinding: Six findings reach the top level and break an advertised security property, while the remaining findings stop lower for recorded reasons.Figure 2 represents findings as climbing levels until evidence no longer supports the next step.
- Evidence and review: The autonomous stage returns a claim, source version, witness, control, code, environment, run record, limitations, and proposed classification for human review.Human review determines whether the reproducible candidate constitutes a break, defect, or coverage gap.
- Evidence and review: Exact arithmetic, predetermined controls, and separate status categories prevent generator confidence from becoming evidence.The workflow records attacks, assumption defects, coverage gaps, unresolved paths, and failed strengthenings separately.
- Validation: A group-ring reproduction failed at a convenient modulus because its union bound was 1.78, but complete separation appeared at the specified parameter sequence.Reproductions not run at stated parameters are treated as unverified.
2 Results at a glance
The results are organized by status and evidence, keeping construction breaks distinct from assumption or certification defects and coverage gaps. The presentation records what each result establishes without merging these categories.
- Result accounting: Results are listed with their status and the evidence carrying each result.The derivations follow the same order as the results listing.
- Status categories: A break reaches a security property claimed by the source, such as key or plaintext recovery, binding, soundness, or a named privacy notion.This category concerns attacks on constructions rather than merely unsupported assumptions.
- Status categories: An assumption or certification defect shows that a stated claim is false or unsupported without exhibiting an attack on the construction.A coverage gap instead records what the source actually proves, not a defect in it.
3 Two axes: what to ask at each join
The paper directs automated searches at two recurring joins: whether a public map exposes or trivializes a hidden relation, and whether the resulting distribution matches the claimed law. These axes apply across unrelated constructions but define a deliberately narrow classification.
- Scope: The two axes are search directions applied at construction joins before they become a classification scheme.The same questions are used across constructions built on different assumptions.
- Scope: The classification is limited by the search questions themselves and is not a discovery about lattice cryptography as a whole.Its narrower contribution is that both questions continued producing findings across unrelated constructions.
- Public maps: A public efficiently computable map can make a hidden relation trivial or enumerable, undermining the role assigned to the assumption.Examples include multiplication by zero, polynomial-product boundary coefficients, group-ring reductions, coefficient sums, and coordinatewise squaring.
- Distribution mismatch: A claimed distribution can diverge from the actual distribution after simulation, error generation, projection, or parameter conversion.The consequences range from distinguishers to invalid security labels.
- Combined failures: Several targets lie on both axes because a public map exposes an object whose distribution also fails the proof’s requirements.The paper presents this combination as especially decisive.
4 Findings
The findings expose construction-level failures caused by non-injective maps, invalid parameter reasoning, and mismatched distributions, while also identifying concrete repairs and attack boundaries.
- Ring-LWR commitment: Binding fails with probability one because an opener-chosen zero multiplier makes one commitment open to two distinct messages for every public key.The same cancellation also defeats the associated proof system's soundness under the natural type correction.
- Signature hash: The signature encoding is non-injective after concatenating variable-length byte codewords without boundaries, producing equal-length printable messages with identical digests without search.The witness is E("(y") = E("y(") = 29, and retaining all six trits or using any uniquely decodable code restores injectivity.
- Middle-product encryption: The attack boundary is determined by ciphertext under-determination at t∗ = 96.32, whereas the security lemmas require t ≥ 98 because of the 2λ/(k + 1) slack.The extended attack changes the explained margin but reaches no further printed row because no published parameter set lies between 9 and 98.
- Receipt-freeness: The e-voting simulator has the wrong distribution at every permitted ternary parameter, allowing transcript holders to read votes and reject fabricated receipts.The one-component distinguisher has advantage 0.999999804160, while the optimal test uses the zero count conditioned on the observed ±2 count.
5 Where a proof covers less than the construction needs
Three targets are not construction breaks: their cited assumptions support narrower regimes than the constructions invoke, so the record separates coverage gaps from attacks.
- Three targets are reported as neither wrong nor attacked, because their proofs cover less than the constructions require.
- The recurring gap is between a hardness theorem’s stated conditions and a construction’s wider use of the same named assumption.
- These entries support checking exactly which assumption version a theorem establishes, not distrust of the source papers or claims that the schemes are insecure.
- For Jain, Lin, and Saha, the reduction is LWE_k ≲ SparseLWE_n,k, so increasing n at fixed sparsity k does not inherit dimension-n hardness.
- For Tensor LWE, the reduction covers ξ = 0 or one fixed x, not several distinct ξ_i sharing one secret as invoked by the ABE construction.
- For the headline compression, ordinary LWE supports the wide regime m̂ = ℓm, while the construction uses m̂ = m and relies on an additional assumption.
6 Reproducibility
Reproducibility is enforced through executable standard-library checks, predetermined controls, and explicit scope limits on reduced or non-full-size analyses.
- Every executable check uses only the Python standard library, runs in seconds, and includes a discriminating control with a fixed expected outcome.
- Hollow-LWE runs assume the permutation and validate post-permutation algebra only at reduced dimensions, not full-size recovery.
- The corrected Hollow-LWE parameter rows are a lower bound on the repair because they use only the estimator-free direction.
- The permutation-recovery premise comes from prior work, while the paper supplies the bridge to old-key and plaintext recovery.
7 What a security argument should enumerate
The case studies motivate security arguments that enumerate public algebraic images and verify distributions at each representation layer before transferring security properties.
- Autonomous search discovers reproducible failures at representation and distribution boundaries before human review.
- Each defect occurs before the advertised hard problem becomes relevant, and surviving results require a deterministic controlled check.
- Security arguments should enumerate efficiently computable images of published objects and explain why the secret remains neither enumerable nor distinguishable through projected error.
- Input encodings should be shown injective or uniquely decodable before security properties are transferred through them.
A The grind calculus
The grind calculus separates candidate generation from evidence admission and classifies verified outcomes after human audit.
- The calculus assigns an intermediate evidence judgment at admission and a final result type after human audit.
A.1 The arena
The arena records the source claim, a proposed violating relation, and a predicted observable at argument boundaries. Search directions ask which computable map preserves useful signal and which distribution actually results.
- The arena: Each source document carries a version stamp recording its revision date and archive identifier.The predicate Ver(π) ensures the attacked source version is recorded.
- The arena: The arena marks boundaries where arguments change algebra, representation, distribution, encoding, quantification, or parameter instantiation.
- The arena: Each hypothesis combines a source claim, an alleged mathematical or state relation, and a predicted observable fixed before execution.
- Search directions: At each join, search asks which efficiently computable map preserves useful signal and which probability law actually results.
- Search directions: Hypotheses answering both search questions at one join are the candidates that reach the highest levels of the evidence process.
A.2 The agents
The autonomous loop uses five agents to propose and redirect hypotheses, while human auditing performs final classification. Generator confidence is excluded from evidentiary judgment because fluent proposals can be wrong.
- The agents: Five agents execute the autonomous loop, but only a human auditor performs final classification.
- The agents: The generator is a sampler whose distribution is not explicitly known and is steered through the selected join and search questions.
- The agents: Generator confidence is inadmissible for ranking, ordering, triage, admission, or classification.The workflow excludes confidence rather than attempting to calibrate it against truth.
- The agents: Under a finite budget, the workflow records its scheduling rule and every unevaluated candidate because scheduling determines coverage.
A.3 Predicates
The predicates separate hypothesis testing from security-property assessment and classification. A control is a paired hypothesis designed to test whether the apparatus discriminates the claimed cause.
- Predicates: The rules divide predicates into evidence admission, security-property reach, and final classification, with human auditing required for every classification.
- Predicates: η is the hypothesis under test, while ¯η is a control differing in the single respect claimed to drive the analysis.
- Controls: A control must demonstrate discrimination, not a predetermined positive or negative verdict.Negative controls may fail and positive controls may pass; either outcome can be informative when fixed in advance.
A.4 Evidence types, and the axiom that keeps them apart
The framework distinguishes breaks, assumption or certification defects, coverage gaps, and results attributable to other authors. Its no-coercion axiom forbids promoting one evidence type into another without a fresh derivation.
- Evidence types: Evidence types include breaks of security properties, assumption or certification defects, coverage gaps, and known corrections by other authors.
- Keeping types apart: The no-coercion axiom permits only identity morphisms, so defects and gaps cannot be promoted into breaks without deriving the target classification anew.
- Counting: Results attributable to other authors receive zero tally contribution even when they support the analysis.The Schur-product permutation recovery is explicitly treated as such a case.
A.5 Admission and promotion
The admission and promotion calculus separates reproducible evidence from cryptanalytic classification, preserves unresolved outcomes, and treats normal form as a stopping condition rather than a completeness claim.
- Admission and classification: Rule A.8 classifies audited evidence only when its required premises establish an attack or a claim-relevant bridge, defect, or limitation.Absence of a bridge alone does not establish a defect, and hypotheses satisfying none of the rules remain unclassified.
- Unresolved outcomes: A timeout, cancellation, resource failure, or tool failure is recorded as unresolved evidence, never as a refutation.This preserves the distinction between an unsuccessful computation and an impossibility result.
- Promotion and maximality: Completed pushes either strengthen a result or prove that the attempted limitation cannot be removed; incomplete pushes remain unresolved with their attempts recorded.The Type-I block maximality statement is an example of the second productive exit.
- Normal form: A run reaches grind normal form when survivors stop changing, but this stopping condition does not claim that all limitations or attacks have been found.The evidence store retains moved, immovable, and unresolved limitations, while audit and classification operate on the autonomous search output.
- Run accounting: The run retained eleven results, three coverage gaps, and one rejected strengthening for its discriminating evidence.Failed proposals were not counted because the generator did not record them; the method values the surviving evidence set rather than proposal survival rate.
- Scope of the calculus: The calculus fixes hypothesis generation and evidence admission but does not derive which construction joins deserve attention or in what order.A poorly chosen search can return nothing while satisfying every stated rule.