On the Information-Theoretic Security of Combinatorial All-or-Nothing Transforms
Yujie Gu, Sonata Akao, Navid Nasr Esfahani, Ying Miao, Kouichi Sakurai · IEEE Transactions on Information Theory · 2022
All-or-nothing transforms (AONTs) were proposed by Rivest as a message preprocessing technique for encrypting data to protect against brute-force attacks, and have numerous applications in cryptography and information security. Later the unconditionally secure AONTs and their combinatorial characterization were introduced by Stinson. Informally, a combinatorial AONT is an array with the unbiased requirements and its security properties in general depend on the prior probability distribution on the inputs$s$-tuples. Recently, it was shown by Esfahani and Stinson that a combinatorial AONT has perfect security provided that all the inputs$s$-tuples are equiprobable, and has weak security provided that all the inputs$s$-tuples are with non-zero probability. This paper aims to explore on the gap between perfect security and weak security for combinatorial$(t,s,v)$-AONTs. Concretely, we consider the typical scenario that all the$s$inputs take values independently (but not necessarily identically) and quantify the amount of information$H(\mathcal {X}|\mathcal {Y})$about any$t$inputs$\mathcal {X}$that is not revealed by any$s-t$outputs$\mathcal {Y}$. In particular, we establish the general lower and upper bounds on$H(\mathcal {X}|\mathcal {Y})$for combinatorial AONTs using information-theoretic techniques, and also show that the derived bounds can be attained in certain cases. Furthermore, the discussions are extended for the security properties of combinatorial asymmetric AONTs.