## CryptoDB

### Jintai Ding

#### Publications

**Year**

**Venue**

**Title**

2008

EPRINT

Algebraic Cryptanalysis of MQQ Public Key Cryptosystem by MutantXL
Abstract

In this paper, we present an efficient attack to the multivariate
Quadratic Quasigroups (MQQ) cryptosystem. Our cryptanalysis breaks
MQQ cryptosystems by solving systems of multivariate quadratic
polynomial equations using a modified version of the MutantXL
algorithm. We present experimental results comparing the behavior of
our implementation of MutantXL to Magma's implementation of $F_4$ on
MQQ systems ($\geq$ 135 bit). Based on our results we show that the
MutantXL implementation solves with much less memory than Magma's
implementation of $F_4$ algorithm.

2008

EPRINT

New Differential-Algebraic Attacks and Reparametrization of Rainbow
Abstract

A recently proposed class of multivariate quadratic schemes, the
Rainbow-Like signature Schemes, in which successive sets of central
variables are obtained from previous ones by solving linear
equations, seem to lead to efficient schemes (TTS, TRMS, and
Rainbow) that perform well on systems of low computational
resources. Recently SFLASH ($C^{\ast-}$) was broken by Dubois,
Fouque, Shamir, and Stern via a differential attack. In this paper,
we exhibit similar attacks based on differentials, that will reduce
published Rainbow-like schemes below their security levels. We will
present a new type of construction of Rainbow-Like schemes and
design signature schemes with new parameters for practical
applications.

2008

EPRINT

Small Odd Prime Field Multivariate PKCs
Abstract

We show that Multivariate Public Key Cryptosystems (MPKCs)
over fields of small odd prime characteristic, say 31, can be highly
efficient. Indeed, at the same design security of $2^{80}$ under
the best known attacks, odd-char MPKC is generally
faster than prior MPKCs over \GF{2^k}, which are in turn faster than
``traditional'' alternatives.
This seemingly counter-intuitive feat is accomplished by exploiting
the comparative over-abundance of small integer arithmetic resources
in commodity hardware, here embodied by SSE2 or more advanced
special multimedia instructions on modern x86-compatible CPUs.
We explain our implementation techniques and design choices in
implementing our chosen MPKC instances modulo small a odd prime.
The same techniques are also applicable in modern FPGAs which often
contains a large number of multipliers.

2008

EPRINT

Odd-Char Multivariate Hidden Field Equations
Abstract

We present a multivariate version of Hidden Field Equations (HFE)
over a finite field of odd characteristic, with an extra
``embedding'' modifier. Combining these known ideas makes our new
MPKC (multivariate public key cryptosystem) more efficient
and scalable than any other extant multivariate encryption scheme.
Switching to odd characteristics in HFE-like schemes affects how an
attacker can make use of field equations. Extensive empirical tests
(using MAGMA-2.14, the best commercially available \mathbold{F_4}
implementation) suggests that our new construction is indeed secure
against algebraic attacks using Gr\"obner Basis algorithms. The
``embedding'' serves both to narrow down choices of pre-images and
to guard against a possible Kipnis-Shamir type (rank-based) attack. We
may hence reasonably argue that for practical sizes, prior attacks
take exponential time.
We demonstrate that our construction is in fact efficient by
implementing practical-sized examples of our ``odd-char HFE'' with 3
variables (``THFE'') over $\mathrm{GF}(31)$. To be precise, our preliminary
THFE implementation is $15\times$--$20\times$ the speed of RSA-1024.

2007

EPRINT

Multivariates Polynomials for Hashing
Abstract

We propose the idea of building a secure hash using quadratic or
higher degree multivariate polynomials over a finite field as the
compression function, whose security relies on simple hard questions. We analyze some security properties and
potential feasibility, where the compression functions are randomly
chosen high-degree polynomials. Next, we propose to improve on the
efficiency of the system by using some specially designed
polynomials using composition of maps and certain sparsity property, where the security of
the system would then relies on stronger assumptions.

2007

EPRINT

Kipnis-Shamir's Attack on HFE Revisited
Abstract

In this paper, we show that the claims in the original
Kipnis-Shamir's attack on the HFE cryptosystems and the improved
attack by Courtois that the complexity of the attacks is polynomial
in terms of the number of variables are invalid. We present computer
experiments and a theoretical argument using basic algebraic
geometry to explain why it is so. Furthermore we show that even with
the help of the powerful new Gr\"{o}bner basis algorithm like $F_4$,
the Kipnis-Shamir's attack still should be exponential not
polynomial. This again is supported by our theoretical argument.

2007

EPRINT

Identifying Ideal Lattices
Abstract

Micciancio defined a generalization of cyclic lattices, called ideal lattices. These lattices can be used in cryptosystems to decrease the number of parameters necessary to describe a lattice by a square root, making them more efficient. He proves that the computational intractability of classic lattice problems for these lattices gives rise to provably secure one-way and collision-resistant hash functions. This provable security relies on the assumption that reducing bases of ideal lattices is similar to reducing bases of random lattices. We give an indication that lattice problems in ideal lattices do not represent the general case by providing a distinguisher, which decides in time $O(n^4)$ whether a given basis of rank $n$ spans an ideal lattice or not. Using this algorithm we perform a statistical analysis for several dimensions and show that randomly generated lattices are practically never ideal.

2007

EPRINT

Breaking the Symmetry: a Way to Resist the New Differential Attack
Abstract

Sflash had recently been broken by Dubois, Stern, Shamir, etc., using
a differential attack on the public key. The $C^{\ast-}$ signature
schemes are hence no longer practical. In this paper, we will study
the new attack from the point view of symmetry, then (1) present a
simple concept (projection) to modify several multivariate schemes
to resist the new attacks; (2) demonstrate with practical examples
that this simple method could work well; and (3) show that the same
discussion of attack-and-defence applies to other big-field
multivariates. The speed of encryption schemes is not affected, and
we can still have a big-field multivariate signatures resisting the
new differential attacks with speeds comparable to Sflash.

2007

EPRINT

Cryptanalysis of Rational Multivariate Public Key Cryptosystems
Abstract

In 1989, Tsujii, Fujioka, and Hirayama proposed a family of multivariate public key cryptosystems, where the public key is given as a set of multivariate rational functions of degree 4\cite{Tsujii-Fujioka:89}. These cryptosystems are constructed via composition of two quadratic rational maps. In this paper, we present the cryptanalysis of this family of cryptosystems. The key point of our attack is to transform a problem of decomposition of two rational maps into a problem of decomposition of two polynomial maps. We develop a new improved 2R decomposition method and other new techniques, which allows us to find an equivalent decomposition of the rational maps to break the system completely. For the example suggested for practical applications, it is extremely fast to perform the computation to derive an equivalent private key, and it requires only a few seconds on a standard PC.

2007

EPRINT

Cryptanalysis of Two New Instances of TTM Cryptosystem
Abstract

In 2006, Nie et al proposed an attack to break an instance of TTM
cryptosystems. However, the inventor of TTM disputed this attack and
he proposed two new instances of TTM to support his viewpoint. At
this time, he did not give the detail of key construction
--- the construction of the lock polynomials in these instances
which would be used in decryption. The two instances are claimed to
achieve a security of $2^{109}$ against Nie et al attack. In this
paper, we show that these instances are both still insecure, and in
fact, they do not achieve a better design in the sense that we can
find a ciphertext-only attack utilizing the First Order
Linearization Equations while for the previous version of TTM, only
Second Order Linearization Equations can be used in the beginning
stage of the previous attack. Different from previous attacks, we
use an iterated linearization method to break these two instances.
For any given valid ciphertext, we can find its corresponding
plaintext within $2^{31}$ $\mathbb{F}_{2^8}$-computations after
performing once for any public key a computation of complexity less
than $2^{44}$. Our experiment result shows we have unlocked the lock
polynomials after several iterations, though we do not know the
detailed construction of lock polynomials.

2007

EPRINT

Secure PRNGs from Specialized Polynomial Maps over Any $F_q$
Abstract

We prove that a random map drawn from any class ${\frak C}$ of polynomial
maps from $F_q^n$ to $F_q^{n+r}$ that is (i) totally
random in the affine terms, and (ii) has a negligible chance of being
not strongly one-way, provides a secure PRNG (hence a secure stream
cipher) for any q. Plausible choices for ${\frak C}$ are semi-sparse
(i.e., the affine terms are truly random) systems and other systems
that are easy to evaluate from a small (compared to a generic map)
number of parameters.
To our knowledge, there are no other positive results for provable
security of specialized polynomial systems, in particular sparse
ones (which are natural candidates to investigate for speed). We
can build a family of provably secure stream ciphers
a rough implementation of which at the same security level
can be more than twice faster than an optimized QUAD (and any other
provably secure stream ciphers proposed so far), and uses much less
storage. This may also help build faster provably secure hashes.
We also examine the effects of recent results on specialization on
security, e.g., Aumasson-Meier (ICISC 2007), which precludes
Merkle-Damgaard compression using polynomials systems {uniformly
very sparse in every degree} from being universally
collision-free. We conclude that our ideas are consistent with and
complements these new results. We think that we can build secure
primitives based on specialized (versus generic) polynomial
maps which are more efficient.

2006

EPRINT

Zhuang-Zi: A New Algorithm for Solving Multivariate Polynomial Equations over a Finite Field
Abstract

We present the Zhuang-Zi algorithm, a new method for solving multivariate polynomial equations over a finite field. We describe the algorithm and present examples, some of which cannot be solved with the fastest known algorithms.

2006

EPRINT

Note on Design Criteria for Rainbow-Type Multivariates
Abstract

This was a short note that deals with the design of Rainbow or
``stagewise unbalanced oil-and-vinegar'' multivariate signature
schemes. We exhibit new cryptanalysis for current schemes that
relates to flawed choices of system parameters in current schemes.
These can be ameliorated according to an updated list of security
design criteria.

2006

EPRINT

High Order Linearization Equation (HOLE) Attack on Multivariate Public Key Cryptosystems
Abstract

In the CT-track of the 2006 RSA conference, a new multivariate
public key cryptosystem, which is called the Medium Field Equation
(MFE) multivariate public key cryptosystem, is proposed by Wang,
Yang, Hu and Lai. We use the second order linearization equation
attack method by Patarin to break MFE. Given a ciphertext, we can
derive the plaintext within $2^{23}$ $\F_{2^{16}}$-operations,
after performing once for any public key a computation of
complexity less than $2^{52}$. We also propose a high order
linearization equation (HOLE) attack on multivariate public key
cryptosystems, which is a further generalization of the (first and
second order) linearization equation (LE). This method can be used
to attack extensions of the current MFE.

2005

EPRINT

Inoculating Multivariate Schemes Against Differential Attacks
Abstract

We demonstrate how to prevent differential attacks on multivariate public key cryptosystems using the Plus (+) method of external perturbation. In particular, we prescribe adding as few as 10 Plus polynomials to the Perturbed Matsumoto-Imai (PMI) cryptosystem when $g=1$ and $r=6$, where $\theta$ is the Matsumoto-Imai exponent, $n$ is the message length, $g=\gcd{(\theta,n)}$, and $r$ is the internal perturbation dimension; or as few as $g+10$ when $g \neq 1$. The external perturbation does not significantly decrease the efficiency of the system, and in fact has the additional benefit of resolving the problem of finding the true plaintext among several preimages of a given ciphertext. We call this new scheme the Perturbed Matsumoto-Imai-Plus (PMI+) cryptosystem.

2004

EPRINT

Cryptanalysis of SFlash v3
Abstract

Sflash is a fast multivariate signature scheme. Though the first version Sflash-v1 was flawed, a second version, Sflash-v2 was selected by the Nessie Consortium and was recommended for implementation of low-end smart cards. Very recently, due to the security concern, the designer of Sflash recommended that Sflash-v2 should not be used, instead a new version Sflash-v3 is proposed, which essentially only increases the length of the signature.
The Sflash family of signature schemes is a variant of the Matsumoto and Imai public key cryptosystem. The modification is through the Minus method, namely given a set of polynomial equations, one takes out a few of them to make them much more difficult to solve.
In this paper, we attack the Sflash-v3 scheme by combining an idea from the relinearization method by Kipnis and Shamir, which was used to attack the Hidden Field Equation schemes, and the linearization method by Patarin. We show that the attack complexity is less than 2^80, the security standard required by the Nessie Consortium.

2004

EPRINT

Multivariable public--key cryptosystems
Abstract

Recently Landau and Diffie gave in a series of articles in the Notices of the American Mathematical Society and in the American Mathematical Monthly excellent expositions on how the theory of multivariable polynomials are used in cryptography. However they covered only half of the story. They covered only the theory of polynomials in symmetric or secret cryptography. There is another half of the story, namely the story about the theory of multivariable polynomials in asymmetric or public key cryptosystems. We give an overview of the families of public key cryptosystems, which have been developed in the last ten years.

2003

EPRINT

Cryptanalysis of an implementation scheme of the Tamed Transformation Method cryptosystem
Abstract

A Tamed Transformation Method (TTM) cryptosystem was proposed by T.T.Moh
in 1999. We describe how the first implementation scheme of the TTM system can be defeated. The computational complexity of our attack is $2^{33}$ computations on the finite field with $2^8$ elements.

2003

EPRINT

A defect of the implementation schemes of the TTM cryptosystem
Abstract

We show all the existing TTM implementation schemes have a defect that there exist linearization equations
$$
\sum_{i=1,j=1}^{n,m} a_{ij}x_iy_j(x_1,\dots,x_{n})+ \sum_{i=1}^{n} b_ix_i+\sum_{j=1}^{m} c_jy_j(x_1,\dots,x_{n}) + d= 0,
$$
which are satisfied by the components $y_i(x_1,\dots,x_n)$ of the ciphers of the TTM schemes. We further demonstrate that, for the case of the most recent two implementation schemes in two versions of the paper \cite{CM}, where the inventor of TTM used them to refute a claim in \cite{CG}, if we do a linear substitution with the linear equations derived from the linearization equations for a given ciphertext, we can find the plaintext easily by an iteration of the procedure of first search for linear equations by linear combinations and then linear substitution. The computation complexity of the attack on these two schemes is less than $2^{35}$ over a finite field of size $2^8$.

#### Program Committees

- PKC 2013

#### Coauthors

- John Baena (1)
- Johannes Buchmann (1)
- Chia-Hsin Owen Chen (1)
- Ming-Shing Chen (4)
- Owen Chen (2)
- Anna Chen an Ming-Shing Chen (1)
- Tien-Ren Chen (2)
- Jiun-Ming Chen (1)
- Anna Inn-Tung Chen (1)
- Doug Cheng (1)
- Chen-Mou Cheng (3)
- Özgür Dagdelen (1)
- Vivien Dubois (1)
- Jason E. Gower (3)
- Timothy Hodges (2)
- Lei Hu (5)
- Xin Jiang (2)
- Eric Kuo (1)
- Eric Li-Hsiang Kuo (1)
- Frost Yu-Shuang Lee (1)
- Jianyu Li (2)
- Frost Li (1)
- Richard Lindner (1)
- Michael Feng-Hao Liu (1)
- Chi-Jen Lu (1)
- Alexei Miasnikov (1)
- Mohamed Saied Emam Mohamed (1)
- Xuyun Nie (3)
- Albrecht Petzoldt (1)
- Jaiberth Porras (1)
- Dieter Schmidt (5)
- Michael Snook (2)
- Chengdong Tao (2)
- Alexander Ushakov (1)
- John Wagner (3)
- Fabian Werner (1)
- Christopher Wolf (1)
- Bo-Yin Yang (10)
- Jiang Zhang (2)
- Zhenfeng Zhang (2)