Algebraic generalization of Diffie–Hellman key exchange

2.1 Computation

We follow the standard model of probabilistic polynomial time computation. A search problem is a binary relation R={0,1}*×({0,1}*∪{⊥}). For every (x,y)∈R, we call x an instance of the problem and y the solution to the instance x. If y=⊥, then we say that x has no solution. The set of solutions of an instance x is denoted by R⁢(x). A probability ensemble X={Xk}k∈ℕ consists of random variables Xk indexed by the natural numbers. Our problems will be distributional, meaning that a computational problem P=(R,X) always comes with a probability ensemble X={Xk}k∈ℕ from which its instances are drawn. Here, the index k∈ℕ determines the binary length of the instance. The notation y←𝖠⁢(x;r) means that a probabilistic algorithm 𝖠 on input x and randomness r outputs y.

Given a distributional search problem P=(R,X) and a probabilistic polynomial time (PPT) algorithm 𝖠, we are interested in the probability of 𝖠 solving a typical instance, called the advantage,

A function ϵ is negligible if for every n∈ℕ, there exists k′∈ℕ such that ϵ⁢(k)≤1/nk for every k≥k′. A problem P is infeasible if 𝐀𝐝𝐯𝖠P⁢(k) is negligible for every PPT algorithm 𝖠. The problem of distinguishing probability ensembles X={Xk}k∈ℕ and Y={Yk}k∈ℕ is denoted by D⁢(X,Y), and we have

for every PPT algorithm 𝖣.

2.2 Diffie–Hellman key exchange

The Diffie–Hellman scheme [24] is defined as follows. Let us assume that 𝖲 is an algorithm that on input the security parameter 1s, where s∈ℕ, samples a cyclic group G of a suitably large order and a generator g of G. Depending on the representation of the group, the order of the group should be chosen so that the Diffie–Hellman problem (see Definitions 2.2 and 2.3) is infeasible.

The security of the scheme depends on the infeasibility of the Diffie–Hellman problem.

The infeasibility of the computational version is often insufficient. We want the adversary to be unable to determine any information about ga⁢b. This is formalized by the decision version of the problem.

The DDHP is the problem of distinguishing the probability ensembles determined by (g,ga,gb,ga⁢b) and (g,ga,gb,gc).

2.3 Universal algebra

Universal algebra encompasses general concepts underlying different algebraic structures such as groups, semigroups, modules and quasigroups. Let A be a non-empty set and let n∈ℕ. A (finitary) operation on A of arityn is a function f:An→A. We define A0={∅}. A type of algebras is a function τ:Ω→ℤ≥0, where the elements of Ω are the basic operators of the type. The type τ assigns an arity for each basic operator f∈Ω.

An algebra (or an algebraic structure) of type τ is an ordered pair 𝐀=(A,F), where A is a non-empty set and F is a set of operations on A such that for every n-ary basic operator f of the type, there exists an n-ary operation f𝐀 on A. By the notation x∈𝐀, we mean x∈A, where 𝐀=(A,F). We often write f for f𝐀 when it is clear that we mean an operation and not an operator. If Ω={f1,f2,…,fn} for the type, then we write 𝐀=(A,f1,f2,…,fn) or 𝐀=(A,f1𝐀,f2𝐀,…,fn𝐀) for 𝐀=(A,{f1𝐀,f2𝐀,…,fn𝐀}) and often τ⁢(f1)≥τ⁢(f2)≥⋯≥τ⁢(fn). The set A of an algebra 𝐀=(A,F) is called the underlying set (or the universe) of 𝐀. An algebra 𝐀=(A,F) is finite if A is a finite set.

Let 𝐀=(A,FA) and 𝐁=(B,FB) be algebras of the same type. If B⊆A and for every basic operator f of the type, f𝐀|B=f𝐁, then 𝐁 is a subalgebra of 𝐀. In such a case, we write 𝐁≤𝐀. The set of subalgebras of an algebra 𝐀 is closed under intersections. Therefore, every X⊆A determines the smallest subalgebra 〈X〉≤𝐀 that contains X, the subalgebra generated by X.

Let 𝐀=(A,FA) and 𝐁=(B,FB) be algebras of the same type τ. A mapping α:A→B is a homomorphism from 𝐀 to 𝐁 if

for every n-ary basic operator f of the type and every ordered n-tuple (a1,a2,…,an)∈An. The set of homomorphisms from 𝐀 to 𝐁 is denoted by Hom⁢(𝐀,𝐁). If 𝐀=𝐁, then α is an endomorphism. The set of all endomorphisms of 𝐀 constitutes a semigroup and it is denoted by End⁢(𝐀). If α:𝐀→𝐁 is a surjective homomorphism, then 𝐁 is a homomorphic image of 𝐀.

Let τ be a type of algebras and let Ω be the set of basic operators of the type. Let X be a set of distinct objects called variables. The set of terms of type τ with variables X is the smallest set T⁢(X) such that X⊆T⁢(X), and for every p1,p2,…,pn∈T⁢(X) and every n-ary basic operator f∈Ω, the string f⁢(p1,p2,…,pn) belongs to T⁢(X).

We often consider n-ary polynomials over a field 𝔽 as polynomial functions 𝔽n→𝔽. Such a consideration can be also applied to terms. Let p⁢(x1,x2,…,xn) be a term of type τ over a set of variables X. Given an algebra 𝐀=(A,F) of type τ, the term function on 𝐀 corresponding to p is p𝐀:𝐀n→𝐀, defined as follows:

1. If p is a variable xi, then p𝐀⁢(a1,a2,…,an)=ai for a1,a2,…,an∈A.

2. If p is of the form f⁢(p1⁢(x1,…,xn),…,pk⁢(x1,…,xn)), where f is an k-ary basic operator, then

   p𝐀⁢(a1,a2,…,an)=f𝐀⁢(p1𝐀⁢(a1,…,an),…,pk𝐀⁢(a1,…,an)).

For our considerations, the term functions are useful since they behave like the finitary operations with respect to congruences and homomorphisms [14]. In particular, for every homomorphism α:𝐀→𝐁 and every n-ary term p, we have

for every a1,a2,…,an∈𝐀.

3.1 Cyclic group based schemes

Different versions of the DH have been obtained by replacing ℤp* with another cyclic group [70, 49]. There are suggestions based on finite extension fields [12] and groups based on elliptic curves over finite fields [56, 47]. A common element is obtained by the commutativity of exponentiation or multiplication. In particular, the elliptic curve groups E⁢(𝔽p), for p prime, have yielded very successful variants of the DH. Other groups over Abelian varieties have been also suggested in [48]. Another variant is the XTR [50] and its predecessors [51, 58, 59, 75, 49, 12]. Rubin and Silverberg [69] suggested the group structure on an algebraic torus. A common element is established by the commutativity of exponentiation in 𝔽qm and by mapping the result to the torus using a birational map. Buchmann and Williams suggested a generalization of the Diffie–Hellman scheme based on an “almost” cyclic group structure on a set of reduced principal ideals of a real quadratic field [13]. A common reduced ideal is derived based on the commutativity of real number multiplication and addition. These methods are based on the idea of replacing the original group family. Therefore, algebraically such schemes can be considered in the framework of the original DH.

3.2 Diffie–Hellman based on pairings and multilinear maps

Pairings on elliptic curves have been used both in cryptanalytic investigations, as well as in many useful cryptographic constructions. Joux was the first to point out the cryptographic potential of such pairings and suggested a three-party generalization of the Diffie–Hellman scheme based on the Weil and Tate pairings [43]. The common key is established between three parties based on the homomorphic property of the pairing e. The security follows from the hardness of computing e⁢(P,P)a⁢b⁢c from (P,a⁢P,b⁢P,c⁢P), where P is a point on the curve and a,b,c are random integers. Based on Joux’s scheme, Verheul [80] suggested a variant with reduced exponentiations and half the number of exchanged bits, as well as a variant of the ElGamal encryption scheme. Bilinearity was also used by Boneh and Franklin [7] to construct a fully functional identity-based encryption scheme.

Boneh and Silverberg [8] extended Joux’s scheme to n≥4 parties using multilinear maps. First practical schemes for n-party key exchange for any n were suggested by Garg, Gentry and Halevi [33] using ideal lattices (the GGH scheme) and by Coron, Lepoint and Tibouchi [20] using the integers (the CLT scheme). However, these schemes have been shown to be insecure [39, 15]. The improved version of GGH [34] have been also shown to be insecure [19]. Obfuscation-based multilinear maps have been suggested in [83, 9, 1].

3.3 Schemes based on commuting functions

Several methods have been suggested to generalize the DH by replacing group exponentiations with other commuting functions. In principle, for such schemes, we are not interested in the underlying algebraic structure. However, the functions are often generated using algebraic methods. For example, Shpilrain and Zapata [73] characterized discrete logarithm based primitives on groups of prime order as a group action Aut⁢(G)×G→G. They suggested a generalization based on commuting semigroup actions on a set. To the best of our knowledge, semigroup actions were first suggested by Monico [57]. Similar suggestions can be found in [53] and [78]. There are also suggestions based on commuting chaotic maps [82].

3.4 Non-commutative structure based schemes

The field on non-commutative cryptography is often considered to have started with the work of I. Anshel, M. Anshel and Goldfeld [4] and Ko et al. [46]. Ko et al. suggested a Diffie–Hellman like scheme using the braid group and commuting inner automorphisms. According to [21], the same scheme has been independently suggested by Sidel’nikov [74] using a non-commutative semigroup. A polynomial time algorithm breaking the Ko et al. scheme on the braid group can be found in [16]. Baumslag et al. [5] suggested a scheme based on a finitely presented group G with two commuting subgroups A,B≤G. A common key is derived using the identity a⁢b⁢g⁢b′⁢a′=b⁢a⁢g⁢a′⁢b′ for every g∈G,a,a′∈A and b,b′∈B. A semidirect product A⋊B of two groups, where B is Abelian, was suggested by Habeeb, Kahrobaei and Shpilrain [37]. A common key was established based on two commuting embeddings φ,ϕ:A→Aut⁢(B).

In the supersingular isogeny key exchange (SIDH), Alice and Bob create distinct, non-commuting isogenies ϕA, ϕB of a known curve E. They generate point pairs (PA,QA) and (PB,QB), and share their images (ϕA⁢(PB),ϕA⁢(QB)) and (ϕB⁢(PA),ϕB⁢(QA)) under the secret isogenies. In the supersingular case, the endomorphism ring is non-commutative. However, based on the homomorphic properties of the two isogenies ϕA and ϕB, Alice and Bob are able to derive a shared curve EA⁢B that is isogenous to E. The established key is defined as the j-invariant of this curve [41].

For the Anshel–Anshel–Goldfeld (AAG) scheme [4], the common key follows from the homomorphic property β⁢(x,y1⋅y2)=β⁢(x,y1)⋅β⁢(x,y2) together with γ1⁢(x,β⁢(y,x))=γ2⁢(y,β⁢(x,y)). For the conjugation based AAG [4, 3] on a non-commutative group, the key is derived as the commutator [a,b] of elements a and b contributed by Alice and Bob, respectively. Shpilrain and Ushakov [72] generalized the construction to use the centralizer instead of the commutator. For both of these schemes, the common key follows from the homomorphic property. Braid groups have been suggested as the platform. However, both schemes can be broken in polynomial time on the braid group [79].

Stickel [77] suggested the application of a non-commutative semigroup G for key exchange. Let g1,g2∈G be non-commuting elements. Alice and Bob exchange g1a1⁢g2a2 and g1b1⁢g2b2. A common key g1a1+b1⁢g2a2+b2 is derived by the commutativity ga+b=gb+a. The application of tropical algebras for the implementation of this scheme was suggested in [35]. Rabi and Sherman [67] suggested the use of associative one-way binary operations. In such a case, a common key is derived based on associativity.

3.5 Schemes based on lattices

Due to strong security guarantees, lattice based schemes have become a strong alternative for post-quantum cryptography. Since the seminal work of Regev [68] on the learning with errors problem (LWE), a lot of research has been attracted on schemes implementing, for example, cryptographic hash functions, public-key cryptography, digital signature schemes, as well as fully homomorphic encryption [65].

In [42], Ding, Xie and Lie introduced an extension of the Diffie–Hellman problem with errors based on the LWE (and the corresponding problem in a cyclotomic ring, R-LWE). The common key is derived based on the associativity of matrix multiplication by computing a bilinear form in two different ways: (xT⁢A)⁢y=xT⁢(A⁢y), where T denotes the transpose. Peikert [66] applied the R-LWE in the construction of a key encapsulation mechanism and an authenticated key exchange scheme. In the scheme, a “randomized function” 𝖽𝖻𝗅, a reconciliation function 𝗋𝖾𝖼 and two modular rounding functions ⌊⋅⌉2,〈⋅〉2 are used to establish a common key μ in two different ways: μ=⌊𝖽𝖻𝗅(v)⌉2 and μ=𝗋𝖾𝖼⁢(w,〈𝖽𝖻𝗅⁢(v)〉2), where w=g⁢(e0⁢a+e1)⁢s1 and v=g⁢e0⁢(a⁢s1+s0)+e2 are noisy ring elements. A key encapsulation mechanism can be also implemented based on the NTRU cryptosystem [38, 22], as well as on error correcting codes [23].

Based on Peikert’s scheme, Bos et al. [11] investigated the parameters for a practical implementation, and the resulting scheme was later optimized by Alkim et al. [2] into a scheme called NewHope. Based on the work of Ding, Xie and Lin [42], Bos et al. [10] applied the generic LWE in a scheme called Frodo. A provably secure authenticated key exchange protocol applying the R-LWE was presented by Zhang et al. [84], and a password authenticated key exchange scheme was presented by Ding et al. [25].

3.6 Non-associative structure based schemes

There are many suggested applications of non-associative algebras in cryptography. It has been applied, for example, to construct block ciphers, stream ciphers, hash functions and authentication schemes.

Some suggestions for key exchange exist. The implementation of commuting semigroup actions based on both exponentiation and conjugation in a Moufang loop was suggested by Maze [52]. A generalization of the conjugation based AAG for LCC loops was given by Partala and Seppänen [64]. The construction works for any LCC left quasigroup [63] and, similarly to the original AAG, the common key is derived as the commutator but this time on the left multiplication group; the permutation group generated by the bijections La⁢(x)=a*x, where * is the binary operation of the left quasigroup. A generalized Diffie–Hellman scheme was first described in [61] and it is refined in this paper. The common key is derived based on the homomorphic property. Wang et al. [81] suggested a scheme similar to the DH by considering conjugacy search in a monoid. The scheme works in a non-associative left distributive (LD) structure Q, satisfying a*(b*c)=(a*b)*(a*c) for every a,b,c∈Q, induced by conjugation, and a common key is derived based on the property an+m*b=an*(am*b), where * is the binary operation of the LD structure and the exponentiation is conducted in the original monoid. In this case, the common key is a result of both the homomorphic property of conjugation and the commutativity of exponentiation.

We have gathered the essentially different key exchange schemes and their algebraic properties into Table 1.

4.1 Universal algebraic view of the Diffie–Hellman scheme

Our construction is based on the following observation. Let us consider a cyclic group Gi as an algebra 𝐆i. Then every exponentiation function αa:x↦xa is both an endomorphism and a term function 𝐆i→𝐆i. Let us now consider the original Diffie–Hellman key agreement scheme in the following form that introduces an apparent asymmetry in the computational procedures of Alice and Bob.

Alice first samples a private endomorphism αa:x↦xa, where a←U⁢(ℤ|𝐆i|). Bob generates a random term p of the type of 𝐆i such that the term function p𝐆i is polynomial time computable. He computes

The same term function is applied on αa⁢(g)=ga to obtain a secret element:

The binary operation is not actually applied b-1 times. Rather, Bob chooses a term function such that the fast exponentiation algorithm can be applied to reach gb and ga⁢b in a polynomial number of operations. Alice can compute αa⁢(gb)=ga⁢b and the equality of the established key follows from the homomorphic property of αa.

We can immediately see that it is possible to exchange the group family 𝔾 with a family of non-group algebras. That is, we can consider two algebras 𝐀,𝐁 of the same type and let αa∈Hom⁢(𝐀,𝐁). There are three different algorithms implicit in the scheme:

1. The sampling algorithm 𝖲 that can be considered to sample both (i,g) and αa.

2. A probabilistic polynomial time random composition algorithm𝖱 that, on input i∈I and an element x∈𝐆i, samples a term p and computes the term function on x.

3. A deterministic polynomial time homomorphism computation algorithm𝖧 that, given i∈I, a∈ℤ and an element x∈𝐆i, evaluates αa⁢(x).

For the generalization of the group family to a family of algebras, these algorithms need to be made explicit. For example, for the group family case, both 𝖱 and 𝖧 compute xa using the fast exponentiation algorithm.

4.2 The homomorphic image problem

In this section, we carefully construct a rigorous definition for the family of algebras, as well as for the homomorphic image problem. In order to be able to increase the security of the different constructions using a security parameter, the family has to consist of pairs (𝐀i,𝐁i) indexed by a countably infinite index set I. We need a sampling algorithm 𝖲 that samples such pairs, outputs the corresponding i∈I and a set of generators a1,a2,…,an for 𝐀i. We also need the family to have a meaningful composition algorithm 𝖱, for term function generation, that can be randomized. For an algebra with n generators, potentially several such algorithms can be devised. In contrast, the only meaningful composition algorithm for a group family is the fast exponentiation algorithm with a randomized exponent. To see why this is the case, we observe that each element of a cyclic group 𝐆i is of the form gx for x∈ℕ, where g is a generator of the group. Therefore, for every term p, there exists z∈ℕ such that p𝐆i⁢(g)=gz, and the fastest way to compute it is using the fast exponentiation algorithm. Finally, we require participants to be able to efficiently compute homomorphisms φ∈Hom⁢(𝐀i,𝐁i) for every i∈I. Therefore, the family has to come with an explicitly stated set of efficiently computable homomorphisms and a deterministic homomorphism computation algorithm 𝖧.

We consider a family of algebras as a countably infinite set of triples (𝐀i,𝐁i,ℋi), where 𝐀i and 𝐁i are algebras of the same type and ℋi⊆Hom⁢(𝐀i,𝐁i), together with the three algorithms explained above. Let us formulate these notions in a rigorous manner.

The requirement (4.1) imposed on 𝖱 restricts it to respect the homomorphisms of the algebra. In general, this means that 𝖱 generates a random n-ary term p of the type such that 𝖱 can compute both term functions p𝐀 and p𝐁 in polynomial time. Then, depending on d, 𝖱 computes either p𝐀 or p𝐁.

Let us consider the DH in the form of Definition 4.1. Alice obtains ga⁢b as the image under the endomorphism α. For an eavesdropper, the problem of computing ga⁢b from (g,ga,gb)=(g,αa⁢(g),gb) can be seen as the problem of computing the image of gb under an unknown endomorphism αa. Therefore, we formulate an analogue for the computational DHP in the following manner: we give a set of elements and their homomorphic images under an unknown homomorphism. Then we sample a random element x from the algebra and ask for its homomorphic image under the same homomorphism. We call this analogue of the DHP the homomorphic image problem (HIP).

We can easily deduce a necessary condition for the infeasibility of the CHIP. Suppose that it is feasible to find a term p of the type such that the term function on a1,a2,…,an evaluates to x. Suppose also that the term function can be computed as a polynomial number of applications of the operations of 𝐀i. If such a factorization as a term is given, we can exchange each occurrence of aj by φh⁢(aj) and each occurrence of an operation of 𝐀i by the corresponding operation of 𝐁i. Since φh is a homomorphism, the image φh⁢(x) is then obtained by evaluating the obtained expression, which can be done in polynomial time since 𝐁i is efficiently computable. Therefore, finding such a factorization as a term needs to be infeasible.

The requirement for the polynomial length in i ensures that p𝐀 can be evaluated in polynomial time. For the group family case, finding a factorization of ga using the generator g is equivalent to the DLP.

Let us now formulate the decision version of the HIP.

Note that when B=1, 𝖱 is run with fresh randomness. That is, we are either given the correct homomorphic image (B=0) or a random element from 〈φh⁢(a1),φh⁢(a2),…,φh⁢(an)〉 (B=1) each with probability 1/2. Let S={Ss}s∈ℕ denote the probability ensemble corresponding to the choice of the string

according to (i,h,a1,a2,…,an)←𝖲⁢(1s), and let X={Xs}s∈ℕ and Z={Zs}s∈ℕ denote the probability ensembles corresponding to the choice of x and z according to

If 𝖣 is a probabilistic polynomial time algorithm, we define its DHIP-advantage on 𝔸 as

For a group family 𝔾, the DHI assumption is equivalent to the decision Diffie–Hellman assumption with the choice of 𝖲,𝖱 and 𝖧 as in Example 4.6.

In the more general setting, the DH can be now written in the following form.

The secret randomness used by Alice is the index h of the homomorphism φh. For Bob, the secret randomness is the internal randomness r used by 𝖱.

Comparing AGDH to DH, we note that several properties of the platform algebra affect the performance of the scheme. For example, a large number of generators n results in a large number of transmitted elements from Alice to Bob. The optimal case is obtained with mono-generated algebras. In this regard, DH is optimal. On the other hand, contrary to DH, AGDH is not symmetric with respect to Alice and Bob. Asymmetry enables us to minimize the computational effort of Bob in a scenario where we want the key exchange to be light-weight for one of the parties. Contrary to DH, where 𝖧 and 𝖱 essentially apply the same algorithm, in AGDH these can be different. It is possible that, for some algebras, 𝖱 can be made very efficient at the expense of 𝖲 and 𝖧. For example, if the number of generators is large, then Alice needs to compute and communicate a large number of homomorphic images. However, since the number of generators is large, Bob can reach a large number of different elements of the algebra with only a few applications of the finitary operations.

4.3 Potential instantiations

In this section, we offer some concrete examples of potential algebras for AGDH. To instantiate AGDH, the family of algebras has to support a large set of homomorphisms. We have identified four different approaches and described them below.