Score:2

What is the effect of solving short integer solution problem in Dilithium or any other post quantum signature scheme?

cn flag

I am trying to understand the post quantum based signature scheme Dilithium. I know what the hard problems are in the scheme, but I am having trouble in understanding the utilization of short integer solution in the scheme. Specifically speaking, I can't understand exactly where this problem is used in the scheme. Also, what would happen if someone finds a solution to this hard problem, besides finding collisions for the hash function??

Score:2
ru flag

The hardness of SIS (or more precisely, the hardness of the module version of SIS: MSIS) is the assumption used to demonstrated the Strong Unforgeability of Crystal Dilithium under Chosen Message Attacks (SUF-CMA). In other words if this problem is hard then even producing a new signature for a previously signed message is hard even if the adversary is allowed to request multiple signatures of other messages. This is seen in section 6.2.2 of the paper.

If one can solve MSIS, powerful attacks are possible: consider the key generation algorithm on page 4 of the specification:

Gen

01 $A←R^{k×l} q$

02 $(\mathbf s_1,\mathbf s_2)\leftarrow S_\eta^l \times S_\eta^k$

03 $\mathbf t := A\mathbf s_1 +\mathbf s_2$

04 return(pk=($A,\mathbf t$),sk=($A,\mathbf t,\mathbf s_1,\mathbf s_2$))

We are given the values $A$ and $\mathbf t$ and wish to recover $\mathbf s_1$ and $\mathbf s_2$ for a key recovery attack (top of the attack outcome hierarchy).

Note that the matrix $$\begin{matrix}(A|I|-T)\end{matrix}$$ where $I$ is the $k\times k$ identity matrix and $T$ is the $k\times k$ diagonal matrix with entries taken from $\mathbf t$ has the short solution $(\mathbf s_1^T,\mathbf s_2^T,1,\cdots 1)^T$. A solution to this problem therefore allows recovery of the private key and complete impersonation of the owner.

Muhammad Awais avatar
cn flag
But this answers the second half of the question that a person has found the solution and he uses that solution to impersonate as someone else. But, how SIS is being utilized here and in documentation, where have they specified SIS problem?
cn flag
It's a bit too strong to say "A solution to this problem therefore allows recovery of the private key". The implication is the other way round. Recovering the key implies finding a short solution. A short solution will in general not be a valid secret key. So breaking SIS is necessary but not (obviously) sufficient for key recovery.
Daniel S avatar
ru flag
I've added an initial paragraph.
Daniel S avatar
ru flag
@Maeher true though I believe that Dilithium is parameterised to make non-causal solutions statistically unlikely.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.