Join Log in
Score:1
Krakhit avatar Crypto

regarding MDS matrix and security

kg flag
Krakhit

I found a construction for MDS matrix (algorithm 4 of https://eprint.iacr.org/2020/1143) for a hash function that compresses elements in a prime field $F_p$

If the hash has a rate and capacity $(r,c)$ and $m = r+c$. It proceeds as

  1. Identify a primitive root of unity $g$ in $F_p$.
  2. Write a Vandermonde Matrix $V[i,j] = g^{ij}$ where $ i=0,1,\ldots m-1$ and $j=0,1,\ldots 2m$
  3. Reduce it to a row echelon form
  4. Then $V = I|M^T$ where $I_{m\times m}$ is unit matrix and $M$ is the desired MDS matrix.

The security level offered by the hash $s= \log_2(\sqrt{p})min(r,c)$. I wanted to know if the MDS construction in this form is independent of the security level.

The above resource is from the rescue hash function, that provides $122$ bit security, with $p = 2^{61}+20.2^{32}+1$ and $r=8, c=4$.

32
0 + 0
mds
Score:1
kodlu avatar Crypto
sa flag
kodlu

Generally MDS matrices are chosen because of their mixing properties see, e.g., this question and those properties hold for any MDS matrix. So I would say that the choice of the specific MDS matrix is independent of the security level.

In the document you linked to the authors say, on page 12:

There are cases where better performance is afforded by optimizing the MDS with respect to some design criterion. Section 2.4 specifies Vandermonde matrices as the standard way to generate the MDS matrix. However the original publication did not limit the choice of MDS to any specific type and argues its security with respect to any MDS matrix. The decision to be more restrictive merely simplifies the standard specification and is not known to have any security implications for algorithms following the Marvellous design strategy.

Choosing the MDS matrix: any MDS matrix can be used. The number of rounds is unaffected by this decision. Selection the Round Constants is unaffected by this decision.

Confidence Level is high. This variant was explicitly covered in the generic security argument of the original publication

0 + 0
Krakhit avatar
kg flag
Krakhit
Thanks a lot! I missed it.
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

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.