2
$\begingroup$

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??

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$ Nov 14, 2022 at 7:25
  • $\begingroup$ 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. $\endgroup$
    – Maeher
    Nov 14, 2022 at 8:02
  • $\begingroup$ I've added an initial paragraph. $\endgroup$
    – Daniel S
    Nov 14, 2022 at 8:02
  • $\begingroup$ @Maeher true though I believe that Dilithium is parameterised to make non-causal solutions statistically unlikely. $\endgroup$
    – Daniel S
    Nov 14, 2022 at 8:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.