Design
amoeba-1
The stated decryption failure rate counts three or more coefficient errors, while a detected double error is a failure too
Security proof gap · Argued · Cause: parameter size
Property: IND-CCA security
Cost against claim: true failure rate 2-86.1 at Amoeba-576 against the 2-133.3 stated and the 2-128 the design requires; at 280 queries the security argument has no margin left
Table 4 gives one decryption failure rate per set, computed as the probability of three or more wrong coefficients among the 523 of a codeword. The shortened extended Hamming code corrects one error and only detects two, and both the specification and the code reject on a detected double error, which is a failure as well: the rate is the probability of two or more wrong coefficients, 47 to 90 bits above the stated one under the designers' own noise model, and no set meets the specification's own target of a rate below 2-λ at level λ. At Amoeba-576 the failure term of the FO argument over the 280 decapsulation queries the call allows is about 2-6 classically, and the corresponding term of the quantum random-oracle bound is about 278, above 1, so the security argument no longer establishes the level-128 claim. No attack is known.
| Parameter set | Claim | Attack cost | Verdict |
|---|
| Amoeba-576 | DFR 2-133.3 (Table 4); 128 classical | DFR 2-86.1; FO term 2-6.1 at 280 queries | Security proof gap |
| Amoeba-864 | DFR 2-208.6; 192 classical | DFR 2-138.3; FO term 2-58.3 at 280 queries | Security proof gap |
| Amoeba-1152 | DFR 2-267.9; 256 classical | DFR 2-177.9; FO term 2-97.9 at 280 queries | Security proof gap |
| Amoeba-1728 | DFR 2-229.3; 384 classical | DFR 2-152.2; FO term 2-72.2 at 280 queries | Security proof gap |
| Amoeba-2304 | DFR 2-205.3; 512 classical | DFR 2-136.1; FO term 2-56.1 at 280 queries | Security proof gap |
What causes it
Section 2.3.2 gives the failure rate as formula (21), the probability of more than t wrong coefficients among ℓ = 523, and takes t = 2 for a code that corrects one error and detects two; the same section says a detected double error is rejected. A rejection is a failure, so t = 1 is the right value. Section 3.2.6 then asserts that Amoeba-576, -864 and -1152 satisfy ∆ < 2-λ and that the two larger sets stay below 2-200, on the strength of Table 4; neither holds with the corrected rate. The submitted code rejects on two detected errors as the specification says (decode_ECC in hamming.c).
Evidence
The per-coefficient error probability and the block probabilities were recomputed from the specification's noise model (Theorem 2.3 and the designers' noise notebook) at 80 decimal digits. The probability of three or more errors reproduces Table 4 to the decimal for four sets and within 3 bits for Amoeba-576, which pins the model; the probability of two or more errors is 2-86.1, 2-138.3, 2-177.9, 2-152.2 and 2-136.1 for the five sets. A second member of PQC-X rebuilt the noise model independently, obtained the same five rates and the same agreement with Table 4, checked the rejection rule in the specification and in the code, and recomputed the FO terms at 280 queries.
Cause in the specification, traced to the specification text.
Limits
No decryption failure was observed and no attack is claimed: with honest ciphertexts, about 2-6 failures are expected within 280 queries at Amoeba-576, and whether failure boosting closes that gap was not computed. The four larger sets keep a failure term of 2-56 to 2-98 at 280 queries: their rates are overstated, but failures stay out of an attacker's reach. The defect of the submitted code that signals decoding failures on chosen ciphertexts (the implementation finding) does not depend on this rate.
Credit
First public report: Yijian Liu (ngcc.dev kem-02-3, 2026-09-23). Found independently by PQC-X.
Failure boosting and key recovery from decryption failures: D'Anvers, Guo, Johansson, Nilsson, Vercauteren and Verbauwhede (PKC 2019).
Implementation
Bugs in the submitted code; the specification is sound on these points.
amoeba-i1
The re-encryption check reads one ciphertext byte in four, so a tampered ciphertext is accepted
Minor break · Demonstrated · Cause: code
Property: IND-CCA security
Cost against claim: 785 of the 1047 ciphertext bytes of Amoeba-576 are never compared: a chosen ciphertext passes the check in one query, against IND-CCA2 at every level
Scope: The reference and the optimised implementations, which share the file; every parameter set.
Decapsulation re-encrypts the decoded message and compares the result with the received ciphertext, but the comparison loop advances four bytes at a time, so three bytes in four are never inspected (785 of 1047 for Amoeba-576). A ciphertext altered only at uninspected positions is accepted and decapsulated on the honest path, so the accept-or-reject behaviour becomes a decryption oracle on the reused secret key, the very thing the re-encryption check exists to prevent. The file is shared by the five parameter sets and by the optimised implementation.
| Parameter set | Claim | Attack cost | Verdict |
|---|
| all five Amoeba sets | IND-CCA2 at 128 to 512 classical | one decapsulation query per chosen ciphertext | Minor break |
What causes it
The specification's decapsulation (section 1.4) returns the fake key whenever the re-encryption differs from the received ciphertext. The code performs that comparison with a loop that steps by four (cmp in backend/ccakem.c, called once over the whole ciphertext); the specification is sound on this point.
Evidence
Run on the unmodified Amoeba-576 reference build, whose official test vectors were first reproduced byte for byte: a one-byte difference is detected at 262 of the 1047 positions, and flipping an uninspected byte of a valid ciphertext returns the accepted-path result while flipping an inspected one returns the rejection. A second member of PQC-X rebuilt the reference, reproduced the test vectors, wrote an independent harness and obtained the same 262 of 1047 positions and the same accept and reject behaviour, and checked that the source is identical in the five parameter sets and in the optimised implementation.
Cause in the submitted code; the specification is not affected.
Limits
PQC-X ran the oracle, not the key recovery it enables: the first public report goes on to recover the secret key of every Amoeba-576 test vector with about 30,000 decapsulation queries, which PQC-X has not reproduced. The key returned on the accepted path differs from the honest one, since the whole tampered ciphertext is hashed into it; what leaks is the accept-or-reject branch. The test vectors do not catch the defect, since honest ciphertexts re-encrypt exactly.
Credit
First public report: Jinnuo Li (PKC forum, also ngcc.dev kem-02-1, 2026-09-22). Found independently by PQC-X.
amoeba-i2
Decapsulation returns an explicit error on a detected decoding failure instead of the specified fake key
Minor break · Demonstrated · Cause: code
Property: IND-CCA security
Cost against claim: the return value of one decapsulation query tells whether the decoder saw two or more errors, a bit that depends on the secret key, against IND-CCA2 at every level
Scope: The reference and the optimised implementations, which share the file; every parameter set.
The specified decapsulation never fails: on any anomaly it returns a fake key derived from a secret string, so the caller cannot tell a rejected ciphertext from an accepted one. The submitted code returns an error code when the Hamming decoder detects two or more wrong coefficients, before the re-encryption check. Whether that happens depends on the product of the secret key with the attacker's chosen ciphertext, so each query leaks one bit about the key: a decryption-failure oracle of the kind the transform is meant to remove, available on every chosen ciphertext whatever the honest failure rate.
| Parameter set | Claim | Attack cost | Verdict |
|---|
| all five Amoeba sets | IND-CCA2 at 128 to 512 classical | one decapsulation query per oracle bit; the key recovery it enables was not costed | Minor break |
What causes it
Section 1.4 specifies the transform with implicit rejection (a fake key on failure, never an error), and section 2.3.2 has the PKE reject a detected double error, which the KEM must then hide. In backend/ccakem.c the decapsulation propagates the error of the PKE decryption (cpapke.c, returned when decode_ECC in hamming.c reports more than one error) as its own return value. The specification is sound on this point; the code deviates.
Evidence
Run on the unmodified Amoeba-576 reference build: a valid ciphertext decapsulates with return value 0, while a chosen ciphertext whose message part is corrupted in a few coefficients makes decapsulation return the error, every time. A second member of PQC-X reproduced both outcomes with an independent harness over three runs (2 to 4 corrupted bytes were needed, depending on the noise), traced the return value to the decoder's double-error branch, and confirmed that the specification never returns an error.
Cause in the submitted code; the specification is not affected.
Limits
PQC-X demonstrated the oracle, not the key recovery: the adaptive recovery of the secret key from decryption failures that such an oracle enables was neither run nor costed. Independent of the incomplete comparison (the other implementation finding), and invisible to the test vectors, whose honest ciphertexts decode without error.
Credit
Found by PQC-X.
Related public reports:
- M.-J. Saarinen (ngcc.dev kem-02-2, 2026-09-23): a cache and control-flow side channel in the same decoder; its text also notes the explicit failure return, without using it.
Key recovery from the decryption failures of a lattice KEM with an error-correcting code, through chosen ciphertexts: Guo, Johansson and Yang on LAC (ASIACRYPT 2019); D'Anvers, Guo, Johansson, Nilsson, Vercauteren and Verbauwhede (PKC 2019).