Invertible binary matrices with maximum number of -by- invertible submatrices

详细信息    查看全文

• 作者：Yiwei Zhang^a ; Tao Zhang^b ; Xin Wang^b ; Gennian Ge^a ; ^c ; ^{gnge@zju.edu.cn}
• 关键词：All-or-nothing transforms ; Invertible matrices
• 刊名：Discrete Mathematics
• 出版年：2017
• 出版时间：6 February 2017
• 年：2017
• 卷：340
• 期：2
• 页码：201-208
• 全文大小：422 K
• 卷排序：340

文摘

For given positive integers t≤st≤s, what is the maximum number of tt-by-tt invertible submatrices in an invertible binary matrix of order ss? 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=2t=2, let R2(s)R2(s) denote the maximal proportion of 2-by-2 invertible submatrices of ss-by-ss invertible matrices. D’Arco, Esfahani and Stinson ask whether lims→∞R2(s)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.5lims→∞R2(s)=0.5.