MathSciDoc: An Archive for Mathematician ∫

In a (t,n) threshold scheme any t or more shares can reconstruct the secret s, but less than t shares reveal no information about s. However, an unauthenticated adversary can pretend to be the shareholder at the reconstruction stage. If there were more than t honest shareholders, the unauthenticated adversary without valid share can obtain the secret. To deal with this type of attacks, a model of (t,m,n) group oriented secret sharing (GOSS) scheme was proposed by Miao et al. in 2015. Here the group oriented property means that if m>t parties try to reconstruct the secret, they should all have the authentic shares in advance. It was claimed by Miao et al. that the group oriented property in their GOSS schemes holds in the information-theoretic sense. In this paper, we revisit two instantiations of (t,m,n) group oriented secret sharing schemes and show that these constructions cannot provide the so-called “group oriented property”. Specifically, we develop concrete attacks which allow an unauthenticated adversary with no valid share to participate in the reconstruction phase and obtain the secret provided that there are at least t honest shares presented at the reconstruction phase.

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_i y_j(x_1,...,x_n) + \sum_{i=1}^n b_i x_i + \sum_{j=1}^m c_j y_j(x_1,...,x_n) + d = 0, which are satisfied by the components y_i(x_1,...,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.

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.

Sflash had recently been broken by Dubois, Stern, Shamir, etc., using a differential attack on the public key. The C^{*-} 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.

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 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.

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öbner 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 GF(31). To be precise, our preliminary THFE implementation is 15x--20x the speed of RSA-1024.

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.

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 (\ge 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.

MutantXL is an algorithm for solving systems of polynomial equations that was proposed at SCC 2008 and improved in PQC 2008. This article gives an overview over the MutantXL algorithm. It also presents experimental results comparing the behavior of the MutantXL algorithm to the $F_4$ algorithm on HFE and randomly generated multivariate systems. In both cases MutantXL is faster and uses less memory than the Magma's implementation of $F_4$.

In this paper, we present a new algorithm, such that, for the small integer solution (SIS) problem, if the solution is bounded ( by an integer \beta in l_\infty norm, which we call a bounded SIS (BSIS) problem, {\it and if the difference between the row dimension n and the column dimension m of the corresponding matrix is relatively small with respect the row dimension m}, we can solve it easily with a complexity of polynomial in m.