American Institute of Mathematical Sciences

The concept of parity check matrices of linear binary codes has been extended by Heden [10] to parity check systems of nonlinear binary codes. In the present paper we extend this concept to parity check systems of nonlinear codes over finite commutative Frobenius rings. Using parity check systems, results on how to get some fundamental properties of the codes are given. Moreover, parity check systems and its connection to characters is investigated and a MacWilliams type theorem on the distance distribution is given.

In this paper, a new constructive approach of determining the first descent point distribution for the \begin{document}$k$\end{document}-error linear complexity of \begin{document}$2^n$\end{document}-periodic binary sequences is developed using the sieve method and Games-Chan algorithm. First, the linear complexity for the sum of two sequences with the same linear complexity and minimum Hamming weight is completely characterized and this paves the way for the investigation of the \begin{document}$k$\end{document}-error linear complexity. Second we derive a full representation of the first descent point spectrum for the \begin{document}$k$\end{document}-error linear complexity. Finally, we obtain the complete counting functions on the number of \begin{document}$2^n$\end{document}-periodic binary sequences with given \begin{document}$2^m$\end{document}-error linear complexity and linear complexity \begin{document}$2^n-(2^{i_1}+2^{i_2}+···+2^{i_m})$\end{document}, where \begin{document}$0≤ i_1<i_2<···<i_m<n. $\end{document} In summary, we depict a full picture on the first descent point of the \begin{document}$k$\end{document}-error linear complexity for \begin{document}$2^n$\end{document}-periodic binary sequences and this will help us construct some sequences with requirements on linear complexity and \begin{document}$k$\end{document}-error complexity.

In this paper, a new class of integer-valued Alexis sequences with length N = 2 (mod 4) is proposed and constructed by using integer-valued almost-perfect sequences obtained from three integer-valued elementary sequences. Compared with binary Alexis sequences, the proposed integer-valued Alexis sequences have a larger zero correlation zone (ZCZ). In addition, the maximal energy efficiency of the proposed sequences is investigated.

The negation map can be used to speed up the computation of elliptic curve discrete logarithms using either the baby-step giant-step algorithm (BSGS) or Pollard rho. Montgomery's simultaneous modular inversion can also be used to speed up Pollard rho when running many walks in parallel. We generalize these ideas and exploit the fact that for any two elliptic curve points X and Y, we can efficiently get X-Y when we compute X+Y. We apply these ideas to speed up the baby-step giant-step algorithm. Compared to the previous methods, the new methods can achieve a significant speedup for computing elliptic curve discrete logarithms in small groups or small intervals.

Another contribution of our paper is to give an analysis of the average-case running time of Bernstein and Lange's "grumpy giants and a baby" algorithm, and also to consider this algorithm in the case of groups with efficient inversion.

Our conclusion is that, in the fully-optimised context, both the interleaved BSGS and grumpy-giants algorithms have superior average-case running time compared with Pollard rho. Furthermore, for the discrete logarithm problem in an interval, the interleaved BSGS algorithm is considerably faster than the Pollard kangaroo or Gaudry-Schost methods.

Let \begin{document}$\Bbb F_q$\end{document} be a finite field with \begin{document}$q$\end{document} elements. Suppose that \begin{document}$a, λ∈ \Bbb F_q^*$\end{document}, \begin{document}$a^n=λ$\end{document} with \begin{document}$n|(q-1)$\end{document}. In this paper, we determine the weight distribution of a class of \begin{document}$λ$\end{document}-constacyclic codes of length \begin{document}$nm$\end{document} with the parity check polynomial \begin{document}$h(x)=(x^m-aξ^{st})(x^m-aξ^{s(t+1)})...(x^m-aξ^{s(t+r-1)})$\end{document} and \begin{document}$n>(r-1)m$\end{document}, where \begin{document}$s,t, r$\end{document} are positive integers and \begin{document}$ξ∈ \Bbb F_q$\end{document} is a primitive n-th root of unity. Moreover, we give the weight distributions of \begin{document}$λ$\end{document}-constacyclic codes of length \begin{document}$nm$\end{document} explicitly in several cases: (1) \begin{document}$r=1$\end{document}, \begin{document}$n>1$\end{document}; (2) \begin{document}$r=2$\end{document}, \begin{document}$m=2$\end{document} and \begin{document}$n>2$\end{document}; (3) \begin{document}$r=2$\end{document}, \begin{document}$m=3$\end{document} and \begin{document}$n>3$\end{document}; (4) \begin{document}$r=3$\end{document}, \begin{document}$m=2$\end{document} and \begin{document}$n>4$\end{document}.

In this paper we focus on protocols for private set intersection (PSI), through which two parties, each holding a set of inputs drawn from a ground set, jointly compute the intersection of their sets. Ideally, no further information than which elements are actually shared is compromised to the other party, yet the input set sizes are often considered as admissible leakage.

In the unconditional setting we evidence that PSI is impossible to realize and that unconditionally secure size-hiding PSI is possible assuming a set-up authority is present in an set up phase. In the computational setting we give a generic construction using smooth projective hash functions for languages derived from perfectly-binding commitments. Further, we give two size-hiding constructions: the first one is theoretical and evidences the equivalence between PSI, oblivious transfer and the secure computation of the AND function. The second one is a twist on the oblivious polynomial evaluation construction of Freedman et al. from EUROCRYPT 2004. We further sketch a generalization of the latter using algebraic-geometric techniques. Finally, assuming again there is a set-up authority (yet not necessarily trusted) we present very simple and efficient constructions that only hide the size of the client's set.

Coset constructions of q-ary Reed-Muller codes can be used to store secrets on a distributed storage system in such a way that only parties with access to a large part of the system can obtain information while still allowing for local error-correction. In this paper we determine the relative generalized Hamming weights of these codes which can be translated into a detailed description of the information leakage [2,21,18,9]

It is well-known that maximum rank distance (MRD) codes can be constructed as generalized Gabidulin codes. However, it was unknown until recently whether other constructions of linear MRD codes exist. In this paper, we derive a new criterion for linear MRD codes as well as an algebraic criterion for testing whether a given linear MRD code is a generalized Gabidulin code. We then use the criteria to construct examples of linear MRD codes which are not generalized Gabidulin codes.

The necessary and sufficient conditions for a class of functions \begin{document}$f:\mathbb{Z}_2^n \to \mathbb{Z}_q$\end{document}, where \begin{document}$q ≥q 2$\end{document} is an even positive integer, have been recently identified for \begin{document}$q=4$\end{document} and \begin{document}$q=8$\end{document}. In this article we give an alternative characterization of the generalized Walsh-Hadamard transform in terms of the Walsh spectra of the component Boolean functions of \begin{document}$f$\end{document}, which then allows us to derive sufficient conditions that \begin{document}$f$\end{document} is generalized bent for any even \begin{document}$q$\end{document}. The case when \begin{document}$q$\end{document} is not a power of two, which has not been addressed previously, is treated separately and a suitable representation in terms of the component functions is employed. Consequently, the derived results lead to generic construction methods of this class of functions. The main remaining task, which is not answered in this article, is whether the sufficient conditions are also necessary. There are some indications that this might be true which is also formally confirmed for generalized bent functions that belong to the class of generalized Maiorana-McFarland functions (GMMF), but still we were unable to completely specify (in terms of necessity) gbent conditions.

For an acyclic directed network with multiple pairs of sources and sinks and a set of Menger's paths connecting each pair of source and sink, it is known that the number of mergings among these Menger's paths is closely related to network encoding complexity. In this paper, we focus on networks with two pairs of sources and sinks and we derive bounds on and exact values of two functions relevant to encoding complexity for such networks.

Constacyclic and quasi-twisted Hermitian self-dual codes over finite fields are studied. An alternative algorithm for factorizing \begin{document}$x^n-\lambda $\end{document} over \begin{document}${\mathbb{F}_{{q^2}}}$\end{document} is given, where \begin{document}$λ$\end{document} is a unit in \begin{document}${\mathbb{F}_{{q^2}}}$\end{document}. Based on this factorization, the dimensions of the Hermitian hulls of \begin{document}$\lambda $\end{document}-constacyclic codes of length \begin{document}$n$\end{document} over \begin{document}${\mathbb{F}_{{q^2}}}$\end{document} are determined. The characterization and enumeration of constacyclic Hermitian self-dual (resp., complementary dual) codes of length \begin{document}$n$\end{document} over \begin{document}${\mathbb{F}_{{q^2}}}$\end{document} are given through their Hermitian hulls. Subsequently, a new family of MDS constacyclic Hermitian self-dual codes over \begin{document}${\mathbb{F}_{{q^2}}}$\end{document} is introduced.

As a generalization of constacyclic codes, quasi-twisted Hermitian self-dual codes are studied. Using the factorization of \begin{document}$x^n-\lambda $\end{document} and the Chinese Remainder Theorem, quasi-twisted codes can be viewed as a product of linear codes of shorter length over some extension fields of \begin{document}${\mathbb{F}_{{q^2}}}$\end{document}. Necessary and sufficient conditions for quasi-twisted codes to be Hermitian self-dual are given. The enumeration of such self-dual codes is determined as well.

Let \begin{document}$S$\end{document} be a unital ring, \begin{document}$S[t;\sigma,\delta]$\end{document} a skew polynomial ring where \begin{document}$\sigma$\end{document} is an injective endomorphism and \begin{document}$\delta$\end{document} a left \begin{document}$\sigma$\end{document}-derivation, and suppose \begin{document}$f\in S[t;\sigma,\delta]$\end{document} has degree \begin{document}$m$\end{document} and an invertible leading coefficient. Using right division by \begin{document}$f$\end{document} to define the multiplication, we obtain unital nonassociative algebras \begin{document}$S_f$\end{document} on the set of skew polynomials in \begin{document}$S[t;\sigma,\delta]$\end{document} of degree less than \begin{document}$m$\end{document}. We study the structure of these algebras.

When \begin{document}$S$\end{document} is a Galois ring and \begin{document}$f$\end{document} base irreducible, these algebras yield families of finite unital nonassociative rings \begin{document}$A$\end{document}, whose set of (left or right) zero divisors has the form \begin{document}$pA$\end{document} for some prime \begin{document}$p$\end{document}.

For reducible \begin{document}$f$\end{document}, the \begin{document}$S_f$\end{document} can be employed both to design linear \begin{document}$(f,\sigma,\delta)$\end{document}-codes over unital rings and to study their behaviour.

Using a method for constructing binary self-dual codes having an automorphism of odd prime order \begin{document}$p$\end{document} we classify, up to equivalence, all singly-even self-dual \begin{document}$[78,39,14]$\end{document}, \begin{document}$[80,40,14]$\end{document}, \begin{document}$[82,41,14],$\end{document} and \begin{document}$[84,42,14]$\end{document} codes as well as all doubly-even \begin{document}$[80,40,16]$\end{document} codes for \begin{document}$p=13$\end{document}. The results show that there are exactly 1592 inequivalent binary self-dual \begin{document}$[78,39,14]$\end{document} codes with an automorphism of type \begin{document}$13-(6,0)$\end{document} and we found 6 new values of the parameter in the weight function thus increasing more than twice the number of known values. As for binary \begin{document}$[80,40]$\end{document} self-dual codes with an automorphism of type \begin{document}$13-(6,2)$\end{document} there are 162696 singly-even self-dual codes with minimum distance 14 and 195 doubly-even such codes with minimum distance 16. We also construct many new codes of lengths 82 and 84 with minimum distance 14. Most of the constructed codes for all lengths have weight enumerators for which the existence was not known before.