We study two-dimensional conformal field theories in the semiclassical limit. In this limit, the four-point function is dominated by intermediate primaries of particular weights along with their descendants, and the crossing equations simplify drastically. For a four-point function receiving sufficiently small contributions from the light primaries, the structure constants involving heavy primaries follow a universal formula. Applying our results to the four-point function of the Z_2 twist field in the symmetric product orbifold, we produce the Hellerman bound and the logarithmically corrected Cardy formula that is valid for h ≥ c/12.

We bootstrap N=(1,0) superconformal field theories in six dimensions, by analyzing the four-point function of flavor current multiplets. Assuming E_8 flavor group, we present universal bounds on the central charge C_T and the flavor central charge C_J . Based on the numerical data, we conjecture that the rank-one E-string theory saturates the universal lower bound on C_J , and numerically determine the spectrum of long multiplets in the rank-one E-string theory. We comment on the possibility of solving the higher-rank E-string theories by bootstrap and thereby probing M-theory on AdS_7×S^4/Z_2.

We study five-dimensional superconformal field theories and their holographic dual, matter-coupled Romans supergravity. On the one hand, some recently derived formulae allow us to extract the central charges from deformations of the supersymmetric five-sphere partition function, whose large N expansion can be computed using matrix model techniques. On the other hand, the conformal and flavor central charges can be extracted from the six-dimensional supergravity action, by carefully analyzing its embedding into type I’ string theory. The results match on the two sides of the holographic duality. Our results also provide analytic evidence for the symmetry enhancement in five-dimensional superconformal field theories.

We consider topological defect lines (TDLs) in two-dimensional conformal field theories. Generalizing and encompassing both global symmetries and Verlinde lines, TDLs together with their attached defect operators provide models of fusion categories without braiding. We study the crossing relations of TDLs, discuss their relation to the ’t Hooft anomaly, and use them to constrain renormalization group flows to either conformal critical points or topological quantum field theories (TQFTs). We show that if certain non-invertible TDLs are preserved along a RG flow, then the vacuum cannot be a non-degenerate gapped state. For various massive flows, we determine the infrared TQFTs completely from the consideration of TDLs together with modular invariance.

There are several attempts to build asymmetric pubic key encryption schemes based on multivariate polynomials of degree two over a finite field. However, most of them are insecure. The common defect in many of them comes from the fact that certain quadratic forms associated with their central maps have low rank, which makes them vulnerable to the MinRank attack. We propose a new simple and efficient multivariate pubic key encryption scheme based on matrix multiplication, which does not have such a low rank property. The new scheme will be called Simple Matrix Scheme or ABC in short. We also propose some parameters for practical and secure implementation.

MIFARE Classic is the world’s most widely deployed RFID (radio-frequency identification) technology. It was claimed to be cryptographically protected by the proprietary Crypto-1 stream cipher. However, it proved inadequate after weaknesses in the design and implementation of Crypto-1 and MIFARE Classic started surfacing since late 2007 [7, 8, 12–17]. Some operators of MIFARE Classic-based systems reacted by upgrading to more secure alternatives such as MIFARE DESFire. However, many (especially in Asia) opted to “patch” MIFARE Classic instead. Their risk analysis might have gone as follows: “The most serious threat comes from efficient card-only attacks, where the attacker only needs an off-the-shelf reader and a PC to tamper a target tag. All efficient card-only attacks depend on certain implementation flaws. Ergo, if we just fix these flaws, we can stop the most serious attacks without an expensive infrastructure upgrade.” One such prominent case is “EasyCard 2.0,” today accepted in Taiwan as a means of electronic payment not only in public transportation but also in convenient stores, drug stores, eateries, cafes, supermarkets, book stores, movie theaters, etc. Obviously, the whole “patching” approach is questionable because Crypto-1 is fundamentally a weak cipher. In support of the proposition, we present a new card-only attack based on state-of-the-art algebraic differential cryptanalytic techniques [1, 2]. Still using the same cheap reader as previous attacks, it takes 2–15 min of computation on a PC to recover a secret key of EasyCard 2.0 after 10–20 h of data collection. We hope the new attack makes our point sufficiently clear, and we urge that all MIFARE-Classic operators with important transactions such as electronic payment upgrade their systems to the more secure alternatives soon.

In this paper, we propose an improved version of the Simple Matrix encryption scheme of PQCrypto2013. The main goal of our construction is to build a system with even stronger security claims. By using square matrices with random quadratic polynomials, we can claim that breaking the system using algebraic attacks is at least as hard as solving a set of random quadratic equations. Furthermore, due to the use of random polynomials in the matrix A, Rank attacks against our scheme are not feasible.

Secure group communication systems have become increasingly important for many emerging network applications. An efficient and robust group key management approach is indispensable to a secure group communication system. Motivated by the theory of hyper-sphere, this paper presents a new group key management approach with a group controller (GC). In our new design, a hyper-sphere is constructed for a group and each member in the group corresponds to a point on the hyper-sphere, which is called the member's private point. The GC computes the central point of the hyper-sphere, intuitively, whose “distance” from each member's private point is identical. The central point is published such that each member can compute a common group key, using a function by taking each member's private point and the central point of the hyper-sphere as the input. This approach is provably secure under the pseudo-random function (PRF) assumption. Compared with other similar schemes, by both theoretical analysis and experiments, our scheme (1) has significantly reduced memory and computation load for each group member; (2) can efficiently deal with massive membership change with only two re-keying messages, i.e., the central point of the hyper-sphere and a random number; and (3) is efficient and very scalable for large-size groups.

This paper introduces a new central trapdoor for multivariate quadratic (MQ) public-key cryptosystems that allows for encryption, in contrast to time-tested MQ primitives such as Unbalanced Oil and Vinegar or Hidden Field Equations which only allow for signatures. Our construction is a mixed-field scheme that exploits the commutativity of the extension field to dramatically reduce the complexity of the extension field polynomial implicitly present in the public key. However, this reduction can only be performed by the user who knows concise descriptions of two simple polynomials, which constitute the private key. After applying this transformation, the plaintext can be recovered by solving a linear system. We use the minus and projection modifiers to inoculate our scheme against known attacks. A straightforward C++ implementation confirms the efficient operation of the public key algorithms.

LWE/RLWE-based cryptosystems require sampling error term from discrete Gaussian distribution. However, some existing samplers are somehow slow under certain circumstances therefore efficiency of such schemes is restricted. In this paper, we introduce a more efficient discretized Gaussian sampler based on ziggurat sampling algorithm. We also analyze statistical quality of our sampler to prove that it can be adopted in LWE/RLWE-based cryptosystems. Compared with ziggurat-based sampler by Buchmann et al. related samplers by Peikert, Ducas et al. and Knuth-Yao, our sampler achieves more than 2x speedup when standard deviation is large. This can benefit constructions rely on noise flooding (e.g., homomorphic encryption). We also present two applications: First, we use our sampler to optimize the RLWE-based authenticated key exchange (AKE) protocol by Zhang et al. We achieve 1.14x speedup on total runtime of this protocol over major parameter choices. Second, we give practical post-quantum Transport Layer Security (TLS) ciphersuite. Our ciphersuite inherits advantages from TLS and the optimized AKE protocol. Performance of our proof-of-concept implementation is close to TLS v1.2 ciphersuites and one post-quantum TLS construction.

In this paper, we show that the signal function used in Ring-Learning with Errors (RLWE) key exchange could leak information to find the secret s of a reused public key p = as+2e. This work is motivated by an attack proposed in [1] and gives an insight into how public keys reused for long term in RLWE key exchange protocols can be exploited. This work specifically focuses on the attack on the KE protocol in [2] by initiating multiple sessions with the honest party and analyze the output of the signal function. Experiments have confirmed the success of our attack in recovering the secret.

The HFEv- signature scheme is one of the most studied multivariate schemes and one of the major candidates for the upcoming standardization of post-quantum digital signature schemes. In this paper, we propose three new attack strategies against HFEv-, each of them using the idea of projection. Especially our third attack is very effective and is, for some parameter sets, the most efficient known attack against HFEv-. Furthermore, our attack requires much less memory than direct and rank attacks. By our work, we therefore give new insights in the security of the HFEv- signature scheme and restrictions for the parameter choice of a possible future standardized HFEv- instance.

In this paper, we first present a theoretical analysis model on the Proof-of-Work (PoW) for cryptocurrency blockchain. Based on this analysis, we present a new type of PoW, which relies on the hardness of solving a set of random quadratic equations over the finite field GF(2). We will present the advantages of such a PoW, in particular, in terms of its impact on decentralization and the incentives involved, and therefore demonstrate that this is a new good alternative as a new type for PoW in blockchain applications.

In this paper, we proposed an idea to construct a general multivariate public key cryptographic (MPKC) scheme based on a user’s identity. In our construction, each user is distributed a unique identity by the key distribution center (KDC) and we use this key to generate user’s private keys. Thereafter, we use these private keys to produce the corresponding public key. This method can make key generating process easier so that the public key will reduce from dozens of Kilobyte to several bits. We then use our general scheme to construct practical identity-based signature schemes named ID-UOV and ID-Rainbow based on two well-known and promising MPKC signature schemes, respectively. Finally, we present the security analysis and give experiments for all of our proposed schemes and the baseline schemes. Comparison shows that our schemes are both efficient and practical.

In this paper, we propose a new algorithm for solving the general approximate common divisors (GACD) problems, which is based on lattice reduction algorithms on certain special lattices and linear equation solving algorithms over integers. Through both theoretical arguments and experimental data, we show that our new algorithm works in polynomial time but under roughly the following condition: \begin{itemize} \item There is a positive integer t such that \frac{\gamma+\eta}{t} + \frac{t}{H} + \rho < \eta; \item We have more than t GACD samples. \end{itemize} or equivalently \begin{itemize} \item H(\eta-\rho)^2 - 4(\gamma+\eta) > 0; \item We have more than t = \lceil\frac{H(\eta-\rho) - \sqrt{H^2(\eta-\rho)^2 - 4H(\gamma+\eta)}{2}\rceil GACD samples. \end{itemize} Here \gamma, \eta and \rho are parameters describing a GACD problem, H = 1/\log_2 F and F is the Hermite Factor. In our experiments, H is shown to be roughly 40 when using the LLL reduction algorithm and it should be around 80 when using Deep or BKZ algorithms. % We use our algorithm to solve concrete problems that no other algorithm could solve before. We show how our algorithm can be applied to attack the fully homomorphic encryption schemes which are based on the general approximate common divisors problem and its limitations.

The antiferromagnetic Heisenberg spin chain of odd spin S is in the Haldane phase with several defining physical properties, such as thermodynamical ground-state degeneracy, symmetry-protected edge states, and nonzero string order parameter. If nonzero hole concentration δ and hole hopping energy t are considered, the spin chain is replaced by a spin-S t-J chain. The motivation of this paper is to generalize the discussions of the Haldane phase to the doped spin chain. The first result of this paper is that, for the model considered here, the \mathbb{Z}_2 sign structure in the usual Ising basis can be totally removed by two consecutive unitary transformations consisting of a spatially local one and a nonlocal one. Direct from the sign structure, the second result of this paper is that the Marshall theorem and the Lieb-Mattis theorem for pure spin systems are generalized to the t-J chain for arbitrary S and δ. A corollary of the theorem provides us with the ground-state degeneracy in the thermodynamic limit. The third result of this paper is about the phase diagram. We show that the defining properties of the Haldane phase survive in the small t/J limit. The large t/J phase supports a gapped spin sector with similar properties (ground-state degeneracy, edge state, and string order parameter) of the Haldane chain, although the charge sector is gapless.

We construct an index for BPS operators supported on a ray in five dimensional superconformal field theories with exceptional global symmetries. We compute the E_n representations (for n = 2, . . . , 7) of operators of low spin, thus verifying that while the expression for the index is only SO(2n − 2) × U(1) invariant, the index itself exhibits the full E_n symmetry (at least up to the order we expanded). The ray operators we studied in 5d can be viewed as generalizations of operators constructed in a Yang-Mills theory with fundamental matter by attaching an open Wilson line to a quark. For n ≤ 7, in contrast to local operators, they carry nontrivial charge under the ℤ_{9 − n}  ⊂ E_n center of the global symmetry. The representations that appear in the ray operator index are therefore different, for n ≤ 7, from those appearing in the previously computed superconformal index. For 3 ≤ n ≤ 7, we find that the leading term in the index is a character of a minuscule representation of E_n . We also discuss the case n = 8, which presents a unique technical challenge, and remains an open problem.

We prove that there does not exist any weak coupling limit in the space of superconformal field theories in five and six dimensions, based on an analysis of the representation theory of the corresponding superconformal algebras. Holographically, this implies that superstring theories on AdS6 and AdS7 do not admit tensionless limits. Finally, we discuss the implications of our result on the existence of an action for coincident M5-branes.

We investigate the non-BPS realm of 3d N=4 superconformal field theory by uniting the non-perturbative methods of the conformal bootstrap and supersymmetric localization, and utilizing special features of 3d N=4 theories such as mirror symmetry and a protected sector described by topological quantum mechanics (TQM). Supersymmetric localization allows for the exact determination of the conformal and flavor central charges, and the latter can be fed into the mini-bootstrap of the TQM to solve for a subset of the OPE data. We examine the implications of the Z_2 mirror action for the SCFT single- and mixed-branch crossing equations for the moment map operators, and apply numerical bootstrap to obtain universal constraints on OPE data for given flavor symmetry groups. A key ingredient in applying the bootstrap analysis is the determination of the mixed-branch superconformal blocks. Among other results, we show that the simplest known self-mirror theory with SU(2)×SU(2) flavor symmetry saturates our bootstrap bounds, which allows us to extract the non-BPS data and examine the self-mirror Z_2 symmetry thereof.

Let G=(V,E) be a locally finite connected weighted graph, and Δ be the usual graph Laplacian. In this article, we study blow-up problems for the nonlinear parabolic equation u_t = Δu + f(u) on G. The blow-up phenomenons for u_t = Δu + f(u) are discussed in terms of two cases: (i) an initial condition is given; (ii) a Dirichlet boundary condition is given. We prove that if f satisfies appropriate conditions, then the corresponding solutions will blow up in a finite time.

No abstract uploaded!

This paper summarizes most of the main developments in the cryptanalysis of multivariate cryptosystems and discuss some problems that remain open. A strong emphasis is put on the symbolic computation tools that have been used to achieve these advances.

In this paper we propose a new multivariate public key encryption scheme named ZHFE. The public key is constructed using as core map two high rank HFE polynomials. The inversion of the public key is performed using a low degree polynomial of Hamming weight three. This low degree polynomial is obtained from the two high rank HFE polynomials, by means of a special reduction method that uses Hamming weight three polynomials produced from the two high rank HFE polynomials. We show that ZHFE is relatively efficient and that it is secure against the main attacks that have threatened the security of HFE. We also propose parameters for a practical implementation of ZHFE.

Okumura proposed a candidate of post-quantum cryptosystem based on Diophantine equations of degree increasing type (DEC). Sizes of public keys in DEC are small, e.g., 1,200 bits for 128 bit security, and it is a strongly desired property in post-quantum erea. In this paper, we propose a polynomial time attack against DEC. We show that the one-wayness of DEC is reduced to finding special (relatively) short vectors in some lattices. The usual LLL algorithm does not work well for finding the most important target vector in our attack. The most technical point of our method is to heuristically find a special norm called a weighted norm to find the most important target vector. We call this method “weighted LLL algorithm” in this paper. Our experimental results suggest that our attack can break the one-wayness of DEC for 128 bit security with sufficiently high probability.

Two post-quantum password-based authenticated key exchange (PAKE) protocols were proposed at CTRSA 2017. Following this work, we give much more efficient and portable C++ implementation of these two protocols. We also choose more compact parameters providing 200-bit security. Compared with original implementation, we achieve 21.5x and 18.5x speedup for RLWE-PAK and RLWE-PPK respectively. Compare with quantum-vulnerable J-PAKE protocol, we achieve nearly 8x speedup. We also integrate RLWE-PPK into TLS to construct a post-quantum TLS ciphersuite. This allows simpler key management, mutual authentication and resistant to phishing attack. Benchmark shows that our ciphersuite is indeed practical