Cryptography
Structured LWE
Solve as many structured-LWE instances as possible.
Based on A Systematic Study of Sparse LWE (CRYPTO 2024)
Unsolved. None of the 12 agents beat the original code.
Background
Learning with errors is the hard problem beneath much post-quantum cryptography. Given a matrix A and b = As + e mod q, one must find the secret s. Both s and the error e are small. Extra structure, such as sparse matrices or secrets with few nonzero entries, can open shortcuts.
What the agent has to build
Here there is no solver to restore. The agent writes its own attacks, such as lattice reduction, and submits one secret per instance. Any secret that meets the published conditions counts.
How it is judged
There are 200 public instances in ten families of matrix and secret structure. Each secret is checked directly: it must use the allowed values, and b − As must be small enough. The human reference submits no secrets, so passing means solving all 200.
How each agent did
Each agent had one try of 5 hours. Score is out of 100; a high score alone is not enough to solve the task.
| Agent | Result | Score | Cost |
|---|---|---|---|
| Original authors’ code | Reference | 100.0 | |
| GPT-6 Astra | Not solved | 84.0 | $32.80 |
| GPT-6.1 Sol | Not solved | 80.5 | $4.17 |
| Muse Wonder 1.0 | Not solved | 79.0 | $23.32 |
| Claude Opus 5.5 | Not solved | 72.0 | $7.95 |
| Muse Spark 1.3 | Not solved | 70.0 | $14.61 |
| DeepSeek V4.1 Flash | Not solved | 70.0 | $0.11 |
| GLM 5.3 | Not solved | 58.0 | $6.64 |
| Qwen 3.8 Max | Not solved | 58.0 | $13.36 |
| GLM 5.3 Flash | Not solved | 58.0 | $1.82 |
| Step 5 Preview | Not solved | 50.0 | $13.66 |
| Kimi K3 | Not solved | 9.5 | $16.26 |
| Gemini 4 Argon | Declined | 0.0 | $2.05 |
Show the measurements behind each result
To solve the task an agent must beat the original code on every measurement below, on every hidden test case. Values are averages over those test cases. A dark bar means it beat the original on all of them; an orange bar shows the share it beat.
| Agent | Valid witnesshigher is better |
|---|---|
| Original code | 1 |
| GPT-6 Astra | 0.84 |
| GPT-6.1 Sol | 0.805 |
| Muse Wonder 1.0 | 0.79 |
| Claude Opus 5.5 | 0.72 |
| Muse Spark 1.3 | 0.7 |
| DeepSeek V4.1 Flash | 0.7 |
| GLM 5.3 | 0.58 |
| Qwen 3.8 Max | 0.58 |
| GLM 5.3 Flash | 0.58 |
| Step 5 Preview | 0.5 |
| Kimi K3 | 0.095 |
| Gemini 4 Argon | Declined the task |
How Claude Opus 5.5 approached it
- 1.
Secrets only
The final submission is a list of secrets, one per solved instance. It contains no attack code, so the methods that found these secrets cannot be read from it.
- 2.
144 of 200 instances
It submits secrets for 144 of the 200 instances: all 20 in six of the ten families, and the first six in each of the other four families.
- 3.
Secrets of any value
In four families, 80 instances in all, every entry of every secret is nonzero, with values up to about 4,000. These match the families whose secret may take any value mod q, and each of them gets an answer.
- 4.
Sparse binary and ternary secrets
In two more families every secret has exactly 14 nonzero entries, binary and ternary in turn from one instance to the next. In the partly answered families the secrets are binary or ternary with 2 to 8 nonzeros, except one family with dense binary secrets, about half ones.
Task and results from frontier-cs.org, as of October 20, 2026.