ISSN:
1930-5346
eISSN:
1930-5338
All Issues
Advances in Mathematics of Communications
November 2010 , Volume 4 , Issue 4
Special issue dedicated to Jan Boman
on the occasion of his 75th birthday
Select all articles
Export/Reference:
2010, 4(4): 441-452
doi: 10.3934/amc.2010.4.441
+[Abstract](2319)
+[PDF](248.7KB)
Abstract:
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.
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.
2010, 4(4): 453-483
doi: 10.3934/amc.2010.4.453
+[Abstract](2420)
+[PDF](448.7KB)
Abstract:
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.
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.
2010, 4(4): 485-518
doi: 10.3934/amc.2010.4.485
+[Abstract](2646)
+[PDF](464.2KB)
Abstract:
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.
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.
2010, 4(4): 519-531
doi: 10.3934/amc.2010.4.519
+[Abstract](1937)
+[PDF](276.3KB)
Abstract:
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.
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.
2010, 4(4): 533-545
doi: 10.3934/amc.2010.4.533
+[Abstract](2212)
+[PDF](242.4KB)
Abstract:
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.
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.
2010, 4(4): 547-565
doi: 10.3934/amc.2010.4.547
+[Abstract](2042)
+[PDF](310.1KB)
Abstract:
We apply Schrijver's semidefinite programming method to obtain improved upper bounds on generalized distances and list decoding radii of binary codes.
We apply Schrijver's semidefinite programming method to obtain improved upper bounds on generalized distances and list decoding radii of binary codes.
2010, 4(4): 567-578
doi: 10.3934/amc.2010.4.567
+[Abstract](2637)
+[PDF](237.1KB)
Abstract:
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.
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.
2010, 4(4): 579-596
doi: 10.3934/amc.2010.4.579
+[Abstract](2103)
+[PDF](298.6KB)
Abstract:
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.
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.
2010, 4(4): 597-597
doi: 10.3934/amc.2010.4.597
+[Abstract](1749)
+[PDF](40.0KB)
Abstract:
Erratum to "Combinatorial Batch Codes and Transversal Matroids" (Advances in Mathematics of Communication, Vol. 4, No. 3, 2010, 419--431.
Erratum to "Combinatorial Batch Codes and Transversal Matroids" (Advances in Mathematics of Communication, Vol. 4, No. 3, 2010, 419--431.
2019 Impact Factor: 0.734
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]