A new algorithm that is potentially relevant to the security of Dilithium

[Noah Stephens-Davidowitz]

Hi all,

I just want to bring the following paper to this community's attention: https://arxiv.org/abs/2510.07515 .

In this paper, Kothari, O'Donnell, and Wu (KOW) give polynomial-time algorithms for multiple variants of the SIS problem in which of course the input is a matrix A \in Z_q^{n x m}, and the goal is to find a non-zero vector x such that Ax = 0 but ||x||_\infty <= s for some bound s. I think the most relevant result for this community is their Theorem 1.5, where they show how to achieve s = q/(2k), provided that m >~ n^k. 

So, KOW solve SIS in a parameter regime that I think many experts would have suspected was hard, but in which the bound s on the length of x is quite large and the matrix A is very very far from square. (For what it's worth, the algorithm even works in the worst case.)

Recall that to break Dilithium security levels 3 or 5, it essentially suffices to solve SIS (over module lattices) with s ~ q/8, which might very reasonably make one worry about this new algorithm. However, the effective dimensions of the matrix A are n = 256k and m = 256(k+\ell), where (k,\ell) takes values (4,4), (6,5), and (8,7) in the different parameter sets. So, the Dilithium parameter set is very far from the regime in which this algorithm applies, and to be abundantly clear, this does not apply directly to Dilithium's parameter regime. (KOW discuss this in Section 5.6.)

On the other hand, I think this certainly merits further research from this community. This is a new algorithmic technique for solving SIS that we were presumably unaware of. (I certainly was not aware of this---and presumably if anyone else was aware of this, they would have already written a paper on it. Admittedly, there is some similarity with Wagner/BKW-style algorithms.) The new algorithms do not apply to the parameter regime that is most relevant to us, but in the parameter regime where they do apply, they give not only faster algorithms but actual polynomial-time algorithms. 

I therefore think that it's quite important to ask whether some variant of these techniques can be used to obtain faster algorithms in less extreme parameter regimes, perhaps including the regime of Dilithium. Or, perhaps we can understand these techniques well enough to convince ourselves that they simply will not apply in regimes relevant to cryptography.

This is also probably just a good reminder of the fact that there are still new algorithms to be discovered for these basic problems :).

-Noah

[Natalia]

This sounds very interesting and very difficult from what we have been studying so far. Care to make a Youtube video about it, so we can all follow along?

Natalia D'Onofrio, FRP, MBA

Florida Supreme Court Certified Mediator: Circuit, County, Family, Dependency

Florida Supreme Court Qualified Arbitrator

​The Florida Bar Certified Arbitrator & Mediator

Guardian ad Litem

Affinity Ventures, LLC

P.O. Box 2059

Palm Beach, FL 33480

Tel: (561) 501-1033

--
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 pqc-forum+...@list.nist.gov.
To view this discussion visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/a0eec9e3-a6bf-4c91-8580-e232f0f6d871n%40list.nist.gov.

[Muhammed Esgin]

Thanks for sharing this Noah! Very interesting and I agree with your points.

I was very worried when I saw your post that the attack works for s = q/(2k) and m >~ n^k. For k=1, that could have been very worrying for some schemes. Thankfully, their Theorem 1.5 requires k>=2; so clarifying this for everyone. That means m needs to be at least in the order of n^2.

-Muhammed