Name
Abstract | ||
|---|---|---|
For given positive integers t≤s, what is the maximum number of t-by-t invertible submatrices in an invertible binary matrix of order s? This purely combinatorial problem is posedrecently by D’Arco, Esfahani and Stinson. The motivation is related to all-or-nothing transforms (AONTs) suggested by Rivest as a preprocessing for encrypting data with a block cipher, which has been widely applied in cryptography and security. For the case t=2, let R2(s) denote the maximal proportion of 2-by-2 invertible submatrices of s-by-s invertible matrices. D’Arco, Esfahani and Stinson ask whether lims→∞R2(s) exists or not. If it does exist, then their results indicate that the limit is between 0.494 and 0.625. In this paper we completely solve the problem by showing that lims→∞R2(s)=0.5. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1016/j.disc.2016.08.016 | Discrete Mathematics |
Keywords | Field | DocType |
All-or-nothing transforms,Invertible matrices | Integer,Discrete mathematics,Combinatorics,Block cipher,Logical matrix,Cryptography,Matrix (mathematics),Invertible matrix,Mathematics,Block matrix,Binary number | Journal |
Volume | Issue | ISSN |
340 | 2 | 0012-365X |
Citations | PageRank | References |
2 | 0.48 | 9 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yiwei Zhang | 1 | 52 | 12.65 |
| Tao Zhang | 2 | 57 | 10.22 |
| Xin Wang | 3 | 2 | 0.82 |
| Gennian Ge | 4 | 904 | 95.51 |