A Weak Key Test for Braid Based Cryptography

This work emphasizes an important problem of braid based cryptography: the random generation of good keys. We present a deterministic, polynomial algorithm that reduces the conjugacy search problem in braid group. The algorithm is based on the decomposition of braids into products of canonical factors and gives a partial factorization of the secret: a divisor and a multiple. The tests we performed on different keys of existing protocols showed that many protocols in their current form are broken and that the efficiency of our attack depends on the random generator used to create the key. Therefore, this method gives new critera for testing weak keys. We also propose a new random generator of key which is secure against our attack and the one of Hofheinz and Steinwandt.     

A series solution for nonlinear differential equations using delta operators

In this paper, we shall generalize our previous results [1] to the case of series expansion in powers of several polynomials. For this, we shall extend the ideas of delta operators and their basic polynomial sequences, introduced in conjunction with the algebra (over a field of characteristic zero) of all polynomials in one variable [2] to the algebra (over a field of characteristic zero) of all polynomials in n indeterminates. We apply this technique to derive the formal power series expansion of the input-output map describing a nonlinear system with polynomial inputs.     

Vinberg’s θ-groups in positive characteristic and Kostant–Weierstrass slices

We generalize the basic results of Vinberg’s θ-groups, or periodically graded reductive Lie algebras, to fields of good positive characteristic. To this end we clarify the relationship between the little Weyl group and the (standard) Weyl group. We deduce that the ring of invariants associated to the grading is a polynomial ring. This approach allows us to prove the existence of a KW-section for a classical graded Lie algebra (in zero or odd positive characteristic), confirming a conjecture of Popov in this case.     

Polynomial-time key recovery attack on the Faure–Loidreau scheme based on Gabidulin codes

Encryption schemes based on the rank metric lead to small public key sizes of order of few thousands bytes which represents a very attractive feature compared to Hamming metric-based encryption schemes where public key sizes are of order of hundreds of thousands bytes even with additional structures like the cyclicity. The main tool for building public key encryption schemes in rank metric is the McEliece encryption setting used with the family of Gabidulin codes. Since the original scheme proposed in 1991 by Gabidulin, Paramonov and Tretjakov, many systems have been proposed based on different masking techniques for Gabidulin codes. Nevertheless, over the years most of these systems were attacked essentially by the use of an attack proposed by Overbeck. In 2005 Faure and Loidreau designed a rank-metric encryption scheme which was not in the McEliece setting. The scheme is very efficient, with small public keys of size a few kiloBytes and with security closely related to the linearized polynomial reconstruction problem which corresponds to the decoding problem of Gabidulin codes. The structure of the scheme differs considerably from the classical McEliece setting and until our work, the scheme had never been attacked. We show in this article that for a range of parameters, this scheme is also vulnerable to a polynomial-time attack that recovers the private key by applying Overbeck’s attack on an appropriate public code. As an example we break in a few seconds parameters with 80-bit security claim. Our work also shows that some parameters are not affected by our attack but at the cost of a lost of efficiency for the underlying schemes.     

The chromatic polynomial of fatgraphs and its categorification

Motivated by Khovanov homology and relations between the Jones polynomial and graph polynomials, we construct a homology theory for embedded graphs from which the chromatic polynomial can be recovered as the Euler characteristic. For plane graphs, we show that our chromatic homology can be recovered from the Khovanov homology of an associated link. We apply this connection with Khovanov homology to show that the torsion-free part of our chromatic homology is independent of the choice of planar embedding of a graph. We extend our construction and categorify the Bollobás-Riordan polynomial (a generalization of the Tutte polynomial to embedded graphs). We prove that both our chromatic homology and the Khovanov homology of an associated link can be recovered from this categorification.     

First fall degree and Weil descent

Polynomial systems arising from a Weil descent have many applications in cryptography, including the HFE cryptosystem and the elliptic curve discrete logarithm problem over small characteristic fields. Understanding the exact complexity of solving these systems is essential for the applications. A first step in that direction is to study the first fall degree of the systems. In this paper, we establish a rigorous general bound on the first fall degree of polynomial systems arising from a Weil descent. We also provide experimental data to study the tightness of our bound in general and its plausible consequences on the complexity of polynomial systems arising from a Weil descent.     

Multiround Unconditionally Secure Authentication

Authentication codes are used to protect communication against a malicious adversary. In this paper we investigate unconditionally secure multiround authentication schemes. In a multiround scheme a message is authenticated by passing back and forth several codewords between the sender and receiver. We define a multiround authentication model and show how to calculate the probability of a successful attack for this model. We prove the security for a 3-round scheme and give a construction for the 3-round scheme based on Reed-Solomom codes. This construction has a very small key size for even extremely large messages. Furthermore, a secure scheme for an arbitrary number of rounds is given. We give a new upper bound for the keys size of an n-round scheme.     

On enumeration of polynomial equivalence classes and their application to MPKC

The Isomorphism of Polynomials (IP) is one of the most fundamental problems in multivariate public key cryptography (MPKC). In this paper, we introduce a new framework to study the counting problem associated to IP. Namely, we present tools of finite geometry allowing to investigate the counting problem associated to IP. Precisely, we focus on enumerating or estimating the number of isomorphism equivalence classes of homogeneous quadratic polynomial systems. These problems are equivalent to finding the scale of the key space of a multivariate cryptosystem and the total number of different multivariate cryptographic schemes respectively, which might impact the security and the potential capability of MPKC. We also consider their applications in the analysis of a specific multivariate public key cryptosystem. Our results not only answer how many cryptographic schemes can be derived from monomials and how big the key space is for a fixed scheme, but also show that quite many HFE cryptosystems are equivalent to a Matsumoto–Imai scheme.     

Multivariate Polynomials,Duality, and Structured Matrices

We first review the basic properties of the well known classes of Toeplitz, Hankel, Vandermonde, and other related structured matrices and reexamine their correlation to operations with univariate polynomials. Then we define some natural extensions of such classes of matrices based on their correlation to multivariate polynomials. We describe the correlation in terms of the associated operators of multiplication in the polynomial ring and its dual space, which allows us to generalize these structures to the multivariate case. Multivariate Toeplitz, Hankel, and Vandermonde matrices, Bezoutians, algebraic residues, and relations between them are studied. Finally, we show some applications of this study to rootfinding problems for a system of multivariate polynomial equations, where the dual space, algebraic residues, Bezoutians, and other structured matrices play an important role. The developed techniques enable us to obtain a better insight into the major problems of multivariate polynomial computations and to improve substantially the known techniques of the study of these problems. In particular, we simplify and/or generalize the known reduction of the multivariate polynomial systems to the matrix eigenproblem, the derivation of the Bézout and Bernshtein bounds on the number of the roots, and the construction of multiplication tables. From the algorithmic and computational complexity point, we yield acceleration by one order of magnitude of the known methods for some fundamental problems of solving multivariate polynomial systems of equations.     

A chaotic block cipher algorithm for image cryptosystems

Recently, many scholars have proposed chaotic cryptosystems in order to promote communication security. However, there are a number of major problems detected in some of those schemes such as weakness against differential attack, slow performance speed, and unacceptable data expansion. In this paper, we introduce a new chaotic block cipher scheme for image cryptosystems that encrypts block of bits rather than block of pixels. It encrypts 256-bits of plainimage to 256-bits of cipherimage within eight 32-bit registers. The scheme employs the cryptographic primitive operations and a non-linear transformation function within encryption operation, and adopts round keys for encryption using a chaotic system. The new scheme is able to encrypt large size of images with superior performance speed than other schemes. The security analysis of the new scheme confirms a high security level and fairly uniform distribution.     

Families of discrete advection-reaction operators investigated via divided differences

An infinite matrix formulation of the families of discrete advection-reaction operators is given in order to investigate their relevance to interpolation theory. A basic characteristic under study is the connection of each iteration of the operators to a series of interpolation problems for the canonical polynomial base for selected initial conditions. In order to generalize our results, we extend the definition of advection-reaction operators to sequences of polynomials.     

Polynomial Identities and Nonidentities of Split Jordan Pairs

We show that split Jordan pairs over rings without 2-torsion can be distinguished by polynomial identities with integer coefficients. In particular, this holds for simple finite-dimensional Jordan pairs over algebraically closed fields of characteristic not 2. We also generalize results of Drensky and Racine and of Rached and Racine on polynomial identities of, respectively, Jordan algebras and Jordan triple systems.     

On spherical designs obtained from Q‐polynomial association schemes

We characterize that the image of the embedding of the Q ‐polynomial association scheme into the first eigenspace by primitive idempotent E ₁ is a spherical t‐design in terms of the Krein numbers. Furthermore, we show that the strengths of P‐ and Q‐polynomial schemes as spherical designs are bounded by a constant. Copyright © 2011 John Wiley & Sons, Ltd. 19:167‐177, 2011     

Generalization of Matsui’s Algorithm 1 to linear hull for key-alternating block ciphers

We consider linear approximations of an iterated block cipher in the presence of several strong linear approximation trails. While the effect of such trails in Matsui’s Algorithm 2, also called the linear hull effect, has been previously studied by a number of authors, their effect on Matsui’s Algorithm 1 has not been investigated until now. The goal of this paper is to fill this gap and examine how to generalize Matsui’s Algorithm 1 to work also on linear hulls. We restrict to key-alternating ciphers and develop a mathematical framework for this kind of attacks. The complexity of the attack increases with the number of linear trails that have significant contribution to the correlation. We show how to reduce the number of trails and thus the complexity using related keys. Further, we illustrate our theory by experimental results on a reduced round version of the block cipher PRESENT.     

The (related-key) impossible boomerang attack and its application to the AES block cipher

The Advanced Encryption Standard (AES) is a 128-bit block cipher with a user key of 128, 192 or 256 bits, released by NIST in 2001 as the next-generation data encryption standard for use in the USA. It was adopted as an ISO international standard in 2005. Impossible differential cryptanalysis and the boomerang attack are powerful variants of differential cryptanalysis for analysing the security of a block cipher. In this paper, building on the notions of impossible differential cryptanalysis and the boomerang attack, we propose a new cryptanalytic technique, which we call the impossible boomerang attack, and then describe an extension of this attack which applies in a related-key attack scenario. Finally, we apply the impossible boomerang attack to break 6-round AES with 128 key bits and 7-round AES with 192/256 key bits, and using two related keys we apply the related-key impossible boomerang attack to break 8-round AES with 192 key bits and 9-round AES with 256 key bits. In the two-key related-key attack scenario, our results, which were the first to achieve this amount of attacked rounds, match the best currently known results for AES with 192/256 key bits in terms of the numbers of attacked rounds. The (related-key) impossible boomerang attack is a general cryptanalytic technique, and can potentially be used to cryptanalyse other block ciphers.     

Full analysis of PRINTcipher with respect to invariant subspace attack: efficient key recovery and countermeasures

In this paper we investigate the invariant property of PRINTcipher initially discovered by Leander et al. in their CRYPTO 2011 paper. We provide a complete study of the attack and show that there exist 64 families of weak keys for PRINTcipher–48 and as many as 115,669 for PRINTcipher–96. Moreover, we show that searching the weak key space may be substantially sped up by splitting the search process into two consecutive steps. We show that for many classes of weak keys, key recovery can be done with very small time complexity in the chosen/known plaintext scenario. In fact, at least \(2^{45}\) weak keys can be recovered in less than 10 s per key on a single PC. Still, effective countermeasures exist against the attack. On the methodological level, the method of finding all weak key families has value on its own. It is based on Mixed Integer Linear Programming and can be adapted to solving other interesting problems on similar ciphers.     

Attacks on the RC4 stream cipher

In this article we present some weaknesses in the RC4 cipher and their cryptographic applications. Especially we improve the attack described by Fluhrer, Mantin, Shamir (In: Selected Areas in Cryptography, 2001) in such a way, that it will work, if the weak keys described in that paper are avoided. A further attack will work even if the first 256 Byte of the output remain unused. Finally we show that variants of the RC4 algorithm like NGG and RC4A are also vulnerable by these techniques.      

Euler characteristics of general linear sections and polynomial Chern classes

We obtain a precise relation between the Chern–Schwartz–MacPherson class of a subvariety of projective space and the Euler characteristics of its general linear sections. In the case of a hypersurface, this leads to simple proofs of formulas of Dimca–Papadima and Huh for the degrees of the polar map of a homogeneous polynomial, extending these formula to any algebraically closed field of characteristic \(0\), and proving a conjecture of Dolgachev on ‘homaloidal’ polynomials in the same context. We generalize these formulas to subschemes of higher codimension in projective space. We also describe a simple approach to a theory of ‘polynomial Chern classes’ for varieties endowed with a morphism to projective space, recovering properties analogous to the Deligne–Grothendieck axioms from basic properties of the Euler characteristic. We prove that the polynomial Chern class defines homomorphisms from suitable relative Grothendieck rings of varieties to \(\mathbb{Z }[t]\).     

Revocable hierarchical identity-based encryption with shorter private keys and update keys

Revocable hierarchical identity-based encryption (RHIBE) is an extension of HIBE that supports the revocation of user’s private keys to manage the dynamic credentials of users in a system. Many different RHIBE schemes were proposed previously, but they are not efficient in terms of the private key size and the update key size since the depth of a hierarchical identity is included as a multiplicative factor. In this paper, we propose efficient RHIBE schemes with shorter private keys and update keys and small public parameters by removing this multiplicative factor. To achieve our goals, we first present a new HIBE scheme with the different generation of private keys such that a private key can be simply derived from a short intermediate private key. Next, we show that two efficient RHIBE schemes can be built by combining our HIBE scheme, an IBE scheme, and a tree based broadcast encryption scheme in a modular way.