Search

Security of linear ramp secret sharing schemes can be characterized by the relative generalized Hamming weights of the involved codes. In this paper, we elaborate on the implication of these parameters and devise a method to estimate their value for general one-point algebraic geometric codes. As it is demonstrated, for Hermitian codes, our bound is often tight. Furthermore, for these codes, the relative generalized Hamming weights are often much larger than the corresponding generalized Hamming weights. [ABSTRACT FROM AUTHOR]

In this paper, we consider the maximum absolute value \Delta f in the autocorrelation spectrum (not considering the zero point) of a function f . In an even number of variables n , bent functions possess the highest nonlinearity with \Delta f = 0 . The long standing open question (for two decades) in this area is to obtain a theoretical construction of balanced functions with \Delta f < 2^{n/2} . So far, there are only a few examples of such functions for n = 10, 14 , but no general construction technique is known. In this paper, we mathematically construct an infinite class of balanced Boolean functions on n variables having absolute indicator strictly lesser than \delta n = 2^{n/2}-2^{(({n+6})/{4})} , nonlinearity strictly greater than \rho n = 2^{n-1} - 2^{n/2} + 2^{n/2-3} - 5\cdot 2^{(({n-2})/{4})} and algebraic degree n-1 , where n\equiv 2 \pmod 4 and n\geq 46 . While the bound n \geq 46 is required for proving the generic result, our construction starts from n = 18 and nonlinearity > 2^n-1 - 2^n/2 for n = 18, 22 , and 26. [ABSTRACT FROM PUBLISHER]

Cyclic codes are widely employed in communication systems, storage devices, and consumer electronics, as they have efficient encoding and decoding algorithms. BCH codes, as a special subclass of cyclic codes, are in most cases among the best cyclic codes. A subclass of good BCH codes are the narrow-sense BCH codes over \mathrm GF(q) with length n=(q^m-1)/(q-1) . Little is known about this class of BCH codes when $q>2$ . The objective of this paper is to study some of the codes within this class. In particular, the dimension, the minimum distance, and the weight distribution of some ternary BCH codes with length n=(3^{m}-1)/2 are determined in this paper. A class of ternary BCH codes meeting the Griesmer bound is identified. An application of some of the BCH codes in secret sharing is also investigated. [ABSTRACT FROM PUBLISHER]

Minimal linear codes have interesting applications in secret sharing schemes and secure two-party computation. This paper uses characteristic functions of some subsets of $\mathbb {F}_{q}$ to construct minimal linear codes. By properties of characteristic functions, we can obtain more minimal binary linear codes from known minimal binary linear codes, which generalizes results of Ding et al. [IEEE Trans. Inf. Theory, vol. 64, no. 10, pp. 6536–6545, 2018]. By characteristic functions corresponding to some subspaces of $\mathbb {F}_{q}$ , we obtain many minimal linear codes, which generalizes results of [IEEE Trans. Inf. Theory, vol. 64, no. 10, pp. 6536–6545, 2018] and [IEEE Trans. Inf. Theory, vol. 65, no. 11, pp. 7067–7078, 2019]. Finally, we use characteristic functions to present a characterization of minimal linear codes from the defining set method and present a class of minimal linear codes. [ABSTRACT FROM AUTHOR]

Minimal linear codes have significant applications in secret sharing schemes and secure two-party computation. There are several methods to construct linear codes, one of which is based on functions over finite fields. Recently, many construction methods for linear codes from functions have been proposed in the literature. In this paper, we generalize the recent construction methods given by Tang et al. in [IEEE Transactions on Information Theory, 62(3), 1166-1176, 2016] to weakly regular plateaued functions over finite fields of odd characteristic. We first construct three-weight linear codes from weakly regular plateaued functions based on the second generic construction and then determine their weight distributions. We also give a punctured version and subcode of each constructed code. We note that they may be (almost) optimal codes and can be directly employed to obtain (democratic) secret sharing schemes, which have diverse applications in the industry. We next observe that the constructed codes are minimal for almost all cases and finally describe the access structures of the secret sharing schemes based on their dual codes. [ABSTRACT FROM AUTHOR]

In addition to their applications in data communication and storage, linear codes also have nice applications in combinatorics and cryptography. Minimal linear codes, a special type of linear codes, are preferred in secret sharing. In this paper, a necessary and sufficient condition for a binary linear code to be minimal is derived. This condition enables us to obtain three infinite families of minimal binary linear codes with $w_{\min }/w_{\max } \leq 1/2$ from a generic construction, where $w_{\min }$ and $w_{\max }$ , respectively, denote the minimum and maximum nonzero weights in a code. The weight distributions of all these minimal binary linear codes are also determined. [ABSTRACT FROM AUTHOR]

An involution is a permutation, such that its inverse is itself (i.e., cycle length ≤ 2). Due to this property, involutions have been used in many applications, including cryptography and coding theory. In this paper, we provide a systematic study of involutions that are defined over a finite field of characteristic 2. We characterize the involution property of several classes of polynomials and propose several constructions. Furthermore, we study the number of fixed points of involutions, which is a pertinent question related to permutations with short cycle. In this paper, we mostly have used combinatorial techniques. [ABSTRACT FROM AUTHOR]

Linear codes with a few weights have applications in consumer electronics, communication, data storage system, secret sharing, authentication codes, association schemes, and strongly regular graphs. This paper first generalizes the method of constructing two-weight and three-weight linear codes of Ding et al. and Zhou et al. to general weakly regular bent functions and determines the weight distributions of these linear codes. It solves an open problem proposed by Ding et al. Furthermore, this paper constructs new linear codes with two or three weights and presents their weight distributions. They contain some optimal codes meeting certain bound on linear codes. [ABSTRACT FROM AUTHOR]

Secret sharing schemes allow a dealer to distribute a secret piece of information among several parties such that only qualified subsets of parties can reconstruct the secret. The collection of qualified subsets is called an access structure. The best known example is the k -threshold access structure, where the qualified subsets are those of size at least k . When k=2 and there are n parties, there are schemes for sharing an \ell bits, and this is tight even for secrets of 1 b. In these schemes, the number of parties n must be given in advance to the dealer. In this paper, we consider the case where the set of parties is not known in advance and could potentially be infinite. Our goal is to give the {t} {^{\mathrm{ th}}} party arriving the smallest possible share as a function of t$ . Our main result is such a scheme for the k$ -threshold access structure and 1-bit secrets where the share size of party t$ is . For k=2$ we observe an equivalence to prefix codes and present matching upper and lower bounds of the form \log t + \log \log t + \log \log \log t + O(1)$ . Finally, we show that for any access structure there exists such a secret sharing scheme with shares of size . [ABSTRACT FROM AUTHOR]

Minimum storage regenerating codes have minimum storage of data in each node and therefore are maximal distance separable (for short) codes. Thus, the number of nodes is upper-bounded by 2^ \mathfrak b , where \mathfrak b is the bits of data stored in each node. From both theoretical and practical points of view (see the details in Section 1), it is natural to consider regenerating codes that nearly have minimum storage of data, and meanwhile, the number of nodes is unbounded. One of the candidates for such regenerating codes is an algebraic geometry code. In this paper, we generalize the repairing algorithm of Reed–Solomon codes given by Guruswami and Wotters to algebraic geometry codes and present a repairing algorithm for arbitrary one-point algebraic geometry codes. By applying our repairing algorithm to the one-point algebraic geometry codes based on the Garcia–Stichtenoth tower, one can repair a code of rate 1- \varepsilon and length n over \mathbb Fq with bandwidth (n-1)(1- \tau)\log q for any \varepsilon =2^(\tau -1/2)\log q with a real $\tau \in (0,1/2)$ . In addition, storage in each node for an algebraic geometry code is close to the minimum storage. Due to nice structures of Hermitian curves, repairing of Hermitian codes is also investigated. As a result, we are able to show that algebraic geometry codes are regenerating codes with good parameters. [ABSTRACT FROM AUTHOR]

We study the communication efficient secret sharing (CESS) problem. A classical threshold secret sharing scheme encodes a secret into $n$ shares given to n$ parties, such that any set of at least t$ , t n$ . However, Staircase codes may require dividing the secret and the shares into many symbols. We also describe how Staircase codes can be used to construct threshold changeable secret sharing with minimum storage cost, i.e., minimum share size. [ABSTRACT FROM AUTHOR]

Zero correlation zone (ZCZ) sequences are a class of spreading sequences having ideal auto-correlation and cross correlation in a zone around the origin. They have been extensively studied in recent years due to their important applications in quasi-synchronous code division multiple access systems. In this paper, a construction of ZCZ sequence sets is proposed based on perfect nonlinear functions. It generates multiple ZCZ sequence sets with the properties: 1) each sequence is perfect in the sense that its out-of-phase auto-correlation is always zero; 2) each ZCZ sequence set is optimal with respect to the Tang–Fan–Matsufuji bound in which all the sequences are pairwise cyclically distinct; and 3) the maximum inter-set cross correlation of multiple sequence sets achieves the well-known Sarwate bound. [ABSTRACT FROM AUTHOR]

Complexity of sequences plays an important role in pseudorandom sequences and cryptography. In this paper, we present a construction of sequences with high nonlinear complexity from function fields. The main idea is to make use of function fields with many rational places as well as an automorphism of large order. We illustrate our construction through rational function fields and cyclotomic function fields in which there exist some automorphisms of large order. It turns out that we are able to: 1) slightly increase the length of the inversive sequence without losing nonlinear complexity and 2) obtain sequences with much larger nonlinear complexity than random sequences. [ABSTRACT FROM AUTHOR]

The existence of almost perfect nonlinear (APN) permutations operating on an even number of variables was a long-standing open problem, until an example with six variables was exhibited by Dillon et al. in 2009. However it is still unknown whether this example can be generalized to any even number of inputs. In a recent work, Perrin et al. described an infinite family of permutations, named butterflies, operating on $(4k+2)$ variables and with differential uniformity at most 4, which contains the Dillon APN permutation. In this paper, we generalize this family, and we completely solve the two open problems raised by Perrin et al. Indeed we prove that all functions in this larger family have the best known nonlinearity. We also show that this family does not contain any APN permutation besides the Dillon permutation, implying that all other functions have differential uniformity exactly four. [ABSTRACT FROM PUBLISHER]

As a class of optimal combinatorial objects, bent functions have important applications in cryptography, sequence design, and coding theory. Bent idempotents are a subclass of bent functions and of great interest, since they can be stored in less space and allow faster computation of the Walsh-Hadamard transform. The objective of this paper is to present a generic construction of bent functions from known ones. It includes the previous constructions of bent functions by Mesnager and Xu et al. as special cases, and produces new bent functions, which cannot be produced by earlier ones. In particular, it also generates infinite families of bent idempotents over F2^{2m} of any algebraic degree between 2 and $m$ . This together with a recent construction by Su and Tang gives a positive answer to an open problem on bent idempotents proposed by Carlet. In addition, an infinite family of anti-self-dual bent functions is obtained in which the sum of any three distinct functions is again an anti-self-dual bent function in this family. This solves an open problem recently proposed by Mesnager. [ABSTRACT FROM PUBLISHER]

Plateaued functions are very important crypto- graphic functions due to their various desirable cryptographic characteristics. We point out that plateaued functions are more general than bent functions (that is, functions with maximum nonlinearity). Some Boolean plateaued functions have large nonlinearity, which provides protection against fast correlation attacks when they are used as combiners or filters in stream ciphers, and contributes, when they are the component functions of the substitution boxes in block ciphers, to protection against linear cryptanalysis. P-ary plateaued functions have attracted recently some attention in the literature, and many activities on generalized $p$ -ary functions have been carried out. This paper increases our knowledge on plateaued functions in the general context of generalized p$ -ary functions. We first introduce two new versions of plateaued functions, which we shall call generalized plateaued functions and admissible plateaued functions. The generalized plateaued functions extend the standard notion of plateaued p$ -ary functions to those whose outputs are in the ring . Next, we study the generalized plateaued functions and use admissible plateaued functions to characterize the generalized plateaued functions by means of their components. Finally, we provide for the first time two constructions of generalized plateaued functions. In particular, we generalize a known secondary construction of binary generalized bent functions and derive constructions of binary generalized plateaued functions with different amplitudes. [ABSTRACT FROM PUBLISHER]

The nonlinear complexity of a periodic sequence s is the length of the shortest feedback shift register that can generate s, and its value is upper bounded by the least period of s minus 1. In this paper, a recursive approach that generates all periodic sequences with maximum nonlinear complexity is presented, and the total number of such sequences is determined. The randomness properties of these sequences are also examined. [ABSTRACT FROM PUBLISHER]

In the mid 1960s, Rothaus proposed the so-called “most general form” of constructing new bent functions by using three (initial) bent functions whose sum is again bent. In this paper, we utilize a special case of Rothaus construction when two of these three bent functions differ by a suitably chosen characteristic function of an $n/2$ -dimensional subspace. This simplification allows us to treat the induced bent conditions more easily, also implying the possibility to specify the initial functions in the partial spread class and most notably to identify several instances of the so-called non-normal bent functions. Affine inequivalent bent functions within this class are then identified using a suitable selection of initial bent functions within the partial spread class (stemming from the complete Desarguesian spread). It is also shown that when the initial bent functions belong to the class \mathcal {D} , then, under certain conditions, the constructed functions provably do not belong to the completed Maiorana–McFarland class. We conjecture that our method potentially generates an infinite class of non-normal bent functions (all tested ten-variable functions are non-normal but unfortunately they are weakly normal) though there are no efficient computational tools for confirming this. [ABSTRACT FROM AUTHOR]

Both Maximum Distance Separable and Euclidean self-dual codes have theoretical and practical importance and the study of MDS self-dual codes has attracted lots of attention in recent years. In particular, determining the existence of q -ary MDS self-dual codes for various lengths has been investigated extensively. The problem is completely solved for the case where q is even. This paper focuses on the case where q is odd. We construct a few classes of new MDS self-dual codes through generalized Reed–Solomon codes. More precisely, we show that for any given even length n , we have a q and q is sufficiently large (say q\ge 4^{n}\times n^{2}) . Furthermore, we prove that there exists a q -ary MDS self-dual code of length n if q=r^{2} and n$ satisfies one of the three conditions: 1) n\le r$ and n$ is even; 2) q$ is odd and n-1$ is an odd divisor of and $n=2tr$ for any $t\le (r-1)/2$ . [ABSTRACT FROM PUBLISHER]

Non-malleable codes, defined by Dziembowski, Pietrzak, and Wichs (ICS ’10), provide roughly the following guarantee: if a codeword c encoding some message x is tampered to c' = f(c) such that c' \neq c , then the tampered message x' contained in c' reveals no information about x . The non-malleable codes have applications to immunizing cryptosystems against tampering attacks and related-key attacks. One cannot have an efficient non-malleable code that protects against all efficient tampering functions f . However, in this paper we show “the next best thing”: for any polynomial bound s of size | \mathcal F| \leq 2^s , there is an efficient non-malleable code that protects against all f \in \mathcal F . The rate of our codes, defined as the ratio of message to codeword size, approaches 1. Our results are information-theoretic and our main proof technique relies on a careful probabilistic method argument using limited independence. As a result, we get an efficiently samplable family of efficient codes, such that a random member of the family is non-malleable with overwhelming probability. Alternatively, we can view the result as providing an efficient non-malleable code in the “common reference string” model. We also introduce a new notion of non-malleable key derivation, which uses randomness $x$ to derive a secret key $y = h(x)$ in such a way that, even if $x$ is tampered to a different value $x' = f(x)$ , the derived key $y' = h(x')$ does not reveal any information about $y$ . Our results for non-malleable key derivation are analogous to those for non-malleable codes. As a useful tool in our analysis, we rely on the notion of “leakage-resilient storage” of Davì, Dziembowski, and Venturi (SCN ’10), and, as a result of independent interest, we also significantly improve on the parameters of such schemes. [ABSTRACT FROM PUBLISHER]

Multiply constant-weight codes (MCWCs) were introduced recently to improve the reliability of certain physically unclonable function response. In this paper, the bounds of MCWCs and the constructions of optimal MCWCs are studied. First, we derive three different types of upper bounds which improve the Johnson-type bounds given by Chee et al. for some parameters. The asymptotic lower bound of MCWCs is also examined. Then, we obtain the asymptotic existence of two classes of optimal MCWCs, which shows that the Johnson-type bounds for MCWCs with distances 2\sum i=1^{m}wi-2 or $2mw-2w$ are asymptotically exact. Finally, we construct a class of optimal MCWCs with total weight four and distance six by establishing the connection between such MCWCs and a new kind of combinatorial structures. As a consequence, the maximum sizes of MCWCs with total weight less than or equal to four are determined almost completely. [ABSTRACT FROM AUTHOR]

In this paper we extend the notion of locally repairable codes to secret sharing schemes. The main problem that we consider is to find optimal ways to distribute the shares of a secret among a set of storage-nodes (participants) such that the content of each node (share) can be recovered by using the contents of only few other nodes, and at the same time the secret can be reconstructed by only some allowable subsets of nodes. As a special case, an eavesdropper observing some set of specific nodes (such as less than certain number of nodes) does not get any information. In other words, we propose to study a locally repairable distributed storage system that is secure against a passive eavesdropper that can observe some subsets of nodes. We provide a number of results related to such systems, including upper bounds and achievability results on the number of bits that can be securely stored with these constraints. In particular, we provide conditions under which a locally repairable code can be turned into a secret sharing scheme and extend the results of secure repairable storage to cooperative repair and storage on networks. In addition, we consider perfect secret sharing schemes over general access structures under locality constraints and give an example of a perfect secret sharing scheme that can have small locality. Finally, we provide a lower bound on the size of a share compared with the size of the secret that shows how locality affects the sizes of shares in a perfect scheme. [ABSTRACT FROM PUBLISHER]

The generalized Hamming weights (GHWs) of linear codes are fundamental parameters, the knowledge of which is of great interest in many applications. However, to determine the GHWs of linear codes is difficult in general. In this paper, we study the GHWs for a family of reducible cyclic codes and obtain the complete weight hierarchy in several cases. This is achieved by extending the idea of Yang et al. into higher dimension and by employing some interesting combinatorial arguments. It shall be noted that these cyclic codes may have arbitrary number of nonzeros. [ABSTRACT FROM PUBLISHER]

Nonlinearity is one of the most challenging combinatorial property in the domain of Boolean function research. Obtaining nonlinearity greater than the bent concatenation bound for odd number of variables continues to be one of the most sought after combinatorial research problems. The pioneering result in this direction has been discovered by Patterson and Wiedemann in 1983 (IEEE-IT), which considered Boolean functions on 5 \times 3 = 15 variables that are invariant under the actions of the cyclic group {GF(2^{5})}^\ast \,{\cdot }\, {GF(2^{3})}^\ast as well as the group of Frobenius automorphisms. Some of these Boolean functions possess nonlinearity greater than the bent concatenation bound. The next possible option for exploring such functions is on 7 \times 3 = 21$ variables. However, obtaining such functions remained elusive for more than three decades even after substantial efforts as evident in the literature. In this paper, we exploit combinatorial arguments together with heuristic search to demonstrate such functions for the first time. [ABSTRACT FROM AUTHOR]

Non-malleable codes, introduced by Dziembowski et al., encode messages s in a manner, so that tampering the codeword causes the decoder to either output s or a message that is independent of s . While this is an impossible goal to achieve against unrestricted tampering functions, rather surprisingly non-malleable coding becomes possible against every fixed family of tampering functions that is not too large (for instance, when | \mathcal {F}| \leqslant 2^{2^{\vphantom {R^{a}}\alpha n}} for some \alpha <1 , where n is the number of bits in a codeword). In this paper, we study the capacity of non-malleable codes, and establish optimal bounds on the achievable rate as a function of the family size, answering an open problem from Dziembowski et al. Specifically, We prove that for every family \mathcal {F} with | \mathcal {F}| \leqslant 2^{2^{\vphantom {R^{}}\alpha n}} , there exist non-malleable codes against \mathcal F with rate arbitrarily close to 1-\alpha [this is achieved with high probability (w.h.p.) by a randomized construction]. We show the existence of families of size \exp (n^O(1) 2^\alpha n) against which there is no non-malleable code of rate $1-\alpha $ (in fact this is the case w.h.p for a random family of this size). We also show that 1-\alpha $ is the best achievable rate for the family of functions, which are only allowed to tamper the first \alpha n$ bits of the codeword, which is of special interest. As a corollary, this implies that the capacity of non-malleable coding in the split-state model (where the tampering function acts independently but arbitrarily on the two halves of the codeword, a model which has received some attention recently) equals 1/2. We also give an efficient Monte Carlo construction of codes of rate close to 1 with polynomial time encoding and decoding that is non-malleable against any fixed c > 0 of size 2^{n^{c}} , in particular tampering functions with, say, cubic size circuits. [ABSTRACT FROM PUBLISHER]

Let \(m\geq 3\) be an odd integer and \(p\) be an odd prime. In this paper, a number of classes of three-weight cyclic codes \(\mathcal {C}_{(1,e)}\) over \(\mathbb {F}_{p}\) , which have parity-check polynomial \(m_1(x)m_e(x)\) , are presented by examining general conditions on the parameters \(p\) , \(m\) , and \(e\) , where \(m_i(x)\) is the minimal polynomial of \(\pi ^{-i}\) over \(\mathbb {F}_{p}\) for a primitive element \(\pi \) of \(\mathbb {F}_{p^m}\) . Furthermore, for \(p\equiv 3 \pmod {4}\) and a positive integer \(e\) satisfying \((p^k+1)\cdot e\equiv 2 \pmod {p^m-1}\) for some positive integer \(k\) with \(\gcd (m,k)=1\) , the value distributions of the exponential sums \(T(a,b)=\sum \nolimits _{x\in \mathbb {F}_{p^m}}\omega ^{ \text {Tr}(ax+bx^e)}\) and \(S(a,b,c)=\sum \nolimits _{x\in \mathbb {F}_{p^m}}\omega ^{ \text {Tr}(ax+bx^e+cx^s)},\) where \(s=(p^m-1)/2\) , are determined. As an application, the value distribution of \(S(a,b,c)\) is utilized to derive the weight distribution of the cyclic codes \(\mathcal {C}_{(1,e,s)}\) with parity-check polynomial \(m_1(x)m_e(x)m_s(x)\) . In the case of \(p=3\) and even \(e\) satisfying the above condition, the dual of the cyclic code \(\mathcal {C}_{(1,e,s)}\) has optimal minimum distance. [ABSTRACT FROM PUBLISHER]