کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4646573 | 1413648 | 2017 | 8 صفحه PDF | دانلود رایگان |
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.
Journal: Discrete Mathematics - Volume 340, Issue 2, 6 February 2017, Pages 201–208