Mathematical Modelling for Next-Generation Cryptography

This paper presents a survey on the multivariate public key cryptosystem (MPKC), which is a public key cryptosystem whose public key is a set of multivariate quadratic forms over a finite field.

We present a survey of recent results in the area of zero-knowledge (ZK) protocols based on coding problems and the related Learning Parities with Noise (LPN) problem. First, we sketch the constructions of two ZK code-based identification schemes: the one based on general decoding by Jain et al. (Asiacrypt 2012) and the one based on syndrome decoding by Stern (Crypto 1993). Next, we show that these two systems can also be used to implement a proof of plaintext knowledge for the code-based public key encryption schemes: the one by McEliece and the one by Niederreiter, respectively. Finally, we briefly discuss verifiable encryption and digital signatures as applications.

Cayley hash functions are a family of cryptographic hash functions constructed from Cayley graphs, with appealing properties such as a natural parallelism and a security reduction to a clean, well-defined mathematical problem. As this problem involves non-Abelian groups, it is a priori resistant to quantum period finding algorithms and Cayley hash functions may therefore be a good foundation for post-quantum cryptography. Four particular parameter sets for Cayley hash functions have been proposed in the past, and so far dedicated preimage algorithms have been found for all of them. These algorithms do however not seem to extend to generic parameters, and as a result it is still an open problem to determine the security of Cayley hash functions in general. In this chapter, we introduce how to design hash functions based on Ramanujan graphs, which can be considered as an optimal expander graphs in a sense of qualities of transmission network schemes. We introduce a polynomial time preimage attack against Cayley hash functions based on two explicit Ramanujan graphs. We suggest some possible ways to construct the Cayley hash functions that may not be affected by this type of attacks as open problems, which can contribute to a better understanding of the hard problems underlying the security of Cayley hash functions.

In this paper, we analyze and reexamine the key lengths of the pairings on the hyperelliptic curves of genus 2 and considering the estimated run time of the (special) extended tower number field sieve. Pairing-based cryptosystems have become a major research topic in cryptography and have attracted more attention because of the increasing interest in the efficient and functional cryptographic protocols, e.g., functional encryption. Recently, the algorithm of number field sieve and its variants have made progress, and it is urgently necessary to estimate key lengths of pairings taking into account of impact of the algorithms. We report the detailed computational cost of the pairings on the Kawazoe–Takahashi curves of genus 2, and give the comparison of our pairing and the pairing on the BLS24 elliptic curves at the 192-bit security level. The estimated cost of our pairing is approximately 2.5 times more than the cost of the BLS24 pairing.

We summarize efficient isogeny sequence computations on elliptic and genus 2 Jacobians. For cryptographic purposes, sequences of low-degree isogenies are important. Then we focus on sequences of 2- and 3-isogenies on elliptic curves and (2, 2)- and (3, 3)-isogenies on genus 2 Jacobians. Our aim is to explicitly describe the low-degree isogeny sequence computations and improve them for cryptographic applications such as post-quantum cryptosystems and random self-reducibility of discrete logarithm problem (DLP).

The aim of this article is to investigate certain family of (so-called constraint) polynomials which determine the quasi-exact spectrum of the asymmetric quantum Rabi model. The quantum Rabi model appears ubiquitously in various quantum systems and its potential applications include quantum computing and quantum cryptography. In (Wakayama, Symmetry of Asymmetric Quantum Rabi Models) [30], using the representation theory of the Lie algebra \(\mathfrak {sl}_2\), we presented a picture of the asymmetric quantum Rabi model equivalent to the one drawn by confluent Heun ordinary differential equations. Using this description, we proved the existence of spectral degeneracies (level crossings in the spectral graph) of the asymmetric quantum Rabi model when the symmetry-breaking parameter \(\varepsilon \) equals \(\frac{1}{2}\) by studying the constraint polynomials, and conjectured a formula that ensures the presence of level crossings for general \(\varepsilon \in \frac{1}{2}\mathbb {Z}\). These results on level crossings generalize a result on the degenerate spectrum, given first by Kuś in 1985 for the (symmetric) quantum Rabi model. It was demonstrated numerically by Li and Batchelor in 2015, investigating an earlier empirical observation by (Braak, Phys. Rev. Lett. 107, 100401–100404, 2011) [3]. In this paper, although the proof of the conjecture has not been obtained, we deepen this conjecture and give insights together with new formulas for the target constraint polynomials.

Graphs with large isoperimetric constants play an important role in cryptography because one can utilize such graphs to construct cryptographic hash functions. Ramanujan graphs are important optimal examples of such graphs, and known explicit construction of infinite families of Ramanujan graphs are given by Cayley graphs. A group–subgroup pair graph, which is a generalization of a Cayley graph, is defined for a given triplet consisting of finite group, its subgroup, and a suitable subset of the group. We study the spectra, that is the eigenvalues of the adjacency operators, of such graphs. In fact, we give an explicit formula of the eigenvalues of such graphs when the corresponding subgroups are abelian in terms of the characters of the subgroups as well as give a lower bound estimation for the second largest eigenvalues.

Ramanujan graphs are graphs which have many connections with various mathematical fields including an application to the cryptography. In this article, as a continuous work of our research on Ramanujan graphs, we investigate the bound of the valency of the Cayley graphs of the generalized quaternion groups which guarantees to be Ramanujan. As is the cases of the cyclic and dihedral groups, we show that the determination of the bound in a special setting is related to the classical Hardy–Littlewood conjecture for primes represented by a quadratic polynomial.

In this paper, we investigate the problems of uniform random number generation, independent uniform random number generation, and secret key agreement, which provide the information theoretic security. We consider the strong uniformity and strong independence, where it has been unclear whether or not sparse matrices can be applied to these problems for general (correlated) sources with respect to these criteria. To prove the theorems, we first introduce the notion of the balanced-coloring property and the collision-resistance property. We next apply these properties to the problems. Since an ensemble of sparse matrices (with logarithmic column weight) over a finite field satisfies these properties, we can construct a code achieving the fundamental limits by using sparse matrices.

In this paper, we discuss how to recover the RSA secret key from a noisy version of the secret key obtained through physical attacks such as cold boot and side channel attacks. For example, consider a cold boot attack to extract the RSA secret key stored in the memory. The attacker can obtain a degraded version of the secret key so that some bits are erased. In principle, if many erasures occur, the key recovery for the secret key becomes rather difficult. To date, many noise models other than the erasure model have been introduced. For the discrete noise case, the binary erasure model, binary error model, and binary erasure and error model have been introduced. Effective algorithms have been proposed for each noise model, and the conditions for noise which the original secret key can be recovered in polynomial time have been derived. Research has also been conducted on models that can obtain continuous leakage. In this case, several algorithms have been proposed according to the degree of knowledge of the leakage model. Many studies have been conducted on by taking heuristic approaches. In this paper, we provide a survey of existing research and then attempt to explain it within a unified framework.

Recently, the learning with errors (LWE) problem has become a central building block to construct modern schemes in lattice-based cryptography. The security of such schemes relies on the hardness of the LWE problem. In particular, LWE-based cryptography has been paid attention as a candidate of post-quantum cryptography. In 2015, Laine and Lauter analyzed a key recovery attack against the search variant of the LWE problem. Their analysis is based on a generalization of the Boneh–Venkatesan method for the hidden number problem to the LWE problem. They adopted the LLL algorithm and Babai’s nearest plane method in the attack, and they also demonstrated a successful range of the attack by experiments for hundreds of LWE instances. In this paper, we give a simple analysis of the attack. While Laine and Lauter’s analysis gives explicit information about the effective approximation factor in the LLL algorithm and Babai’s nearest plane method, our analysis is useful to estimate which LWE instances can be solved by the key recovery attack.

Lattice-based cryptography is based on the hardness of the lattice problems, e.g., the shortest vector problem and the closed vector problem. In fact, these mathematical optimization problems are known to be NP-hard. Our interest is to know how large-scale shortest vector problems can be solved. For this, we provide a mixed integer quadratic programming formulation for the shortest vector problem and propose a technique to restrict the search space of the shortest vector problem. This approach is a potential technique to improve the performance of the state-of-the-art software for mixed integer programming problems. In fact, we observe that this technique improves the numerical performance for TU Darmstadt’s benchmark instances with the dimension up to 49.

This article is a survey on upper and lower bounds of Dirichlet L-functions \(L(s,\chi )\) associated with Dirichlet characters \(\chi \) at \(s=1\). We give proofs of well-known upper and lower bounds of \(L(1, \chi )\) to let the reader know the difficulty of giving (lower) bounds of \(L(1,\chi )\). In the last part, we also review some explicit upper and lower bounds of Dirichlet L-functions which will be applied to security analysis of ideal lattice-based cryptography for cyclotomic fields explained in Part 2 (S. Okumura, On analysis of recovering short generator problems via upper and lower bounds of Dirichlet L-functions : Part 2 [20]).

In recent years, some fully homomorphic encryption schemes and cryptographic multilinear maps have been constructed by using short generators and ideal lattices arising from \(2^k\)th cyclotomic fields. Moreover, these systems are expected to have resistance to the attacks by quantum computers. The security of some of such cryptosystems depends on the principal ideal problem (PIP) and the recovering short generator problem (RSGP). Biasse and Song showed a quantum algorithm solving PIP on arbitrary number fields in polynomial time under GRH. On the other hand, Campbell et al. explain an algorithm solving RSGP on \(2^k\)th cyclotomic fields. Their algorithm is analyzed independently by Cramer, Ducas, Peikert and Regev/Okumura, Sugiyama, Yasuda and Takagi. Their analyses suggest that RSGP on \(2^k\)th cyclotomic fields is solved easily for practical parameters, and that cryptosystems of which the security is based on PIP and RSGP may not be post-quantum cryptosystems. Important tools in their analyses are upper and lower bounds of special values of Dirichlet L-functions at 1. In this paper, we give a survey on their analyses and explain some cryptographic and number theoretic open problems on RSGP.

In 1996, Coppersmith proposed a lattice-based method to solve the small roots of a univariate modular equation in polynomial time. Since its invention, Coppersmith’s method has become an important tool in the cryptanalysis of RSA crypto algorithm and its variants. In 2006, Jochemsz and May introduced a general strategy to solve small roots of any form of multivariate modular equations in polynomial time. Based on Jochemsz–May’s strategy, for any given multivariate equations one can easily construct the desired lattices with triangular matrix basis. However, for some attacks, Jochemsz–May’s general strategy could not fully capture the algebraic structure of the target polynomials. Thus, some sophisticated techniques that can deeply exploit the algebraic relations have been proposed. In this paper, we give a survey of these recent approaches for lattice constructions, and also give small examples to show how these approaches work.

We give a survey on generic transformations that strengthen the security of signature schemes, which are exploited in most cryptographic protocols, in the leakage models. In ProvSec 2014, Wang and Tanaka proposed a transformation which converts weakly existentially unforgeable signature schemes into strongly existentially unforgeable ones in the bounded leakage model. To obtain the construction, they combined a leakage resilient chameleon hash function with the Generalized Boneh–Shen–Waters (GBSW) transformation proposed by Steinfeld, Pieprzyk, and Wang. In ACISP 2015, Wang and Tanaka proposed another transformation in the continual leakage model. To achieve the goal, they defined a continuous leakage resilient (CLR) chameleon hash function and constructed it based on the CLR signature scheme proposed by Malkin, Teranishi, Vahlis, and Yung. Then they improved the GBSW transformation by making use of the Groth–Sahai proof system and then combine it with CLR chameleon hash functions. In Security and Communication Networks, Wang and Tanaka additionally gave an instantiation of (restricted) fully leakage resilient strong one-time signature based on leakage resilient chameleon hash functions, following the construction of strong one-time signature by Mohassel. They also proved that by combining a (restricted) fully leakage resilient strong one-time signature scheme with the transformation proposed by Huang, Wong, and Zhao, another transformation that can strengthen the security of fully leakage resilient signature schemes without changing signing keys can be obtained.

Homomorphic encryption allows a user to receive encrypted data and to perform arbitrary computation on that data without decrypting it. The homomorphic encryption scheme which supports only a bounded number of homomorphic operations is called “somewhat homomorphic encryption”. The scheme which supports arbitrary number of homomorphic operations is called “fully homomorphic encryption”. We need to construct an fully homomorphic encryption scheme which satisfies strong security for practical use to use a homomorphic encryption scheme practically, but essentially, we cannot construct a scheme which satisfies IND-CCA2 security Thus, one of the strongest security notions for homomorphic encryption is IND-CCA1 security. In this paper, we construct an fully homomorphic encryption scheme which satisfies IND-CCA1 security. Our construction has a restriction that our scheme can compute an arbitrary number of operations, but the arity of circuits is bounded. Our construction is based on the leakage-resilient bounded arity fully homomorphic encryption scheme proposed by Berkoff and Liu (TCC 2014). We show that their general construction can work for our construction.