Search

This paper proposes a joint coding with three functions: source coding, channel coding, and public-key encryption. A codeword is simply generated as a product of an encoding matrix and a sparse information word. This encoding method has much lower encoding complexity than the conventional coding techniques in which source coding, encryption, and channel coding are successively applied to an information word. The encoding matrix is generated by using two linear error control codes and randomly generated nonsingular matrices. Encryption is based on the intractableness of factorizing a matrix into randomly constructed factor matrices, and of decoding an error control code defined by a random parity-check matrix. Evaluation shows that the proposed joint coding gives a lower bit error rate and a superior compression ratio than the conventional codings. [ABSTRACT FROM AUTHOR]

New quaternary Plotkin constructions are given and are used to obtain new families of quaternary codes. The parameters of the obtained codes, such as the length, the dimension and the minimum distance are studied. Using these constructions new families of quaternary Reed-Muller codes are built with the peculiarity that after using the Gray map the obtained ℤ4-linear codes have the same parameters as the codes in the classical binary linear Reed-Muller family. [ABSTRACT FROM AUTHOR]

Finding new classes of permutation polynomials is a challenging problem. Blockhuis at al. investigated the permutation behavior of polynomials of the form $\sum_{i=0}^{n-1}a_iX^{2^i+1}$ over ${\mathbb F}_{{2^n}}$. In this paper, we extend their results and propose as a new conjecture that if n = 2e then X2 is the only unitary permutation polynomial of this type. [ABSTRACT FROM AUTHOR]

Here we study a weakness of the RC4 Key Scheduling Algorithm (KSA) that has already been noted by Mantin and Mironov. Consider the RC4 permutation S of N (usually 256) bytes and denote it by SN after the KSA. Under reasonable assumptions we present a simple proof that each permutation byte after the KSA is significantly biased (either positive or negative) towards many values in the range 0..., N − 1. These biases are independent of the secret key and thus present an evidence that the permutation after the KSA can be distinguished from random permutation without any assumption on the secret key. We also present a detailed empirical study over Mantin's work when the theoretical formulae vary significantly from experimental results due to repetition of short keys in RC4. Further, it is explained how these results can be used to identify new distinguishers for RC4 keystream. [ABSTRACT FROM AUTHOR]

We examine the mechanism of homomorphic encryptions based on the subgroup membership problem. Using the mechanism, we construct a homomorphic encryption of a direct sum of groups. [ABSTRACT FROM AUTHOR]

We prove an upper bound on the covering radius of linear codes over ${\mathbb{F}_q}$in terms of their generalized Hamming weights. We show that this bound is strengthened if we know that the codes satisfy the chain condition or a partial chain condition. We show that this bound improves all prior bounds. Necessary conditions for equality are also presented. Several applications of our bound are presented. We give tables of improved bounds on the covering radius of many cyclic codes using their generalized Hamming weights. We show that most cyclic codes of length ≤ 39 satisfy the chain condition or partial chain condition up to level 5. We use these results to derive tighter bounds on the covering radius of cyclic codes. [ABSTRACT FROM AUTHOR]

We consider a generalization of the codes defined by norm and trace functions on finite fields introduced by Olav Geil. The codes in the new family still satisfy Geil's duality properties stated for norm-trace codes. That is, it is easy to find a minimal set of parity checks guaranteeing correction of a given number of errors, as well as the set of monomials generating the corresponding code. Furthermore, we describe a way to find the minimal set of parity checks and the corresponding generating monomials guaranteeing correction at least of generic errors. This gives codes with even larger dimensions. [ABSTRACT FROM AUTHOR]

In this paper we consider some properties of quasi-cyclic codes over the integer residue rings. A quasi-cyclic code over ℤk, the ring of integers modulo k, reduces to a direct product of quasi-cyclic codes over ${\mathbb{Z}}_{p_i^{e_i}}$, $k = \prod_{i=1}^s p_i^{e_i}$, pi a prime. Let T be the standard shift operator. A linear code $\mathcal{C}$ over a ring R is called an l-quasi-cyclic code if $T^l(c) \in \mathcal{C}$, whenever $ c\in \mathcal{C}$. It is shown that if (m, q) = 1, q = pr, p a prime, then an l-quasi-cyclic code of length lm over ℤq is a direct product of quasi-cylcic codes over some Galois extension rings of ℤq. We have discussed about the structure of the generator of a 1-generator l-quasi-cyclic code of length lm over ℤq. A method to obtain quasi-cyclic codes over ℤq, which are free modules over ℤq, has been discussed. [ABSTRACT FROM AUTHOR]

Recently, 9-variable Boolean functions having nonlinearity 241, which is strictly greater than the bent concatenation bound of 240, have been discovered in the class of Rotation Symmetric Boolean Functions (RSBFs) by Kavut, Maitra and Yücel. In this paper, we present several 9-variable Boolean functions having nonlinearity of 242, which we obtain by suitably generalizing the classes of RSBFs and Dihedral Symmetric Boolean Functions (DSBFs). These functions do not have any zero in the Walsh spectrum values, hence they cannot be made balanced easily. This result also shows that the covering radius of the first order Reed-Muller code R(1, 9) is at least 242. [ABSTRACT FROM AUTHOR]

The uniform distribution of the trace map lends itself very well to the construction of binary and non-binary codes from Galois fields and Galois rings. In this paper we study the distribution of the trace map with the argument ax2 over the Galois field GF(p,2). We then use this distribution to construct two-weight, self-orthogonal, trace codes. [ABSTRACT FROM AUTHOR]

The split-radix FFT computes a size-n complex DFT, when n is a large power of 2, using just $4n\lg n-6n+8$ arithmetic operations on real numbers. This operation count was first announced in 1968, stood unchallenged for more than thirty years, and was widely believed to be best possible. Recently James Van Buskirk posted software demonstrating that the split-radix FFT is not optimal. Van Buskirk's software computes a size-n complex DFT using only $(34/9+o(1))n\lg n$ arithmetic operations on real numbers. There are now three papers attempting to explain the improvement from 4 to 34/9: Johnson and Frigo, IEEE Transactions on Signal Processing, 2007; Lundy and Van Buskirk, Computing, 2007; and this paper. This paper presents the "tangent FFT," a straightforward in-place cache-friendly DFT algorithm having exactly the same operation counts as Van Buskirk's algorithm. This paper expresses the tangent FFT as a sequence of standard polynomial operations, and pinpoints how the tangent FFT saves time compared to the split-radix FFT. This description is helpful not only for understanding and analyzing Van Buskirk's improvement but also for minimizing the memory-access costs of the FFT. [ABSTRACT FROM AUTHOR]

The novel algebraic structure for the cyclic codes, Cyclic Multiplicative Groups (CMGs) over polynomial ring, is proposed in this paper. According to this algorithm, traditional cyclic codes can be considered as a subclass in these cyclic codes. With CMGs structure, more plentiful good cyclic code cosets can be found in any polynomial rings than other methods. An arbitrary polynomial in polynomial ring can generate cyclic codes in which length of codewords depend on order of the polynomial. Another advantage of this method is that a longer code can be generated from a smaller polynomial ring. Moreover, our technique is flexibly and easily implemented in term of encoding as well as decoding. As a result, the CMGs can contribute a new point of view in coding theory. The significant advantages of proposed cyclic code cosets can be applicable in the modern communication systems and crypto-systems. [ABSTRACT FROM AUTHOR]

There are characteristics of Hadamard matrices that enable an exhaustive search using algorithmic techniques. The search derives primarily from the eigenvalues which are constant after the Hadamard matrix is multiplied by its transpose. Generally this would be a performance concern but there are additional properties that enable the eigenvalues to be predicted. Here an algorithm is given to obtain a Hadamard matrix from a matrix of 1s using optimisation techniques on a row-by-row basis. [ABSTRACT FROM AUTHOR]

In this paper we present a theoretical construction of Rotation Symmetric Boolean Functions (RSBFs) on odd number of variables with maximum possible algebraic immunity (AI) and further these functions are not symmetric. Our RSBFs are of better nonlinearity than the existing theoretical constructions with maximum possible AI. To get very good nonlinearity, which is important for practical cryptographic design, we generalize our construction to a construction cum search technique in the RSBF class. We find 7, 9, 11 variable RSBFs with maximum possible AI having nonlinearities 56, 240, 984 respectively with very small amount of search after our basic construction. [ABSTRACT FROM AUTHOR]

Let Fn be the binary n-cube, or binary Hamming space of dimension n, endowed with the Hamming distance, and ${\cal E}^n$ (respectively, ${\cal O}^n$) the set of vectors with even (respectively, odd) weight. For r ≥ 1 and x ∈ Fn, we denote by Br(x) the ball of radius r and centre x. A code C ⊆ Fn is said to be r-identifying if the sets Br(x) ∩ C, x ∈ Fn, are all nonempty and distinct. A code $C\subseteq {\cal E}^n$ is said to be r-discriminating if the sets Br(x) ∩ C, $x\in {\cal O}^n$, are all nonempty and distinct. We show that the two definitions, which were given for general graphs,are equivalent in the case of the Hamming space, in the following sense: for any odd r, there is a bijection between the set of r-identifying codes in Fn and the set of r-discriminating codes in Fn + 1. [ABSTRACT FROM AUTHOR]

The cross-realm client-to-client password-based authenticated key exchange (C2C-PAKE) is protocol which two clients in two different realms with different passwords exchange a session key through their corresponding servers. Recently, a provably secure cross-realm C2C-PAKE scheme with the optimal number of rounds for a client is pointed out that the scheme is insecure against an undetectable on-line dictionary attack and an unknown-key share attack. In this paper, we propose a new cross-realm C2C-PAKE scheme with the optimal number of rounds for a client, which has resistances to previously considered attacks which should be prevented, including undetectable on-line dictionary attacks and unknown-key share attacks. Moreover, our scheme assumes no pre-established secure channels between different realms, but just basic setups of ID-based systems. [ABSTRACT FROM AUTHOR]