Invertible binary matrices with maximum number of [formula omitted]-by-[formula omitted] invertible submatrices.

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 R 2 ( s ) denote the maximal proportion of 2-by-2 invertible submatrices of s -by- s invertible matrices. D’Arco, Esfahani and Stinson ask whether lim s → ∞ R 2 ( 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 lim s → ∞ R 2 ( s ) = 0 . 5 . [ABSTRACT FROM AUTHOR]