Answers are grounded in this paper and cite their sources.
In this paper, we observe simple yet subtle interconnections among design theory, coding theory and cryptography. Maximum distance separable (MDS) matrices have applications not only in coding theory but are also of great importance in the design of block ciphers and hash functions. It is nontrivial to find MDS matrices which could be used in lightweight cryptography. In the SAC 2004 paper [12], Junod and Vaudenay considered bi-regular matrices which are useful objects to build MDS matrices. Bi-regular matrices are those matrices all of whose entries are nonzero and all of whose <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mrow> <m:mn>2</m:mn> <m:mo>×</m:mo> <m:mn>2</m:mn> </m:mrow> </m:math> {2× 2} submatrices are nonsingular. Therefore MDS matrices are bi-regular matrices, but the converse is not true. They proposed the constructions of efficient MDS matrices by studying the two major aspects of a <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mrow> <m:mi>d</m:mi> <m:mo>×</m:mo> <m:mi>d</m:mi> </m:mrow> </m:math> {d× d} bi-regular matrix M , namely <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mrow> <m:msub> <m:mi>v</m:mi> <m:mn>1</m:mn> </m:msub> <m:mo></m:mo> <m:mrow> <m:mo>(</m:mo> <m:mi>M</m:mi> <m:mo>)</m:mo> </m:mrow> </m:mrow> </m:math> {v₁(M)} , i.e. the number of occurrences of 1 in M , and <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mrow> <m:msub> <m:mi>c</m:mi> <m:mn>1</m:mn> </m:msub> <m:mo></m:mo> <m:mrow> <m:mo>(</m:mo> <m:mi>M</m:mi> <m:mo>)</m:mo> </m:mrow> </m:mrow> </m:math> {c₁(M)} , i.e. the number of distinct elements in M other than 1. They calculated the maximum number of ones that can occur in a <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mrow> <m:mi>d</m:mi> <m:mo>×</m:mo> <m:mi>d</m:mi> </m:mrow> </m:math> {d× d} bi-regular matrices, i.e. <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:msubsup> <m:mi>v</m:mi> <m:mn>1</m:mn> <m:mrow> <m:mi>d</m:mi> <m:mo>,</m:mo> <m:mi>d</m:mi> </m:mrow> </m:msubsup> </m:math> {v₁d,d} for d up to 8, but with their approach, finding <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:msubsup> <m:mi>v</m:mi> <m:mn>1</m:mn> <m:mrow> <m:mi>d</m:mi> <m:mo>,</m:mo> <m:mi>d</m:mi> </m:mrow> </m:msubsup> </m:math> {v₁d,d} for <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mrow> <m:mi>d</m:mi> <m:mo>≥</m:mo> <m:mn>9</m:mn> </m:mrow> </m:math> {d≥ 9} seems difficult. In this paper, we explore the connection between the maximum number of ones in bi-regular matrices and the incidence matrices of Balanced Incomplete Block Design (BIBD). In this paper, tools are developed to compute <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:msubsup> <m:mi>v</m:mi> <m:mn>1</m:mn> <m:mrow> <m:mi>d</m:mi> <m:mo>,</m:mo> <m:mi>d</m:mi> </m:mrow> </m:msubsup> </m:math> {v₁d,d} for arbitrary d . Using these results, we construct a restrictive version of <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mrow> <m:mi>d</m:mi> <m:mo>×</m:mo> <m:mi>d</m:mi> </m:mrow> </m:math> {d× d} bi-regular matrices, introducing by calling almost-bi-regular matrices, having <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:msubsup> <m:mi>v</m:mi> <m:mn>1</m:mn> <m:mrow> <m:mi>d</m:mi> <m:mo>,</m:mo> <m:mi>d</m:mi> </m:mrow> </m:msubsup>
No takes yet. Share an insight, caveat, or question.
Gupta et al. (2017) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: