Vectorial Resilient PC（l） of Order k Boolean Functions from AG-Codes

Propagation criteria and resiliency of vectorial Boolean functions are important for cryptographic purpose (see [1–4, 7, 8, 10, 11, 16]). Kurosawa, Stoh [8] and Carlet [1] gave a construction of Boolean functions satisfying PC(l) of order k from binary linear or nonlinear codes. In this paper, the algebraic-geometric codes over GF(2m) are used to modify the Carlet and Kurosawa-Satoh’s construction for giving vectorial resilient Boolean functions satisfying PC(l) of order k criterion. This new construction is compared with previously known results.     

Highly Nonlinear Resilient Functions Through Disjoint Codes in Projective Spaces

Functions which map n-bits to m-bits are important cryptographic sub-primitives in the design of additive stream ciphers. We construct highly nonlinear t-resilient such functions ((n, m, t) functions) by using a class of binary disjoint codes, a construction which was introduced in IEEE Trans. Inform. Theory, Vol. IT-49 (2) (2003). Our main contribution concerns the generation of suitable sets of such disjoint codes. We propose a deterministic method for finding disjoint codes of length ν m by considering the points of PG ). We then obtain some lower bounds on the number of disjoint codes, by fixing some parameters. Through these sets, we deduce in certain cases the existence of resilient functions with very high nonlinearity values. We show how, thanks to our method, the degree and the differential properties of (n, m, t) functions can be improved.Communicated by: J.D. Key     

New degree bounds for polynomial threshold functions

A real multivariate polynomial p(x ₁, …, x _n ) is said to sign-represent a Boolean function f: {0,1} ⁿ →{−1,1} if the sign of p(x) equals f(x) for all inputs x∈{0,1} ⁿ . We give new upper and lower bounds on the degree of polynomials which sign-represent Boolean functions. Our upper bounds for Boolean formulas yield the first known subexponential time learning algorithms for formulas of superconstant depth. Our lower bounds for constant-depth circuits and intersections of halfspaces are the first new degree lower bounds since 1968, improving results of Minsky and Papert. The lower bounds are proved constructively; we give explicit dual solutions to the necessary linear programs.     

Linear codes from simplicial complexes

In this article we introduce a method of constructing binary linear codes and computing their weights by means of Boolean functions arising from mathematical objects called simplicial complexes. Inspired by Adamaszek (Am Math Mon 122:367–370, 2015) we introduce n-variable generating functions associated with simplicial complexes and derive explicit formulae. Applying the construction (Carlet in Finite Field Appl 13:121–135, 2007; Wadayama in Des Codes Cryptogr 23:23–33, 2001) of binary linear codes to Boolean functions arising from simplicial complexes, we obtain a class of optimal linear codes and a class of minimal linear codes.     

On binary linear <Emphasis Type="Italic">r</Emphasis>-identifying codes

A subspace C of the binary Hamming space F ⁿ of length n is called a linear r-identifying code if for all vectors of F ⁿ the intersections of C and closed r-radius neighbourhoods are nonempty and different. In this paper, we give lower bounds for such linear codes. For radius r =  2, we give some general constructions. We give many (optimal) constructions which were found by a computer search. New constructions improve some previously known upper bounds for r-identifying codes in the case where linearity is not assumed.     

A continuous approach to inductive inference

In this paper we describe an interior point mathematical programming approach to inductive inference. We list several versions of this problem and study in detail the formulation based on hidden Boolean logic. We consider the problem of identifying a hidden Boolean function:{0, 1} ⁿ {0, 1} using outputs obtained by applying a limited number of random inputs to the hidden function. Given this input—output sample, we give a method to synthesize a Boolean function that describes the sample. We pose the Boolean Function Synthesis Problem as a particular type of Satisfiability Problem. The Satisfiability Problem is translated into an integer programming feasibility problem, that is solved with an interior point algorithm for integer programming. A similar integer programming implementation has been used in a previous study to solve randomly generated instances of the Satisfiability Problem. In this paper we introduce a new variant of this algorithm, where the Riemannian metric used for defining the search region is dynamically modified. Computational results on 8-, 16- and 32-input, 1-output functions are presented. Our implementation successfully identified the majority of hidden functions in the experiment.     

Upper Bounds on the Dual Distance of BCH(255, k)

To obtain upper bounds on the distance of a binary linear code, many probabilistic algorithms have been proposed. The author presents a general variation to these algorithms, specific for cyclic codes, which is shown to be an improvement. As an example, the author optimizes Brouwer's algorithm to find the best upper bounds on the dual distance of BCH[255,k,d].     

Binary linear codes from vectorial boolean functions and their weight distribution

Binary linear codes with good parameters have important applications in secret sharing schemes, authentication codes, association schemes, and consumer electronics and communications. In this paper, we construct several classes of binary linear codes from vectorial Boolean functions and determine their parameters, by further studying a generic construction developed by Ding et al. recently. First, by employing perfect nonlinear functions and almost bent functions, we obtain several classes of six-weight linear codes which contain the all-one codeword, and determine their weight distribution. Second, we investigate a subcode of any linear code mentioned above and consider its parameters. When the vectorial Boolean function is a perfect nonlinear function or a Gold function in odd dimension, we can completely determine the weight distribution of this subcode. Besides, our linear codes have larger dimensions than the ones by Ding et al.’s generic construction.     

Constructions and bounds on linear error-block codes

We obtain new bounds on the parameters and we give new constructions of linear error-block codes. We obtain a Gilbert–Varshamov type construction. Using our bounds and constructions we obtain some infinite families of optimal linear error-block codes over . We also study the asymptotic of linear error-block codes. We define the real valued function α _q,m,a (δ), which is an analog of the important real valued function α _q (δ) in the asymptotic theory of classical linear error-correcting codes. We obtain both Gilbert–Varshamov and algebraic geometry type lower bounds on α _q,m,a (δ). We compare these lower bounds in graphs.      

Bounds for the Multicovering Radii of Reed-Muller Codes with Applications to Stream Ciphers

The multicovering radii of a code are recentgeneralizations of the covering radius of a code. For positivem, the m-covering radius of C is the leastradius t such that everym-tuple of vectors is contained in at least one ball of radiust centered at some codeword. In this paper upper bounds arefound for the multicovering radii of first order Reed-Muller codes. These bounds generalize the well-known Norse bounds for the classicalcovering radii of first order Reed-Muller codes. They are exactin some cases. These bounds are then used to prove the existence of secure families of keystreams against a general class of cryptanalytic attacks. This solves the open question that gave rise to the study ofmulticovering radii of codes.     

Optimal doubly constant weight codes

A doubly constant weight code is a binary code of length n₁ + n₂, with constant weight w₁ + w₂, such that the weight of a codeword in the first n₁ coordinates is w₁. Such codes have applications in obtaining bounds on the sizes of constant weight codes with given minimum distance. Lower and upper bounds on the sizes of such codes are derived. In particular, we show tight connections between optimal codes and some known designs such as Howell designs, Kirkman squares, orthogonal arrays, Steiner systems, and large sets of Steiner systems. These optimal codes are natural generalization of Steiner systems and they are also called doubly Steiner systems. © 2007 Wiley Periodicals, Inc. J Combin Designs 16: 137–151, 2008     

On Perfect Ternary Constant Weight Codes

We consider the space of ternary words of length n and fixed weight w with the usual Hamming distance. A sequence of perfect single error correcting codes in this space is constructed. We prove the nonexistence of such codes with other parameters than those of the sequence.     

Improved Bounds for Ternary Linear Codes of Dimension 8 Using Tabu Search

In this paper, new codes of dimension 8 are presented which give improved bounds on the maximum possible minimum distance of ternary linear codes. These codes belong to the class of quasi-twisted (QT) codes, and have been constructed using a stochastic optimization algorithm, tabu search. Twenty three codes are given which improve or establish the bounds for ternary codes. In addition, a table of upper and lower bounds for d ₃(n, 8) is presented for n 200.     

Constructing Covering Codes with Given Automorphisms

Let K(n,r) denote the minimum cardinality of a binary covering code of length n and covering radius r. Constructions of covering codes give upper bounds on K(n,r). It is here shown how computer searches for covering codes can be sped up by requiring that the code has a given (not necessarily full) automorphism group. Tabu search is used to find orbits of words that lead to a covering. In particular, a code D found which proves K(13,1) 704, a new record. A direct construction of D given, and its full automorphism group is shown to be the general linear group GL(3,3). It is proved that D is a perfect dominating set (each word not in D is covered by exactly one word in D) and is a counterexample to the recent Uniformity Conjecture of Weichsel.     

An Alternative Way to Generalize the Pentagon

We introduce the concept of a pentagonal geometry as a generalization of the pentagon and the Desargues configuration, in the same vein that the generalized polygons share the fundamental properties of ordinary polygons. In short, a pentagonal geometry is a regular partial linear space in which for all points x, the points not collinear with the point x, form a line. We compute bounds on their parameters, give some constructions, obtain some nonexistence results for seemingly feasible parameters and suggest a cryptographic application related to identifying codes of partial linear spaces.     

Sets of disjoint snakes based on a Reed-Muller code and covering the hypercube

A snake-in-the-box code (or snake) of word length n is a simple circuit in an n-dimensional cube Q _n , with the additional property that any two non-neighboring words in the circuit differ in at least two positions. To construct such snakes a straightforward, non-recursive method is developed based on special linear codes with minimum distance 4. An extension of this method is used for the construction of covers of Q _n consisting of 2 ^m-1 vertex-disjoint snakes, for 2 ^m-1 < n ≤ 2 ^m . These covers turn out to have a symmetry group of order 2 ^m .      

On Some Special Classes of Sequential Dynamical Systems

Sequential Dynamical Systems (SDSs) are mathematical models for analyzing simulation systems. We investigate phase space properties of some special classes of SDSs obtained by restricting the local transition functions used at the nodes. We show that any SDS over the Boolean domain with symmetric Boolean local transition functions can be efficiently simulated by another SDS which uses only simple threshold and simple inverted threshold functions, where the same threshold value is used at each node and the underlying graph is d-regular for some integer d. We establish tight or nearly tight upper and lower bounds on the number of steps needed for SDSs over the Boolean domain with 1-, 2- or 3-threshold functions at each of the nodes to reach a fixed point. When the domain is a unitary semiring and each node computes a linear combination of its inputs, we present a polynomial time algorithm to determine whether such an SDS reaches a fixed point. We also show (through an explicit construction) that there are Boolean SDSs with the NOR function at each node such that their phase spaces contain directed cycles whose length is exponential in the number of nodes of the underlying graph of the SDS.AMS Subject Classification: 68Q10, 68Q17, 68Q80.     

Binary linear codes with few weights from Boolean functions

Boolean functions have very nice applications in coding theory and cryptography. In coding theory, Boolean functions have been used to construct linear codes in different ways. The objective of this paper is to construct binary linear codes with few weights using the defining-set approach. The defining sets of the codes presented in this paper are defined by some special Boolean functions and some additional restrictions. First, two families of binary linear codes with at most three or four weights from Boolean functions with at most three Walsh transform values are constructed and the parameters of their duals are also determined. Then several classes of binary linear codes with explicit weight enumerators are produced. Some of the binary linear codes are optimal or almost optimal according to the tables of best codes known maintained at http://www.codetables.de, and the duals of some of them are distance-optimal with respect to the sphere packing bound.

     

Bounds for Covering Codes over Large Alphabets

Let K_q(n,R) denote the minimum number of codewords in any q-ary code of length n and covering radius R. We collect lower and upper bounds for K_q(n,R) where 6 ≤ q ≤ 21 and R ≤ 3. For q ≤ 10, we consider lengths n ≤ 10, and for q ≥ 11, we consider n ≤ 8. This extends earlier results, which have been tabulated for 2 ≤ q ≤ 5. We survey known bounds and obtain some new results as well, also for s-surjective codes, which are closely related to covering codes and utilized in some of the constructions.AMS Classification: 94B75, 94B25, 94B65Gerzson Kéri - Supported in part by the Hungarian National Research Fund, Grant No. OTKA-T029572.Patric R. J. Östergård - Supported in part by the Academy of Finland, Grants No. 100500 and No. 202315.     

Linear codes from vectorial Boolean power functions

In this paper, three classes of binary linear codes with few weights are proposed from vectorial Boolean power functions, and their weight distributions are completely determined by solving certain equations over finite fields. In particular, a class of simplex codes and a class of first-order Reed-Muller codes can be obtained from our construction by taking the identity map, whose dual codes are Hamming codes and extended Hamming codes, respectively.