The Secure Parameters and Efficient Decryption Algorithm for Multivariate Public Key Cryptosystem EFC ∗

PAPER Special Section on Discrete Mathematics and Its Applications

The Secure Parameters and Efficient Decryption Algorithm for Multivariate Public Key Cryptosystem EFC ^∗

Yacheng WANG^†a),Nonmember, Yasuhiko IKEMATSU^†b),Member, Dung Hoang DUONG^††c),Nonmember, andTsuyoshi TAKAGI^†d),Member

SUMMARY At PQCrypto 2016, Szepieniec et al. proposed a new type of trapdoor called Extension Field Cancellation (EFC) for construct- ing secure multivariate encryption cryptosystems. They also specifically suggested two schemes EFC⁻p and EFC⁻_{p t2} that apply this trapdoor and some modifiers. Although both of them seem to avoid all attacks used for cryptanalysis on multivariate cryptography, their decryption efficiency has room for improvement. On the other hand, their security was analyzed mainly through an algebraic attack of computing the Gröbner basis of the public key, and there possibly exists more effective attacks. In this paper, we introduce a more efficient decryption approach for EFC⁻pand EFC⁻_{p t2}, which manages to avoid all redundant computation involved in the original decryption algorithms without altering their public key. In addition, we estimate the secure parameters for EFC⁻p and EFC⁻_{p t2} through a hybrid attack of algebraic attack and exhaustive search.

key words: multivariate cryptography, extension field cancellation, de- cryption algorithm, hybrid attack

1. Introduction

Ever since Shor [20] introduced a polynomial-time algo- rithm in 1994 for solving the integer factorization problem and the discrete logarithm problem on quantum computers, on which currently used public key cryptosystems such as RSA and ECC are based, cryptology community has been re- searching on finding alternative cryptosystems that are quan- tum resistant (Post-quantum cryptography). Specially, the National Institute of Standards and Technology (NIST) in the United States is calling for post-quantum cryptosystems (PQC) proposals to be standardized, the National Security Agency (NSA) also announced their plan for switching to quantum resistant public key cryptosystems in the future.

Multivariate cryptography is considered as one of the main candidates for post-quantum cryptography because the security of multivariate cryptography is based on the hard- ness of the problem of solving a set of multivariate quadratic

Manuscript received September 25, 2018.

Manuscript revised January 25, 2019.

†The authors are with the Graduate School of Information Sci- ence and Technology, The University of Tokyo, Tokyo, 113-8656 Japan.

††The author is with the School of Computing and Information Technology, University of Wollongong, NSW 2522, Australia.

∗The preliminary version of this paper was presented at 23rd Australasian Conference on Information Security and Privacy[23].

a) E-mail: [email protected] b) E-mail: [email protected] c) E-mail: [email protected]

d) E-mail: [email protected] DOI: 10.1587/transfun.E102.A.1028

polynomials, which was proven to be NP-complete, and mul- tivariate cryptography is in general very efficient and re- quires very modest computational resources. In more than 30 years of research on multivariate cryptography, results on constructing signature schemes seem to be more fruit- ful, UOV[15]and Rainbow[7] remains secure after many years of attack attempts. On the other hand, history on mul- tivariate encryption is more turbulent. Many multivariate encryption schemes have been proposed, such as MI[16], HFE [18], ABC [22], ZHFE [19], SRP [24], EFC [21], HFERP[13]and EFLASH[3]. Most of them were proven to be insecure under various attacks, such as MinRank[12], HighRank[4], Linearization[17]. Nevertheless, ABC, EFC, HFERP and EFLASH still remain secure. At PQCrypto 2016, Szepieniec et al.[21]proposed multivariate encryp- tion schemes EFC⁻_pand EFC⁻_pt2,which use matrix multipli- cations as in ABC[22], and extension field structure as in MI[16], HFE[18]and ZHFE[19].

In this paper, we introduce a more efficient decryption approach for EFC⁻pand EFC⁻_pt2.The decryption algorithms for EFC⁻_p and EFC⁻_pt2 rely on the bilinear relation between the plaintext and an augmented ciphertext, that is the con- catenation of a ciphertext and the values of the deleted poly- nomials by the minus modifier. This bilinear relation is used for constructing linear systems in the decryption process of EFC⁻_pand EFC⁻_pt2. Our proposed decryption algorithms aim to separate the computation of constructing the linear sys- tem into two kinds of computations. One is the computation involving the plaintext and the ciphertext. The other one is computation involving the plaintext and the guessed val- ues. In addition, we experimentally investigate the security of EFC⁻p and EFC⁻_pt2 through hybrid attack[1], which is a combination of algebraic attack and exhaustive search.

This paper is structured as follows. In Sect. 2, we recall multivariate cryptography. In Sect. 3, we recall the construc- tion of EFC⁻p and EFC⁻_pt2, and their decryption algorithms in[21]. In Sect. 4, we introduce our proposed new decryp- tion algorithms for EFC⁻_p and EFC⁻_pt2.In Sect. 5, we apply hybrid algebraic attack on EFC⁻p and EFC⁻_pt2 and estimate new secure parameters for them. Finally, we conclude the paper in Sect. 6.

2. Multivariate Cryptography

In this section, we give a short introduction to multivariate Copyright © 2019 The Institute of Electronics, Information and Communication Engineers

cryptography. LetFdenote a finite field with q elements, n,mbe two positive integers and denote the polynomial ring in variablesx₁, . . . ,x_noverFbyF[x₁, . . . ,x_n].

2.1 Quadratic Maps and MQ Problem

In this subsection, we introduce the notion of quadratic maps and MQ-problem.

Given quadratic polynomialsf₁, . . . , fm∈F[x1, . . . ,xn],

f_k = Xn

i=1

Xn

j=1

a_{i j}x_ix_j+ Xn

i=1

b_ix_i+c, (1≤k≤m) where ai j,bi,c ∈ F, then F(x₁, . . . ,xn) = (f₁, . . . , fm) : Fⁿ →F^mis called aquadratic map.

Multivariate cryptography refers to the study of public key cryptosystems whose public keys are quadratic maps.

The security of multivariate cryptography is based onMQ problem, that is, givenmquadratic polynomialsp₁, . . . ,p_m∈ F[x₁, . . . ,x_n],findz∈Fⁿsuch thatp₁(z)=· · ·=p_m(z)=0. MQ problem is proven to be NP-complete even for the sim- plest case of multivariate quadratic polynomials over GF(2).

Therefore, multivariate cryptography is considered to be a candidate for post-quantum cryptography.

2.2 Construction of Multivariate Encryption Schemes To construct a multivariate encryption scheme, we need to design its private key, public key, encryption and decryption processes.

–Private Key

We start with choosing an easy-to-invert quadratic mapF(x₁, . . . ,x_n) =(f₁, . . . ,f_m). “Easy-to-invert” means given the value (y₁, . . . , y_m) ∈ F^m, solving the system f_i = y_i (1 ≤ i ≤ m) is easy. Such mapF is also called acentral map. Then we choose two invertible linear maps S :Fⁿ →FⁿandT :F^m→F^m.The set{F,S,T}is a private key.

–Public Key

Given a private key{F,S,T},a public key P can be generated from the composition ofF,S,T, i.e. P=T◦F◦S.

–General Workflow

Given a public keyPand a plaintextz∈Fⁿ,the cipher- textc∈F^mofzcan be obtained by performingc=P(z).

Conversely, given a private key{F,S,T}and a cipher- textc∈F^m,a multivariate encryption scheme decryptscby computing the inverse ofT,FandSindividually.

2.3 Algebraic Attack

Algebraic attack directly solves the system:

p₁(x₁, . . . ,xn)=c₁,· · ·,pm(x₁, . . . ,xn)=cm, (1) wherep_i’s are public key polynomials, andc=(c₁, . . . ,c_m) is a ciphertext. Usually, Gröbner basis method is used in the

solving process.

Gröbner basis method was introduced by Buchberger, who proposed Buchberger algorithm[2], and was later im- proved by Faugere with F4/F5 algorithms, see [10],[11].

“Field equations” x^q₁ −x₁ =0,· · ·,x^q_n−x_n =0 are added to the polynomial system (Eq. (1)) to solve this system inF, and it is much faster to compute a Gröbner basis when field equations are added. In multivariate cryptography, let

G={p₁−c₁, . . . ,p_m−c_m,x^q₁ −x₁, . . . ,x^q_n−x_n}, (2) we then need to compute the Gröbner basis of the ideal I generated byG.The complexity of the Gröbner basis method is determined by a so-calleddegree of regularity. There are several different definitions for degree of regularity, through out this paper, we regard the degree of regularity as the degree where a non-trivial syzygy producing a degree fall first occurs, which is also called thefirst fall degree[14]. If F4 or F5 algorithm is used, the complexity of computing the Gröbner basis ofIis

Complexity_F4/F5 =O* ,

n+d_{r eg}−1 dr eg

!2 n 2

! + -

, (3)

whered_{r eg}is the degree of regularity ofI.

In[1], Bettale et al. proposed a hybrid algebraic method for solving multivariate systems over finite fields, which can speed up the computation of Gröbner basis with F4/F5 algo- rithms. Hybrid algebraic method is a combination of alge- braic attack and exhaustive search. Specifically, givene∈N, hybrid algebraic method first guesses the value of variables x₁, . . . ,x_e, evaluate them inGwith the guessing values, and then apply algebraic attack on the remaining polynomial sys- tem. The guessing processes terminates when a solution is found.

3. Extension Field Cancellation (EFC)

In this section, we recall the constructions of EFC⁻_p and EFC⁻_pt2 [21], and the original decryption algorithms de- signed for them.

3.1 Notations

Let F be a finite field of 2 elements. Given a positive integer n, x₁, . . . ,x_n are n variables over F, and define x = (x₁, . . . ,xn).E denotes a degree n extension field of F.Denote the set of alln×mmatrices byF^n×m.Matrices are denoted by capital letters, vectors are denoted by bold low- ercase letters, and all vectors are treated as row vectors. The i-th entry of a vectorvis denoted byv_i,thei-th row of a ma- trixMis denoted byM_i.ForN,M ∈F^n×n,(N||M)∈F^n×2n denotes the horizontal join of NandM.

Choose a basis{θ₁, . . . , θ_n}ofE/F,and define the iso- morphismϕ:Fⁿ 3v7→vb^>∈E,whereb=(θ₁, . . . , θ_n)∈ Eⁿ. For A ∈ F^n×n, and v = (v₁, . . . , v_n) ∈ Fⁿ, define α(v) = ϕ(vA) ∈ E. The matrix associated with the lin- ear mapE3 X 7→α(v)X ∈Eis denoted byα_m(v)∈F^n×n.

For a matrix B ∈ F^n×n and v ∈ Fⁿ, we define β(v) and β_m(v)in the same way as α(v)andα_m(v). For a positive integera,π_astands for the following projection:

π_a :F²ⁿ 3(v₁,· · ·, v_2n)7→(v₁,· · ·, v_2n−a)∈F^2n−a.

3.2 Construction of the EFC⁻pScheme –Key Generation

Given a prime numbern,randomly choose A,B ∈F^n×n of rankn−1 such that the intersection of the kernel spaces ofA andBis the zero subspace. Randomly choose two invertible linear maps S : Fⁿ → Fⁿ andT : F²ⁿ → F²ⁿ, we identify these linear maps with matricesS ∈F^n×n,T ∈F^2n×2n. The central mapFfor EFC⁻pis

F :Fⁿ 3x7→(x·α_m(x), x·β_m(x))∈F²ⁿ. The public key for EFC⁻pis given by

P=(p₁,· · ·,p_2n−a)=π_a◦T◦F◦S :Fⁿ →F^2n−a, where p_i (1 ≤ i ≤ 2n −a) are quadratic polynomials in x₁, . . . ,x_noverF.

Next we take a look at the explicit form of the central mapF.For anyx ∈Fⁿ, α(x) ∈ Ecan be represented with basis{θ₁, . . . , θ_n},i.e. α(x)=xAb^>.Letα_i =Aib^>∈Efor 1≤i ≤n,then we haveα(x)=Pn

i=1x_iα_i. Define matrices C⁽ⁱ⁾ ∈ F^n×nby (C⁽ⁱ⁾)^>_j =ϕ⁻¹(α_iθ_j)for 1 ≤i,j ≤n. It is easy to check thatC⁽ⁱ⁾ satisfiesbC⁽ⁱ⁾ =α_ibfor 1≤i ≤ n, which indicatesα_m(x) =Pn

i=1xiC⁽ⁱ⁾.Similarly, we define matricesD⁽ⁱ⁾ ∈F^n×nfor 1≤i≤nand they satisfyβ_m(x)= Pn

i=1x_iD⁽ⁱ⁾.Therefore, the explicit form ofFis F:Fⁿ 3x7→*

, x·*

, Xn

i=1

C⁽ⁱ⁾x_i+ -

, x·* ,

Xn

i=1

D⁽ⁱ⁾x_i+ - + -

∈F²ⁿ. –Encryption

Given a public keyPand a plaintextz∈Fⁿ, its ciphertext is c=P(z)∈F^2n−a.

–Decryption

Given the private key{A,B,S,T}and a ciphertextc∈F^2n−a, decryption process is to find the plaintextz∈ Fⁿsuch that P(z) = c. First, we need to guess the value v from F^a for the deleted polynomials by π_a. Second, we compute Fⁿ×Fⁿ 3(d₁,d₂)=d=T⁻¹(c,v).Next we invert the map Fby solving the linear system

d₂α_m(x)=d₁β_m(x), (4) and obtain a solutionh∈Fⁿ.Finally, ifF(h)=(d₁,d₂),then we obtain the plaintext byz=S⁻¹(h).The loop of guessing the valuevfromF^a terminates when the correct plaintextz is found. The details are shown in Algorithm 1.

Regrading the complexity of this decryption algorithm,

we have the following proposition:

Proposition 1. The number of field operations involved in the decryption algorithm for EFC⁻_pis

8n⁴+9n³+1 2n²−7

2n+2^(a−1) 26 3 n³+21

2 n²−31 6 n

! . (5)

Algorithm 1:Decryption algorithm for EFC⁻p[21]

Input :A ciphertextc∈F^2n−a,

The private keyA,B,S∈F^n×nandT ∈F^2n×2n. Output:The plaintextz∈Fⁿ.

1 Si nv←S⁻¹,Ti nv←T⁻¹

2 Generateαm(x), βm(x)andFfromA,B

3 for v∈F^ado

4 Fⁿ×Fⁿ3(d₁,d₂)=d←(c,v)·Ti nv

5 construct a linear systemd₂·αm(x)−d₂·βm(x)=0

6 x=h←solved₂·αm(x)−d₂·βm(x)=0

7 ifF(h)=d then

8 break

9 Fⁿ 3z←h·Si nv 10 Return z.

Proof. Let [+]F denotes F-addition, and [×]F denotes F- multiplication ofF.We recall the complexity of Gaussian Elimination, and multiplication in E. For an input ofn × m (m ≥ n) matrix overF,Gaussian Elimination requires

n−1

P

i=1(n−i)(m−i)[+]_Fandⁿ⁻P¹

i=1(n−i)(m−i)+ⁿ⁻P¹

i=1(n−i)[×]_F. For any a,b ∈E,that are represented in basis{θ₁, . . . , θ_n}, the multiplicationa·brequires(n−1)(2n−1)[+]_Fand 2n² [×]_F.

Now we analyze the complexity based on the Algo- rithm 1.

In step 1, computingT⁻¹requires^n(20n2−₃¹²ⁿ⁺¹⁾[+]Fand

2n(10n²−3n−1)

3 [×]F, and computingS⁻¹ requires ⁿ⁽⁵ⁿ²⁻₆⁶ⁿ⁺¹⁾ [+]_F and ⁿ⁽⁵ⁿ²⁻₆³ⁿ⁻²⁾ [×]_F. In step 2, to obtainα_m(x), we need to computeα(x)=Pn

i=1xiα_i, whereα_i = Aib^>(1 ≤ i≤n), and this requiresn(n−1)[+]Fandn²[×]F. Then we need to computeα_ibfor 1≤i≤n,which indicatesn²[×]_E, and it requiresn²(n−1)(2n−1)[+]Fand 2n⁴ [×]F. Same complexity holds for obtaining β_m(x).

From step 3 to step 8, we enter a loop of size 2^a. In step 4,(c,v)·Tinvrequires 2n(2n−1)[+]_Fand 4n²[×]_F. In step 5, constructing the linear system needs 2n³ −n² [+]_F and 2n³[×]_F. In step 6, solving the linear system with Gaussian Elimination requires ^n(n−1)(₆²ⁿ⁺⁵⁾ [+]F and ⁿ⁽ⁿ²⁺³₃ⁿ⁻¹⁾ [×]F. In step 7, verifying whetherF(h)=dholds costs 2n(n²−1) [+]F and 2n²(n+1) [×]F. The loop terminates in step 8 after an average of 2^(a−1)times. Therefore, the loop costs 2^(a−1)(¹³₃n³+⁷₂n²−²⁹₆n)[+]Fand 2^(a−1)(¹³₃n³+7n²−¹₃n) [×]_Fin average.

In step 9, computingh·S_invneedsn(n−1) [+]Fand n²[×]_F.

Since step 1, step 2 and step 9 together costs 4n⁴ +

32n³−⁵₂n[+]Fand 4n⁴+¹⁵₂ n³+¹₂n²−n[×]F, the total cost of this decryption algorithm is Eq. (5). This completes the

proof.

3.3 Construction of the EFC⁻_pt2Scheme –Key Generation

Choose the secret keyA,BandS,Tas in EFC⁻_p.The central mapFfor EFC⁻_pt2 is

F:Fⁿ→F²ⁿ :x7→

xα_m(x)+ϕ⁻¹(β(x)³), xβ_m(x)+ϕ⁻¹(α(x)³)

. (6)

The public key for EFC⁻_pt2isP=(p₁, . . . ,p_2n−a)=π_a◦T◦ F◦S : Fⁿ → F^2n−a. The private key consists of A,Band S,T.

We take a look at the explicit structure of (6) usingb= (θ₁, . . . , θ_n).Sincex·α_m(x)andx·β_m(x)can be represented in the same way as in Sect. 3.2, we show the explicit form ofϕ⁻¹(α(x))andϕ⁻¹(β(x))here. LetΘ=b^>·b ∈ E^n×n and ϕ⁻¹(Θ) = (Θ₁, . . . ,Θ_n) ∈ (F^n×n)ⁿ. Define a matrix

∆∈F^n×n by itsi-th row∆_i =ϕ⁻¹(θ_i²).Thenα(x)³ can be represented as

α(x)³ =α(x)²·α(x)=xA

θ²₁,· · ·, θ²_n>

·b(xA)^>

=xA∆Θ(xA)^>=

n

X

i=1

θ_i·xA∆Θ_i(xA)^>.

β(x)³can be represented in the same way. Therefore, ϕ⁻¹(α(x)³)=(xA∆Θ₁(xA)^>, . . . ,xA∆Θ_n(xA)^>), ϕ⁻¹(β(x)³)=(xB∆Θ₁(xB)^>, . . . ,xB∆Θ_n(xB)^>).

–Encryption

Given a public keyPand a plaintextz∈Fⁿ,the ciphertext isc=P(z)∈F^2n−a.

–Decryption

We take a look at how to invert the central mapF.It requires solving the systemF(x)=d∈F²ⁿ, i.e.

x·α_m(x)+ϕ⁻¹(β(x)³)=d₁,x·β_m(x)+ϕ⁻¹(α(x)³)=d₂, (7) whered =(d₁,d₂) ∈ Fⁿ×Fⁿ. By definition ofα_m(x) in Sect. 3.1, the equationϕ(x·α_m(x))=ϕ(x)α(x)holds. Thus (7) is equivalent to

ϕ(x)α(x)+β(x)³ =ϕ(d₁), ϕ(x)β(x)+α(x)³=ϕ(d₂), from which the following system can be constructed:

d₂α_m(x)−d₁β_m(x)=ϕ⁻¹(α(x)⁴−β(x)⁴). (8)

Define a matrixΛ∈ F^n×n byΛ_i =ϕ⁻¹(θ⁴_i)for 1≤i ≤n, and apply it to (8). Then (8) turns into

d₂α_m(x)−d₁β_m(x)=x(A−B)Λ, (9) which is a linear system inx. The rest of the procedures of decryption is similar to that of EFC⁻p, details are shown in Algorithm 2.

Algorithm 2:Decryption algorithm for EFC⁻_pt2[21]

Input : b=(θ₁, . . ., θn)∈Eⁿ,a ciphertextc∈F^2n−a, the private keyA,B,S∈F^n×nandT ∈F^2n×2n. Output:The plaintextz∈Fⁿ.

1 Si nv←S⁻¹,Ti nv←T⁻¹

2 DefineΛ∈F^n×nbyΛ_i=ϕ⁻¹(θ_i⁴)

3 Generateαm(x), βm(x)andFfromA,B

4 for v∈F^ado

5 Fⁿ×Fⁿ3(d₁,d₂)=d←(c,v)·Ti nv

6 construct a linear systemd₂αm(x)−d₁βm(x)=x(A−B)Λ

7 x=h←solved₂αm(x)−d₁βm(x)=x(A−B)Λ

8 ifF(h)=d then

9 break

10 Fⁿ 3z←h·Si nv 11 Return z.

We analyze the complexity of the decryption algorithm for EFC⁻_pt2 adopting the same approach as in the proof of Proposition 1, and obtain the number of field operations involved in the decryption algorithm for EFC⁻_pt2as

8n⁴+17n³−11 2 n²−3

2n+2^(a−1) 32 3 n³+19

2 n²−31 6 n

! . (10)

4. Our Proposed Efficient Decryption Algorithms for EFC⁻_pand EFC⁻

pt²

In this section, we introduce our new decryption algorithms for EFC⁻pand EFC⁻_pt2.

4.1 New Decryption Algorithm for EFC⁻_p

The new decryption algorithm is derived from linearization equations, which represent a relation between the plaintext and ciphertext.

We begin with deriving linearization equations related to the central map of EFC⁻_p. Recall that the linear system (4) for inverting its central map is

d₂α_m(x)−d₁β_m(x)=0, which can also be written as

α(x)ϕ(d₂)−β(x)ϕ(d₁)=xAb^>·bd^>₂ −xBb^>·bd^>₁ =0. LetΘ=b^>·band(Θ₁, . . . ,Θ_n)=ϕ⁻¹(Θ),then from this equation, we can obtain linearization equations correspond- ing to the central map of EFC⁻_pas follows:

x(BΘ_i||AΘ_i)d^>=0, (1≤i≤n), (11) whered=(d₁,d₂).

Subsequently, we apply S andT to the linearization equation related to the central map. Let c ∈ F²ⁿ be a ci- phertext of EFC⁻p without minus modifier, thenc=T(d).

Apply the linear mapsSandTto Eq. (11), and we obtain the linearization equations between a plaintextxandcas

xS(BΘ_i||AΘ_i)(cT⁻¹)^>=0. (12) For a ciphertextcof EFC⁻pwithout minus modifier, its cor- responding plaintext can be found by solving Eq. (12).

Next we show how to represent Eq. (12) into one simple equation. Let N⁽ⁱ⁾ = T⁻¹(SBΘ_i||S AΘi)^> ∈ F^2n×n, and define matricesU^(j) byU_i^(j) = N_j⁽ⁱ⁾ for 1 ≤ j ≤ 2n and 1≤i≤n.Then Eq. (12) turns into one simple equation

(c₁U⁽¹⁾+· · ·+c_2nU⁽²ⁿ⁾)·x^>=0. (13) This equation indicates that as long as we have the setΨ= (U⁽¹⁾, . . . ,U⁽²ⁿ⁾),the decryption process of EFC⁻_p without minus modifier can be reduced into the computation of the right kernel space ofc₁U⁽¹⁾+. . .+c_2nU⁽²ⁿ⁾.

Since in our new decryption algorithm, only the ci- phertextcandU⁽¹⁾, . . . ,U⁽²ⁿ⁾ are necessary, we intend to saveΨ=(U⁽¹⁾, . . . ,U⁽²ⁿ⁾)as the new private key for EFC⁻p, which is 2n/7 times larger than the original private key.

Now we explain our proposed decryption algorithm for EFC⁻_p.First, we compute L = P2n−a

i=1 ciU⁽ⁱ⁾. Second, we guess the values for the deleted polynomials byπ_afromF^a, and denote these values byv=(v₁,· · ·, v_a).Next, we com- pute the right kernel spaceker=ker(L+Pa

i=1v_iU^(2n−a+i)).

Finally, we check if there existsz∈kersuch thatP(z)=c holds. If so, thenzis the plaintext, otherwise, go back to the guessing step and start over. The details of the procedures of generating Ψ and the decryption process are shown in Algorithm 3.

Remark 1. The iterative computation complexity of Pa

i=1v_iU^(2n−a+i) can be further reduced. Assume we have v⁽¹⁾,v⁽²⁾∈F^a₂,and we need to compute

L⁽¹⁾=

a

X

i=1

v_i⁽¹⁾U^(2n−a+i), L⁽²⁾=

a

X

i=1

v_i⁽²⁾U^(2n−a+i).

If we know the difference betweenv⁽¹⁾andv⁽²⁾,we will be able to computeL⁽²⁾fromL⁽¹⁾by subtracting a few matrices.

Since Gray code has the property that two successive binary numeral values differ in only one bit, we use Gray code to representF^a₂.Assumev⁽¹⁾andv⁽²⁾are two successive codes, and they differ atj-th bit, then we can computeL⁽²⁾by

L⁽²⁾=L⁽¹⁾+U^(2n−a+j).

Therefore, this technique reduces the number of operations of matrix addition involved in recursive computation of Pa

i=1v_iU^(2n−a+i).We consider this technique when we eval- uate the complexity of our new decryption.

Algorithm 3:New decryption algorithm for EFC⁻_p

Input : b=(θ₁,· · ·, θn), the private keyA,B,S∈F^n×nand T ∈F^2n×2n,a ciphertextc∈F^2n−a.

Output:The plaintextz∈Fⁿs.t.P(z)=c.

1 Θ←b^>·b, (Θ₁, . . .,Θ_n)←ϕ⁻¹(Θ)

2 fori←1tondo

3 N⁽ⁱ⁾←T⁻¹(SBΘi| |S AΘi)^>∈F^2n×n

4 forj←1to2nandi←1tondo

5 U_i^(j)←N⁽ⁱ⁾_j

6 L←P_2n−a i=1 ciU⁽ⁱ⁾

7 for v=(v₁, . . ., va)∈F^ado

8 H←L+Pa

i=1viU^(2n−a+i)

9 ker←RightKer(H)

10 for z∈ker do

11 ifP(z)=c then

12 Return z

13 break

Regarding the complexity of the new decryption algo- rithm for EFC⁻p,we have the following proposition.

Proposition 2. The number of field operations involved in the new decryption for EFC⁻_pis

2^(a−1) 14

3 n³+(11

2 −2a)n²−(a+19 6 )n+a

!

+4n³−(2a+1)n²

(14)

Proof. Let [+]_F denoteF-addition, and [×]_F denote theF- multiplication. We analyze the complexity based on Algo- rithm 3. Note that we analyze the complexity starting from step 6 since we saveΨas the new private key.

In step 6,P2n−a

i=1 ciU⁽ⁱ⁾requiresn²(2n−a−1)[+]_Fand n²(2n−a)[×]F.

From step 7 to 13, we enter a loop of size 2^a.In step 8, L +Pa

i=1v_iU^(2n−a+i) costs 2n² [+]F using Gray code technique in Remark 1. In step 9, finding the right ker- nel of Hrequires ^{n(n−1)(2n+5)}₆ [+]_Fand ^n(n2+3n−₃ ¹⁾ [×]_F. In step 11, verifying the solution requires (2n−a)(n²−1) [+]_F and(2n −a)(n² +n) [×]_F. In step 13, the loop ter- minates after an average of 2^(a−1) times. Therefore, the loop requires 2^(a−1)(⁷₃n³+(⁵₂ −a)n²−¹⁷₆n+a)[+]Fand 2^(a−1)(⁷₃n³+(3−a)n²−(a+¹₃)n)[×]Fin average.

Therefore, the total cost of this decryption algorithm is

Eq. (14). This completes the proof.

4.2 New Decryption Algorithm for EFC⁻_pt2

Same as EFC⁻p, the new decryption algorithm for EFC⁻_pt2

also derives from linearization equations.

We first consider linearization equations related to the central map of EFC⁻_pt2. Recall in Sect. 3.3, inverting the central map of EFC⁻_pt2requires solving the linear system

d₂α_m(x)−d₁β_m(x)=x(A−B)Λ, (15) whereΛ∈F^n×n,Λ_i =ϕ⁻¹(θ⁴_i)for 1≤i≤n.This equation can also be written as

ϕ(d₂)α(x)−ϕ(d₁)β(x)=ϕ(x(A−B)Λ). (16) Applyingϕ⁻¹on both sides of Eq. (16) gives us

x(BΘ_i||AΘ_i)d^>−(x(A−B)Λ)_i=0, (1≤i≤n), (17) which are the linearization equations related to the central map of EFC⁻_pt2.

Next we applyS andT to the linearization equations we obtained. Letc∈F²ⁿbe a ciphertext of EFC⁻_pt2 without minus modifier, thenc=T(d).Applying linear mapsSand T on (17) gives us the linearization equations of a plaintext xand a ciphertextc:

x(SBΘ_i||S AΘ_i)(cT⁻¹)^>−(xS(A−B)Λ)_i =0. (18) Next we show how to represent Eq. (18) into one sim- ple equation. Let M = S(A− B)Λ ∈ F^n×n, N⁽ⁱ⁾ = T⁻¹(SBΘ_i||S AΘ_i)^> ∈ F^2n×n, and define matricesU^(j) by U_i^(j)=N_j⁽ⁱ⁾for 1≤ j ≤2nand 1≤i ≤n.Then (18) can be rearranged into

(c₁U⁽¹⁾+· · ·+c₂nU⁽²ⁿ⁾−M^>)·x^>=0. (19) This equation indicates that the decryption of EFC⁻_pt2 with- out minus modifier can be reduced to the computation of the right kernel space ofc₁U⁽¹⁾+· · ·+c_2nU⁽²ⁿ⁾−M^>.

Similar to EFC⁻p,we saveΨ=(U⁽¹⁾, . . . ,U⁽²ⁿ⁾,M)as the new private key for EFC⁻_pt2,which is(2n+1)/7 times larger than the original private key. New decryption algo- rithm for EFC⁻_pt2 works similarly to that of EFC⁻p,detailed procedures are shown in Algorithm 4.

We can analyze the complexity of the decryption algo- rithm for EFCpt²using the same approach as in the proof of Proposition 2. The number of field operations involved in the new decryption algorithm for EFC⁻_pt2is

2^(a−1) 14

3 n³+(11

2 −2a)n²−(a+19 6 )n+a

!

+4n³−2an².

(20)

4.3 Implementation

We verify the effectiveness of our decryption method through implementation operated on a 2.10 GHz Intel^® Xero^® Gold 6130 CPU with Magma V2.23-10 under originally claimed 80-bit security parameters, see[21], and then compare the results with complexity given in (5), (10), (14) and (20). The implementation results are given in Table 1.

From Table 1, we know, under 80-bit security parameter given in[21], theoretically our new decryption algorithms are 2.24 times faster for EFC⁻_pand 3.58 times faster for EFC⁻_pt2

Algorithm 4:New decryption algorithm for EFC⁻_pt2

Input : b=(θ₁,· · ·, θn), the private keyA,B,S∈F^n×nand T ∈F^2n×2n.

Output:The plaintextz∈Fⁿs.t.P(z)=c.

1 Θ←b^>·b, (Θ₁, . . .,Θ_n)←ϕ⁻¹(Θ)

2 DefineΛ∈F^n×n,whereΛi=ϕ⁻¹(θ⁴_i)

3 M←S(A−B)Λ

4 fori←1tondo

5 N⁽ⁱ⁾←T⁻¹(SBΘi| |S AΘi)^>∈F^2n×n

6 forj←1to2nandi←1tondo

7 U_i^(j)←N⁽ⁱ⁾_j

8 L←P₂n−a

i=1 ciU⁽ⁱ⁾−M^>

9 for v=(v₁, . . ., va)∈F^ado

10 H←L+Pa

i=1viU^(2n−a+i);

11 ker←RightKer(H)

12 for z∈ker do

13 ifP(z)=c then

14 Return z

15 break

Table 1 Timing comparison between old EFC⁻p,EFC⁻_{p t2} with new EFC⁻p,EFC⁻_{p t2}under 80-bit security parameter given in[21], [+,×] repre- sents the number of involved field operations^†.

Scheme(n,a) KeyGen.[s] Enc.[s] Dec.[s] [+,×]F Old EFC⁻p(83,10) 0.022 0.00023 0.116 2.96×10⁹

EFC⁻_{p t2}(83,8) 0.023 0.00023 0.028 1.18×10⁹ New EFC⁻p(83,10) 0.022 0.00023 0.013 1.32×10⁹ EFC⁻_{p t2}(83,8) 0.023 0.00023 0.003 0.33×10⁹

than the original decryption algorithms, and the speed-up obtained in our implementation are 8.92 and 9.33 times for EFC⁻_p and EFC⁻_pt2, respectively.

Since our proposed decryption algorithms do not alter public keys for EFC⁻p and EFC⁻_pt2, their security does not change. As for the private key, to match with our proposed decryption algorithms, we use new private keys, which is 2n/7 times larger for EFC⁻p, and(2n+1)/7 times larger for EFC⁻_pt2compared to the original private keys.

5. Hybrid Attack Against EFC⁻_pand EFC⁻

pt²

Because of the minus modifier, the most efficient attack against EFC⁻p and EFC⁻_pt2 is expected to be the algebraic attack, see Sect. 2.3, which computes the Gröbner basis of the ideal generated by the public key and the field equations.

Normally we use F4/F5 [10], [11] algorithms, which has complexity given in Eq. (3). In[21], upper bounds for the degree of regularity of EFC⁻_pand EFC⁻_pt2 are given:

†Note that only 80-bit security level parameters are proposed in[21].

dr eg≤ r

2 +2, r =( 2+a, EFC⁻_p,

4+a, EFC⁻_pt2. (21) And[21]also claimed the degree of regularity of EFC⁻pand EFC⁻_pt2 lie close to these upper bounds. Under the assump- tion that these upper bounds are identical to the degree of regularity of EFC⁻pand EFC⁻_pt2, 80-bit and 128-bit security parameters are estimated in[21]and[23], respectively.

In this section, we apply hybrid algebraic attack on EFC⁻p and EFC⁻_pt2 to learn how parametersn anda affect their degree of regularity. All of our experiments are con- ducted on a 2.10 GHz Intel^® Xero^® Gold 6130 Processor with Magma V2.23-10, where F4 algorithm is implemented.

5.1 Notations

Notations used in this section are as follows:

• d_{r eg}: degree of regularity (see Sect. 2.3).

• stepdeg: step degree, a sequence of degrees of polyno- mials appeared in all the steps of F4 algorithm.

• s_deg : solving degree, the degree of the most time- consuming step of F4 algorithm.

• e: the number of variables evaluated in hybrid algebraic attack (see Sect. 2.3).

• time/gb : average time cost of one round of F4 algorithm in hybrid algebraic attack.

• total time (est.) : estimated time cost of hybrid al- gebraic attack, and it holds the following equation:

total time (est.)=2^e−1∗(time/gb).

• total time : average time cost of hybrid algebraic attack.

• s,h,d, y : second, hour, day, year.

5.2 Hybrid Attack on EFC⁻pand Update Secure Parameters For EFC⁻_p,we first verify if the claimed 80-bit security pa- rameter in [21] indeed has 80-bit security against hybrid attack. Let e be a positive integer. We guess values for variables(x₁, . . . ,x_e)fromF^e(|F^e| =2^e), and evaluate the systemG, see (2), with those guessing values, then perform algebraic attack on the obtained system. The experiment terminates when a solution can be found. The results are shown in Table 2. From this table, we know whene=16, both ofd_{r eg}ands_{r eg}are 4, and the complexity of the hybrid attack is around 2¹⁶_{83−16+4−1}

4

2₈₃₋₁₆

2

≈2⁶⁷by formula (3).

Therefore, the originally proposed 80-bit security parameter fails in achieving its claimed security level.

To update secure parameters for EFC⁻p,we need to find a lower bound for the degree of regularity for EFC⁻p.The upper bound given in (21) is given following analysis on HFE based schemes[5],[6],[8],[9], and it is deduced according to the fact that thed_{r eg}of a subsystem is equal to or larger than the full polynomial system. Following this approach, we know thedr eg of an EFC⁻_psystem witha−1 polynomial deleted is equal to or smaller than that of an EFC⁻p system witha polynomial deleted. It means a lower bound for dr eg of

Table 2 Hybrid algebraic attack on EFC⁻p(83,10). e stepd eg dr eg sd eg time/gb total time (est.)

15 (2,3,4,4,5,...) 4 ≥5 − −

16 (2,3,4,4,4,4) 4 4 2.618d 235.065y

17 (2,3,4,4,4) 4 4 1.896d 340.418y

18 (2,3,4,4,3) 4 4 23.658h 353.983y

19 (2,3,4,4) 4 4 4.900h 146.647y

20 (2,3,4,4) 4 4 4.016h 240.370y

21 (2,3,4,4) 4 4 3.132h 374.864y

Table 3 Behave ofdr egof EFC⁻p(n=41,a)withe=1.

a stepd eg d_{r eg} s_{d eg} total time 10 (2,3,4,4,5,2,3,4,5,6,7) 4 5 2.181h

11 (2,3,4,5,2,3,4,5,6,7) 5 5 2.550h

12 (2,3,4,5,4,2,3,4,5,6,7) 5 5 2.707h

13 (2,3,4,5,5,2,3,4,6,7) 5 5 6.204h

14 (2,3,4,5,5,2,3,4,5,6,7) 5 5 6.995h 15 (2,3,4,5,5,2,3,4,5,6,7) 5 5 7.911h 16 (2,3,4,5,5,2,3,4,5,6,7) 5 5 8.713h 17 (2,3,4,5,5,2,3,4,5,6,7) 5 5 9.305h

18 (2,3,4,5,6,...) ≥6 ≥6 –

EFC⁻p can be obtained as long as one linear combination of the polynomials deleted by minus modifier can be recovered.

However, this indicates the total break of EFC⁻p, and it is a very difficult task. Therefore, we experiment with small parameters to find an experimental lower bound. Parameter n is fixed to be 41, then we experiment with parameter a increasing. The results are shown in Table 3, from which we know there are two turning points for the degree of regularity.

One of them is when a rises to 11 from 10, the degree of regularity turns into 5, the other one is whena rises from 17 to 18, the degree of regularity turns into 6. We regard them as lower bounds to update new parameters in Sect. 5.4.

Since thed_{r eg}of an EFC⁻_p system with larger parameter is equal to or larger than the d_{r eg} of an EFC⁻p system with smaller parameter, updateding new parameters using those experimental lower bounds should be enough.

5.3 Hybrid Attack on EFC⁻_pt2

We apply hybrid attack on EFC⁻_pt2in the same approach as EFC⁻p,the results are shown in Table 4. This table shows hybrid attack cannot work any better than algebraic attack.

Therefore, the originally proposed 80-bit security parameter set for EFC⁻_pt2remains secure against hybrid attack. Table 4 also shows the variation of d_{r eg}of EFC⁻_pt2 is more drastic compared to EFC⁻_p, which is also the reason why we were not able to perform hybrid attack with small parameters. Even withn =40,a =8,which is expected to have dr eg ≤ 8,it takes significantly long time to perform F4 algorithm that we were not able to get the results. We therefore use bound given in (21) to estimate 128-bit security level parameter.

From Table 4, we can see that there is a tendency of hy- brid attack not outperforming direct attack for EFC⁻_pt2. Be- cause of this, the estimation of secure parameters for EFC⁻_pt2