All Issues

Volume 11, 2017

Volume 10, 2016

Volume 9, 2015

Volume 8, 2014

Volume 7, 2013

Volume 6, 2012

Volume 5, 2011

Volume 4, 2010

Volume 3, 2009

Volume 2, 2008

Volume 1, 2007

Advances in Mathematics of Communications

2010 , Volume 4 , Issue 4

Special issue dedicated to Jan Boman
on the occasion of his 75th birthday

Select all articles


On cycle-free lattices with high rate label codes
Amin Sakzad and  Mohammad-Reza Sadeghi
2010, 4(4): 441-452 doi: 10.3934/amc.2010.4.441 +[Abstract](37) +[PDF](248.7KB)
Etzion et al. have shown that high rate codes based on cycle-free Tanner graphs have minimum distance at most $2$. This result was extended by Sadeghi et al. to a small class of lattices based on Construction $D'$ only. In this paper, we prove a key theorem which relates the minimum distance of every lattice to the minimum distance of its label code. Then, using this powerful tool along with some new bounds on minimum distance of cycle-free group codes, we generalize those results to a large class of lattices here called RPS and PFP lattices. More importantly, we show that this class of cycle-free lattices are not so good in the view of coding gain.
On the generic construction of identity-based signatures with additional properties
David Galindo , Javier Herranz and  Eike Kiltz
2010, 4(4): 453-483 doi: 10.3934/amc.2010.4.453 +[Abstract](47) +[PDF](448.7KB)
It has been stated / demonstrated by Shamir (Crypto 1984) / Bellare, Neven, and Namprempre (Eurocrypt 2004) that identity-based signature schemes can be generically constructed from standard digital signature schemes. In this paper we consider the following natural extension: is there a generic construction of "identity-based signature schemes with additional properties'' (such as identity-based blind signatures, verifiably encrypted signatures, ...) from standard signature schemes with the same properties? Our results show that this is possible for a number of properties including proxy signatures; (partially) blind signatures; verifiably encrypted signatures; undeniable signatures; forward-secure signatures; (strongly) key insulated signatures; online/offline signatures; threshold signatures; and (with some limitations) aggregate signatures.
   Using well-known results for standard signature schemes, we conclude that explicit identity-based signature schemes with additional properties can be constructed, enjoying sometimes better properties than specific schemes proposed until now. In particular, our work implies the existence of identity-based signatures with additional properties that are provably secure in the standard model, do not need bilinear pairings, or can be based on general assumptions.
Efficient list decoding of a class of algebraic-geometry codes
Peter Beelen and  Kristian Brander
2010, 4(4): 485-518 doi: 10.3934/amc.2010.4.485 +[Abstract](52) +[PDF](464.2KB)
We consider the problem of list decoding algebraic-geometry codes. We define a general class of one-point algebraic-geometry codes encompassing, among others, Reed-Solomon codes, Hermitian codes and norm-trace codes. We show how for such codes the interpolation constraints in the Guruswami-Sudan list-decoder, can be rephrased using a module formulation. We then generalize an algorithm by Alekhnovich [2], and show how this can be used to efficiently solve the interpolation problem in this module reformulation. The family of codes we consider has a number of well-known members, for which the interpolation part of the Guruswami-Sudan list decoder has been studied previously. For such codes the complexity of the interpolation algorithm we propose, compares favorably to the complexity of known algorithms.
Some applications of lattice based root finding techniques
Santanu Sarkar and  Subhamoy Maitra
2010, 4(4): 519-531 doi: 10.3934/amc.2010.4.519 +[Abstract](36) +[PDF](276.3KB)
In this paper we present some problems and their solutions exploiting lattice based root finding techniques.
   In CaLC 2001, Howgrave-Graham proposed a method to find the Greatest Common Divisor (GCD) of two large integers when one of the integers is exactly known and the other one is known approximately. In this paper, we present three applications of the technique. The first one is to show deterministic polynomial time equivalence between factoring $N$ ($N = pq$, where $p > q$ or $p, q$ are of same bit size) and knowledge of $q$-1 mod $p$. Next, we consider the problem of finding smooth integers in a short interval. The third one is to factorize $N$ given a multiple of the decryption exponent in RSA.
   In Asiacrypt 2006, Jochemsz and May presented a general strategy for finding roots of a polynomial. We apply that technique to solve the following two problems. The first one is to factorize $N$ given an approximation of a multiple of the decryption exponent in RSA. The second one is to solve the implicit factorization problem given three RSA moduli considering certain portions of LSBs as well as MSBs of one set of three secret primes are same.
Input-state-output representations and constructions of finite support 2D convolutional codes
Diego Napp , Carmen Perea and  Raquel Pinto
2010, 4(4): 533-545 doi: 10.3934/amc.2010.4.533 +[Abstract](39) +[PDF](242.4KB)
Two-dimensional convolutional codes are considered, with codewords having compact support indexed in $\mathbb N$2 and taking values in $\mathbb F$n, where $\mathbb F$ is a finite field. Input-state-output representations of these codes are introduced and several aspects of such representations are discussed. Constructive procedures of such codes with a designed distance are also presented.
Bounds for binary codes relative to pseudo-distances of $k$ points
Christine Bachoc and  Gilles Zémor
2010, 4(4): 547-565 doi: 10.3934/amc.2010.4.547 +[Abstract](47) +[PDF](310.1KB)
We apply Schrijver's semidefinite programming method to obtain improved upper bounds on generalized distances and list decoding radii of binary codes.
On $q$-ary linear completely regular codes with $\rho=2$ and antipodal dual
Joaquim Borges , Josep Rifà and  Victor A. Zinoviev
2010, 4(4): 567-578 doi: 10.3934/amc.2010.4.567 +[Abstract](53) +[PDF](237.1KB)
We characterize all $q$-ary linear completely regular codes with covering radius $\rho=2$ when the dual codes are antipodal. These completely regular codes are extensions of linear completely regular codes with covering radius 1, which we also classify. For $\rho=2$, we give a list of all such codes known to us. This also gives the characterization of two weight linear antipodal codes. Finally, for a class of completely regular codes with covering radius $\rho=2$ and antipodal dual, some interesting properties on self-duality and lifted codes are pointed out.
On dual extremal maximal self-orthogonal codes of Type I-IV
Annika Meyer
2010, 4(4): 579-596 doi: 10.3934/amc.2010.4.579 +[Abstract](41) +[PDF](298.6KB)
For a Type $T \in${I, II, III, IV} of codes over finite fields and length $N$ where there exists no self-dual Type $T$ code of length $N$, upper bounds on the minimum weight of the dual code of a self-orthogonal Type $T$ code of length $N$ are given, allowing the notion of dual extremal codes. It is proven that for $T \in${II, III, IV} the Hamming weight enumerator of a dual extremal maximal self-orthogonal Type $T$ code of a given length is unique.
Richard A. Brualdi , Kathleen P. Kiernan , Seth A. Meyer and  Michael W. Schroeder
2010, 4(4): 597-597 doi: 10.3934/amc.2010.4.597 +[Abstract](32) +[PDF](40.0KB)
Erratum to "Combinatorial Batch Codes and Transversal Matroids" (Advances in Mathematics of Communication, Vol. 4, No. 3, 2010, 419--431.

2016  Impact Factor: 0.8




Email Alert

[Back to Top]