[CFRG] Fwd: [pqc-forum] Re: HAWK-n Key Recovery Reduces to SVP in Dimension n/2 + 1

[Dmitry Belyavsky <[e-mail]>]

As the discussion of this paper takes place at multiple ML and this email
looks like a relevant evaluation, I want to share it.

SY, Dmitry Belyavsky

---------- Forwarded message ---------
Od: Markku-Juhani O. Saarinen <[e-mail]>
Date: ne 9. 8. 2026 20:57
Subject: Re: [pqc-forum] Re: HAWK-n Key Recovery Reduces to SVP in
Dimension n/2 + 1
To: Cong Ling <[e-mail]>
Cc: pqc-forum <[e-mail]>


On Sun, Aug 9, 2026 at 5:58 PM 'Cong Ling' via pqc-forum <
[e-mail]> wrote:

> A Polynomial-Time Quantum Algorithm for the Dihedral Coset Problem
> <https://eprint.iacr.org/2026/1591>
>
> Has anyone independently checked the proof in this paper, either manually
> or using a formal proof assistant such as Lean?
>

Dear Cong Ling & Co,

Well, the paper just came out a couple of days ago (and many of the lemmas
are sketches.) Initial, direct attempts to check the proofs fail -- Lemma
3's central independence claim doesn't work as stated (it spends randomness
in D twice), and Lemma 4 applies unconditional hashing bounds after heavy
quantum conditioning. So the main proofs don't hold exactly as stated.

But it is important to note that a bug in the proofs doesn't demonstrate
that the algorithm itself doesn't work (which is really the more important
point from a cryptanalytic viewpoint). One can also restate the main
Theorem, if necessary.

So the community would indeed be very curious to know whether anyone has
found a way to repair the paper -- or found substantial evidence against
the algorithm.

However, there is a consensus that even if the paper's proof of correctness
and reductions were repaired, this would not threaten the quantum security
claims of NIST PQC algorithms. Such a result would be asymptotically
important, but its concrete quantum resource costs are too high.

ps. I'm obviously not the only one who has used GPT-5.6 Sol and Fable 5 on
this, and ran extensive computational experiments.I have a fairly generous
45-minute slot at WAC 8 (Workshop on Attacks in Cryptography, a Crypto
2026-affiliated event at UCSB on Sunday, August 16). I'm turning the
original title (on Hawk Guessing Game) into a subtitle and will intead talk
mostly about AI Cryptanalysis, including my attempts to prove this DCP
paper. https://wac8.cryptanalysis.fun/

Best Regards,
-markku

Dr. Markku-Juhani O. Saarinen <[e-mail]>



>
> On Monday, August 3, 2026 at 11:03:33 AM UTC+1 Alice Pellet-Mary wrote:
>
>> Dear Betül,
>>
>> To answer your questions, we have worked on this since the end of May, so
>> for approximatively 2 months (maybe a few weeks more for Guilhem). In terms
>> of budget, we did not use any costly tool, so that would be mostly human
>> (salary) cost. We weren't working full time on it at all, so I would say a
>> safe upper bound on the cost would be 2 person*month.
>>
>> Best regards,
>> Alice
>> Le samedi 1 août 2026 à 00:31:14 UTC+2, Betül Durak a écrit :
>>
>>> That’s pretty cool. Did they say how much budget they had/used and how
>>> long it took?
>>>
>>> On Fri, Jul 31, 2026 at 08:10 Damien Robert <[e-mail]>
>>> wrote:
>>>
>>>> Here is a message by Guilhem Mureau and Alice Pellet-Mary that they
>>>> asked me to post on their behalf.
>>>>
>>>> --------------------------------------------
>>>>
>>>> Dear all,
>>>>
>>>> We would also like to share a third key recovery attack on Hawk whose
>>>> result is very similar to the one of Hengyi Luo [2], even though we use
>>>> yet another mathematical tool. Our article should appear soon on
>>>> ePrint,
>>>> and is accessible for the moment here:
>>>>
>>>> https://apelletm.pages.math.cnrs.fr/page-perso/documents/articles/trace-zero-attack.pdf
>>>> <
>>>> https://apelletm.pages.math.cnrs.fr/page-perso/documents/articles/trace-zero-attack.pdf
>>>> >
>>>>
>>>> Our attack builds on our previous reduction from rank-2 module-LIP in a
>>>> cyclotomic field K to the norm reduced principal ideal problem (nrdPIP)
>>>> in a quaternion algebra [1]. We show that this nrdPIP instance can
>>>> itself be reduced to module-LIP in a module of rank 3 over the maximal
>>>> totally real subfield F of K. This allows us to reduce module-LIP in
>>>> modules of rank 2 in K to module-LIP in modules of rank 3 in F (note
>>>> that the degree of F is half the degree of K, so we are reducing the
>>>> lattice dimension by a factor 3/4).
>>>>
>>>> Applying this to Hawk, we obtain a key recovery attack on Hawk which
>>>> makes SVP calls in lattices of dimension at most 3n/4+1 (where n is the
>>>> degree of K), which is similar to the attack obtained by Hengyi Luo
>>>> [2].
>>>> The attack of Zygimantas Straznickas and Steve Weis [3] achieves an
>>>> even
>>>> smaller dimension for the SVP calls (namely n/2+1).
>>>>
>>>> The attack itself is quite simple. We wrote a detailed technical
>>>> overview section which we hope can be understood by any cryptographer
>>>> interested in module-LIP, so that they can get an idea of how the
>>>> attack
>>>> works without reading the full paper.
>>>>
>>>> In the upcoming weeks, we plan to investigate the relationship between
>>>> the three attacks. Given the strong similarities between the results,
>>>> it
>>>> seems that the three attacks may be doing very similar things with
>>>> different formalism.
>>>>
>>>> Implementation: we did a toy implementation of our attack in SageMath
>>>> (available here:
>>>> https://plmlab.math.cnrs.fr/apelletm/attack_hawk-trace-zero) We only
>>>> implemented the new part of the attack, i.e., the algorithm that solves
>>>> nrdPIP via module-LIP in modules of rank 3 over F. Due to limited
>>>> computational resources, we were able to run the attack only until n =
>>>> 128 (which runs in 2 hours on a laptop and uses BKZ with blocksize 30).
>>>> The point of the implementation was mostly to make sure that there was
>>>> no mistake in our proofs or that we did not overlook something, and the
>>>> results are satisfactory.
>>>>
>>>>
>>>> Guilhem Mureau and Alice Pellet-Mary
>>>>
>>>>
>>>> LLM disclaimer: We would like to acknowledge that this was found by
>>>> humans, with minimal technical guidance from LLMs. More precisely, we
>>>> used LLMs for improving the editorial quality of some parts of the
>>>> article, and for answering some technical mathematical questions that
>>>> we
>>>> had about quaternion algebras.
>>>>
>>>> References:
>>>> [1] Chevignard, C., Mureau, G., Espitau, T., Pellet-Mary, A., Pliatsok,
>>>> H., & Wallet, A. A reduction from hawk to the principal ideal problem
>>>> in
>>>> a quaternion algebra. Eurocrypt 2025. ePrint 2025/287
>>>> <https://eprint.iacr.org/2025/287.pdf>[2] Luo, H. Adjoint-Lattice
>>>> Reduction for the HAWK Gram-Factor Problem. link
>>>> <
>>>> https://harylo.github.io/files/preprints/adjoint-lattice-reduction-for-the-hawk-gram-factor-problem.pdf
>>>> >
>>>> [3] Straznickas, Z. and Weis, S. HAWK-n Key Recovery Reduces to SVP in
>>>> Dimension n/2 + 1. link
>>>> <
>>>> https://www-cdn.anthropic.com/e8d50c167ad47beeb03d6109a4a484be95cb38ea/hawk_key_recovery.pdf
>>>> >
>>>>
>>>>
>>>> On Tuesday, July 28, 2026 at 7:06:14 PM UTC+2 Steve Weis wrote:
>>>>
>>>>> Hello pqc-forum. We would like to announce an improved key recovery
>>>>> attack against HAWK-n that reduces to SVP in dimension n/2 + 1. The paper
>>>>> will appear at https://anthropic.com/document/hawk_key_recovery.pdf and
>>>>> is linked to from an accompanying blog post that will shortly be live:
>>>>> https://www.anthropic.com/research/discovering-cryptographic-weaknesses
>>>>>
>>>>> In the gate-count model of AGPS'20, the improved attack lowers the
>>>>> key-recovery cost of HAWK-512 from 2^150 to 2^108 and of HAWK-1024 from
>>>>> 2^288 to 2^182. We demonstrate this with a practical implementation that
>>>>> recovers a HAWK-256 secret key end-to-end in a few hours on a single
>>>>> server. The implementation can be found at:
>>>>> https://github.com/anthropics/cryptography-research-demo
>>>>>
>>>>> This result does not impact Falcon, ML-DSA, or other latticed-based
>>>>> schemes.
>>>>>
>>>>> We would like to thank the HAWK team for their help verifying this
>>>>> result and for their feedback. We would also like to acknowledge that this
>>>>> was found by Claude, with minimal technical guidance from people. For more
>>>>> information on the process, please refer to the above blog post.
>>>>>
>>>>> Thank you very much.
>>>>>
>>>> --
>>>>
>>> You received this message because you are subscribed to the Google
>>>> Groups "pqc-forum" group.
>>>> To unsubscribe from this group and stop receiving emails from it, send
>>>> an email to [e-mail].
>>>>
>>> To view this discussion visit
>>>> https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/09f45a33-bf7c-42cd-956d-ad4fecaccf3cn%40list.nist.gov
>>>> <https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/09f45a33-bf7c-42cd-956d-ad4fecaccf3cn%40list.nist.gov?utm_medium=email&utm_source=footer>
>>>> .
>>>>
>>> --
> You received this message because you are subscribed to the Google Groups
> "pqc-forum" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to [e-mail].
> To view this discussion visit
> https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/43aea96a-98bd-46cb-a7e1-0b11d094d40cn%40list.nist.gov
> <https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/43aea96a-98bd-46cb-a7e1-0b11d094d40cn%40list.nist.gov?utm_medium=email&utm_source=footer>
> .
>
-- 
You received this message because you are subscribed to the Google Groups
"pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an
email to [e-mail].
To view this discussion visit
https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CA%2BiU_qkUtn3xNxy0V1y7kKhpmK%2BkKsPyyW1ZCFOLtKs04f1xkw%40mail.gmail.com
<https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CA%2BiU_qkUtn3xNxy0V1y7kKhpmK%2BkKsPyyW1ZCFOLtKs04f1xkw%40mail.gmail.com?utm_medium=email&utm_source=footer>
.