Catálogo de publicaciones - libros

Compartir en
redes sociales


Applied Algebra, Algebraic Algorithms and Error-Correcting Codes: 16th International Symposium, AAECC-16, Las Vegas, NV, USA, February 20-24, 2006, Proceedings

Marc P. C. Fossorier ; Hideki Imai ; Shu Lin ; Alain Poli (eds.)

En conferencia: 16º International Symposium on Applied Algebra, Algebraic Algorithms, and Error-Correcting Codes (AAECC) . Las Vegas, NV, USA . February 20, 2006 - February 24, 2006

Resumen/Descripción – provisto por la editorial

No disponible.

Palabras clave – provistas por la editorial

Coding and Information Theory; Data Encryption; Discrete Mathematics in Computer Science; Algorithm Analysis and Problem Complexity; Symbolic and Algebraic Manipulation; Algorithms

Disponibilidad
Institución detectada Año de publicación Navegá Descargá Solicitá
No detectada 2006 SpringerLink

Información

Tipo de recurso:

libros

ISBN impreso

978-3-540-31423-3

ISBN electrónico

978-3-540-31424-0

Editor responsable

Springer Nature

País de edición

Reino Unido

Fecha de publicación

Información sobre derechos de publicación

© Springer-Verlag Berlin Heidelberg 2006

Tabla de contenidos

Computing Gröbner Bases for Vanishing Ideals of Finite Sets of Points

Jeffrey B. Farr; Shuhong Gao

We present an algorithm to compute a Gröbner basis for the vanishing ideal of a finite set of points in an affine space. For distinct points the algorithm is a generalization of univariate Newton interpolation. Computational evidence suggests that our method compares favorably with previous algorithms when the number of variables is small relative to the number of points. We also present a preprocessing technique that significantly enhances the performance of all the algorithms considered. For points with multiplicities, we adapt our algorithm to compute the vanishing ideal via Taylor expansions.

Pp. 118-127

A Class of Fermat Curves for which Weil-Serre’s Bound Can Be Improved

Francis N. Castro; Ernesto Gomez; Oscar Moreno

In this paper we introduce the class of semiprimitive Fermat curves, for which Weil-Serre’s bound can be improved using Moreno-Moreno -adic techniques. The basis of the improvement is a technique for giving the exact divisibility for Fermat curves, by reducing the problem to a simple finite computation.

Pp. 128-135

Nonbinary Quantum Codes from Hermitian Curves

Pradeep Kiran Sarvepalli; Andreas Klappenecker

The extreme sensitivity of quantum information to ambient noise has prompted the study of quantum error-correcting codes.In this paper two families of quantum error-correcting codes are constructed based on Hermitian curves. Unlike the case of classical codes, it is a difficult, sometimes impossible, task to puncture a quantum stabilizer code. The puncture code of Hermitian codes is computed that allows one to determine the admissible puncturings. A large number of punctured Hermitian codes are derived by exploiting known facts about the weight distribution of these puncture codes.

Pp. 136-143

A Genetic Algorithm for Cocyclic Hadamard Matrices

V. Álvarez; J. A. Armario; M. D. Frau; P. Real

A genetic algorithm for finding cocyclic Hadamard matrices is described. Though we focus on the case of dihedral groups, the algorithm may be easily extended to cover any group. Some executions and examples are also included, with aid of .

Pp. 144-153

Unconditionally Secure Chaffing-and-Winnowing: A Relationship Between Encryption and Authentication

Goichiro Hanaoka; Yumiko Hanaoka; Manabu Hagiwara; Hajime Watanabe; Hideki Imai

A chaffing-and-winnowing is a cryptographic scheme which does not require encryption but instead use a message authentication code (MAC) to provide the same function as encryption. In this paper, we discuss and introduce some new insights in the relationship between unconditionally secure authentication codes (A-code) and unconditionally secure encryption schemes through observing the mechanisms of chaffing-and-winnowing. Particularly, we show through chaffing-and-winnowing that an A-code with a security level considerably low stands equivalently for an encryption scheme with perfect secrecy, and a fully secure authentication scheme implies both perfect secrecy and non-malleability for an encryption scheme in the unconditionally secure setting.

Pp. 154-162

A Fast Calculus for the Linearizing Attack and Its Application to an Attack on KASUMI

Nobuyuki Sugio; Shunichi Nambu; Toshinobu Kaneko

This paper describes a linearizing attack with fast calculus for higher order differential attack. The linearizing attack, proposed by Shimoyama et al. [13], [15], linearizes the attack equation and determines the key by Gaussian elimination. The cost of calculating the coefficient matrix is dominant overhead in this attack. We improve the algorithm used to calculate the coefficient matrix by applying a bit-slice type implementation [3]. We apply this method to five-round KASUMI and show that it need 2 chosen plaintexts and 2 KASUMI encryptions.

Pp. 163-172

On Achieving Chosen Ciphertext Security with Decryption Errors

Yang Cui; Kazukuni Kobara; Hideki Imai

Perfect decryption has been always assumed in the research of public key encryption, however, this is not true all the time. For some public key encryption primitives, like NTRU [9] or Ajtai-Dwork [1], the decryption process may not obtain the corresponding message even the encryption and decryption are run correctly. Furthermore, such a kind of decryption errors will lead to some dangerous attacks against the underlying primitive. Another interesting point is that, those primitives are not based on the factoring, nor the discrete log problem which are subject to the Shor’s algorithm [18] with quantum computers. This kind of primitives may be promising in the post-quantum cryptography. Therefore, the decryption errors deserve much attention and should be coped with carefully.

In this paper, our main technique is not to use any error-correcting codes to the errors, but to use some padding (transform) to “bad” errors from attacker’s control. We 1) efficiently enhance these error-prone public key encryption primitives to the chosen ciphertext security, even in the presence of the decryption errors, and 2) show that the solution is more generic, rather than some specific padding methods previously presented, to thwart the decryption errors based attacks successfully.

Pp. 173-182

Applying Fujisaki-Okamoto to Identity-Based Encryption

Peng Yang; Takashi Kitagawa; Goichiro Hanaoka; Rui Zhang; Kanta Matsuura; Hideki Imai

The Fujisaki-Okamoto (FO) conversion is widely known to be able to generically convert a weak public key encryption scheme, say one-way against chosen plaintext attacks (OW-CPA), to a strong one, namely, indistinguishable against adaptive chosen ciphertext attacks (IND-CCA). It is not known that if the same holds for identity-based encryption (IBE) schemes, though many IBE and variant schemes are in fact specifically using the FO conversion. In this paper, we investigate this issue and confirm that the FO conversion is generically effective also in the IBE case. However, straightforward application of the FO conversion only leads to an IBE scheme with a loose (but polynomial) reduction. We then propose a simple modification to the FO conversion, which results in considerably more efficient security reduction.

Pp. 183-192

A Short Random Fingerprinting Code Against a Small Number of Pirates

Manabu Hagiwara; Goichiro Hanaoka; Hideki Imai

In this paper, we propose a variant of Tardos code which is practical for various applications against a small number of pirates. As an example of our results, for =5, the code length becomes only 1500 log(1/) bits while the conventional Tardos code requires 2500 log(1/) bits, where is a security parameter.

Furthermore our codes do not need a continuous distribution which is needed to construct the original Tardos codes. Our codes are based on a simple random variable drawn from a small set. It implies that it makes to implement and to perform a simulation extremely easier than the original one.

Pp. 193-202

A General Formulation of Algebraic and Fast Correlation Attacks Based on Dedicated Sample Decimation

Miodrag J. Mihaljević; Marc P. C. Fossorier; Hideki Imai

This paper proposes a novel approach for cryptanalysis of certain cryptographic pseudorandom sequence (keystream) generators consisting of the composition of a linear finite state machine (LFSM) and nonlinear mapping. The proposed approach includes a dedicated decimation of the sample for cryptanalysis based on the following: Suppose certain bits of the LFSM initial state as known and identify time instances where certain arguments of the nonlinear function depend only on these bits and are equal to zero. As opposed to previously reported methods, the proposed one also identifies and uses certain characteristics of the LFSM state-transition matrix in order to reduce the nonlinearity of the system of overdefined equations employed in an algebraic attack scenario, or to reduce the noise introduced by the linearization of the nonlinear function which corrupts the linear equations employed in a correlation attack scenario.

Pp. 203-214