ISSN:
1930-5346
eISSN:
1930-5338
All Issues
Advances in Mathematics of Communications
February 2011 , Volume 5 , Issue 1
Select all articles
Export/Reference:
2011, 5(1): 1-10
doi: 10.3934/amc.2011.5.1
+[Abstract](3096)
+[PDF](323.1KB)
Abstract:
Elliptic curves over finite fields have applications in public key cryptography. A Koblitz curve is an elliptic curve $E$ over $\mathbb F$2; the group $E(\mathbb F$2n$)$ has convenient features for efficient implementation of elliptic curve cryptography.
Wiener and Zuccherato and Gallant, Lambert and Vanstone showed that one can accelerate the Pollard rho algorithm for the discrete logarithm problem on Koblitz curves. This implies that when using Koblitz curves, one has a lower security per bit than when using general elliptic curves defined over the same field. Hence for a fixed security level, systems using Koblitz curves require slightly more bandwidth.
We present a method to reduce this bandwidth when a normal basis representation for $\mathbb F$2n is used. Our method is appropriate for applications such as Diffie-Hellman key exchange or Elgamal encryption. We show that, with a low probability of failure, our method gives the expected bandwidth for a given security level.
Elliptic curves over finite fields have applications in public key cryptography. A Koblitz curve is an elliptic curve $E$ over $\mathbb F$2; the group $E(\mathbb F$2n$)$ has convenient features for efficient implementation of elliptic curve cryptography.
Wiener and Zuccherato and Gallant, Lambert and Vanstone showed that one can accelerate the Pollard rho algorithm for the discrete logarithm problem on Koblitz curves. This implies that when using Koblitz curves, one has a lower security per bit than when using general elliptic curves defined over the same field. Hence for a fixed security level, systems using Koblitz curves require slightly more bandwidth.
We present a method to reduce this bandwidth when a normal basis representation for $\mathbb F$2n is used. Our method is appropriate for applications such as Diffie-Hellman key exchange or Elgamal encryption. We show that, with a low probability of failure, our method gives the expected bandwidth for a given security level.
2011, 5(1): 11-21
doi: 10.3934/amc.2011.5.11
+[Abstract](3392)
+[PDF](354.2KB)
Abstract:
In this paper, we present a duality construction for multiarcs in projective Hjelmslev geometries over chain rings of nilpotency index 2. We compute the parameters of the resulting arcs and discuss some examples.
In this paper, we present a duality construction for multiarcs in projective Hjelmslev geometries over chain rings of nilpotency index 2. We compute the parameters of the resulting arcs and discuss some examples.
2011, 5(1): 23-36
doi: 10.3934/amc.2011.5.23
+[Abstract](3842)
+[PDF](353.3KB)
Abstract:
We develop a construction method for finding self-dual codes with an automorphism of order $p$ with $c$ independent $p$-cycles. In more detail, we construct a self-dual code with an automorphism of type $p-(c,f+2)$ and length $n+2$ from a self-dual code with an automorphism of type $p-(c,f)$ and length $n$, where an automorphism of type $p-(c, f)$ is that of order $p$ with $c$ independent cycles and $f$ fixed points. Using this construction, we find three new inequivalent extremal self-dual $[54, 27, 10]$ codes with an automorphism of type $7-(7,5)$ and two new inequivalent extremal self-dual $[58, 29, 10]$ codes with an automorphism of of type $7-(8,2)$. We also obtain an extremal self-dual $[40, 20, 8]$ code with an automorphism of type $3-(10, 10)$, which is constructed from an extremal self-dual $[38, 19, 8]$ code of type $3-(10,8)$, and at least 482 inequivalent extremal self-dual $[58,29,10]$ codes with an automorphism of type $3-(18,4)$, which is constructed from an extremal self-dual $[54, 27, 10]$ code of type $3-(18,0);$ we note that the extremality is preserved.
We develop a construction method for finding self-dual codes with an automorphism of order $p$ with $c$ independent $p$-cycles. In more detail, we construct a self-dual code with an automorphism of type $p-(c,f+2)$ and length $n+2$ from a self-dual code with an automorphism of type $p-(c,f)$ and length $n$, where an automorphism of type $p-(c, f)$ is that of order $p$ with $c$ independent cycles and $f$ fixed points. Using this construction, we find three new inequivalent extremal self-dual $[54, 27, 10]$ codes with an automorphism of type $7-(7,5)$ and two new inequivalent extremal self-dual $[58, 29, 10]$ codes with an automorphism of of type $7-(8,2)$. We also obtain an extremal self-dual $[40, 20, 8]$ code with an automorphism of type $3-(10, 10)$, which is constructed from an extremal self-dual $[38, 19, 8]$ code of type $3-(10,8)$, and at least 482 inequivalent extremal self-dual $[58,29,10]$ codes with an automorphism of type $3-(18,4)$, which is constructed from an extremal self-dual $[54, 27, 10]$ code of type $3-(18,0);$ we note that the extremality is preserved.
2011, 5(1): 37-40
doi: 10.3934/amc.2011.5.37
+[Abstract](3246)
+[PDF](222.8KB)
Abstract:
It has been verified that in $PG(4,4)$ the smallest size of complete caps is 20 and that the values from 20 to 41 form the spectrum of possible sizes of complete caps. This result has been obtained by a computer-based proof helped by the non existence of some codes.
It has been verified that in $PG(4,4)$ the smallest size of complete caps is 20 and that the values from 20 to 41 form the spectrum of possible sizes of complete caps. This result has been obtained by a computer-based proof helped by the non existence of some codes.
2011, 5(1): 41-57
doi: 10.3934/amc.2011.5.41
+[Abstract](3840)
+[PDF](390.4KB)
Abstract:
We introduce an additive but not $\mathbb F$4-linear map $S$ from $\mathbb F$4n to $\mathbb F$42n and exhibit some of its interesting structural properties. If $C$ is a linear $[n,k,d]$4-code, then $S(C)$ is an additive $(2n,2$2k,$2d)$4-code. If $C$ is an additive cyclic code then $S(C)$ is an additive quasi-cyclic code of index $2$. Moreover, if $C$ is a module $\theta$-cyclic code, a recently introduced type of code which will be explained below, then $S(C)$ is equivalent to an additive cyclic code if $n$ is odd and to an additive quasi-cyclic code of index $2$ if $n$ is even. Given any $(n,M,d)$4-code $C$, the code $S(C)$ is self-orthogonal under the trace Hermitian inner product. Since the mapping $S$ preserves nestedness, it can be used as a tool in constructing additive asymmetric quantum codes.
We introduce an additive but not $\mathbb F$4-linear map $S$ from $\mathbb F$4n to $\mathbb F$42n and exhibit some of its interesting structural properties. If $C$ is a linear $[n,k,d]$4-code, then $S(C)$ is an additive $(2n,2$2k,$2d)$4-code. If $C$ is an additive cyclic code then $S(C)$ is an additive quasi-cyclic code of index $2$. Moreover, if $C$ is a module $\theta$-cyclic code, a recently introduced type of code which will be explained below, then $S(C)$ is equivalent to an additive cyclic code if $n$ is odd and to an additive quasi-cyclic code of index $2$ if $n$ is even. Given any $(n,M,d)$4-code $C$, the code $S(C)$ is self-orthogonal under the trace Hermitian inner product. Since the mapping $S$ preserves nestedness, it can be used as a tool in constructing additive asymmetric quantum codes.
2011, 5(1): 59-68
doi: 10.3934/amc.2011.5.59
+[Abstract](2945)
+[PDF](334.0KB)
Abstract:
We consider the problem of constructing optimal authentication codes with splitting. New infinite families of such codes are obtained. In particular, we establish the first known infinite family of optimal authentication codes with splitting that are secure against spoofing attacks of order two.
We consider the problem of constructing optimal authentication codes with splitting. New infinite families of such codes are obtained. In particular, we establish the first known infinite family of optimal authentication codes with splitting that are secure against spoofing attacks of order two.
2011, 5(1): 69-86
doi: 10.3934/amc.2011.5.69
+[Abstract](3669)
+[PDF](241.6KB)
Abstract:
The results of the enumeration of Costas arrays of order 28 are presented: all arrays found are accounted for by the Golomb and Welch construction methods, making 28 the first order (larger than 5) for which no sporadic Costas arrays exist. The enumeration was performed on several computer clusters and required the equivalent of 70 years of single CPU time. Furthermore, a classification of Costas arrays in four classes is proposed, and it is conjectured, based on the results of the enumeration combined with further evidence, that two of them eventually become extinct.
The results of the enumeration of Costas arrays of order 28 are presented: all arrays found are accounted for by the Golomb and Welch construction methods, making 28 the first order (larger than 5) for which no sporadic Costas arrays exist. The enumeration was performed on several computer clusters and required the equivalent of 70 years of single CPU time. Furthermore, a classification of Costas arrays in four classes is proposed, and it is conjectured, based on the results of the enumeration combined with further evidence, that two of them eventually become extinct.
2011, 5(1): 87-92
doi: 10.3934/amc.2011.5.87
+[Abstract](3424)
+[PDF](272.1KB)
Abstract:
An Advances in Mathematics of Communications article from 2007 proposes an informal 2-party key establishment along the lines of the classic Diffie-Hellman construction, but using a two-sided matrix semiring action. The article contains no formal security analysis, but a specific parameter choice has been considered. We describe a heuristic attack technique against the suggested instance, which for the published "challenge value" results in a complete session key recovery with only a minor computational effort.
An Advances in Mathematics of Communications article from 2007 proposes an informal 2-party key establishment along the lines of the classic Diffie-Hellman construction, but using a two-sided matrix semiring action. The article contains no formal security analysis, but a specific parameter choice has been considered. We describe a heuristic attack technique against the suggested instance, which for the published "challenge value" results in a complete session key recovery with only a minor computational effort.
2011, 5(1): 93-108
doi: 10.3934/amc.2011.5.93
+[Abstract](3110)
+[PDF](427.9KB)
Abstract:
We examine the $p$-ary codes from incidence matrices of Paley graphs $P(q)$ where $q\equiv 1$(mod $4$) is a prime power, and show that the codes are $[\frac{q(q-1)}{4},q-1,\frac{q-1}{2}]$2 or $[\frac{q(q-1)}{4},q,\frac{q-1}{2}]$p for $p$ odd. By finding PD-sets we show that for $q > 9$ the $p$-ary codes, for any $p$, can be used for permutation decoding for full error-correction. The binary code from the line graph of $P(q)$ is shown to be the same as the binary code from an incidence matrix for $P(q)$.
We examine the $p$-ary codes from incidence matrices of Paley graphs $P(q)$ where $q\equiv 1$(mod $4$) is a prime power, and show that the codes are $[\frac{q(q-1)}{4},q-1,\frac{q-1}{2}]$2 or $[\frac{q(q-1)}{4},q,\frac{q-1}{2}]$p for $p$ odd. By finding PD-sets we show that for $q > 9$ the $p$-ary codes, for any $p$, can be used for permutation decoding for full error-correction. The binary code from the line graph of $P(q)$ is shown to be the same as the binary code from an incidence matrix for $P(q)$.
2011, 5(1): 109-118
doi: 10.3934/amc.2011.5.109
+[Abstract](4380)
+[PDF](234.9KB)
Abstract:
Class invariants are singular values of modular functions which generate the class fields of imaginary quadratic number fields. Their minimal polynomials, called class polynomials, are uniquely determined by a discriminant $-D<0$ and are used in many applications, including the generation of elliptic curves. In all these applications, it is desirable that the size of the polynomials is as small as possible. Among all known class polynomials, Weber polynomials constructed with discriminants $-D \equiv 1$ (mod $8$) have the smallest height and require the least precision for their construction. In this paper, we will show that this fact does not necessarily lead to the most efficient computations, since the congruences modulo $8$ of the discriminants affect the degrees of the polynomials.
Class invariants are singular values of modular functions which generate the class fields of imaginary quadratic number fields. Their minimal polynomials, called class polynomials, are uniquely determined by a discriminant $-D<0$ and are used in many applications, including the generation of elliptic curves. In all these applications, it is desirable that the size of the polynomials is as small as possible. Among all known class polynomials, Weber polynomials constructed with discriminants $-D \equiv 1$ (mod $8$) have the smallest height and require the least precision for their construction. In this paper, we will show that this fact does not necessarily lead to the most efficient computations, since the congruences modulo $8$ of the discriminants affect the degrees of the polynomials.
2011, 5(1): 119-147
doi: 10.3934/amc.2011.5.119
+[Abstract](4929)
+[PDF](566.6KB)
Abstract:
Let $\mathcal A$R,q denote a family of covering codes, in which the covering radius $R$ and the size $q$ of the underlying Galois field are fixed, while the code length tends to infinity. The construction of families with small asymptotic covering densities is a classical problem in the area of Covering Codes.
In this paper, infinite sets of families $\mathcal A$R,q, where $R$ is fixed but $q$ ranges over an infinite set of prime powers are considered, and the dependence on $q$ of the asymptotic covering densities of $\mathcal A$R,q is investigated. It turns out that for the upper limit $\mu$q*(R,$\mathcal A$R,q) of the covering density of $\mathcal A$R,q, the best possibility is $\mu$q*(R,$\mathcal A$R,q)=$O(q)$. The main achievement of the present paper is the construction of optimal infinite sets of families $\mathcal A$R,q, that is, sets of families such that relation $\mu$q*(R,$\mathcal A$R,q)=$O(q)$ holds, for any covering radius $R\geq 2$.
We first showed that for a given $R$, to obtain optimal infinite sets of families it is enough to construct $R$ infinite families $\mathcal A$R,q(0), $\mathcal A$R,q(1), $\ldots$, $\mathcal A$R,q(R-1) such that, for all $u\geq u$0, the family $\mathcal A$R,q($\gamma$) contains codes of codimension $r$u$=Ru + \gamma$ and length $f$q($\gamma$)($r$u) where $f$q($\gamma$)$(r)=O(q$(r-R)/R$)$ and $u$0 is a constant. Then, we were able to construct the necessary families $\mathcal A$R,q($\gamma$) for any covering radius $R\geq 2$, with $q$ ranging over the (infinite) set of $R$-th powers. A result of independent interest is that in each of these families $\mathcal A$R,q($\gamma$), the lower limit of the covering density is bounded from above by a constant independent of $q$.
The key tool in our investigation is the design of new small saturating sets in projective spaces over finite fields, which are used as the starting point for the $q$m-concatenating constructions of covering codes. A new concept of $N$-fold strong blocking set is introduced. As a result of our investigation, many new asymptotic and finite upper bounds on the length function of covering codes and on the smallest sizes of saturating sets, are also obtained. Updated tables for these upper bounds are provided. An analysis and a survey of the known results are presented.
Let $\mathcal A$R,q denote a family of covering codes, in which the covering radius $R$ and the size $q$ of the underlying Galois field are fixed, while the code length tends to infinity. The construction of families with small asymptotic covering densities is a classical problem in the area of Covering Codes.
In this paper, infinite sets of families $\mathcal A$R,q, where $R$ is fixed but $q$ ranges over an infinite set of prime powers are considered, and the dependence on $q$ of the asymptotic covering densities of $\mathcal A$R,q is investigated. It turns out that for the upper limit $\mu$q*(R,$\mathcal A$R,q) of the covering density of $\mathcal A$R,q, the best possibility is $\mu$q*(R,$\mathcal A$R,q)=$O(q)$. The main achievement of the present paper is the construction of optimal infinite sets of families $\mathcal A$R,q, that is, sets of families such that relation $\mu$q*(R,$\mathcal A$R,q)=$O(q)$ holds, for any covering radius $R\geq 2$.
We first showed that for a given $R$, to obtain optimal infinite sets of families it is enough to construct $R$ infinite families $\mathcal A$R,q(0), $\mathcal A$R,q(1), $\ldots$, $\mathcal A$R,q(R-1) such that, for all $u\geq u$0, the family $\mathcal A$R,q($\gamma$) contains codes of codimension $r$u$=Ru + \gamma$ and length $f$q($\gamma$)($r$u) where $f$q($\gamma$)$(r)=O(q$(r-R)/R$)$ and $u$0 is a constant. Then, we were able to construct the necessary families $\mathcal A$R,q($\gamma$) for any covering radius $R\geq 2$, with $q$ ranging over the (infinite) set of $R$-th powers. A result of independent interest is that in each of these families $\mathcal A$R,q($\gamma$), the lower limit of the covering density is bounded from above by a constant independent of $q$.
The key tool in our investigation is the design of new small saturating sets in projective spaces over finite fields, which are used as the starting point for the $q$m-concatenating constructions of covering codes. A new concept of $N$-fold strong blocking set is introduced. As a result of our investigation, many new asymptotic and finite upper bounds on the length function of covering codes and on the smallest sizes of saturating sets, are also obtained. Updated tables for these upper bounds are provided. An analysis and a survey of the known results are presented.
2020
Impact Factor: 0.935
5 Year Impact Factor: 0.976
2020 CiteScore: 1.5
Authors
Editors
Referees
Librarians
Email Alert
Add your name and e-mail address to receive news of forthcoming issues of this journal:
[Back to Top]