首都大学東京 博士（理学）学位論文（課程博士）
論 文 名
多変数公開鍵暗号系について
著 者
小椋 直樹
審査担当者 主 査 委 員 委 員 委 員
上記の論文を合格と判定する 平成 年 月 日
首都大学東京大学院理工学研究科教授会 研究科長
DISSERTATION FOR A DEGREE OF DOCTOR OF PHILOSOPHY IN SCIENCE
TOKYO METROPOLITAN UNIVERSITY
TITLE：
On Multivariate Public-Key Cryptosystems
AUTHOR：
Naoki Ogura
EXAMINED BY
Examiner in chief
Examiner
Examiner
Examiner
QUALIFIED BY THE GRADUATE SCHOOL OF SCIENCE AND ENGINEERING
TOKYO METROPOLITAN UNIVERSITY
Dean
Date
On Multivariate Public-Key Cryptosystems
Presented by
Naoki Ogura
Supervised by
Assoc. Prof. Shigenori Uchiyama
A dissertation submitted in partial fulfillment of the requirements for the degree of
Doctor of Philosophy in Science
Department of Mathematics and Information Sciences Graduate School of Science and Engineering
Tokyo Metropolitan University
March 2012
Abstract
Nowadays cryptographic technologies are widely used in the information society.
The theme of this paper is public-key cryptosystems (PKCs). PKCs are systems which need two separate keys: a public-key and a secret-key. This system is one of the most powerful tools in modern cryptography. One of the typical applications of PKCs is public-key encryptions, which is a technique for secret communications over public channels. Another is digital signatures, which is a technique for demonstrating the authenticity of a digital messages.
The security of public-key cryptosystems depends on some mathematical problems which are considered as computationally hard. Many mathematicians and computational scientists have been trying to find efficient algorithms for these problems, but in the current condition, these problems cannot be solved efficiently if sizes of involving parameters are large enough. However, it is shown by Shor [76] that a quantum computer can efficiently solve some problems. That is, some cryptosystems including the RSA cryptosystem, which is one of the most famous cryptosystems, would be broken by using quantum computers. Although the computer is not yet up to scratch at the moment, we could not predict when engineers will complete such computers. Therefore, we need to be planning now for the future by looking ahead.
Multivariate Public-Key Cryptosystems (MPKCs) are one of the candidates which resist to the quantum computer. MPKCs are based on the hardness of solving simultaneous multivariate equations over a finite field (ME). The decisional version of ME is in NP-complete and is expected not to be efficiently solvable even if you can use classical (ordinary) and quantum computers. Some MPKCs seem to be suitable for devices with limited computational resources, such as smart cards, PDAs, or active RFID tags.
In this paper, we discuss attacks against four cryptographic schemes related to multivariate equations: SFLASH,ℓIC, Hashimoto-Sakurai, Algebraic Surface Cryptosystem. Also, we propose a new multivariate public-key cryptosystem constructed by using some techniques in affine algebraic geometry.
Though the SFLASH signature scheme [14] was one of the most attrac- tive scheme in MPKC, Dubois et al. [25] proposed a practical attack against
i
SFLASH. We describe a concrete algorithm of an attack against SFLASH. Also, our experimental results show that our attack is efficient.
The ℓIC [23] scheme is proposed by Ding et al. The ℓIC- [23] scheme, which is similar to SFLASH, is also proposed by Ding et al. as one of variants of ℓIC. Fouque et al. [34] proposed an efficient attack against ℓIC by using a Gr¨obner basis algorithm. We propose another practical attack against the ℓIC encryption/signature schemes. Our proposed attack againstℓIC does not employ Gr¨obner basis algorithms, and can be applied to the both even and odd cases.
We show the efficiency of our attack by using some experimental results under the most general condition that a secret-key as a pair of two transformationsS, T is a pair of affine ones. To the best of our knowledge, we for the first time show some experimental results of a practical attack against theℓIC- signature scheme for the even case. Our attack is simpler than an attack using Gr¨obner basis algorithms. Therefore, we estimate the complexity of our attack theoretically.
Hashimoto and Sakurai [43] proposed a new efficient signature scheme, which uses a non-commutative ring. We call this scheme the HS scheme for short. They expected that its noncommutativity makes us difficult to apply known attacks.
Then, we propose an attack against the HS scheme, which is efficient under the condition that its step size and the number of steps are small. Also, we discuss efficiency of our attack with some experimental results. Moreover, we suggest some specific parameters for the HS scheme based on our cryptanalysis.
In 2009, Akiyama, Goto, and Miyake [5] proposed a practical algebraic sur- face cryptosystem, which uses algebraic surfaces. We call it ASC09. Faug´ere et al. [31] proposed an efficient attack against ASC09. We show conditions which guarantee that their attack works well. Also, we show the efficiency of their attack for keys, which are more random than the keys which Faug´ere et al. used.
Moreover, in this paper, we propose a new multivariate public-key cryp- tosystem by applying some techniques in affine algebraic geometry such as wild automorphisms. Wild automorphisms are polynomial automorphisms which are not generated two basic automorphisms: elementary automorphisms and affine automorphisms. Whether wild automorphisms exist or not had been an open problem until 2003. Shestakov and Umirbaev [75] solved this problem by proving the correctness of the famous conjecture proposed by Nagata [53]. The theory of Shestakov-Umirbaev was reconstructed and generalized by Kuroda [49]. In this way, recently mathematicians have been working on problems of old standing in affine algebraic geometry. By contrast, we do not know any example of applying wild automorphisms to cryptography explicitly. So constructing cryptosystems by using affine algebraic geometry can be considered as interesting.
ii
Acknowledgements
The author would like to express my sincere gratitude to my supervisor Asso- ciate Professor Shigenori Uchiyama for his enormous comments and invaluable support throughout my master’s course and doctoral course. The author would also like to deeply thank to Professor Ken Nakamula, who was my supervisor during master’s course, for his kind comments and discussions. The author is deeply grateful to Associate Professor Noboru Kunihiro and Professor Hiro-o Tokunaga for their advices in the examination process.
Toshiyuki Miyazawa gives generous comments and suggestions on the ℓIC scheme. The author extends my gratitude to Dr. Pierre-Alain Fouque for send- ing me his paper. Dr. Yasufumi Hashimoto and Professor Kouichi Sakurai give insightful comments and suggestions on their schemes. Discussions with Chiho Mihara, Dr. Koichiro Akiyama, and Hideyuki Miyake on the algebraic surface cryptosystem have been illuminating. The author would like to express my gratitude to Associate Professor Shigeru Kuroda for his insightful comments and suggestions about affine algebraic geometry. The author would like to thank Dr. Go Yamamoto and Dr. Tetsutaro Kobayashi for constructive comments and discussions. The author would like to thank Dr. Naoki Kanayama and Professor Eiji Okamoto for useful comments and discussions.
The author wants to thank Uchiyama’s and Nakamula’s laboratories and all its members, in particular, Dr. Tetsushi Matsui, Dr. Satoru Tanaka, Dr.
Keiichiro Nishimoto, Shingo Ichiki, and Yasunori Miyamoto. The author also grateful to my family and friends for their tolerances, encouragements and sup- port.
A part of this research was supported by Grant-in-Aid for JSPS Fellows (No.
00236561).
iii
Contents
Abstract i
Acknowledgements iii
1 Introduction 1
1.1 Cryptology . . . . 1
1.2 Encryption Scheme . . . . 2
1.3 Digital Signature . . . . 2
1.4 Post-Quantum Cryptography . . . . 3
1.5 Our Contributions . . . . 4
1.6 Outline . . . . 6
2 The Basic of MPKC 7 2.1 Polynomial Function . . . . 7
2.2 Multivariate Public-Key Cryptosystems . . . . 8
3 General Attack against MPKC 11 3.1 Gr¨obner Basis . . . . 11
3.2 Algebraic Attack . . . . 13
4 SFLASH 15 4.1 MI . . . . 15
4.2 Attack against MI . . . . 17
4.2.1 Preparation . . . . 17
4.2.2 Summary of Attack against MI . . . . 18
4.2.3 Reduction to Linear Transformation . . . . 19
4.2.4 Forging Equation . . . . 20
4.3 SFLASH . . . . 21
4.4 Attack against SFLASH . . . . 22
4.4.1 Summary of Attack against SFLASH . . . . 22
4.4.2 Recovering with Differential . . . . 24 v
4.5 Experimental Result . . . . 25
4.5.1 MI . . . . 25
4.5.2 SFLASH . . . . 26
5 ℓIC 29 5.1 ℓIC . . . . 29
5.2 Attack against ℓIC . . . . 31
5.2.1 Summary of Attack against ℓIC . . . . 32
5.2.2 Linearization Equation . . . . 33
5.3 ℓIC- . . . . 34
5.4 Attack against ℓIC- . . . . 35
5.4.1 Recovering with Differential . . . . 37
5.5 Experimental Result . . . . 37
5.5.1 ℓIC . . . . 38
5.5.2 ℓIC- . . . . 39
6 Hashimoto-Sakurai 41 6.1 Hashimoto-Sakurai . . . . 41
6.2 Attack against Hashimoto-Sakurai . . . . 45
6.2.1 Reduction to Commutative Case . . . . 45
6.2.2 Attack against Commutative Case . . . . 48
6.3 Experimental Results . . . . 50
6.4 Selection of Parameters . . . . 50
7 ASC09 53 7.1 Algebraic Surface Cryptosystem . . . . 53
7.2 ASC09 . . . . 55
7.3 Attack against ASC09 . . . . 58
7.3.1 Mathematical Preliminaries . . . . 58
7.3.2 Summary of Attack against Faug´ere et al. . . . . 59
7.3.3 Correctness for Attack of Faug´ere et al. . . . 60
7.4 Experimental Results . . . . 63
7.4.1 Parameters for Our Experiment . . . . 63
7.4.2 Experimental Results . . . . 64
8 A New Construction of MPKC 67 8.1 Proposed Scheme . . . . 67
8.1.1 Mathematical Preliminaries . . . . 67
8.1.2 Summary of Proposed Scheme . . . . 69
8.1.3 Affine p-derivations . . . . 72
8.1.4 Generating the Kernel . . . . 73 vi
8.1.5 Generating Polynomial Functions . . . . 74 8.2 Composition Inverting Problem . . . . 75
9 Conclusion 77
Bibliography 79
vii
List of Algorithms
4.1 The algorithm of an attack against MI . . . . 19
4.2 The algorithm of an attack against SFLASH . . . . 23
5.1 The algorithm of an attack against odd-IC . . . . 32
5.2 The algorithm of an attack against odd-IC− . . . . 36
6.1 The algorithm of an attack against the r-Rainbow scheme . . . 48
7.1 Level 2 Attack: computing in the field of fractions Fp(t) [31] . . 60
7.2 Level 3 Attack: computing in the finite fields Fp(t)/(Pi) [31] . . 61
ix
List of Tables
4.1 Experimental Results against MI . . . . 26
4.2 Experimental Results against SFLASH . . . . 27
5.1 Experimental Results against odd-IC (over q= 28) . . . . 38
5.2 Experimental Results against even-IC (over q= 2) . . . . 39
5.3 Experimental Results against 3IC- (over q= 28) . . . . 40
5.4 Experimental Results against 2IC- with Linear (over q= 2) . . . 40
6.1 Experimental Results against r-Rainbow . . . . 50
6.2 Experimental Results against r-Rainbow for r= 2, l= 4 . . . . 50
6.3 Specific Parameters for r-Rainbow with N = 65537(≃216) . . . 51 7.1 Experimental Results of an attack of Faug´ere et al. against ASC09 64
xi
Chapter 1 Introduction
Nowadays the technology of cryptography is widely used in the information society. The internet rapidly transfers a large amount of information through global network. A lot of information has been stored on some data storages.
We may be not aware of that even if it includes personal secret information. So we need to protect and control our private data by ourselves. Mathematicians have found one of solutions for this problem by using mathematical tools. It is known as the word “cryptology”.
1.1 Cryptology
Cryptology is the collective term of the techniques how to communicate with- out unintentional actions by third parties. For example, the technique called as encryption enables us to keep privacy in sending private data to intended parties only. Also, the technique of digital signature gives an assurance that a received message is not altered by someone. These will be explained in detail at next two sections. Cryptology is almost considered as encryption until mod- ern times. That is, it was most important to transmit some secret information without leaking out to others. In these days, the presence of internet, which has various capabilities, increases problems on security for rich functionalities, such as electronic voting, electronic auction and digital cash. One of the most important problem is to authenticate the validity of the identity of a person.
One of the solution for the problem is use of digital signature. In this paper, we consider encryption schemes and digital signature schemes only. This is because these are the most basic techniques. Cryptology is the study of not only creating schemes but also threating its security. The former is called as cryptography, while the latter is called as cryptanalysis. Cryptanalysis is important. This is because the toughness of security may be not understood enough by inventers
2 CHAPTER 1. INTRODUCTION of schemes only. If a scheme which has a security hole would be widely used, a number of people might carry a risk of suffering serious damage. So the security of schemes must be checked in a careful manner by various cryptanalysts.
1.2 Encryption Scheme
Encryption is the most typical techniques of cryptography. This is the technique for communicating information to intended parties only. It protects private in- formation from adversaries, who try to steal or tamper that. Encryption can be divisible into two groups according to key type: symmetric-key encryption and public-key encryption. In what follows, we focus attention on public-key encryption only. Let’s assume that you have to communicate some secret mes- sage for an intended receiver over a public channel such as internet. Then, you can perform the following steps.
• A receiver, who receives messages, generates a pair of (e, d) and widely distributes the public key e.
• A sender, who wants to send a message (which is called a plain text) to the receiver, encrypts a message M with e and sends the encrypted messages (which is called the cipher text) C.
• The receiver decrypts C with the secret key d.
This system is called as public-key cryptosystem because the key e is in public.
The public keyeand the cipher textC may be intercepted by an adversary, who wants to illegally obtain the message M. But he could not derive M since d is unknown for him. The public-key cryptosystem has two advantages compared to the symmetric-key cryptosystem. The first is that a key for encrypting a message is easy to send. If you want to share the key with a receiver, only you have to place the key where the receiver can obtain easily such as the public web site or e-mail. The second is that any receivers can use same key. The public key is not responsible for the privacy of communications, while the secret key, that is, a key for decrypting a message, should be kept secret.
1.3 Digital Signature
Digital signature is an application of the technique of public-key encryption.
This is a technique for demonstrating that a message was created by an in- tended party. It prevents adversaries from pretending to be the valid party or tempering the message. Let’s assume that you want to insert signatures to digital documents, you may perform the following steps.
1.4. POST-QUANTUM CRYPTOGRAPHY 3
• A signer, who wants to sign documents, generates a pair of (e, d) and widely distributes the public keye.
• The signer generates a signatureσ for a document M with the secret key dand sends (M, σ).
• A verifier, who wants to verify the signature, checks whether σ is a valid signature with M and e.
Because d is known for only the signer, an adversary, who wants to forge the signature, could not generate any valid signature. The technique of digital signature is often described as as an application of public-key encryption. That is, the secret-key is used as the authentication of the signer, while the public-key is used as the information for checking the signature. Therefore, often public-key encryption and digital signature are discussed in parallel. 1
1.4 Post-Quantum Cryptography
The security of almost all known public-key encryption and digital signature schemes depends on some mathematical problems which are considered as com- putationally hard. For example, the most famous public-key cryptosystem would be the RSA cryptosystem [71], which is based on the problem of factoring large integers, the ElGamal cryptosystem [27], which is based on the difficulty of solv- ing discrete logarithms (of which [18] is the first cryptographic application) and the elliptic curve cryptosystems [51], [48], which is based on the hardness of computing elliptic curve discrete logarithms. Many mathematicians and com- putational scientists have been trying to solve these problems, but in the current condition these problems cannot be solved efficiently if the size of involving pa- rameters are large enough. However, it is shown by Shor [76], Proos and Zalka [70] that the quantum computer can efficiently solve these problems. A quantum computer is a computer which uses quantum mechanical superposition. At the moment the computer is not yet up to scratch. However, we could not predict when engineers will complete quantum computers. Therefore, we need to be planning now for the future by looking ahead. To resist to the quantum com- puter, two cryptographic categories are proposed: quantum cryptography and post-quantum cryptography. Quantum cryptography is techniques for realizing cryptographic tasks with quantum mechanical properties such as superposition, quantum entanglement, and so on. These system must use special devices to im- plement quantum mechanical action. Current implementations seem to be only
1Note that it is possible that we create a digital signature scheme which keeps out of any public-key encryption.
4 CHAPTER 1. INTRODUCTION used for communication between short distance. Then, we do not discuss quan- tum cryptography. Post-quantum cryptography is the inclusive term of crypto- graphic schemes which are believed to resist classical computers and quantum computers. We assume that these schemes can be efficiently implemented in any (classical and quantum) computers. It is considered that most of all symmetric- key encryption schemes are in post-quantum cryptography. So we focus on public-key cryptography. We call post-quantum cryptography on public-key en- cryption schemes as post-quantum public-key cryptosystem (PQPKC). 2 There are the following four PQPKCs:
• Hash-based cryptography
• Code-based cryptography
• Lattice-based cryptography
• Multivariate equations cryptography
Many of these system are related to problems in NP-complete or NP-hard. For example, code-based cryptography is related to syndrome decodings [7]. Lattice- based cryptography is related to the shortest vector problem [80]. Also, multi- variate equations cryptography is related to solving multivariate equations [35].
Such problems are expected not to be efficiently solvable even if you can use clas- sical and quantum computers. Efficient classic/quantum polynomial algorithms for solving these problems are still unknown. In this paper, we confine our attention to multivariate equations cryptography. Multivariate equations cryp- tosystem is widely called as Multivariate Public-Key Cryptosystem (MPKC).
Some schemes in MPKC seem to be suitable for devices with limited computa- tional resources, such as smart cards, PDAs, or active RFID tags. The most computation of schemes in MPKC is simple evaluating polynomials over a finite field. This computation is usually fast, that is, takes only a few millisecond.
Although key size in a scheme in MPKC can be very large, that is, about a few or a few dozens kilobytes, this property is attractive for implementing the scheme in the real world.
1.5 Our Contributions
In this paper, we discuss cryptanalysis against four schemes: SFLASH, ℓIC, Hashimoto-Sakurai, Algebraic Surface Cryptosystem. Although we explain these
2Usually, post-quantum public-key cryptography is simply called as post-quantum cryp- tography for short.
1.5. OUR CONTRIBUTIONS 5 scheme and cryptanalysis for it in detail from the next consecutive sections, we briefly address the differences between our works and related works.
Though the SFLASH scheme [14] was one of the most attractive scheme in MPKC, Dubois et al. [25] proposed a practical attack against SFLASH. But they did not write down their algorithm explicitly. Then, we describe a concrete algorithm of our attack against SFLASH. Also, our experimental results show that our attack is efficient.
The ℓIC [23] scheme is proposed by Ding et al. The ℓIC- scheme, which is similar to SFLASH, is also proposed by Ding et al. as one of the variant ofℓIC.
Fouque et al. proposed an efficient attack against ℓIC by using Gr¨obner basis algorithm. However, they only considered the cryptanalysis under a certain condition; namely, they only considered the case that a secret-key as a pair of two transformations S, T is a pair of linear functions not affine ones. Also, they only explicitly dealt with the odd case, that is, a parameter ℓ is odd, but not the even case; they only implemented their attack in the odd case.
Furthermore, they only estimated the complexity of their attack based on their experimental results. Then, we propose another practical attack against the ℓIC encryption/signature schemes. Our proposed attack against ℓIC does not employ Gr¨obner basis algorithms, and can be applied to the both even and odd cases. We show the efficiency of the attack by using some experimental results under the most general condition that a secret-key as a pair of two transformationsS, T is a pair of affine ones. To the best of our knowledge, we for the first time show some experimental results of a practical attack against the ℓIC- signature scheme for the even case. Our attack is simpler than an attack using Gr¨obner basis algorithms. Therefore, we estimate the complexity of our attack theoretically.
Hashimoto and Sakurai [43] proposed a new efficient signature scheme, which uses a non-commutative ring. They expected that its noncommutativity makes us difficult to apply these attacks. Then, we propose an attack against the HS scheme, which is efficient under the condition that its step size and the number of steps are small. Note that the condition would be preferable for increasing efficiency and reducing the key size. Also, we discuss efficiency of our attack with some experimental results. Moreover, we suggest some specific parameters for the HS scheme based on our cryptanalysis. Note that our attack do not employ the technique of non-commutative schemes such as [72].
The Algebraic Surface Cryptosystems (ASC) [2], [3], [4], [5] is collective term of schemes which use algebraic surfaces. As we explain later, it is considered that ASC is regarded as MPKC. Faug´ere [31] proposed an efficient attack against ASC proposed in 2009 (ASC09). Although they insisted that their attack is correct by using their lemmata, we consider that some gaps between their lemmata and
6 CHAPTER 1. INTRODUCTION their algorithms include. Also, they uses restricted keys in their experiment of their attack. Then, we show conditions which guarantee that their attack works. Also, we show that their attack is efficient for another keys by using our implementation. The keys can be considered as more random than the keys which Faug´ere et al. used.
Moreover, in this paper, we propose a new multivariate public-key cryp- tosystem by applying some techniques in affine algebraic geometry such as wild automorphisms. Wild automorphisms are polynomial automorphisms which are not generated two basic automorphisms: elementary automorphisms and affine automorphisms. Whether wild automorphisms exist or not had been an open problem until 2003. Shestakov and Umirbaev [75] solved this problem by proving the correctness of the famous conjecture proposed by Nagata [53]. The theory of Shestakov-Umirbaev was reconstructed and generalized by Kuroda [49]. In this way, recently mathematicians have been working on problems of old standing in affine algebraic geometry. By contrast, we do not know any example of applying wild automorphisms to cryptography explicitly. So constructing cryptosystems by using affine algebraic geometry can be considered as interesting.
1.6 Outline
The thesis is organized as follows. Following this introduction, we will sum- marize the multivariate public-key cryptosystems. And, in these two sections, we will briefly remind you about a basic idea of multivariate public-key cryp- tosystems (MPKC) and a general attack against MPKC by using Gr¨obner basis.
After this, we will explain the four schemes: SFLASH, ℓIC, Hashimoto-Sakurai, Algebraic Surface Cryptosystem. In these sections, we will explain the construc- tion of these schemes, and discuss cryptanalysis against these schemes. Then, we will discuss a new scheme constructed by the techniques of affine algebraic geometry. Finally, we will conclude this paper.
Chapter 2
The Basic of Multivariate Public Key Cryptosystems
In this chapter, we briefly explain about general basics of multivariate public- key cryptosystems. In what follows, N, Z and Q denote the set of natural numbers, the set of integers, and the rational field, respectively. Also, we write Z≥0 :={0} ∪N.
2.1 Polynomial Function
LetK =Fq be the finite field which is a set ofq ∈Nelements. qshould be some prime power. Let n1 ∈ N be the number of variables, and here x1, x2, . . . , xn1 are variables over K. We denote the set of multivariate polynomials over K as R := K[x1, x2, . . . , xn1]. Let n2 ∈ N be the number of polynomials, and d ∈ N the degree of each polynomials. For λ = (λ1, λ2,· · ·, λn1) ∈ (Z≥0)n, we define as xλ := x1λ1 ·x2λ2· · ·xnλn1. Then, any polynomial function Kn1 7→
Kn2; (x1, x2, . . . , xn)7→(f1(x1, x2, . . . , xn1), f2(x1, x2, . . . , xn1), . . . , fn2(x1, x2, . . . , xn1)) has the following form:
f1 =∑
λ∈Λγλ(1)xλ f2 =∑
λ∈Λγλ(2)xλ ...
fn2 =∑
λ∈Λγλ(n2)xλ ,
where Λ := {(i1, i2, . . . , in1) ∈ (Z≥0)n1 | i1 +i2 +· · ·+in1 ≤ d}, γλ(j) ∈ K for j = 1,2, . . . , n1.
Here we considered the number of terms in f1, f2, . . . , fn2. It is known that the number of monomialsx1i1·x2i2· · ·xn1in1 such thati1, i2, . . . , in1 ≥0, i1+i2+
8 CHAPTER 2. THE BASIC OF MPKC
· · ·+in1 =i is i-multicombination (ori-combination with repetitions) (n1+i−1
i
). So the number of terms fi whose degree is d is as the following 1:
∑d i=0
(n1+i−1 i
)
=
(n1+d d
) .
That is, the size of the function for given parameters K, n1, n2, and d is n2
(n1+d d
)
lgq =O(n2n1dlgq),
where lg := log2 and d≪n1. Note that we may reduce the number of term by using the relation xiq =xi (i = 1,2, . . . , n1). If this relation is used, d must be less or equal to n1(q−1).
In particular, in the case of d= 2, as the following:
f1 =∑
1≤i1≤i2≤nζi(1)1,i2xi1xi2 +∑
1≤i≤n1νi(1)xi+ϵ(1) f2 =∑
1≤i1≤i2≤nζi(2)
1,i2xi1xi2 +∑
1≤i≤n1νi(2)xi+ϵ(2) ...
fn2 =∑
1≤i1≤i2≤n1ζi(n1,i22)xi1xi2 +∑
1≤i≤n1νi(n2)xi+ϵ(n2) ,
where ζi(j)
1,i2, νi(j), ϵ(j)∈K for j = 1,2, . . . , n1. The number of terms is:
{ (n1+2
n1
)= (n1+ 2)(n1+ 1)/2 K ̸=F2
(n1+2
n1
)−n1 =n1(n1+ 1)/2 + 1 K =F2
This function (f1, f2, . . . , fn2) is considered as a one-way function. A one-way function can be efficiently computable for any inputs, but the inverse images is hard to compute efficiently for the image of a random input. In fact, given an image of a random input y = (y1, y2, . . . , yn2), the problem that we find x = (x1, x2, . . . , xn1) such that y = (f1(x), f2(x), . . . , fn2(x)) is equivalent to solving simultaneous Multivariate Equations. The decisional version of Multivariate Equations(ME) is in NP-complete even ifd= 2. So in cryptographic use we can take a degree d as a small value (usually 2).
2.2 Multivariate Public-Key Cryptosystems
We will briefly review about Multivariate public-key cryptosystems. In the sec- tion 2.1, we described polynomial functions whose degree is more or equal to 2 are one-way functions. Then, if we find some polynomial functions are trapdoor
1If you know the homogenization, you can obtain this formula directly.
2.2. MULTIVARIATE PUBLIC-KEY CRYPTOSYSTEMS 9 functions, whose inverse image can be efficiently found by using some secret information, we can construct public-key cryptosystems. Matsumoto and Imai [44] proposed the first MPKC scheme. In the last few decades, there has been enormous amount of work devoted to this area. Most public-key cryptosystems based on the ME problem use a trapdoor function below. For two vector spaces Kn1 and Kn2 over a finite field K =Fq, we construct a public-key as a polyno- mial function P : Kn1 → Kn2. Each scheme has the function F : Kn1 → Kn2 whose inverse images are efficiently computable. This function, which is con- structed by the n2 polynomials with n1 variables, is called “central function.”
We generate a secret-key as a pair of two bijective affine transformations (S,T).
We call these transformations “secret transformations.” Of course, the inverse images of secret transformations is easy to compute if these transformations are known. Finally, the function P = T ◦F ◦ S is made to public. Since it is believed that solving the ME problem is intractable, we may assume that it is difficult to compute an inverse image for the public-key if secret transformations are unknown.
For the encryption scheme use, Alice (a sender) sends a ciphertext C = P(M), where M is a plaintext and P is Bob’s public-key. Bob (a receiver) obtainsM =P−1(C), where P−1 =S−1◦F−1◦T−1. For the signature scheme use, on the other hand, Alice (a signer) generates a signatureσ =P−1(M), where M is a message 2 and P is Alice’s public-key. Bob (a verifier) checks whether M =P(σ) or not. Note that the construction of algebraic surface cryptosystems is completely different to that of it. We describe the scheme in detail at the chapter 7. As I have pointed out, the degree of the polynomial function in many schemes is 2. This means that many schemes should be based on the central function construction. Since the degree of a composition of polynomial functions is usually much higher than the original functions, secret transformations S, T should be affine transformations if the degree of P is 2. MPKC which uses polynomials whose degree is 2 is called as Multivariate Quadratic Public-Key Cryptosystem (MQPKC). Many MQPKCs can be classed as the following types in terms of the central functions:
• MI (Matsumoto-Imai,C∗) [44], [50]
• HFE (Hidden Field Equations) [65]
• UOV (Unbalanced Oil and Vinegar) [66], [47]
• STS (Stepwise Triangular Systems) [41], [85]
2In practice, we usually apply a special compression function called a Hash function to the message.
10 CHAPTER 2. THE BASIC OF MPKC It is considered that the ℓIC scheme is another intermediate class between MI and STS. Also, the Hashimoto-Sakurai (HS) scheme seems to be a new MPKC construction. However, our attack shows that the HS scheme can be regarded as the special case in the intermediate class between UOV and STS.
Although these schemes are efficient, some of them are broken. So some modifiers have been proposed for enforcing schemes against known attacks. For more information about the modifiers, [84] is very useful for us. Ding et al. [23]
recommended three modifiers below for the ℓIC scheme.
• Minus [73]
• Internal Perturbed Plus [65], [19], [21], [20]
• Embedding [23], similar to Fixing [15]
We will describe SFLASH, which is a variation of MI with the minus modifica- tion, and ℓIC-, which is a variation ofℓIC with the minus modification later.
Chapter 3
General Attack against MPKC
In this chapter, we briefly explain about an attack against MPKC by using computations of a Gr¨obner basis.
3.1 Gr¨obner Basis
In this section, we consider that K is a general field, that is, not necessary a finite field. LetR :=K[x1, x2, . . . , xn] be the multivariate polynomial ring inn variables overK. A polynomial is a finite linear combination of monomials with coefficients in K as the following:
f =∑
λ∈Λ
γλxλ,
where γλ ∈ K. For study of polynomials, we give a definition of the famous notion, monomial ordering.
Definition 3.1.1 (monomial order) For the set of monomials
T :={x1e1x2e2· · ·xnen | e1, e2, . . . , en ∈Z≥0},
we call the order ⪯ on T the monomial order if ⪯ satisfies the following three conditions:
• The order ⪯ is a total order.
• For u, v ∈T, if u⪯v, then uw⪯vw for w∈T.
• For allw∈T, 1⪯w.
12 CHAPTER 3. GENERAL ATTACK AGAINST MPKC Now we explain about two famous examples of monomial orders. The first is called as the lexicographic order (Lex). This ordering compares exponents of each variable in monomials in order of increasing until exponents are unbalanced.
The second is called as the graded reverse lexicographic order (Grevlex). This ordering compares first each total degree. If its degrees are equal, then the ordering compares exponents of each variable in monomials in order of decreasing and reverses its outcome. Note that both monomial orders satisfy the following conventional ordering:
x1 ⪰x2 ⪰ · · · ⪰xn .
In what follows, we assume that some monomial ordering is fixed.
For the sake of this definition, we can extend some basic notions in univariate polynomials to multivariate polynomials.
Definition 3.1.2 (leading monomial, leading term, leading coefficient) For a non-zero multivariate polynomial f = ∑
λaλxλ ∈ R, we can find xλm :=
max{xλ ∈Z≥0 |aλ ̸= 0}corresponding to a fixed monomial order. We define the leading monomial of f as LM(f) := xλm. Also, we define the leading coefficient of f as LC(f) := aλm. Moreover, we define the leading term of f as LT(f) :=
LC(f)·LM(f).
Then, we can define the “division of multivariate polynomials”.
Definition 3.1.3 (normal form)
Let G := {g1, g2, . . . , gs} (0 ̸= gi ∈ R) be a finite set of polynomials. For a polynomial f ∈ R, we can find some q1, q2, . . . , qs ∈ R such that either of the following two conditions is satisfied:
• f =∑s
i=1qigi
• LM(gi)̸ | LM(r) ∀i
We call the operation of the computation of r :=f −∑s
i=1qigi as the normal- ization of f by G. We call the “residue” r as the normal form of f by G. We write r as NFG(f).
NFG(f) is not unique in general. This means that we may have results NFG(f)s in different values depending on how to calculate NFG(f). However, NFG(f) can be unique for all f if G is “good”. This notion deduce the following definition.
Definition 3.1.4
For an ideal ∅ ̸= I ⊂ R, an finite subset G ̸= ∅ is a Gr¨obner basis of I if NFG(f) = 0 for all elements f in I.
