American Institute of Mathematical Sciences

The weight distribution \begin{document} $\{ \mathcal{W}_C^{(w)} \} _{w=0} ^n$ \end{document} of a linear code \begin{document} $C \subset {\mathbb F}_q^n$ \end{document} is put in an explicit bijective correspondence with Duursma's reduced polynomial \begin{document} $D_C(t) ∈ {\mathbb Q}[t]$ \end{document} of \begin{document} $C$ \end{document}. We prove that the Riemann Hypothesis Analogue for a linear code \begin{document} $C$ \end{document} requires the formal self-duality of \begin{document} $C$ \end{document}. Duursma's reduced polynomial \begin{document} $D_F(t) ∈ {\mathbb Z}[t]$ \end{document} of the function field \begin{document} $F = {\mathbb F}_q(X)$ \end{document} of a curve \begin{document} $X$ \end{document} of genus \begin{document} $g$ \end{document} over \begin{document} ${\mathbb F}_q$ \end{document} is shown to provide a generating function \begin{document} $\frac{D_F(t)}{(1-t)(1-qt)} = \sum\limits _{i=0} ^{∞} \mathcal{B}_i t^{i}$ \end{document} for the numbers \begin{document} $\mathcal{B}_i$ \end{document} of the effective divisors of degree \begin{document} $i ≥0$ \end{document} of a virtual function field of a curve of genus \begin{document} $g-1$ \end{document} over \begin{document} ${\mathbb F}_q$ \end{document}.

Let \begin{document} $p$ \end{document} be an odd prime, \begin{document} $n≥q3$ \end{document} and \begin{document} $k$ \end{document} positive integers with \begin{document} $e=\gcd(n,k)$ \end{document}. In this paper, a new family \begin{document} $\mathcal{S}$ \end{document} of \begin{document} $p$ \end{document}-ary sequences with period \begin{document} $N=p^n-1$ \end{document} is proposed. The sequences in \begin{document} $\mathcal{S}$ \end{document} are constructed by adding a \begin{document} $p$ \end{document}-ary sequence to its two decimated sequences with different phase shifts. The correlation distribution among sequences in \begin{document} $\mathcal{S}$ \end{document} is completely determined. It is shown that the maximum magnitude of nontrivial correlations of \begin{document} $\mathcal{S}$ \end{document} is upper bounded by \begin{document} $p^e\sqrt{N+1}+1$ \end{document}, and the family size of \begin{document} $\mathcal{S}$ \end{document} is \begin{document} $N^2$ \end{document}. Our sequence family has a large family size and low correlation.

For two odd integers \begin{document} $l,k$ \end{document} with \begin{document} $0<l<k$ \end{document} and \begin{document} $\gcd(l,k)=1$ \end{document}, let \begin{document} $m=2k$ \end{document} and \begin{document} $d=\frac{2^{lk}+1}{2^l+1}$ \end{document}. In this paper, we study the cross-correlation between a binary \begin{document} $m$ \end{document}-sequence \begin{document} $(s_t)$ \end{document} of length \begin{document} $2^m-1$ \end{document} and its \begin{document} $d$ \end{document}-decimated sequences \begin{document} $(s_{dt+u}), 0≤q u<\frac{2^k+1}{3}.$ \end{document} It is shown that the maximum magnitude of cross-correlation values is \begin{document} $2^{\frac{m}{2}+1}+1.$ \end{document} Moreover, a new sequence family with maximum correlation magnitude \begin{document} $2^{\frac{m}{2}+1}+1$ \end{document} and family size \begin{document} $2^{\frac{m}{2}}$ \end{document} is proposed.

Some families of constant dimension codes arising from Riemann-Roch spaces associated with particular divisors of a curve \begin{document}$\mathcal{X}$\end{document} are constructed. These families are generalizations of the one constructed by Hansen.

In this work, we introduce an active attack on a Group Key Exchange protocol by Burmester and Desmedt. The attacker obtains a copy of the shared key, which is created in a collaborative manner with the legal users in a communication group.

We consider a variation of Construction A of lattices from linear codes based on two classes of number fields, totally real and CM Galois number fields. We propose a generic construction with explicit generator and Gram matrices, then focus on modular and unimodular lattices, obtained in the particular cases of totally real, respectively, imaginary, quadratic fields. Our motivation comes from coding theory, thus some relevant properties of modular lattices, such as minimal norm, theta series, kissing number and secrecy gain are analyzed. Interesting lattices are exhibited.

In this note, we study the classification of \begin{document} $\mathbb{Z}_4$ \end{document}-codes. For some special cases \begin{document} $(k_1,k_2)$ \end{document}, by hand, we give a classification of \begin{document} $\mathbb{Z}_4$ \end{document}-codes of length \begin{document} $n$ \end{document} and type \begin{document} $4^{k_1}2^{k_2}$ \end{document} satisfying a certain condition. Our exhaustive computer search completes the classification of \begin{document} $\mathbb{Z}_4$ \end{document}-codes of lengths up to \begin{document} $7$ \end{document}.

In this paper we study subspace codes with constant intersection dimension (SCIDs). We investigate the largest possible dimension spanned by such a code that can yield non-sunflower codes, and classify the examples attaining equality in that bound as one of two infinite families. We also construct a new infinite family of primitive SCIDs.

In this note, we investigate the performance of optimal double circulant even codes which are not self-dual, as measured by the decoding error probability in bounded distance decoding. To achieve this, we classify the optimal double circulant even codes that are not self-dual which have the smallest weight distribution for lengths up to 72. We also give some restrictions on the weight distributions of (extremal) self-dual [54, 27, 10] codes with shadows of minimum weight 3. Finally, we consider the performance of extremal self-dual codes of lengths 88 and 112.

In this article we count the number of $[n, k]$ generalized Reed-Solomon (GRS) codes, including the codes coming from a non-degenerate conic plus nucleus. We compare our results with known formulae for the number of $[n, 3]$ MDS codes with $n=6, 7, 8, 9$.

The purpose of this paper is to study the structure of quadratic residue codes over the ring \begin{document} $R=\mathbb{F}_{p^r}+u_1\mathbb{F}_{p^r}+u_2 \mathbb{F}_{p^r}+...+u_t \mathbb{F}_{p^r}$ \end{document}, where \begin{document} $r, t ≥ 1$ \end{document} and \begin{document} $p$ \end{document} is a prime number. First, we survey known results on quadratic residue codes over the field \begin{document} $\mathbb{F}_{p^r}$ \end{document} and give general properties with quadratic residue codes over \begin{document} $R$ \end{document}. We introduce the Gray map from \begin{document} $R$ \end{document} to \begin{document} $\mathbb{F}^{t+1}_{p^r}$ \end{document} and study more details about the quadratic residue codes over the ring \begin{document} $R$ \end{document} for \begin{document} $p=2, 3$ \end{document}. Finally, we obtain a number of Hermitian self-dual codes over \begin{document} $R$ \end{document} in the following two cases, where \begin{document} $t$ \end{document} is an odd number; the first case, when \begin{document} $p=2$ \end{document} and \begin{document} $r$ \end{document} is an even number or \begin{document} $r=1$ \end{document}, the second case, when \begin{document} $p=3$ \end{document} and \begin{document} $r$ \end{document} is an even number.

In Crypto 1996, the Hidden Number Problem was introduced by Boneh and Venkatesan. Howgrave-Graham, Nguyen and Shparlinski (Mathematics of Computation 2003) generalized this problem and called it Hidden Number Problem with Hidden Multiplier (HNPHM). It has application in security analysis of timed-release crypto. They proposed a polynomial time algorithm to solve HNPHM. They showed that one can solve it if absolute error is less than \begin{document} $m^{0.20}$ \end{document} for some positive integer \begin{document} $m$ \end{document}. They improved this bound up to \begin{document} $m^{0.25}$ \end{document} heuristically. It was also proved that one can not solve HNPHM if error is larger than \begin{document} $m^{0.5}$ \end{document}. In this paper, we show that one can solve HNPHM in polynomial time heuristically if error is bounded by \begin{document} $m^{0.5}$ \end{document}.

We consider discrete memoryless channels with input alphabet size \begin{document} $n$ \end{document} and output alphabet size \begin{document} $m$ \end{document}, where \begin{document} $m=\left\lceil{γ n}\right\rceil$ \end{document} for some constant \begin{document} $γ>0$ \end{document}. The channel transition matrix consists of entries that, before being normalized, are independent and identically distributed nonnegative random variables \begin{document} $V$ \end{document} and such that \begin{document} $\mathbb{E}{(V \log V)^2}<∞$ \end{document}. We prove that in the limit as \begin{document} $n{\to }∞$ \end{document} the capacity of such a channel converges to \begin{document} $\text{Ent}(V) / \mathbb{E}[V]$ \end{document} almost surely and in \begin{document} $\text{L}^{2}$ \end{document}, where \begin{document} $\text{Ent}(V):= \mathbb{E}[{V\log V}]-\mathbb{E}[{V}]\log \mathbb{E}[{V}]$ \end{document} denotes the entropy of \begin{document} $V$ \end{document}. We further show that, under slightly different model assumptions, the capacity of these random channels converges to this asymptotic value exponentially in \begin{document} $n$ \end{document}. Finally, we present an application in the context of Bayesian optimal experiment design.

In a first part of this paper, we investigate those Boolean functions satisfying two apparently related, but in fact distinct conditions concerning the algebraic degree:

1. we study those Boolean functions \begin{document} $f$ \end{document} whose restrictions to all affine hyperplanes have the same algebraic degree (equal to \begin{document} $deg(f)$ \end{document}, the algebraic degree of \begin{document} $f$ \end{document}),

2. we study those functions whose derivatives \begin{document} $D_af(x)=f(x)+ f(x+a)$ \end{document}, \begin{document} $a≠ 0$ \end{document}, have all the same (optimal) algebraic degree \begin{document} $deg(f)-1$ \end{document}.

For determining to which extent these two questions are related, we find three classes of Boolean functions: the first class satisfies both conditions, the second class satisfies the first condition but not the second and the third class satisfies the second condition but not the first. We also give for any fixed positive integer \begin{document} $k$ \end{document} and for all integers \begin{document} $n$ \end{document}, \begin{document} $p$ \end{document}, \begin{document} $s$ \end{document} such that \begin{document} $p≥q k+1$ \end{document}, \begin{document} $s≥q k+1$ \end{document} and \begin{document} $n≥q ps$ \end{document}, a class (denoted by \begin{document} $C_{n,p,s}$ \end{document}) of functions whose restrictions to all \begin{document} $k$ \end{document}-codimensional affine subspaces of \begin{document} ${\Bbb F}_2^n$ \end{document} have the same algebraic degree as the function.

In a second part of the paper, we introduce the notion of second-order-bent function, whose second order derivatives \begin{document} $D_aD_bf(x)=f(x)+f(x+a)+f(x+b)+f(x+a+b)$ \end{document}, \begin{document} $a≠ 0, b≠ 0, a≠ b$ \end{document}, are all balanced. We exhibit an example in 3 variables and we prove that second-order-bent functions cannot exist if \begin{document} $n$ \end{document} is not congruent with 3 mod 4. We characterize second-order-bent functions by the Walsh transform, state some of their properties and prove the non existence of such functions for algebraic degree 3 when \begin{document} $n>3$ \end{document}. We leave open the question whether second-order-bent functions can exist for \begin{document} $n$ \end{document} larger than \begin{document} $3$ \end{document}.