Search

In 1990 Cooper suggested to use Groebner bases' computations to decode cyclic codes and his idea gave rise to many research papers. In particular, as proved by Sala-Orsini, once defined the polynomial ring whose variables are the syndromes, the locations and the error values and considered the syndrome ideal, only one polynomial of a lexicographical Groebner basis for such ideal is necessary to decode (the general error locator polynomial, a.k.a. GELP). The decoding procedure only consists in evaluating this polynomial in the syndromes and computing its roots: the roots are indeed the error locations. A possible bottleneck in this procedure may be the evaluation part, since a priori the GELP may be dense. In this paper, focusing on binary cyclic codes with length n = 2 m - 1 , correcting up to two errors, we give a Groebner-free, sparse analog of the GELP, the half error locator polynomial (HELP). In particular, we show that it is not necessary to compute the whole Groebner basis for getting such kind of locator polynomial and we construct the HELP, studying the quotient algebra of the polynomial ring modulo the syndrome ideal by a combinatorial point of view. The HELP turns out to be computable with quadratic complexity and it has linear growth in the length n of the code: O n + 1 2 . [ABSTRACT FROM AUTHOR]

The correctness in decrypting a ciphertext after some operations in the DGVH scheme depends heavily on the dimension of the secret key. In this paper we compute two bounds on the size of the secret key for the DGHV scheme to decrypt correctly a ciphertext after a fixed number of additions and a fixed number of multiplication. Moreover we improve the original bound on the dimension of the secret key for a general circuit. [ABSTRACT FROM AUTHOR]

BEAR, LION and LIONESS are block ciphers presented by Biham and Anderson (), inspired by the famous Luby-Rackoff constructions of block ciphers from other cryptographic primitives (). The ciphers proposed by Biham and Anderson are based on one stream cipher and one hash function. Good properties of the primitives may ensure good properties of the block cipher. In particular, Biham and Anderson are able to prove that their ciphers are immune to any efficient known-plaintext key-recovery attack that can use as input only one plaintext-ciphertext pair. Our contribution is showing that these ciphers are actually immune to any efficient known-plaintext key-recovery attack that can use as input any number of plaintext-ciphertext pairs. We are able to get this improvement by using slightly different hypotheses on the primitives. We also discuss the attack by Morin (). [ABSTRACT FROM AUTHOR]