ISO/IEC standardizes several chosen ciphertext-secure key encapsulation mechanism (KEM) schemes in ISO/IEC 18033-2. However, all ISO/IEC KEM schemes are not quantum resilient. In this paper, we introduce new isogeny-based KEM schemes (i.e., CSIDH-ECIES-KEM and CSIDH-PSEC-KEM) by modifying Diffie-Hellman-based KEM schemes in ISO/IEC standards. The main advantage of our schemes are compactness. The key size and the ciphertext overhead of our schemes are smaller than these of SIKE, which is submitted to NIST's post-quantum cryptosystems standardization, for current security analyses. Moreover, though SIKE is proved in the classical random oracle model, CSIDH-PSEC-KEM is proved in the quantum random oracle model. Finally, we discuss difficulty to construct isogeny-based KEM from ISO/IEC KEM schemes in the standard model (i.e., ACE-KEM and FACE-KEM).

Multivariate public key cryptosystem (MPKC) is one of the major post quantum cryptosystems (PQC), and the National Institute of Standards and Technology (NIST) recently selected four MPKCs as candidates of their PQC. The security of MPKC depends on the hardness of solving systems of algebraic equations over finite fields. In particular, the multivariate quadratic (MQ) problem is that of solving such a system consisting of quadratic polynomials and is regarded as an important research subject in cryptography. In the Fukuoka MQ challenge project, the hardness of the MQ problem is discussed, and algorithms for solving the MQ problem and the computational results obtained by these algorithms are reported. Algorithms for computing Gröbner basis are used as the main tools for solving the MQ problem. For example, the F4 algorithm and M4GB algorithm have succeeded in solving many instances of the MQ problem provided by the project. In this paper, based on the F4-style algorithm, we present an efficient algorithm to solve the MQ problems with dense polynomials generated in the Fukuoka MQ challenge project. We experimentally show that our algorithm requires less computational time and memory for these MQ problems than the F4 algorithm and M4GB algorithm. We succeeded in solving Type II and III problems of Fukuoka MQ challenge using our algorithm when the number of variables was 37 in both problems.

The security of current public-key cryptosystems relies on the hardness of factoring large integers or solving discrete logarithm problems. However, these mathematical problems can be solved in polynomial time using a quantum computer. This vulnerability has prompted research into post-quantum cryptography using alternative mathematical problems that are secure in the era of quantum computers. In this regard, the National Institute of Standards and Technology (NIST) began to standardize post-quantum cryptography in 2016. In this expository article, we give an overview of recent research on post-quantum cryptography. In particular, we describe the construction and security of multivariate polynomial cryptosystems and lattice-based cryptosystems, which are the main candidates of post-quantum cryptography.

One of major ideas to design a multivariate public key cryptosystem (MPKC) is to generate its quadratic forms by a polynomial map over an extension field. In fact, Matsumoto-Imai's scheme (1988), HFE (Patarin, 1996), MFE (Wang et al., 2006) and multi-HFE (Chen et al., 2008) are constructed in this way and Sflash (Akkar et al., 2003), Quartz (Patarin et al., 2001), Gui (Petzoldt et al, 2015) are variants of these schemes. An advantage of such extension field type MPKCs is to reduce the numbers of variables and equations to be solved in the decryption process. In the present paper, we study the security of MPKCs whose quadratic forms are derived from a “quadratic” map over an extension field and propose a new attack on such MPKCs. Our attack recovers partial information of the secret affine maps in polynomial time when the field is of odd characteristic. Once such partial information is recovered, the attacker can find the plain-text for a given cipher-text by solving a system of quadratic equations over the extension field whose numbers of variables and equations are same to those of the system of quadratic equations used in the decryption process.

In PQCrypto 2013, Yasuda, Takagi and Sakurai proposed a new signature scheme as one of multivariate public key cryptosystems (MPKCs). This scheme (called YTS) is based on the fact that there are two isometry classes of non-degenerate quadratic forms on a vector space with a prescribed dimension. The advantage of YTS is its efficiency. In fact, its signature generation is eight or nine times faster than Rainbow of similar size. For the security, it is known that the direct attack, the IP attack and the min-rank attack are applicable on YTS, and the running times are exponential time for the first and the second attacks and sub-exponential time for the third attack. In the present paper, we give a new attack on YTS whose approach is to use the diagonalization of matrices. Our attack works in polynomial time and it actually recovers equivalent secret keys of YTS having 140-bits security against min-rank attack in around fifteen seconds.

Rainbow is one of signature schemes based on the problem solving a set of multivariate quadratic equations. While its signature generation and verification are fast and the security is presently sufficient under suitable parameter selections, the key size is relatively large. Recently, Quaternion Rainbow — Rainbow over a quaternion ring — was proposed by Yasuda, Sakurai and Takagi (CT-RSA'12) to reduce the key size of Rainbow without impairing the security. However, a new vulnerability emerges from the structure of quaternion ring; in fact, Thomae (SCN'12) found that Quaternion Rainbow is less secure than the same-size original Rainbow. In the present paper, we further study the structure of Quaternion Rainbow and show that Quaternion Rainbow is one of sparse versions of the Rainbow. Its sparse structure causes a vulnerability of Quaternion Rainbow. Especially, we find that Quaternion Rainbow over even characteristic field, whose security level is estimated as about the original Rainbow of at most 3/4 by Thomae's analysis, is almost as secure as the original Rainbow of at most 1/4-size.

It is well known that solving randomly chosen Multivariate Quadratic equations over a finite field (MQ-Problem) is NP-hard, and the security of Multivariate Public Key Cryptosystems (MPKCs) is based on the MQ-Problem. However, this problem can be solved efficiently when the number of unknowns n is sufficiently greater than that of equations m (This is called “Underdefined”). Indeed, the algorithm by Kipnis et al. (Eurocrypt'99) can solve the MQ-Problem over a finite field of even characteristic in a polynomial-time of n when n ≥ m(m+1). Therefore, it is important to estimate the hardness of the MQ-Problem to evaluate the security of Multivariate Public Key Cryptosystems. We propose an algorithm in this paper that can solve the MQ-Problem in a polynomial-time of n when n ≥ m(m+3)/2, which has a wider applicable range than that by Kipnis et al. We will also compare our proposed algorithm with other known algorithms. Moreover, we implemented this algorithm with Magma and solved the MQ-Problem of m=28 and n=504, and it takes 78.7 seconds on a common PC.

The security of pairing-based cryptosystems is determined by the difficulty of solving the discrete logarithm problem (DLP) over certain types of finite fields. One of the most efficient algorithms for computing a pairing is the ηT pairing over supersingular curves on finite fields of characteristic 3. Indeed many high-speed implementations of this pairing have been reported, and it is an attractive candidate for practical deployment of pairing-based cryptosystems. Since the embedding degree of the ηT pairing is 6, we deal with the difficulty of solving a DLP over the finite field GF(36n), where the function field sieve (FFS) is known as the asymptotically fastest algorithm of solving it. Moreover, several efficient algorithms are employed for implementation of the FFS, such as the large prime variation. In this paper, we estimate the time complexity of solving the DLP for the extension degrees n=97, 163, 193, 239, 313, 353, and 509, when we use the improved FFS. To accomplish our aim, we present several new computable estimation formulas to compute the explicit number of special polynomials used in the improved FFS. Our estimation contributes to the evaluation for the key length of pairing-based cryptosystems using the ηT pairing.

The multivariate public key cryptosystem (MPKC), which is based on the problem of solving a set of multivariate systems of quadratic equations over a finite field, is expected to be secure against quantum attacks. Although there are several existing schemes in MPKC that survived known attacks and are much faster than RSA and ECC, there have been few discussions on security against physical attacks, aside from the work of Okeya et al. (2005) on side-channel attacks against Sflash. In this study, we describe general fault attacks on MPKCs including Big Field type (e.g. Matsumoto-Imai, HFE and Sflash) and Stepwise Triangular System (STS) type (e.g. UOV, Rainbow and TTM/TTS). For both types, recovering (parts of) the secret keys S,T with our fault attacks becomes more efficient than doing without them. Especially, on the Big Field type, only single fault is sufficient to recover the secret keys.

NTRU is a public key cryptosystem based on hard problems over lattices. In this paper, we present efficient methods for convolution product computation which is a dominant operation of NTRU. The new methods are based on the observation that repeating patterns in coefficients of an NTRU polynomial can be used for the construction of look-up tables, which is a similar approach to the sliding window methods for exponentiation. We provide efficient convolution algorithms to implement this idea, and we make a comprehensive analysis of the complexity of the new algorithms. We also give software implementations over a Pentium IV CPU, a MICAz mote, and a CUDA-based GPGPU platform. According to our analyses and experimental results, the new algorithms speed up the NTRU encryption and decryption operations by up to 41%.

Pairings on elliptic curves over finite fields are crucial for constructing various cryptographic schemes. The ηT pairing on supersingular curves over GF(3n) is particularly popular since it is efficiently implementable. Taking into account the Menezes-Okamoto-Vanstone attack, the discrete logarithm problem (DLP) in GF(36n) becomes a concern for the security of cryptosystems using ηT pairings in this case. In 2006, Joux and Lercier proposed a new variant of the function field sieve in the medium prime case, named JL06-FFS. We have, however, not yet found any practical implementations on JL06-FFS over GF(36n). Therefore, we first fulfill such an implementation and we successfully set a new record for solving the DLP in GF(36n), the DLP in GF(36·71) of 676-bit size. In addition, we also compare JL06-FFS and an earlier version, named JL02-FFS, with practical experiments. Our results confirm that the former is several times faster than the latter under certain conditions.

Shi-Hui et al. proposed a new public key cryptosystem using ergodic binary matrices. The security of the system is derived from some assumed hard problem based on ergodic matrices over GF(2). In this note, we show that breaking this system, with a security parameter n (public key of length 4n2 bits, secret key of length 2n bits and block length of length n2 bits), is equivalent to solving a set of n4 linear equations over GF(2) which renders this system insecure for practical choices of n.

Since the Merkle-Damgård hash function (denoted by MDFH) that uses a fixed input length random oracle as a compression function is not indifferentiable from a random oracle (denoted by RO) due to the extension attack, there is no guarantee for the security of cryptosystems, which are secure in the RO model, when RO is instantiated with MDHF. This fact motivates us to establish a criteria methodology for confirming cryptosystems security when RO is instantiated with MDHF. In this paper, we confirm cryptosystems security by using the following approach: 1.Find a weakened random oracle (denoted by WRO) which leaks values needed to realize the extension attack. 2.Prove that MDHF is indifferentiable from WRO. 3.Prove cryptosystems security in the WRO model. The indifferentiability framework of Maurer, Renner and Holenstein guarantees that we can securely use the cryptosystem when WRO is instantiated with MDHF. Thus we concentrate on such finding WRO. We propose Traceable Random Oracle (denoted by TRO) which leaks values enough to permit the extension attack. By using TRO, we can easily confirm the security of OAEP encryption scheme and variants of OAEP encryption scheme. However, there are several practical cryptosystems whose security cannot be confirmed by TRO (e.g. RSA-KEM). This is because TRO leaks values that are irrelevant to the extension attack. Therefore, we propose another WRO, Extension Attack Simulatable Random Oracle (denoted by ERO), which leaks just the value needed for the extension attack. Fortunately, ERO is necessary and sufficient to confirm the security of cryptosystems under MDHF. This means that the security of any cryptosystem under MDHF is equivalent to that under the ERO model. We prove that RSA-KEM is secure in the ERO model.

Many knapsack cryptosystems have been proposed but almost all the schemes are vulnerable to lattice attack because of their low density. To prevent the lattice attack, Chor and Rivest proposed a low weight knapsack scheme, which made the density higher than critical density. In Asiacrypt2005, Nguyen and Stern introduced pseudo-density and proved that if the pseudo-density is low enough (even if the usual density is not low enough), the knapsack scheme can be broken by a single call to SVP/CVP oracle. However, the usual density and the pseudo-density are not sufficient to measure the resistance to the lattice attack individually. In this paper, we first introduce the new notion of density D, which naturally unifies the previous two density. Next, we derive conditions for our density so that a knapsack scheme is secure against lattice attack. We obtain a critical bound of density which depends only on the rate of the message length and its Hamming weight. Furthermore, we show that if D<0.8677, the knapsack scheme is solved by lattice attack. Next, we show that the critical bound goes to 1 if the Hamming weight decreases, which means that it is (almost) impossible to construct a low weight knapsack scheme which is supported by an argument of density.

In this paper, we suggest that all pairings are in a group from an abstract angle. Based on the results, some new pairings with the short Miller loop are constructed for great efficiency. It is possible that our observation can be applied into other aspects of pairing-based cryptosystems.

Scalar multiplication methods using the Frobenius maps are known for efficient methods to speed up (hyper)elliptic curve cryptosystems. However, those methods are not efficient for the cryptosystems constructed on fields of small extension degrees due to costs of the field operations. Iijima et al. showed that one can use certain automorphisms on the quadratic twists of elliptic curves for fast scalar multiplications without the drawback of the Frobenius maps. This paper shows an extension of the automorphisms on the Jacobians of hyperelliptic curves of arbitrary genus.

This paper proposes a Weil descent attack against elliptic curve cryptosystems over quartic extension fields. The scenario of the attack is as follows: First, one reduces a DLP on a Weierstrass form over the quartic extention of a finite field k to a DLP on a special form, called Scholten form, over the same field. Second, one reduces the DLP on the Scholten form to a DLP on a genus two hyperelliptic curve over the quadratic extension of k. Then, one reduces the DLP on the hyperelliptic curve to one on a Cab model over k. Finally, one obtains the discrete-log of original DLP by applying the Gaudry method to the DLP on the Cab model. In order to carry out the scenario, this paper shows that many of elliptic curve discrete-log problems over quartic extension fields of odd characteristics are reduced to genus two hyperelliptic curve discrete-log problems over quadratic extension fields, and that almost all of the genus two hyperelliptic curve discrete-log problems over quadratic extension fields of odd characteristics come under Weil descent attack. This means that many of elliptic curve cryptosystems over quartic extension fields of odd characteristics can be attacked uniformly.

Koblitz curves belong to a special class of binary curves on which the scalar multiplication can be computed very efficiently. For this reason, they are suitable candidates for implementations on low-end processors. However, such devices are often vulnerable to side channel attacks. In this paper, we propose a new countermeasure against side channel attacks on Koblitz curves, which utilizes a fixed-pattern recoding to defeat simple power analysis. We show that in practical cases, the recoding can be performed from left to right, and can be easily stored or even randomly generated.

Elliptic curves offer interesting possibilities for alternative cryptosystems, especially in constrained environments like smartcards. However, cryptographic routines running on such lightweight devices can be attacked with the help of "side channel information"; power consumption, for instance. Elliptic curve cryptosystems are not an exception: if no precaution is taken, power traces can help attackers to reveal secret information stored in tamper-resistant devices. Okeya-Takagi scheme (OT scheme) is an efficient countermeasure against such attacks on elliptic curve cryptosystems, which has the unique feature to allow any size for the pre-computed table: depending on how much memory is available, users can flexibly change the table size to fit their needs. Since the nature of OT scheme is different from other side-channel attack countermeasures, it is necessary to deeply investigate its security. In this paper, we present a comprehensive security analysis of OT scheme, and show that based on information leaked by power consumption traces, attackers can slightly enhance standard attacks. Then, we explain how to prevent such information leakage with simple and efficient modifications.

Non-supersingular elliptic curves are important for the security of pairing-based cryptosystems. But there are few suitable non-supersingular elliptic curves for pairing-based cryptosystems. This letter introduces a method which allows the existing method to generate more non-supersingular elliptic curves suitable for pairing-based cryptosystems when the embedding degree is 6.