We prove that a random map drawn from any class \mathfrak{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 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.

No abstract uploaded!

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. 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 very fast to derive an equivalent private key, and it requires only a few seconds on a standard PC.

The ideal anti-Zeno effect means that a perpetual observation leads to an immediate disappearance of the unstable system. We present a straightforward way to derive sufficient conditions under which such a situation occurs expressed in terms of the decaying states and spectral properties of the Hamiltonian. They show, in particular, that the gap between Zeno and anti-Zeno effects is in fact very narrow.

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.