Balanced Oil and Vinegar signature schemes and the unbalanced Oil and Vinegar signature schemes are public key signature schemes based on multivariable polynomials. In this paper, we suggest a new signature scheme, which is a generalization of the Oil-Vinegar construction to improve the efficiency of the unbalanced Oil and Vinegar signature scheme. The basic idea can be described as a construction of multi-layer Oil-Vinegar construction and its generalization. We call our system a Rainbow signature scheme. We propose and implement a practical scheme, which works better than Sflash^{v_2}, in particular, in terms of signature generating time.

We apply internal perturbation [3] to the matrix-type cryptosystems [C_n] and HM constructed in [9]. Using small instances of these variants, we investigate the existence of linearization equations and degree 2 equations that could be used in a XL attack. Our results indicate that these new variants may be suitable for use in practical implementations. We propose a specific instance for practical implementation, and estimate its performance and security.

In ACISP ’00, Wu et al. proposed attacks to break the Polynomial Authentication and Signature Scheme (PASS), in particular, they are able to generate valid authentication transcripts and digital signatures without knowing the private key and any previous transcripts/ signatures. They showed that PASS can be broken with around 238.3 trials. In this paper, we analyze the security of the improved versions of PASS; viz. PASS II and MiniPASS, and extend the Wu et al.’s attacks to PASS II and MiniPASS to break them. Furthermore, we discuss why and how these schemes are broken from the view point of the structure of cryptosystems and point out the fundamental weakness behind.

Though the Perturbed Matsumoto-Imai (PMI) cryptosystem is considered insecure due to the recent differential attack of Fouque, Granboulan, and Stern, even more recently Ding and Gower showed that PMI can be repaired with the Plus (+) method of externally adding as few as 10 randomly chosen quadratic polynomials. Since relatively few extra polynomials are added, the attack complexity of a Gröbner basis attack on PMI+ will be roughly equal to that of PMI. Using Magma’s implementation of the F 4 Gröbner basis algorithm, we attack PMI with parameters q = 2, 0 ≤ r ≤ 10, and 14 ≤ n ≤ 59. Here, q is the number of field elements, n the number of equations/variables, and r the perturbation dimension. Based on our experimental results, we give estimates for the running time for such an attack. We use these estimates to judge the security of some proposed schemes, and we suggest more efficient schemes. In particular, we estimate that an attack using F 4 against the parameters q = 2, r = 5, n = 96 (suggested in [7]) has a time complexity of less than 250 3-DES computations, which would be considered insecure for practical applications.

Hidden field equation (HFE) multivariable cryptosystems were first suggested by Patarin. Kipnis and Shamir showed that to make the cryptosystem secure, a special parameter D of any HFE cryptosystem can not be too small. Consequently Kipnis, Patarin and Goubin proposed an enhanced variant of the HFE cryptosystem by combining the idea of Oil and Vinegar construction with the HFE construction. Essentially they “perturb” the HFE system with some external variables. In this paper, we will first present a new cryptanalysis method for the HFEv schemes. We then use the idea of internal perturbation to build a new cryptosystem, an internally perturbed HFE cryptosystem (IPHFE).

The Matsumoto-Imai (MI) cryptosystem was the first multivariate public key cryptosystem proposed for practical use. Though MI is now considered insecure due to Patarin’s linearization attack, the core idea of MI has been used to construct many variants such as Sflash, which has recently been accepted for use in the New European Schemes for Signatures, Integrity, and Encryption project. Linearization attacks take advantage of the algebraic structure of MI to produce a set of equations that can be used to recover the plaintext from a given ciphertext. In our paper, we present a solution to the problem of finding the dimension of the space of linearization equations, a measure of how much work the attack will require.

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 θ is the Matsumoto-Imai exponent, n is the message length, g = gcd(θ,n), and r is the internal perturbation dimension; or as few as g+10 when g ≠ 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.

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.

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.

The first author constructed a q-parameterized spherical category $\sC$ over C(q) in [Liu15], whose simple objects are labelled by all Young diagrams. In this paper, we compute closed-form expressions for the fusion rule of $\sC$, using Littlewood-Richardson coefficients, as well as the characters (including a generating function), using symmetric functions with infinite variables.

This paper classifies the Grothendieck rings of complex fusion categories of multiplicity one up to rank six. Among 72 possible fusion rings, 25 ones are filtered out by using categorification criteria. Each of the remaining 47 fusion rings admits a unitary complex categorification. We found 6 new Grothendieck rings, categorified by applying a localization approach of the Pentagon Equation.

In this paper, we prove that discrete Morse functions on digraphs are flat Witten-Morse functions and Witten complexes of transitive digraphs approach to Morse complexes. We construct a chain complex consisting of the formal linear combinations of paths which are not only critical paths of the transitive closure but also allowed elementary paths of the digraph, and prove that the homology of the new chain complex is isomorphic to the path homology. On the basis of the above results, we give the Morse inequalities on digraphs.

We study a certain discrete differentiation of piecewise-constant functions on the adjoint of the braid hyperplane arrangement, defined by taking finite-differences across hyperplanes. In terms of Aguiar-Mahajan's Lie theory of hyperplane arrangements, we show that this structure is equivalent to the action of Lie elements on faces. We use layered binary trees to encode flags of adjoint arrangement faces, allowing for the representation of certain Lie elements by antisymmetrized layered binary forests. This is dual to the well-known use of (delayered) binary trees to represent Lie elements of the braid arrangement. The discrete derivative then induces an action of layered binary forests on piecewise-constant functions, which we call the forest derivative. Our main result states that forest derivatives of functions factorize as external products of functions precisely if one restricts to functions which satisfy the Steinmann relations, which are certain four-term linear relations appearing in the foundations of axiomatic quantum field theory. We also show that the forest derivative satisfies the Lie properties of antisymmetry the Jacobi identity. It follows from these Lie properties, and also crucially factorization, that functions which satisfy the Steinmann relations form a left comodule of the Lie cooperad, with the coaction given by the forest derivative. Dually, this endows the adjoint braid arrangement modulo the Steinmann relations with the structure of a Lie algebra internal to the category of vector species. This work is a first step towards describing new connections between Hopf theory in species and quantum field theory.

Let G=(V,E) be a finite weighted graph, and Ω⊆V be a domain such that Ω^∘≠∅. In this paper, we study the following initial boundary problem for the non-homogenous wave equation ∂^2_t u(t,x) − Δ_Ω u(t,x) = f(t,x), (t,x)∈[0,∞)×Ω^∘ u(0,x)=g(x), x∈Ω^∘, ∂_t u(0,x)=h(x), x∈Ω^∘, u(t,x)=0, (t,x)∈[0,∞)×∂Ω, where Δ_Ω denotes the Dirichlet Laplacian on Ω^∘. Using Rothe's method, we prove that the above wave equation has a unique solution.

Graph theory is important in information theory. We introduce a quantization process on graphs and apply the quantized graphs in quantum information. The quon language provides a mathematical theory to study such quantized graphs in a general framework. We give a new method to construct graphical quantum error correcting codes on quantized graphs and characterize all optimal ones. We establish a further connection to geometric group theory and construct quantum low-density parity-check stabilizer codes on the Cayley graphs of groups. Their logical qubits can be encoded by the ground states of newly constructed exactly solvable models with translation-invariant local Hamiltonians. Moreover, the Hamiltonian is gapped in the large limit when the underlying group is infinite.

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.

Let G=(V,E) be a locally finite connected weighted graph, and Ω be an unbounded subset of V. Using Rothe's method, we study the existence of solutions for the semilinear heat equation ∂_t u+|u|^{p−1}⋅u=Δu (p≥1) and the parabolic variational inequality ∫_{Ω^∘} ∂_t u⋅(v−u)dμ ≥ ∫_{Ω^∘} (Δu+f)⋅(v−u)dμ for any v∈H, where H={u∈W^{1,2}(V):u=0 on V∖Ω^∘}.

We give a new type of Schur-Weyl duality for the representations of a family of quantum subgroups and their centralizer algebra. We define and classify singly-generated, Yang-Baxter relation planar algebras. We present the skein theoretic construction of a new parameterized planar algebra. We construct infinitely many new subfactors and unitary fusion categories, and compute their trace formula as a closed-form expression, in terms of Young diagrams.

In this paper, we prove some analogues of Payne-Polya-Weinberger, Hile-Protter and Yang's inequalities for Dirichlet (discrete) Laplace eigenvalues on any subset in the integer lattice $\Z^n.$ This partially answers a question posed by Chung and Oden.

No abstract uploaded!

We introduce fusion bialgebras and their duals and systematically study their Fourier analysis. As an application, we discover new efficient analytic obstructions on the unitary categorification of fusion rings. We prove the Hausdorff-Young inequality, uncertainty principles for fusion bialgebras and their duals. We show that the Schur product property, Young's inequality and the sum-set estimate hold for fusion bialgebras, but not always on their duals. If the fusion ring is the Grothendieck ring of a unitary fusion category, then these inequalities hold on the duals. Therefore, these inequalities are analytic obstructions of categorification. We classify simple integral fusion rings of Frobenius type up to rank 8 and of Frobenius-Perron dimension less than 4080. We find 34 ones, 4 of which are group-like and 28 of which can be eliminated by applying the Schur product property on the dual. In general, these inequalities are obstructions to subfactorize fusion bialgebras.

In this paper, we give a necessary and sufficient condition that discrete Morse functions on a digraph can be extended to be Morse functions on its transitive closure, from this we can extend the Morse theory to digraphs by using quasi-isomorphism between path complex and discrete Morse complex, we also prove a general sufficient condition for digraphs that the Morse functions satisfying this necessary and sufficient condition.

Inspired by the quantum McKay correspondence, we consider the classical ADE Lie theory as a quantum theory over sl2. We introduce anti-symmetric characters for representations of quantum groups and investigate the Fourier duality to study the spectral theory. In the ADE Lie theory, there is a correspondence between the eigenvalues of the Coxeter element and the eigenvalues of the adjacency matrix. We formalize related notions and prove such a correspondence for representations of Verlinde algebras of quantum groups: this includes generalized Dynkin diagrams over any simple Lie algebra g at any level k. This answers a recent comment of Terry Gannon on an old question posed by Victor Kac in 1994.

Let G=(V,E) be a locally finite graph. Firstly, using calculus of variations, including a direct method of variation and the mountain-pass theory, we get sequences of solutions to several local equations on G (the Schrödinger equation, the mean field equation, and the Yamabe equation). Secondly, we derive uniform estimates for those local solution sequences. Finally, we obtain global solutions by extracting convergent sequence of solutions. Our method can be described as a variational method from local to global.