No abstract uploaded!

In this paper, we propose an algebraic broadcast attack against NTRU, which recovers a single message encrypted multiple times using different NTRU public keys. Namely, when a message is broadcasted, under some reasonable assumptions, our attack can be completed in polynomial time and space. To the best of our knowledge, this is the first successful broadcast attack against NTRU.

Let X = (x_1,..,x_n) and Y = (y_1,...,y_m) be a pair of corresponding plaintext and ciphertext for a cryptosystem. We define an embedded surface of this cryptosystem as any polynomial equation: E(X,Y)=E(x_1,..,x_n,y_1,...,y_m)=0, which is satisfied by all such pairs. In this paper, we present a new attack on the multivariate public key cryptosystems from Diophantine equations developed by Gao and Heindl by using the embedded surfaces associated to this family of multivariate cryptosystems.

In this paper, we present and prove the first closed formula bounding the degree of regularity of an HFE system over an arbitrary finite field. Though these bounds are not necessarily optimal, they can be used to deduce 1. if D, the degree of the corresponding HFE polynomial, and q, the size of the corresponding finite field, are fixed, inverting HFE system is polynomial for all fields; 2. if D is of the scale O(n^α) where n is the number of variables in an HFE system, and q is fixed, inverting HFE systems is quasi-polynomial for all fields. We generalize and prove rigorously similar results by Granboulan, Joux and Stern in the case when q = 2 that were communicated at Crypto 2006.

The public key of the Oil-Vinegar scheme consists of a set of m quadratic equations in m + n variables over a finite field F_q. Kipnis and Shamir broke the balanced Oil-Vinegar scheme where d = n − m = 0 by finding equivalent keys of the cryptosytem. Later their method was extended by Kipnis et al to attack the unbalanced case where 0 < d < m and d is small with a complexity of O(q^{d−1} m^4). This method uses the matrices associated with the quadratic polynomials in the public key, which needs to be symmetric and invertible. In this paper, we give an optimized search method for Kipnis el al’s attack. Moreover, for the case that the finite field is of characteristic 2, we find the situation becomes very subtle, which, however, was totally neglected in the original work of Kipnis et al. We show that the Kipnis-Shamir method does not work if the field characteristic is 2 and d is a small odd number, and we fix the situation by proposing an alternative method and give an equivalent key recovery attack of complexity O(q^{d+1} m^4). We also prove an important experimental observation by Ding et al for the Kipnis-Shamir attack on balanced Oil-Vinegar schemes in characteristic 2.