An improvement of cryptographic schemes based on the conjugacy search problem.pdf 1. Introduction The first detailed proposal for a key exchange protocol, due to Diffie and Hellman [1], was based on the discrete logarithm problem for a finite field. This protocol is one of the earliest practical examples of public key exchange implemented within the field of cryptography. It was followed by few alternative proposals for key exchange protocols, all based on commutative algebraic structures. Noncommutative cryptography is the area of cryptology where the cryptographic primitives, methods, and systems are based on algebraic structures like semigroups, groups and rings which are noncommutative. One of the earliest applications of a noncommutative algebraic structure for cryptographic purposes was the use of braid groups to develop the Commutator key exchange protocol by Anshel, Anshel and Goldfeld (AAG) [2] and the noncommutative key exchange protocol on braids by Ko et al. [3]. Later, several other noncommutative structures like nilpotent and polycyclic groups, and matrix groups have been identified as potential candidates for cryptographic applications. In [4], the author introduced the method of linear decomposition applicable in algebraic cryptanalysis. In [5], this method was further developed by the author and A. G. Myasnikov, see also [6]. In [7], this method was supplemented by the nonlinear decomposition method. These applications are called linear and nonlinear decomposition attacks respectively. They are deterministic, provable and polynomial-time. These methods were widely applied in cryptanalysis of dozens of protocols of algebraic cryptography, see monograph [8] and references therein. The linear decomposition attack can be applied to protocols based on matrix groups over arbitrary (finite or infinite) fields. The nonlinear decomposition attack is applicable to protocols based on groups that are not necessary matrix, or do not use matrix representations. The main distinguishing feature of these methods is that they reveal secret exchanged keys from open data without calculating the secret parameters used in the algorithm. Thus, we show that in this case, contrary to the common opinion, the typical computational security assumptions are not very relevant to the security of the schemes, i.e., one can break the schemes without solving the algorithmic problems on which the assumptions are based. In [9] (see also [10]), B. Tsaban et al. introduced a method for obtaining provable polynomial-time solutions of problems in noncommutative algebraic cryptography called the linear span-method, or simply the span-method. This method is probabilistic. This method is a fundamental base for algebraic span cryptanalysis, a general approach for provable polynomial-time solutions of computational problems in groups of matrices over finite fields, and thus in all groups with efficient matrix representations over finite fields. This approach is widely applicable, in particular, it is applicable to the protocols mentioned above. The main aim of this note is to describe the idea of using the concept of marginal sets to enhance the protocols based on the conjugacy search problem. In [11], the author presented an improved version of the AAG protocol based on this idea, see also [12] with some versions of AAG and Ko et al. protocols. In [13], the author proposed a new more strong version of the Diffie - Hellman non-commutative key exchange protocol of Ko et al. These new versions are resistant against attacks by methods of linear algebra. They are based on new hard algorithmic problems using a notion of a marginal set. In particular, they are resistant against attacks by the methods of Tsaban, and against the authors methods of the linear and nonlinear decompositions. Notations: N - the set of nonnegative integers, Sn - symmetric group of degree n, gh = = hgh-:i - conjugate, Fq - field of order q, M(n, Fq) is the algebra of n х n matrices over Fq. 2. The marginal sets The introducing concept of marginal set formally generalizes the well-known concept of the marginal subgroup, but it is worth noting that this generalization is very different from the original concepts. The marginal subgroup is determined by the word, but the marginal subset is determined by the word and its chosen value. The set of all marginal subsets is not closed under algebra-and group-theoretic operations. It can be very wild. For brevity, we give definitions only for the case of algebra. Let F be a free associative algebra with unity on a countably infinite set {xi, x2, . . .} and let w = w(xi, . . . , xk) G F. If gi, . . . , gk are elements of the algebra M, we define the value of the word w at g = (gi,... ,gk) to be w(g) = w(gi,... ,gk). A subset N C M is said to be w-marginal in M if w(gi, . . . , gk) = w(uigi, . . . , ukgk) for all gi E G, ui E N, 1 < i < n. Obviously, all w-marginal subsets constitutes the maximal marginal subset w*(M), which is a submonoid in Mk. We introduce a new concept that significantly extends the marginality property. Definition 1. For k E N, let w = w(xi, . . . , xk) be an algebra word, M be an algebra and g = (gx,..., gk) be a tuple of elements of M. We say that a tuple c = (cx,..., ck) E Mk is a marginal tuple determined by w and g if w(cigi, ..., Ck gk) = w(gb ..., gk ')■ We will write c ± w(g) in this case. A set (J Q Mk is said to be marginal with respect to w and g if c ± w(g) for every tuple c E C. We write C ± w(g) in this case. Now we give a very simple and efficient algorithm for constructing a marginal set C ± w(gi, . . . , gk). This method does not depend on the structure of M. Let w(gi, . . . , gk) E M be any value of w(xi, . . . , xk). Note that some elements gi, gj can be equal to each other, that is, gi = gj. Consider an equation of the form w(zigi,...,zkgk)=w(gi,...,gk) (1) such that there is zi that can be expressed in the form zi = zi(zi, . . zi-i, zi+i, . . . , zk, gi, . . . , gk). (2) Then for any substitution zj = fj, fj E M, j = 1, . . . , i - 1, i + 1, . . . , k, we get a new marginal tuple (fi,...,fi-i,zi(fi,...,fi-i,fi+i,...,fk,gi,...,gk),fi+i,...,fk)EMk (3) with respect to w and gJ. To hide the word w in (1) and elements fi, . . . , fk, gi, . . . , gk, (2) can be rewritten by expressing all the constituent elements through parameters and the generating elements mi, . . . , ms of the algebra M. The formula (2) can be changed as follows. Let us introduce into consideration the set of parameters yi, . . . , yq with arbitrary values in M. Let zj = = zj(yi, . . . , yq, mi, . . . , ms) be an arbitrary presentation for j = 1, . . . , i - 1, i + 1, . . . , k. Then zi = zi(yx,...,yq,mi,...,mk) be the rewritten presentation (2) of zi. These parametric presentations can be published. This form of representation does not make it easy to recover the word w in (1). Every solution of (1) can be included in a marginal set C, C ± w(g). We also can multiply a marginal tuple cJ= (ci, . . . , ck) to any tuple uJ = (ui, . . . , uk) E w*(M)k, and get new marginal tuple cJuJ = (uici, . . . , ukck). 3. An improved version of the conjugacy search problem Recall the classical definition. Definition 2. Conjugacy Search Problem (CSP). For a group G, we are asked to find an element x from u, v E G satisfying v = ux E G. The version suggested below uses any private expression of the element g in the form of a word. Such view allows the use of a marginal set for given expression, defined below. It also becomes possible to apply multipliers that are not changed by the used transformation (conjugation). These methods protect the protocol from the attacks by methods of linear algebra. They change the underlying problem to a much more complex one. Let's move on to a description of the proposed changes. They are partially presented in [11-13]. Assumptions. Let F be an arbitrary field (in particular Fq). Let G C M(n. F) be a matrix group and B be a finitely generated subgroup of G. Fix an element g G M = Alg(G) (the algebra generated by G in M(n. F)). We assume that all the data above is public. We set Fix(B) = {o G G : ob = o for all b G B}. Algorithm. Data selection and transmission. Firstly we describe Alice's action: - Alice chooses a tuple g = (g1..... gk) G Mk and a ring word u = u(x1..... xk) such that g = u(g1..... gk). This data is private. - Alice takes arbitrary private elements gk+1..... gm G M (these elements are called virtual) to obtain g = (g1.....gk. gk+1..... gm) G Mm. She also chooses a private tuple of elements h = (h1..... hk) G Fix(B)k and adds this tuple by random private elements hk+1..... hm of M to get h = (h1.....hk .hk+1.... .hm) G Mm. Alice gets gh = gh = (g1 hb....gfc hk. gk+1hk+1..... gmhm) G Mm. Then she picks up a private random permutation n G Sm and publishes the tuple ghn (gn(1)hn(1). . . . . gn(m)hn(m)). - Alice constructs a marginal set C C Mk, C ± u(g1..... gk), adds each c = (c1..... ck) G G C by arbitrary elements ck+1..... cm to get c = (c1..... ck. ck+1..... cm) and publishes Cn {cn (cn(1)..... cn(m)) : c G C}. Bob's action is similar. Now we restrict ourselves by considering the improved version of the conjugacy search problem, not some specific protocol. Algorithm. Data processing: - Bob chooses a random element b G B. - Bob chooses a random tuple cn G Cn and calculates cn(gh)n. Then he computes (cn (gh)n) ((cn(1)gn(1)hn(1)) ..... (cn(m)gn(p) hn(p)) ) and sends the result to Alice. Algorithm. The key generation. Alice's action: - Alice uses n-1 to remove virtual elements and get from (cn(g h)n)b the tuple (cg)bL - She multiplies the result to h-1 = (h-1..... h-1) and gets cgb. - Alice computes u(cgb) = u(cg)b = u(g)b = gb. In many protocols Alice obtains the shared key as K = (gb)a = gab. where a G G is her private element commuting with b. Cryptanalysis. One cannot directly apply known method to calculate b. Indeed, for this one need in a pair of the form r, rb (r G M), but instead one has r, (cr)b (c G M). Instead, one can try to find the word u/(x1,...,xk) (one can be change k), indexes i1, . . . , ik and elements hi G Fix(B) (i = 1, . . . , k) so that u (gii hii h1, ... , gik hik hk) g. But even if successful, this does not guarantee that the following equality holds: u ((gii hii h1) , . . . , (gik hik hk) ) g , because the marginality of C depends of the word u(x1, . . . , xk) and in general is not true for another word that presents g.

Скачать электронную версию публикации