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.

Though the multivariable cryptosystems first suggested by Matsumoto and Imai was defeated by the linearization method of Patarin due to the special properties of the Matsumoto-Imai (MI) cryptosystem, many variants and extensions of the MI system were suggested mainly by Patarin and his collaborators. In this paper, we propose a new variant of the MI system, which was inspired by the idea of “perturbation”. This method uses a set of r (a small number) linearly independent linear functions z_i=∑_{j=1}^n α_{ij}x_j + β_i, i=1,..,r, over the variables x_i , which are variables of the MI system. The perturbation is performed by adding random quadratic function of z i to the MI systems. The difference between our idea and a very similar idea of the Hidden Field Equation and Oil-Vinegar system is that our perturbation is internal, where we do not introduce any new variables, while the Hidden Field Equation and Oil-Vinegar system is an “external” perturbation of the HFE system, where a few extra (external) new variables are introduced to perform the perturbation. A practical implementation example of 136 bits, its security analysis and efficiency analysis are presented. The attack complexity of this perturbed Matsumoto-Imai cryptosystem is estimated.

We use one photon to simulate an n-qubit quantum system for the first time. We propose a new scheme to realize universal quantum computation in polynomial time O(n^5). A generating set of gates can be realized with high accuracy in the lab. We conclude that photonic quantum computation is one of the promising approaches to universal quantum computation.

No abstract uploaded!

We introduce the notions of a path complex and its homologies. Particular cases of path homologies are simplicial homologies and digraph homologies. We state and prove some properties of path homologies, in particular, the K¨unneth formulas for Cartesian product and join, which happen to be true at the level of chain complexes.

This paper proves the local Lipschitz property for harmonic (or positive subharmonic) functions on graphs. An example is also obtained to show that the global Lipschitz property of harmonic function on graphs does not hold.

A self-similar measure on R^n is defined to be a probability measure satisfying \mu = \sum_{j=1}^N p_j\mu\circ S_j^{-1} + \sum_{j=1}^M q_j(\mu*\mu)\circ T_j^{-1}, where S_j x = \rho_j R_j x + b_j, T_j x = \eta_j Q_j x + c_j are contractive similarities, 0 < \rho_j < 1, 0 < \eta_j < 1/2, 0 < p_j < 1, 0 < q_j < 1; \sum_{j=1}^N p_j + \sum_{j=1}^M q_j = 1, R_j, Q_j are orthogonal matrix and \mu*\mu is the convolution of two measures. When M = 0, \mu is a linear self-similar measure, we establish the asymptotic behavior of averages of the derivative of the Fourier transform of \mu, such as \int_{|x|\le R} |(\frac{\partial}{\partial x})^\alpha \hat\mu(x)|^2 dx = O(R^{n-\beta}) for any order derivation of \hat\mu(x) as R\to\infty under certain additional hypotheses. When M > 0, \mu is a nonlinear self-similar measure, we get some results of L^p boundedness for maximal operators of l, from the pointwise asymptotic estimate of the Fourier transform of \mu made by Strichartz.

The problem is concerned about how large (e.g. the Hausdorff dimension) is Whitney's critical set contained in a given fractal. For this, we prove that the Moran arc, an arc containing a Moran set, is a Whitney's critical set. The excellent open set condition is defined, when the condition holds, the associated self-similar set contains a Whitney's critical subset of full dimension. As its application, the Sierpinski gasket and Koch curve have Whitney's critical subset of full dimension. Finally, we provide a self-similar tree which never contains any Whitney's critical set.

We show that if E is an s-regular set in R^2 for which the triple integral \int_E \int_E \int_E c(x, y, z)^{2s} dH^sx dH^sy dH^sz of the Menger curvature c is finite and if 0 < s ≤ 1/2, then H^s almost all of E can be covered with countably many C^1 curves. We give an example to show that this is false for 1/2 <s< 1.

In these notes, we provide an introduction to the hemisphere partition function of 2d (2, 2) supersymmetric gauge theories, and discuss its relation to the “D-brane central charge” which were studied in superstring theory, in 2d supersymmetric quantum field theory, and in topological string theory. We also discuss relation to “macroscopic loop” in matrix models. They are mostly reviews of the work by the authors, but contains some new results such as the partition function for a rotated supersymmetry as well as the differential equations.