Non-overlapping codes have been studied for almost 60 years. In such a code, no proper, non-empty prefix of any codeword is a suffix of any codeword. In this paper, we study codes in which over-laps of certain specified sizes are forbidden. We prove some general bounds and we give several constructions in the case of binary codes. Our techniques also allow us to provide an alternative, elementary proof of a lower bound on non-overlapping codes due to Levenshtein [9] in 1964.

All-or-nothing transforms (AONT) were proposed by Rivest as a message preprocessing technique for encrypting data to protect against brute-force attacks, and have many applications in cryptography and information security. Later the unconditionally secure AONT 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}\mid \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}\mid \mathcal{Y})$ for combinatorial AONTs using information-theoretic techniques, and also show that the derived bounds can be attained in certain cases.

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.

A (t, s, v)-all-or-nothing transform (AONT) is a bijective mapping defined on s-tuples over an alphabet of size v, which satisfies the condition that the values of any t input co-ordinates are completely undetermined, given only the values of any s - t output co-ordinates. The main question we address in this paper is: for which choices of parameters does a (t, s, v)-AONT exist? More specifically, if we fix t and v, we want to determine the maximum integer s such that a (t, s, v)-AONT exists. We mainly concentrate on the case t = 2 for arbitrary values of v, where we obtain various necessary as well as sufficient conditions for existence of these objects. This includes computer searches that establish the existence of (2, q, q)-AONT for all odd primes not exceeding 29. We also show some connections between AONT, orthogonal arrays, and resilient functions.