Sigma Identification Protocol Construction Based on MPF

Abstract

A new sigma identification protocol (SIP) based on matrix power function (MPF) defined over the modified medial platform semigroup and power near-semiring is proposed. It is proved that MPF SIP is resistant against direct and eavesdropping attacks. Our security proof relies on the assumption that MPF defined in the paper is a candidate for one-way function (OWF). Therefore, the corresponding MPF problem is reckoned to be a difficult one. This conjecture is based on the results demonstrated in our previous studies, where a certain kind of MPF problem was proven to be NP-complete.

1. Introduction

In this paper a new paradigm for the so-called Sigma Identification Protocol (SIP) based on the authors’ earlier proposed new candidate for one-way function (OWF) is presented. In general, Sigma protocols are three-round protocols similar to the well-known Schnorr identification protocol. They are typically used as sub-protocols in more complicated settings and for more advanced use. For example, Sigma protocols can easily be transformed into corresponding identification and signature schemes. Another application is to design protocols that allow one party to prove to another that certain facts are true (without revealing private information). For example, to prove that encrypted value V lies in a certain range without revealing any other information about V. Sigma protocols can be combined to make new Sigma protocols. For example, in the AND-proof construction, a Prover can convince a Verifier that he knows witnesses for a pair of statements. In the OR-proof construction, a Prover can convince a Verifier that he knows witnesses for one of two statements. These examples convince us that the development of Sigma protocols based on new paradigms is promising.

The construction of cryptographic primitives based on matrix power function (MPF) belongs to the field of so called non-commuting cryptography [1], [2]. The development of non-commuting cryptography is important due to the need to replace traditional cryptographic methods vulnerable to quantum cryptanalysis. Peter W. Shor has proposed the polynomial-time quantum cryptanalysis [3] for the traditional cryptographic primitives such as Diffie—Hellman key exchange protocol, RSA and ElGamal cryptosystems, Digital signature algorithm (DSA) and Elliptic Curve DSA (ECDSA).

One of the promising trends is the creation of OWFs, the security of which relies on the NP-hard problems [4]. Thus far, there are no known effective quantum cryptanalytic algorithms solving NP-hard problems; therefore, this cryptographic trend is a significant part of the so-called post-quantum cryptography [5]. One of the trends to create cryptographic primitives that can resist quantum cryptanalysis attacks is lattice-based cryptography [6] and hidden field equations (HFE) based cryptosystems [7,8,9,10]. Despite some cryptanalytic attacks on the HFE cryptosystem [8,9], this trend is viewed as promising [10].

MPF is somewhat related to the multivariate polynomials used in HFE cryptosystems since the complexity of so called MPF problem and the NP-completeness of this problem is proved using polynomial-time reduction of multivariate quadratic (MQ) problem [7]. Referencing [11] it is proved that certain kinds of MPF problems are NP-complete as well [12,13].

In this paper the novel MPF based sigma identification protocol (SIP) is presented using several specifically selected algebraic structures introduced in [14]. The concept of abstract MPF as well as main definitions for the construction of SIP are given in Section 2. The algebraic structures for the construction of MPF are defined in Section 3. MPF SIP is presented in Section 4. The security of MPF SIP against eavesdropping attacks is proven in Section 5. In Section 6, the selection of security parameters as well as the efficiency analysis are presented. The discussions and conclusions are presented in Section 7. The table of notations used in this paper as well as the numerical example are displayed in the Abbreviations and Appendix A, respectively.

2. The Construction of the Abstract Matrix Power Function

In this section, the matrix power function (MPF) is constructed in an abstract form without specifying exact algebraic structures that will be introduced in subsequent sections. Let X = {x_il}, W = {w_lj} and Y = {y_jk} be m × m matrices over some semiring, and indices i, j, k, l ∈ I_m = {1, 2, …, m}. Multiplying matrix W by matrix X from the left and by matrix Y from the right yields a new matrix Q = {q_ik}.

$$XWY=Q;{\displaystyle \sum _{j=1}^m\sum _{l=1}^m}{x}_{il}{w}_{lj}{y}_{jk}=q_{ik};i,j,k,l\in I_m.$$

(1)

Let S be some multiplicative semigroup and R some numerical semiring. In the case that MPF S is named a platform semigroup and R an exponent semiring. The exponent semiring of natural numbers with zero is denoted by N₀ = {0, 1, 2, …}. The corresponding semigroup of matrices defined over S is denoted by M_S and the semiring of power matrices defined over R is denoted by M_R. Then, using an analogy with the matrix multiplication defined in (1), the left MPF, the right MPF and the left-right or simply MPF are introduced for X, Y ∈ M_R, x_il, y_jk ∈ R and for W ∈ M_S, w_lj ∈ S as follows.

Definition 1.

The left MPF corresponding to the matrix W powered by matrix X from the left with the MPF value equal to the matrix C = {c_ij} has the following form:

$${}^{X}W=C{c}_{ij}={\displaystyle \prod _{l=1}^m{w}_{lj}{}^{x_{il}}}.$$

(2)

Definition 2.

The right MPF corresponding to the matrix W powered by matrix Y from the right with the MPF value equal to the matrix D = {d_lk} has the following form:

$$W^Y=D{d}_{lk}={\displaystyle \prod _{j=1}^m{w}_{lj}{}^{y_{jk}}}.$$

(3)

Definition 3.

The left-right, or simply MPF corresponds to the matrix W powered by matrix X from the left and by matrix Y from the right with the MPF value equal to the matrix Q = {q_ik} and is expressed in the following way:

$${}^X{W}^Y=A,a_{ik}={\displaystyle \prod _{j=1}^m{\displaystyle \prod _{l=1}^m{w}_{lj}^{x_{il}\cdot y_{jk}}}};i,j,k,l\in I^{(m)}.$$

(4)

The MPF definition is related to the following associativity identities.

Definition 4.

MPF is one-side, (left-side or right-side) associative and two-side associative if the following respective identities hold:

^Y(^XW) = ^(YX)W = ^YXW; (W^X)^Y = W^(XY) = W^XY.

(5)

(^XW)^Y = ^X(W^Y) = ^XW^Y.

(6)

In general, MPF is a function F: M_R × M_S × M_R → M_S. To be concise, we will use the notation $MP{F}_S^R$ for the definition of MPF with base matrix defined over the platform semigroup S in M_S and with power matrices defined over the exponent semiring R in M_R. The categorical interpretation of MPF is presented in [15], in the context of the construction of several key agreement protocols. We slightly reformulate the notions used in the authors’ interpretation by the following proposition, which is more appropriate for our study.

Proposition 1.

If MPF is associative, then M_S is a multiplicative M_R-semibimodule.

This means that there exist bilinear (left and right) actions of the matrix semiring M_R on the matrix semigroup M_S. According to the definition of action, it must satisfy the associative law corresponding to Definition 4. Since matrix semigroup M_S is multiplicative, then M_R-semibimodule M_S is multiplicative in our case. The following lemma is presented without proof. The proof can be found in [14].

Lemma 1.

If R is a commutative numerical semiring (e.g., N₀ = {0, 1, 2, …}) and S is a commutative semigroup, then MPF is two-side associative.

The direct MPF value computation requires finding matrix A in (4), when matrices X, Y and W are given. The inverse MPF value computation requires finding matrices X and Y in (4), when matrices W and A are given. The MPF problem is the computation of the inverse MPF value.

Definition 5.

A function F: Dom → Ran with finite sets of domain (Dom) and range (Ran) is a candidate for one-way function (OWF) if for all d ∈ Dom the F(d) can be computed by a polynomial time algorithm, but any polynomial time randomized algorithm that attempts to compute an inverse value F⁻¹(r) = d for F, where r ∈ Ran is given, succeeds with negligible probability. That is, for all randomized algorithms, all positive integers c and all sufficiently large n = length(d), the probability to compute an inverse value r for F is at most n^−c. The probability is taken over the choice of r from the discrete uniform distribution in Ran.

Paraphrasing this definition in a non-formal way, MPF is candidate for OWF if: (1) the MPF direct value computation is easy, and (2) the MPF problem is hard.

The computation of the direct MPF value is effective and can be done by powering elements of the platform semigroup S by elements of the exponent semiring R with relatively small values (e.g., up to 5 used in this study). It is related to the matrix multiplication by the two matrices from the left and right. In this paper we present some evidence that the solution of the MPF problem is hard.

Proposition 2.

The necessary requirements for MPF for the proposed SIP are the following: (1) it is a candidate for OWF, (2) it is associative, and (3) the following distributive identity holds:

^(U+X)W^{( +Y)} = ^UW^V * ^UW^Y * ^XW^V * ^XW^Y,

(7)

where * is a Hadamard product of matrices [16].

3. The Definition of Algebraic Structures

In order to construct a platform semigroup for MPF, the class of modified multiplicative medial semigroups [17] is used. A medial semigroup S_M has the presentation consisting of two generators a, b and relation R_M is defined in the following way:

S_M = <a, b | R_M>,

(8)

R_M: w₁abw₂ = w₁baw₂,

(9)

where w₁ and w₂ are arbitrary non-empty words in S_M, written in terms of generators a and b. The reason for the introduction of the medial semigroup is the existence of the following identity, based on the relation R_M, valid for all words w₁, w₂ ∈ S_M and any exponent e ∈ N₀, where N₀ = {0, 1, 2, …} is the semiring of natural numbers with zero:

$${(w_1{w}_2)}^e=w_1{}^e{w}_2{}^e.$$

(10)

In order to construct a platform semigroup S for MPF in (4), two extra relations R₁ and R₂ are added to S_M:

R₁: a⁵ = a; R₂: b⁵ = b.

(11)

These relations can be generalized for arbitrary finite exponents instead of 5, however, only relations (11) are considered in this paper for simplicity. Thus, modified medial semigroup S has the following presentation:

S_M = <a, b | R_M, R₁, R₂>.

(12)

Note that we define S as a multiplicative, non-commuting and cancellative semigroup.

Proposition 3.

Semigroups S_M and S are transformed into monoids by introducing an empty word as a multiplicatively neutral element, denoted by 1. Then, conveniently, the following identities hold for all w in S_M and S:

w1 = 1w = w, w⁰ = 1; 0 ∈ N₀.

(13)

Using relation R_M in (9) any word in S_M can be transformed to the form w = b^sa^tb^ua^v moving generators a, b left and right, where s, t, u, v ∈N₀. Let w = b^sa^tb^ua^v be such word in S_M. Reformulating the Theorem 12 in [14], the normal form w_nf of word w in the semigroup S_M is defined by the following function nf: S_M → S_M,nf and is expressed by the relation:

$$w_{nf}=\underset{t,u}{\max }(b^s{a}^t{b}^u{a}^v)=b^{\beta }{a}^{i_a}{b}^{i_b}{a}^{\alpha }=nf(w);\alpha ,\beta \in \{0,1\};i_a,i_b\in N_0.$$

(14)

The normal form in the modified medial semigroup S is defined by the following theorem.

Theorem 1.

The normal form w_η of the word w_nf in the normal form of S_M, is represented by the function η: S_M → S and obtained by applying the minimization procedure of exponents i_a, i_b in (14) using the relations R₁, R₂:

$$w_{\eta }=\underset{i_a,j_b}{min}{w}_{nf}(\beta ,i_a,j_b,\alpha )=\underset{i_a,j_b}{min}(b^{\beta }{a}^{i_a}{b}^{j_b}{a}^{\alpha })=b^{\beta }{a}^i{b}^j{a}^{\alpha }=\eta (w_{nf});\alpha ,\beta \in \{0,1\};i_a,i_b\in N_0.$$

(15)

Since S is a multiplicative semiring, the following exponent identities hold for any generator g ∈ {a, b}:

gⁱg^j = g^i+j; (gⁱ)^j = g ^ij.

(16)

Addition and multiplication tables for exponents i, j are presented in

Table 1. Addition (+) table for exponents i, j.

+	0	1	2	3	4
0	0	1	2	3	4
1	1	2	3	4	1
2	2	3	4	1	2
3	3	4	1	2	3
4	4	1	2	3	4

and

Table 2. Multiplication (•) table for exponents i, j.

•	0	1	2	3	4
0	0	0	0	0	0
1	0	1	2	3	4
2	0	2	4	2	4
3	0	3	2	1	4
4	0	4	4	4	4

below.

Referencing relations R₁, R₂ the semiring N₀ can be replaced by the finite semiring N₄ = {0, 1, 2, 3, 4}. This semiring has an additive semigroup with index 1 and period 4. The exponent functions defined on S are determined by non-negative exponents in semiring N_4.

We generalize these functions by introducing the “imaginary” unit ι which has some weak analogy with complex numbers in classical numerical algebra based on the imaginary unit i (i² = −1). According to this “analogy” the set of complex exponents can be introduced and denoted by ι∙N₄, where “∙“ denotes a formal multiplication of ι by any number in N₄. According to our assumption and using the relation R_M in (9), the following properties of exponent ι are defined:

ι² = 1, 1 ∈ N₄; a^ι = b; b^ι = a; t + ι∙u ≠ ι∙u + t,

(17)

where t, u ∈ N₄. This means that elements t + ι∙u and ι∙u + t do not commute.

The algebraic structure termed a near-semiring [18] was introduced for the construction of MPF in [14]. In general, it can be defined in the following way.

Definition 6.

A near-semiring (NSR) is a nonempty set with two binary operations “+” and “·”, such that <NSR; +; 0> is an additive monoid with neutral element 0, and <NSR; ·; 1> is a multiplicative monoid with neutral element 1, satisfying the following (two-sided) axioms for all x, y, z in NSR:

x·(y + z) = x·y + x·z, and (x + y)·z = x·z + y·z,

(18)

0 + x = x + 0 = x; 0·x = x·0 = 0; 1·x = x·1 = x.

(19)

Referencing to this definition the special type NSR required for MPF SIP construction is defined in the following way.

Definition 7.

The exponent near-semiring NSR consist of non-commuting additive monoid <NSR; +; 0> and commuting multiplicative monoid <NSR; ·; 1> satisfying Definition 6 and is a union of the following sets

NSR = N₄ + ι∙N₄ + N₄ ∪ ι∙N₄ + N₄ + ι∙N₄,

(20)

where the set N₄ + ι∙N₄ + N₄ defines the class of elements {t + ι∙u + v} and the set ι∙N₄ + N₄ + ι∙N₄—the class {t∙ι + u + v∙ι}, where t, u, v ∈ N₄.

The presentation of the semigroup S by relations R_M, R₁, R₂ in (9) and (11) induces certain properties and relations in NSR that can be directly verified and are presented below without the proof.

Proposition 4.

For any x, y ∈ NSR, where x = t + ι∙u + v and y = ι∙t + u + ι·v and t, u, v ∈ N₄, the following identities hold for the exponents of generators a and b in S:

a^x = a^t+ι∙u+v = a^ta^ι∙ua^v= a^tb^ua^v; a^y = a^{ι∙t+u+ι∙v} = a^ι∙ta^u a^ι∙v = b^ta^ub^v.

(21)

Identity to (21) can be extended for any word w ∈ S:

$$w^x=w^{t+\iota \cdot u+v}=w^t{\overline{w}}^u{w}^v;w^y=w^{\iota \cdot t+u+\iota \cdot v}={\overline{w}}^t{w}^u{\overline{w}}^v,$$

(22)

where the word $\overline{w}$ is obtained from w by renaming the generator a to b and b to a respectively. It is easily verified that the exponent function in S satisfies the following more general identities for any w, w₁, w₂ ∈ S and any x, y ∈ NSR:

w^xw^y = w^(x+y) = w^x+y;  (w^x)^y = w^(x∙y) = w^x∙y, (w₁w₂)^x = (w₁)^x(w₂)^x.

(23)

The partial case of (23) are the following identities: a^x a^y = a^x+y, (a^x)^y = a^(x∙y) = a^x∙y and (a₁a₂)^x = (a₁)^x(a₂)^x for any a, a_1, a₂ ∈ S and x, y ∈ NSR. The same is valid for the generator b. The illustration of the computation of exponents in S is presented in Example 1 below.

The set of matrices defined over the NSR is denoted by M_NSR.

Referencing to the Proposition 1, we present the following easily verifiable theorem without a proof.

Theorem 2.

M_Sis a multiplicative M_NSR-semibimodule.

Since NSR is acting on the semigroup S as an exponent function, then M_NSR is acting on M_S as MPF. According to Definition 7 and semigroup S presentation in (12) the following proposition can be formulated.

Proposition 5.

NSRintroduced in the Definitions 6 and 7 has non-commuting additive monoid <NSR; +; 0> and commuting multiplicative monoid <NSR; ·; 1>, i.e., for all x, y, z₁, z₂ ∈ NSR the following identities hold:

z₁ + x + y + z₂ = z₁ + y + x + z₂.

(24)

x·y = y·x.

(25)

Relation (25) implies the following identity:

ι∙x = x∙ι.

(26)

Example 1.

The computation of w^x. Let w = b³aba² and x = 2 + ι∙3 + 4, then the 1-st step of the computation is performed in the following way.

w^x = w^{2+ι∙3∙+ 4} = (b³aba²)^2+ι∙3+4 = (b³aba²)² (b³aba²)^ι∙3 (b³aba²)⁴ = (b⁶a²b²a⁴) (a⁹b³a³b⁶) (b¹²a⁴b⁴a⁴⁸)

At the second step transformation to the normal form (15), every word in parentheses is performed.

(b⁶a²b²a⁴) (a⁹b³a³b⁶) (b¹²a⁴b⁴a⁴⁸) = (b⁷aba⁵) (a¹²b⁹) (b¹⁵aba¹¹) = (b³aba) (a⁴b) (b³aba³) = = ba⁹b⁸a = bab⁴a.

The final word is found using R₁ and R₂ as well, where b⁸ = b⁴, a⁹ = a.

The gray part of Table 1 represents the additive subgroup N₄⁺ = {1, 2, 3, 4} with neutral element equal to 4. Subgroup N₄⁺ has the subset of two generators Γ = {1, 3}. The subgroup N₄⁺ and generators Γ will play an important role in proving the uniform distribution of conversations and the security against eavesdropping attack of MPF SIP in Section 5. Moreover, relations R₁, R₂ in (11) define the smallest exponent e = 5 where subgroup N₄⁺ has at least two generators. It is important to have a random choice in the set having at least two generators and will be used in our construction as well. The gray part of Table 2 represents the multiplicative semigroup N₄⁺ in N₄. It is easily verified that N₄⁺ is a sub- semiring of N₄. Replacing N₄ by N₄⁺ in Definition 7, we obtain a new near-semiring as a sub-semiring of NSR which is denoted by sNSR. The matrix set over the sNSR is denoted by M_aNSR and matrix set with entries in Γ = {1, 3} is denoted by M_Γ. MPFs defined by the multiplicative M_sNSR-semibimodule M_S and by the multiplicative M_sNSR-semibimodule M_S are denoted by $MP{F}_S^{NSR}$ and $MP{F}_S^{sNSR}$ respectively.

Together with the introduced here near-semirings the introduction of anti-NSR, denoted by aNSR, to the original NSR is necessary. According to (20), aNSR is defined by:

aNSR = −N₄ − ι∙N₄ − N₄ ∪ − ι∙N₄ − N₄ − ι∙N₄,

(27)

where for any element x in NSR there exists a unique element x′ in aNSR obtained by switching the sign of x from positive to negative, i.e., x′ = −x. The matrix set over the aNSR is denoted by M_aNSR. For any matrix H in M_NSR there exists a unique matrix −H in M_aNSR with negative entries. Then, formally, we assume that

H − H = O,

(28)

where O is the zero matrix, i.e., matrix with all entries equal to zero.

This construction will be used in the security proofs for the so-called simulator Sim computations. Several additional properties of $MP{F}_S^{aNSR}$ are presented below without the proof. Let O be a zero matrix in M_NSR and E is a unity matrix in M_S consisting of all entries equal to 1 in S. Then according to (7), (27) and (28), for any W, A ∈ M_S and U, H ∈ M_NSR the following identities hold:

A^O = E; ^OA = E; W * E = E * W = W;

(29)

^UA^H * ^UA^−H = ^U(A^H−H) = ^UA^O = ^UE = E.

(30)

The last identity remains valid if the presented actions are reversed from the left to the right.

4. MPF Sigma Identification Protocol (SIP)

In general, sigma identification protocols (SIP) are realized using the conversation between the Prover and the Verifier when the Prover proves to the Verifier the knowledge of the secret (e.g., his private key—witness) without revealing knowledge about this secret [19]. In this case it is said that SIP has the Zero Knowledge Proof (ZKP) property [19]. Prover is using his private, public key pair we denote by PrK, PuK named as a witness-statement pair.

We denote any matrix Q that is generated uniformly at random from the matrix set M by Q ← rand(M).

We use matrix sets M_sNSR and M_Γ introduced in Section 3 instead of the matrix set M_NSR to provide a random uniform distribution of data generated in MPF SIP.

Parties share the same public parameter represented by matrix W in M_S generated at random W ← rand(M_S). The prover runs the following key pair generation algorithm. For the private key PrK-witness generation two secret matrices X, Y in M_Γ = {1, 3} are chosen at random:

X,Y ← rand(M_Γ).

(31)

Then PrK = (X, Y)∈M_Γ × M_Γ.

The public key PuK-statement is computed using $MP{F}_S^{sNSR}$ defined above:

PuK = ^XW^Y = A.

(32)

Prover distributes his PuK = A ∈ M_S to all users including Verifier. According to the 3-rd condition in the Proposition 2 represented by the distributive identity (7), we formulate the following easily verified theorem without proof.

Theorem 3.

$MP{F}_S^{sNSR}$ satisfies the distributive identity (7).

Definition 8.

Equation (32) defines a set of relations Rel between the set of witnesses (PrK) and statements (PuK) which is a subset of the following direct product of sets:Rel ⊆ (M_Γ ×M_Γ) × M_S.

Since relations R₁, R₂ in (11) define a finite semiring S, they induce the finiteness of sNSR. Then, sets M_sNSR and M_S are finite as well.

Definition 9.

Let matrix A = {a_ij} be of finite order and assume that all entries q_ij can be effectively encoded by the finite string of bits not exceeding polynomial length. Then, matrix A is effectively recognizable in M_S if all its entries can be effectively decoded and effectively transformed to the normal form (15).

Proposition 6.

Any finite length word w in S can be transformed to the normal form (15) using the linear number of operations with respect to the length of w.

Definition 10.

RelationRelis efficiently recognizable if every matrix A’ = {a_ij’}, where a_ij’are finite strings of generators a, b in M_S, can be effectively transformed into the matrix A inM_Swith all entries expressed in the normal form (15).

Definition 11.

Relation is an effective relation if it is efficiently recognizable.

Proposition 7.

Relation Rel is effective.

Referencing to the general definition of Sigma protocol in [19], the corresponding definition can be formulated for MPF SIP.

Definition 12.

LetRel ⊆ (M_Γ ×M_Γ) × M_S be an effective relation. An MPF SIP for Rel is a pair (P, V) of interactive protocols executed by the Prover and the Verifier. Protocol P is taking a witness-statement pair (PrK, PuK) ∈ Rel as an input. Protocol V is taking as an input statement PuK ∈ M_S. Then after the conversation V outputs accept or reject.

MPF SIP is performed during three pass communications named as a conversation between the Prover and the Verifier.

• Prover generates two matrices U, V ← rand(M_Γ) at random and using his witness-PrK computes the commitment C = (C₀, C₁, C₂) consisting of three matrices C₀, C₁, C₂ in M_S:

  C₀ = ^UW^V, C₁ = ^UW^Y, C₂ = ^XW^V.

  (33)

  Prover sends C to the Verifier.
• After receiving C, Verifier generates two matrices H′, H″ ← rand(M_sNSR) at random and independently, forms challenge H = (H′, H″) and sends H to the Prover.
• Upon receiving H, Prover computes the response R = (S, T) consisting of two matrices S, T in M_sNSR:

  S = U + H′X, T = V + YH″,

  (34)

  and sends R = (S, T) to the Verifier.

At this stage Prover and Verifier complete the conversation. After receiving R = (S, T), Verifier checks if

^SW^T = C₀ * C₁^H″ * ^H′C₂ * ^H′A^H″,

(35)

and if it is the case outputs accept.

The distinct feature of the proposed protocol (against, e.g., Schnorr or Okamoto protocols, [19]) is that the Prover generates a commitment at the first step of the protocol using components X, Y of the witness-PrK = (X, Y).

Completeness. On the common statement input PuK = A, the honest Prover knows witness-PrK = (X, Y) for PuK and succeeds in convincing the Verifier of his knowledge with probability 1. It follows from the validity of associativity identity (6) and distribution identity (7):

^SW^T = ^(U+H′X)W^(V+YH″) = ^UW^V * ^UW^YH′′ * ^H′XW^V * ^HX′W^YH′ = ^UW^V * (^UW^Y)^H″ * ^H′(^XW^V) * ^H′(^XW^Y)^H′ = C₀ * C₁^H″ * ^H′C₂ * ^H′A^H″.

Verifier uses the conversation (C, H, R) together with the Prover’s statement PuK = A for the verification and yields accept if (35) holds.

The test example of this protocol is presented in Appendix A.

5. Security Analysis

We consider the main three main kind of attacks for SIP presented in [19] ordered by their power, i.e., direct attack, eavesdropping attack and active attack. The weakest attack of the three is a direct attack and it is applied mainly for password protected systems which can also be realized using symmetric cryptography. The outcome of these attacks is either adversary impersonation of legal Prover or even compromisation of legal prover’s secret, namely his password or private key PrK-witnwss. The detailed description of the attack game and the theorem formulating security against this attack is presented in ([19], Section 18.3). Since this attack is not of direct interest for our research, we only use the security formulation for this attack in our construction in Theorem 4 below as an intermediate result to consider the more powerful eavesdropping attack. In this section we prove the conditions under which the proposed MPF SIP is resistant against eavesdropping attack finalizing it in Theorems 5 and 6. Unfortunately, we were not able to prove the resistance against most powerful active attack for the reasons presented below.

Assumption 1.

$MP{F}_S^{NSR}$ is a candidate for one-way function (OWF).

This assumption can be supported by our previous results presented in [11,12,13,14]. The MPF is constructed using similar algebraic structures as in [14]. In [12,13] the NP-completeness of the similar MPF problem is proven. MPF function introduced there is defined in finite modified medial platform semigroup and finite power near-semiring. Despite the lack of proof of the NP-completeness of the MPF problem defined here, we can present some links of this MPF with the well-known multivariate quadratic (MQ) problem which is proved to be NP-complete over any field [7]. Let φ: S → S_a is the homomorphism of the semigroup S to the semigroup S_a defined by the introduced new relation b = 1. Then S_a = {1, a, a², a², a⁴} is a cyclic monoid with index 1 and period 4 [20]. The corresponding public matrix denoted by W’. Then the entries of this public matrix W’ consist of elements aⁱ, where I ∈ {0, 1, 2, 3, 4} due to relation R₁. Analogously, the NSR can be homomorphically transformed to the set of integers Z₅ = {0, 1, 2, 3, 4} by introducing the relation ι = 0. Then the matrices X’, Y’ ← rand(Z₅) are generated.

Since S_a is a cyclic semigroup then the discrete logarithm operation dlog_a with the base a can be applied elementwise to the MPF relation ^X′(W′)^Y′ = A′. In this case we obtain MQ problem but defined not over the field F₅ = {0, 1, 2, 3, 4} (where operations are defined mod 5) since according to relation R₁ in (11) the exponents of generator a cannot be reduced mod 5. It seems that the obtained MQ problem represented by matrix equation

dlog_a(^X′(W′)^Y′) = dlog_a(A′),

is at least no less complex than the “standard” MQ problem. Then, we can make an assumption that MPF introduced in (4), (32), where unknown monomials are in exponents is a candidate for one-way function (OWF).

This assumption is required to prove that the proposed MPF SIP is secure against the eavesdropping attack and to select the values of the security parameters.

Referencing to Assumption 1 and [19], we can formulate the following theorem.

Theorem 4.

If $MP{F}_S^{NSR}$ is a candidate for OWF and the challenge space is super-poly, then MPF SIP identification protocol is secure against the direct attack.

Proof. 

According to the Assumption 1, $MP{F}_S^{NSR}$ is a candidate for OWF.

Referencing to the relations R₁, R₂ in (11), the challenge space is exponential with respect to the order m of matrices in M_NSR. The cardinality of M_NSR is no less than 5^2mm, thus, it is super poly as well. □

It is easily verified that Assumption 1 and Theorem 4 can be applied to $MP{F}_S^{sNSR}$.

In order to formulate the security against the eavesdropping attack, we need the definition and the proof of the Honest Verifier Zero Knowledge (HVZK) property [19] for MPF SIP. We realized that instead of HVZK of MPF SIP we can prove a rather stronger result denoted as a special HVZK.

Definition 13.

Identification protocol is a special HVZK if there exists an efficient probabilistic algorithm called a simulator Sim such that for all possible witness-statement pairs or private and public key pairs (PrK, PuK) the following two conditions hold: 1) the output distribution of Sim on input (PuK, H) is identical to the distribution of transcript of a conversation (C, H, R) between Prover on input (PrK, PuK) and Verifier on input Puk, and 2) for all inputs PuK and H, algorithm Sim always outputs a pair (C, R) such that (C, H, R) is an accepting conversation for PuK.

Following the methodology presented in [19], the following theorem can be formulated.

Theorem 5.

MPF SIP protocol is a special HVZK.

Proof. 

On Sim input R’, H’ and PuK, the valid commitment C′ = (C_0′, C_1′, C_2′) and corresponding transcript of a conversation (C′, H′, R′) must be generated with identical distribution as (C, H, R) between the Prover and the Verifier. □

Lemma 2.

Let W be a public parameter and two pairs of matrices X,Y ← rand(M_Γ), X′,Y′ ← rand(M_Γ) are generated uniformly at random, then the entries of matrices A = ^XW^Y and A′ = ^X′W^Y′ computed according to (32) are uniformly distributed.

Proof of Lemma.

Define two subsemigroups in S, namely S_a = {a, a², a³, a⁴}, S_b = {b, b², b³, b⁴} and a set of exponents of generators in S denoted earlier by N₄⁺ = {1, 2, 3, 4}. Then exponent function of generator a in S_a provides the following 1-to-1 mapping exp_a: N₄⁺ → S_a. Since exp_a is 1-to-1, then for any I ← rand(N₄⁺) the value exp_a (i) = aⁱ will have a uniform random distribution. The same is valid for the function exp_b: N₄⁺ → S_b. Let exp_a,a: N₄⁺ × N₄⁺ → S_a is a function defining multiplication of generator aⁱ by generator a^j, where i, j ← rand(N₄⁺), i.e., exp_a,a (i, j) = aⁱa^j = a^i+j. According to R₁ in (11), function exp_a,a (i, j) provides a 4-to-1 mapping and hence the value a^e obtained after the reduction of exponent a^i+j using R₁ will have a uniform random distribution.

Let us consider the double exponent function expexp_a: N₄⁺ × Γ → S_a, where expexp_a(i, k) = (aⁱ)^k with I ∈ N₄⁺, k ∈ Γ. This function provides a 2-to-1 mapping. Let i, k values are random and uniformly distributed, then the value (aⁱ)^k is also random and uniformly distributed. The same is valid for the generator b and for complex exponents ι·i and ι·k. In the latter case complex unit ι simply changes a to b and vice versa.

As a consequence, the mentioned above exponents of generators a, b are random and uniformly distributed.

If we have any word w ∈ S and exponentiate it by i, then after the reduction of exponents corresponding to the generators a and b the uniform distribution of resulting exponents will be obtained. After that the generators are grouped according to the normal form defined in (15) and this grouping simply corresponds to computing expressions of the type aⁱa^j = a^i+j. Hence the grouping procedure will not change the uniform distribution. As a result, we obtain uniformly distributed normal form w_η in (14).

These results are applied subsequently to the left MPF and right MPF (according to Definitions 1 and 2) to prove the uniform distribution of entries of matrices A and A’ being a value of two sided MPF in Definition 3. The proof is performed by induction with respect to the order m of MPF matrices. The first step of induction for m = 1 is proved above.

The Lemma is proved. □

Lemma 3.

Suppose the following pairs of matrices X, Y ← rand(M_Γ), U, V ← rand(M_Γ), X′, Y′ ← rand(M_Γ), U′, V′ ← rand(M_Γ) and H^′, H^″ ← rand(M_sNSR) are generated uniformly at random. Then the distribution of entries of matrices S, T in (34) and of matrices S′, T′ computed by the relations.

S′ = U′ + H^′X′, T′ = V′ + Y′H^″,

(36)

have the same uniform random distribution.

Proof of Lemma.

Firstly, we prove that the product of matrices H′X, YH″ has the same uniform random distribution as the product of matrices H^′X′, Y′H^″. Let us consider a scalar case with h′x, yh″ and h^′x′, y′h^″ instead, where h′, h″, h^′, h^″ ∈N₄⁺ and x, y, x′, y′ ∈ Γ. Then the multiplication function is defined by the mapping mul_h,x: N₄⁺ × Γ → N₄⁺ which according to Table 2 is 2-to-1. Since multipliers are chosen uniformly at random, then the value mul_{h, x}(h, x) = hx in N₄⁺ is distributed uniformly at random. The same is valid for other terms.

Now consider the addition function add_u,z: Γ × N₄⁺ → N₄⁺ which according to Table 1 is 2-to-1. Then, since the value z = hx is distributed uniformly at random the value add_{u, z}(u, z) = s is also distributed uniformly at random.

The random and uniform distribution of entries of matrices H′X, YH″ and H^′X′, Y′H^″ can be proved by induction using the uniform and random distribution of values of functions mul_{h, x} and add_{u, z}. Then, the entries of matrices S, T and S′, T′ are distributed uniformly at random as well.

The Lemma is proved. □

Proof. 

Proceeding with the proof of the theorem, the response R′ = (S′, T′) must be computed referencing to (34). Then, the following random matrices in M_NSR are generated independently: U′, V′ ← rand(M_Γ), X′, Y′ ← rand(M_Γ). As an additional input the simulator takes two challenge matrices H^′, H^″ ← rand(M_sNSR × M_sNSR). Then, according to (34):

S′ = U′ + H^′X′, T′ = V′ + Y′H^″.

(37)

Referencing to Lemmas 2 and 3, R′ = (S′, T′) and R = (S, T) have the same uniform distribution and hence the distribution of ^S′W^T′ is the same as the distribution of ^SW^T in (35). According to the Theorem 3 ^S′W^T′ has the following expression

^S′W^T′ = ^{(U′+H^′X′)}W^{(V′+Y′H^″)} = ^U′W^V′ * ^U′W^{Y′H^″}* ^{H^′X′}W^V′ * ^{H^′X′}W^{Y′H^″} = ^U′W^V′ * (^U′W^Y′)^{H^″} * ^{H^′}(^X′W^V′) * ^{H^′}B^{H^″},

(38)

where B = ^X′W^Y′.

For given matrices U′, V′, X′, Y′ and (H^′, H^″) generated uniformly at random and independently, Sim must compute a challenge C′ = (C_0′, C_1′, C_2′) satisfying the following equation:

^S′W^T’ = C_0′ * (C_1′)^{H^″} * ^{H^′}(C_2′) * ^{H^′}A^{H^″}

(39)

Referencing to identity (37), Sim computes

C_0′ = ^U′W^V′, C_1′ = ^U′W^Y′, C_2′ = ^X′W^V′ * B^{H^″} * A^{−H^″}.

(40)

According to Theorem 5, the entries of matrices C_0′, C_1′, have the same uniform distribution as of matrices C₀, C₁. Since (1) the distribution of ^S′W^T′ is the same distribution as of ^SW^T, (2) ^X′W^V′ is uniformly distributed and (3) the computation of matrix C_2′ in (39) is based on Hadamar multiplication rule [16] (i.e., elementwise), then the distribution of C_2′ is the same as the distribution of C₂. Then the commitment C′ = (C_0′, C_1′, C_2′) has the same distribution as C = (C₀, C₁, C₂). It remains to prove that (C′, H′, R′) is an accepting conversation using the following identities.

C_0′ * (C_1′)^{H^″} * ^{H^′}(C_2′) * ^{H^′}A^{H^″} = ^U’W^V’ * (^U’W^Y’)^{H^′} * ^{H^′}(^X’W^V’) * ^{H^′}B^{H^″} * ^{H^′}A^{−H^″} * ^{H^′}A^{H^″}
= ^S’W^T’ * ^{H^′}A^{H^″-H^″} = ^S’W^T’ * ^{H^′}A^O = ^S’W^T’ * E = ^S’W^T’.

(41)

The theorem is proved. □

Since special HVZK implies HVZK, then according to the Assumption 1 and Theorems 4 and 5, proposed MPF SIP is secure against the direct attack and is HVZK. The Theorem 19.3 in [19] states that if an identification protocol is secure against direct attacks, and is HVZK, then it is secure against eavesdropping attacks. Referencing to this result we have proven the following theorem.

Theorem 6.

MPF SIP is secure against the eavesdropping attack.

Unfortunately, we are not able to prove the security of MPF SIP against an active attack since we have not proved the soundness of MPF SIP. Our construction is based on far more complicated algebraic structures than many traditional identification protocols including Schnorr protocol.

6. Selection of the Security Parameters and Efficiency Analysis

Since relations R₁, R₂ are fixed, the security parameter is the order m of matrices defining MPF. Then, according to (32) PrK and PuK matrix relation in the Definition 8 consists of m² exponent equations of the type (4). According to the Assumption 1 and the belief that the solution of randomly generated MQ system is hopeless when system consists of n ≥ 80 equations with v ≥ 80 variables [9], it is sensible to choose the number of exponent equations of the type (4) corresponding to the matrix equation (32) to be no less than 80. Then, m can be chosen to be equal to 10, 11, 12. In this case the number of exponent equations is equal to 100, 121, 144 correspondingly. To represent NSR elements of the types t + ι∙u + v and t∙ι + u + v∙ι, where t, u, v ∈ {1, 2, 3, 4} 9 bits are required. Thus, memory requirement for PrK = (X, Y) is 2 × 9 m² bits. To represent the word w in S in normal form (15) 6 bits are required. So, PuK = A representation requires 6 m² bits.

Effectivity of SIP is related to the left and right MPF value computations in (2) and (3) and can be performed using exponentiation tables of the size 4x4 in our case. Transformation of matrix entries to the normal form requires asymptotically O (m²) operations. The computational resources for the one-sided MPF value computation are equivalent to the matrix multiplication and are asymptotically at most O (m³). SIP realization for Prover requires 6 one-sided MPF values computation, 2 multiplication of matrices in NSR requiring O (m³) operations and two additions of matrices in NSR requiring O (m²) operations. Both matrix multiplication and addition can be performed using the table of operations of the size 4 × 4 as shown in Table 1 and Table 2.

For the Verifier’s side one must compute MPF values presented in (35). It takes two one-sided MPF computations for the left side of (35) and six one-sided MPF computations. Hence asymptotically it takes O (m³) operations.

7. Discussion and Conclusions

It was an intriguing idea for the authors to create and analyze Sigma identification protocol (SIP) based on the matrix power function (MPF) defined over the specially selected algebraic structures, namely modified platform medial semigroup S and power near-semiring (NSR). The initial medial semigroup is infinite, cancellative, multiplicative and non-commuting and is chosen to have two generators a and b. The modification of this medial semigroup is performed by introducing two extra relations R₁ and R₂ for the generators. It induces certain homomorphism yielding finite semigroup and preserving other properties of medial semigroup. In order to construct MPF, the certain power NSR is constructed. The properties of NSR are induced by the generic relation R_M of medial semigroup which makes addition operation non-commuting. Therefore, the notion of NSR is applied. The reason is that constructed NSR is simply not a semiring.

These algebraic structures are far more complicated than the structures used currently in well-known identification and sigma identification protocols, e.g., Schnorr or Okamoto protocols. They are based on relatively simple algebraic structures, namely cyclic groups Z_p^* or G_q. MPF SIP construction based on more complicated algebraic structures was successful since a very important property of MPF presented in Proposition 2 was satisfied. In this connection we are expecting that proposed MPF SIP should provide greater security than existing Sigma protocols based on numerical cyclic groups. The investigation of the resistance against quantum cryptanalysis attack is very attractive and could be dedicated for the future research.

MPF, presented here, has some similarity to the certain MPF problem which was proven to be NP-complete in our previous publications [12,13]. It is believed so far that NP-complete problems cannot be effectively solved by quantum computers. The security of MPF SIP presented here relies on the assumption that this MPF problem is a candidate for one-way function (OWF).

Following the methodology, notions and security analysis of Sigma protocols presented in D. Boneh, and V. Shoup tutorial we proved that the proposed SIP is secure against the eavesdropping attack. Unfortunately, the proof that this protocol is secure against active attack was not presented since we have not proved the soundness of this protocol yet. The soundness of identification protocols is easily proven for simple algebraic structures, namely Z_p^* or G_q. In our case, however, the algebraic structures are far more complicated and existing proof methodology used in cyclic groups cannot be applied.