WO2003013052A1

WO2003013052A1 - Cryptosystems based on non-commutatity

Info

Publication number: WO2003013052A1
Application number: PCT/KR2001/001283
Authority: WO
Inventors: Kihyoung Ko; Sangjin Lee; Jaechoon Cha; Dooho Choi
Original assignee: Korea Advanced Institute Of Science And Technology
Priority date: 2001-07-27
Filing date: 2001-07-27
Publication date: 2003-02-13

Abstract

The present invention relates to key agreement protocol, public key cryptosystem and digital signature scheme that are cryptographically secure and efficient. More specifically, the present invention provides a method of constructing a key agreement protocol and a public key cryptosystem based on the difficulty of recovering factors from a hidden product in a non-commutative semi-group and based on a trapdoor using a pair of commutative subsets of the semi-group. The present invention also provides a method of constructing a digital signature scheme using an algebraic structure that has an infeasible search problem but has a cryptographically feasible decision problem. The key agreement protocol, the public key cryptosystem and the digital signature scheme can be implemented on various concrete algebraic platforms described in this invention.

Description

[DESCRIPTION]

[TITLE OF THE INVENTION]

CRYPTOSYSTEMS BASED ON NON-COM MUTATITY

[TECHNICAL FILED]

The present invention relates to encoding and decoding of information

and, more particularly, key agreement protocol, public-key cryptosystem for

encryption and decryption of messages by processor systems, and data security

involving digital signatures transmitted with data.

[BACKGROUND OF THE INVENTION]

With the development of computer technology, the cryptography systems

are widely used to encode messages to preserve the privacy and the integrity of

the messages, as well as the authenticity and the non-repudiation of the

originator of the message.

A public key cryptosystem is one in which each party can publish their

encoding process without compromising the security of the decoding process.

The encoding process is popularly called a trap-door one-way function. Public

key cryptosystems, although generally slower than private key cryptosystems, are

used for transmitting small amount of data, such as credit card numbers, and also

to transmit a private key which is then used for private key encoding.

Since the "public-key cryptosystem" was described by W. Diffie and M. E.

Hellman, "New Directions In Cryptography", IEEE Transactions on Information

Theory 22(1976), 644 — 654, many public-key cryptosystems have been proposed

and broken. Most of successful cryptosystems require large prime numbers.

The difficulty of factorization of integers with large prime factors forms the ground of RSA scheme proposed by R. L. Rivest, A. Shamir and L. Adleman, "A Method

for Obtaining Digital Signatures and Public-key Cryptosystems", Communications

of the ACM 21 (1978), 120—126, and its variants. Also the difficulty of the

discrete logarithm problem forms the ground of Diffie-Hellman type schemes like

EIGamal scheme by T. EIGamal, "A Public Key Cryptosystem and a Signature

Scheme Based on Discrete Logarithms", IEEE Transactions on Information

Theory 31 (1985), 469 — 472, elliptic curve cryptosystem and DSS.

There have been several efforts to develop alternative public-key

cryptosystems that are not based on number theory, since most of the

conventional cryptosystems are based on hard problems in the number theory

whose security is questionable due to newly developed cryptoanalysis and the

improvement in calculation capability. Especially, if the quantum computer

becomes a reality, the security of cryptosystem based on factorization problem

can no longer be guaranteed. Hence, development of a new cryptosystem is

increasingly being asked for.

The first attempt was to use NP-hard problems in combinatorics like

Merkle-Hellman Knapsack system by R. C. Merkle and M. E. Hellman, "Hiding

Information and Signatures in Trapdoor Knapsacks", IEEE Transactions on

Information Theory 24 (1978), 525 — 530, and its modifications.

Another approach is to use hard problems in combinatorial group theory

such as the word problem by N. R. Wagner and M. R. Magyarik, "A Public-key

Cryptosystem Based on the Word Problem", Advances in Cryptology,

Proceedings of Crypto '84, LNCS 196(1985), 19—36, but most of the encryption

systems based on the problem of combinatorial group theory are neither practical nor secure and did not progress beyond a theoretical stage.

Recently there are two attempts to use variations of the conjugacy

problem in combinatorial groups to compose cryptosystems. An algebraic key

agreement protocol is proposed by I. Anshel, M. Anshel and D. Goldfeld, "An

Algebraic Method for Public-key Cryptography", Mathematical Research Letters

6(1999) 287 — 291. The security of this key agreement protocol is based on a

multiple simultaneous conjugacy problem and the trap-door of the one-way

function is the homomorphic property of conjugation. One of disadvantage of this

algebraic key agreement protocol is that it is impossible to compose a practical

public-key cryptosystem,

The other attempt is the public-key cryptosystem as well as the key

agreement protocol proposed by K. H. Ko, S. J. Lee, J. H. Cheon, J. W. Han, J. S.

Kang and C. S. Park, "New public-key cryptosystem using braid groups",

Advances in Cryptology - Proceedings of Crypto 2000, LNCS 1880(2000) 166—

183. The security of the cryptosystems was based on the conjugacy problem in

the braid groups with respect to two commuting subgroups and the trapdoor of

one-way functions is the commutativity of the two subgroups. However the

security of the cryptosystems is actually based on the Diffie-Hellman type

decomposition problem on the braid groups as explained later. Furthermore no

digital signature scheme is proposed in the work. The key agreement protocol

and the public-key cryptosystems in the present invention are more naturally

based the Diffie-Hellman type decomposition problem and therefore the security

and the efficiency are improved. Furthermore the cryptosystem in this invention

are composed on many algebraic structures other than the braid groups. On the other hand, the digital signature is utilized in order to authenticate

or verify that the message received could have only originated from the signatory

and it is identical to the original message. Digital signature schemes are classified

into two categories: digital signature schemes with appendix and digital

signatures with message recovery. And each category is further divided into two

types: randomized (probabilistic) schemes and deterministic schemes. The digital

signature scheme in the present invention is a randomized digital signature

scheme with appendix.

In a randomized digital signature scheme with appendix the originator (or

signer) passes the data to be signed (e. g., a computer file or document) together

with a random nonce through a one-way hash function and then signs the

resulting hash value using the private key of the originator to obtain an appendix.

The originator then sends the data, the random nonce, and the appendix to the

recipient (or verifier). The recipient passes the received data together with a

random nonce through the same one-way hash function obtaining a hash value.

The recipient then verifies the appendix with the public key of the originator

against the recovered hash value.

All of digital signature schemes used in practice are based on the hard

problem in number theory. For example the RSA digital signature schemes and it

variations, the Radin signature schemes, Fiat-Shamir signature schemes, and

GQ signature scheme are based on the integer factoring problem and DSA and

its variations, EIGamal signature schemes, and Schnorr signature scheme are

based on the discrete logarithm problem.

The digital signature scheme in the present invention is the first digital signature scheme that is composed on non-commutative algebraic structures and

yet it is simple, efficient and secure.

[SUMMARY OF THE INVENTION]

The first objective of the present invention is to provide a

cryptographically secure key agreement protocol based on non-commutative

semi-group.

The second objective of the present invention is to provide a

cryptographically secure public-key cryptosystem based on non-commutative

semi-groups.

The third objective of this invention is to provide a cryptographically

secure digital signature scheme based on non-commutative semi-groups.

A method for key agreement between two parties, Alice and Bob, in

accordance with the present invention comprises the steps of selecting a non-

commutative semi-group G; selecting a factor-hiding procedure H in G; selecting

a unique expression procedure U in G; selecting a pair-wise commuting 4-tuple (J,

K, J, K') of subsets in G; choosing an element x in a semi-group G; Alice

choosing a random pair (/,/) e J x J'and sending y_A=H(j, x,j') to Bob; Bob

choosing a random pair (U') e Kχ K'and sending

x, k') to Alice; Alice

receiving ye and computing K = U(jy_BJ') for a shared secret key; and Bob

receiving ^ and computing K = U(k y_A k' ) for said shared secret key.

A method for encoding and decoding a digital message m in public-key

cryptosystem, in accordance with the present invention, comprises the steps of

selecting a non-commutative semi-group G; selecting a factor-hiding procedure H

in G ; selecting a unique expression procedure U in G; selecting a pair-wise commuting 4-tuple (J, K, J', K' ) of subsets in G; selecting an encryption function

E ; selecting a decryption function D ; choosing a fixed x e G; choosing a random

pair ( ,/ ) e J J' ; producing a private key ( ,/) ; producing a public key (x, y) by

constructing y = H(j, x, j' ) ; choosing a random pair (k, k' ) e K x K' ; producing an

encoded message (c, of) from a message m by constructing c = H(k, x, k' ) and

constructing d = E(H( f, y, k'), m) ; decoding an encoded message (c, of) to

recover the message m by computing e = H(J, c,j') and computing m = D(e, d).

A method for digital signature to sign on a digital message m and verify

the signature, in accordance with the present invention, comprises the steps of

selecting a non-commutative semi-group G ; selecting a factor-hiding procedure

H in G ; selecting a family {F_a} _ae G of homomorphic functions with a

cryptographically feasible algorithm P for the matching-pair decision problem;

selecting a hash function h such that for a message m and a random nonce r,

h(m, r) is an element of G ; choosing elements x and a in G ; producing a private

key a ; producing a public key (x, u) by constructing u = F_a(x) ; selecting a random

nonce r until y is not a power of x where y - h(m, r) ; producing a digital signature

(v, r) for a digital message m by constructing v = F_a(y) ; verifying a digital

signature (v, r) for a digital message m by rejecting it if y is a power of x or P(y, v)

= NO or P(W(x, y), W(u, v)) = NO for some Wwritten on two letters, accepting it

otherwise.

[BRIEF DESCRIPTION OF THE DRAWINGS]

Fig. 1 is a step diagram of a system that can be used in an embodiment

of the present invention.

Fig. 2 is a flow diagram of key agreement protocol in accordance with the present invention.

Fig. 3 is a flow diagram of a public key encryption system which, when

taken with the subsidiary flow diagrams referred to therein, can be used in

carrying out embodiments of the present invention.

Fig. 4 is a flow diagram of a routine, in accordance with an embodiment

of the invention, for generating public and private keys.

Fig. 5 is a flow diagram in accordance with an embodiment of the

invention, for encoding a message using a public key.

Fig. 6 is a flow diagram in accordance with an embodiment of the

invention, for decoding an encoded message using a private key.

Fig. 7 is a flow diagram in accordance with an embodiment of the

invention, for generating signature and verifying the signature.

Fig. 8 is a flow diagram of a routine, in accordance with the embodiment

illustrated in Fig. 7, for generating public and private keys.

Fig. 9 is a flow diagram of a routine, in accordance with the embodiment

illustrated in Fig. 7, for generating signature and sending message with the

signature.

Fig. 10 is a flow diagram of a routine, in accordance with the embodiment

in Fig. 7, for verifying the signature.

[BEST MODE FOR CARRYING OUT THE INVENTION]

In order to describe the mathematical concept of the present invention,

the mathematical terminology needs to be made precise. Most of the

terminology is widely used in mathematics and the rest is defined specifically in

this article. Some of the common terminology will be used without definition if there is no danger to cause any confusion.

A semi-group is a set in which an associative binary operation is defined.

A semi-group with the identity in which each element has an inverse, is called a

group. Thus, a group will be regarded as a special case of a semi-group. A

semi-group is non-commutative if the binary operation is not commutative. A

finitely presented semi-group has finitely many generators and defining relations.

A finitely presented semi-group may have either finitely or infinitely many

elements. For example, the n-braid group B„ is a finitely presented group with

(n-1 ) generators

for |/- |>1 and

cησjσi≡σjσjσj for

The symmetric group S_n has the same presentation as

the n-braid group except additional relations σ? =1. Then S_n is finite but B_n is

infinite. See the book of J. S. Birman, "Braids, links and mapping class groups",

Annals of Math. Study 82, Princeton University Press (1974).

An element of a semi-group is a word written in generators, but two

distinct words may express the same element due to defining relations. Thus, in

order to use an infinite non-commutative semi-group for cryptography, it must

have a fast solution to the word problem that asks whether two words are equal.

A good source of finitely presented groups is a set of graphs called Dynkin

diagrams. Coxeter groups are finitely presented groups generated by reflections

and defined by relations according to Dynkin diagrams [J. E. Humphreys,

"Reflection Groups and Coxeter Groups", Cambridge Studies in Advanced

Mathematics 29, Cambridge University Press (1990)]. To each Coxeter group,

an Artin group is associated. For example, the n-braid group B_n is the Artin

group associated to the symmetric group S_n that is a Coxeter group defined by the Dynkin diagram of type >4_n-ι . Many of Artin groups are automatic and so the

word problem for them is solved in quadratic time by transforming a word to its

normal form [D. B. Epstein, "Word Processing in Groups", Jones and Bartlett

Publishers (1992)]. Another source of finitely presented group that are useful in

cryptography is automorphisms of surfaces. The group of isotopy classes of

automorphisms of a surface is called a mapping class group of the surface. For

example the /7-braid group is the mapping class group of t? punctured disk.

Mapping class groups are also automatic [L. Mosher, "Mapping class groups are

automatic", Annals of Math. 142(1995)]. Furthermore mapping class groups can

be totally ordered [H. Short and B. Wiest, Ordering of mapping class groups after

Thurston", L'Enseignement Math. 46(2000)] so that any two elements in a

mapping class group are distinguishable.

A representation of a group G is a homomorphism from G to the group

GL(V) of isomorphisms of a free module V over a commutative ring k. If k is a

numeric field like finite fields, an element of GL(V) can be uniquely expressed by

a numeric matrix and so an element of G is uniquely expressed via a

representation. Any conjugacy invariant of the matrix like coefficients of its

characteristic polynomial becomes an invariant of the conjugacy class of the

group element.

A vector space that forms a group under an associative multiplication that

is compatible with vector space operations is called an algebra. An algebra is

finite dimensional if it has a finite basis as a vector space. An element of a finite

dimensional algebra can be uniquely expressed as a linear combination over a

basis. An interesting construction of algebras is to take deformations of group

rings of some of Coxeter groups, called Weyl groups. These algebras are called

Hecke algebras. For example the Hecke algebra of type A_n- is a deformation of

the complex group algebra C[S_n] of the symmetric group S_n. In cryptographic

purpose, the coefficient ring can be taken as a finite field k instead of the ring of

complex number C and a Hecke algebra becomes an algebra over the Laurent

polynomial ring k[q^V2, q^'V2] of a deformation parameter q. The n-braid group B_n is

mapped into the Hecke algebra of type / i [V. F. R. Jones, "Hecke algebra

representations of braid groups and link polynomials", Ann. of Math. 128 (1987)].

This Hecke algebra is semisimple for a generic deformation parameter and thus

many irreducible representations of B_n can be obtained explicitly. One of the

irreducible representations is the well-known Burau representation. Similarly

many other Artin groups are mapped into the Hecke algebras of the

corresponding types.

The π-braid group is also homomorphically mapped into other algebras,

like the Temperley-Lieb algebra [L. H. Kauffman and S. L. Lins, Temperley-Lieb

Recoupling Theory and Invariants of 3-Manifolds", Princeton University Press

(1994)], the Birman-Murakami-Wenzl algebra [J. S. Birman and H. Wenzl "Braid,

link polynomial and a new algebra" Trans. Amer. Math. Soc. 313 (1989)],

quantum groups over various Lie algebras, and in general an endomorphism

monoid of a tensor product of n copies of an object in a braided tensor category

[G. Lusztig, "Introduction to Quantum Groups", Progress in Math. 110, Birkhauser

(1993)]. One of simple summands of the Birman-Murakami-Wenzl algebra is

known as the Begelow-Krammer-Lawrence representation of the n-braid group |V. Turaev, "Faithful linear representations of the braid groups", arXiv:math

GT0006202 (2000)]. In general simple summands of deformed group algebras

or quantized universal enveloping algebras of Lie algebras are sometimes

determined by a matrix with Laurent polynomial entries of the deformation or

quantization parameters and in this case the matrix evaluated at a numeric value

can be used to extract conjugacy invariants.

Some graded algebras like the algebras which the π-braid group is

mapped into, have an interesting trace that is an conjugacy invariant and

sometimes the trace can be computed efficiently. Many well-known polynomial

invariants of knots and links like the Jones polynomial, the two-variable Jones

polynomial, and the Kaufman polynomial can be obtained via the traces in the

Temperley-Lieb algebra, into the Hecke algebra of type A?-ι, and the Birman-

Murakami-Wenzl algebra, respectively. Thus, these polynomials are also

conjugacy invariants of the n-braid group.

Now we describe the five cryptographical primitives that are essential to

construct the cryptosystems in the present invention.

1. A factor-hiding procedure H in a semi-group G

For any positive integer k > 1 , a factor-hiding procedure H takes a -tuple

(xι, x₂,..., X_k) of digitized elements of G as an input and computes the output - (x-i,

Xz, ..., Xk) which is a digitized form of the product x-ιx₂...Xk in G. An output of H

can be recursively used as an input entry. A factor-hiding procedure H should be

computationally fast and efficient. The other requirement is "factor- hiding," that

is, it should be computationally infeasible to know a factor x,- from /-/(x-,, x₂,..., X_k).

Using a factor-hiding procedure, a complex element of G can be efficiently digitized without revealing its factors so that elements of a semi-group and binary

operations among them can be used on cryptography. Since an output of H can

be recursively used as an input entry, it is enough to define a factor-hiding

procedure that takes a pair (x, y) of digitized elements of G. However, it is

sometimes computationally advantageous to have a factor-hiding procedure that

processes an arbitrary number of factors at the same time, especially under some

hardware environments where parallel processing is possible.

There are several implementations of factor-hiding procedures in the

present invention, depending on algebraic platforms. The following is the

detailed description of the implementations of the present invention.

If the working platform G is an Artin group such as the n-braid group

whose element has a unique canonical form in the sense of [J. S. Birman, "Braids,

links and mapping class groups", Annals of Math. Study 82, Princeton University

Press (1974)] or [J. S. Birman, K. H. Ko and S. J. Lee, "A new approach to the

word and conjugacy problems in the braid groups" Adv. in Math. 139 (1998) 322-

353], then H(x-ι, X2,..., Xk) is the unique canonical form of the product

which is a product of canonical factors. In the n-braid group each canonical

factor can be digitized as a permutation on {1 , 2,..., n}. The procedure H on a

product x-ιx₂...X_k of k canonical factors needs to performs at most k(k+ )/2

operations of the left (or right) weighted decomposition between pairs jX_/+ι of

consecutive factors recursively and, therefore, the time complexity of H is

quadratic in k on a sequential-computing device. Since two operations on two

pairs of consecutive factors situated away from each other can be performed

independently, the time complexity of H of becomes linear in k on a parallel- computing device. In fact, if a parallel-computing device is capable of computing

lk/2J operations of left (or right) weighted decomposition simultaneously, the

procedure H on an input Xι ₂... /c needs to perform at most 2k operations.

If the working platform G is a finite dimensional algebra over a numeric

field, then H(x , x₂,..., X_k) is the list of the coefficients of a unique linear

combination of the product x-ιx₂...Xk over a basis of the algebra. In Hecke

algebras or quantum groups, the coefficients are polynomials in deformation or

quantization parameters.

If the working platform G is a matrix group over a numeric ring, then H(x- ,

x₂,..., Xk) is simply the product

of matrices which is unique.

If the working platform G is an automatic group whose element has a

unique normal form in a regular language in the sense of [D. B. Epstein, "Word

Processing in Groups", Jones and Bartlett Publishers (1992)], then H(x^, x₂,..., x_/c)

is the unique normal form of the product x-ιx₂...Xk which can be digitized by a path

from the start state to an accepted state in an automaton.

If the working platform G is in general a finitely presented semi-group, the

factor-hiding procedure H is a rewriting process, that is, H(xι, x₂,..., X_k) is the

result obtained by applying a random sequence of defining relations to the

concatenation xιx₂...x_/c which can be digitized by a list of symbols [N. R. Wagner

and M. R. Magyarik, "A Public Key Cryptosystem Based on the Word Problem"

Advances in Cryptology-Proceeding of CRYPTO 84, LNCS 196]. In this

implementation the expression H( ι, x₂,..., Xk) depends on a random sequence

and so it is not unique. In order to use this implementation in a key agreement

protocol or a public-key cryptosystem, a unique expression procedure is necessary.

2. A unique expression procedure U in a semi-group G.

A unique expression procedure U takes a digitized element x of a semi¬

group G as an input and computes the output U(x) which is a unique digitized

expression of x so that U(x) and U(y) are identical if x and y represent the same

element in G. A unique expression procedure should be computationally fast

and efficient and it should be also computationally easy to compare two outputs.

In order to design a key agreement protocol using a factor-hiding

procedure that does not output a unique expression such as an output of a

rewriting process mentioned above, the shared common key can be obtained by

the unique expression procedure. If a factor-hiding procedure already outputs a

unique expression as in the other cases above, the unique expression procedure

can be taken as the identity function.

There are several implementations of unique expression procedures in

the present invention, depending on algebraic platforms.

If the working platform G is a finitely presented semi-group and its

quotient semi-group obtained by adding more defining relations has a

computationally feasible solution to the word problem, then a unique expression

procedure is this solution.

If the working platform G is a finitely presented group that has a

computationally feasible representation over a numeric field, a unique expression

procedure is the result by taking this representation.

3. A pair-wise commuting 4-tuple (J, K, J', K' ) of subsets in a semi-group G.

Given a pair (J, J' ) of subsets in a semi-group G, the decomposition problem in G with respect to the pair is defined as:

Instance: A pair (x, y) e G χ G such that y = H(j, x, j' ) for some (j, j' ) e J

x J'

Objective: Find a pair (/,/) e Jx J'such that U(y)= U(H(j, x,/))

where H and U are a factor-hiding procedure and a unique expression procedure,

respectively

A pair-wise commuting 4-tuple (J, K, J', K') of subsets in a semi-group G

consists of four subsets J, K, J', K'oi a semi-group G with the following

properties:

(P1 ) jk = kj for any (j, k) e J x K or for any j, k) e J'χ K'

(P2) The decomposition problems in G with respect to the pairs (J, J' )

and (K, K' ) are infeasible.

A pair-wise commuting 4-tuple induces a problem that is essential to

compose a key agreement protocol and a public-key cryptosystem in the present

invention. The (computational) Diffie-Hellman type decomposition problem in G

with respect to a pair-wise commuting 4-tuple (J, K, J', K') is defined by:

Instance: A 3-tuple (x, y, z) <= G x G x G such that y = H(j, x, j' ) and z =

H(k, x, k' ) for some (j, k, j', k' ) e J K x J'x K'

Objective: Find an element w e G such that U(w)= U(H(j, H(k, x, k'),j' )).

The decisional version of the Diffie-Hellman type decomposition problem in G

with respect to a pair-wise commuting 4-tuple (J, K, J', K' ) can be also defined as

follows:

Instance: A 4-tuple (x, y, z, w) e G x G x G x G such that y = H(j, x, j' )

and z = H(k, x, k' ) for some (j, k, j', k' ) e Jx K x J'x K' Objective: Decide whether U(w)= U(H(j, H(k, x, k' ),}' )).

When G is a group and J is a subset of G, the conjugacy search problem

in G with respect to J is defined as:

Instance: A pair (x, y) e G x G such that y = H(/^"1, x, y) for somey e J

Objective: Find an element y e J such that U(y)= U(H(f x,J)).

A commuting pair (J, K) of subsets of a group G consists of subsets J and K of G

such that

(P1 )y f = A for any (j, k) <= Jχ K

(P2) The conjugacy search problems in G with respect to J and K are

infeasible.

A commuting pair (J, K) induces a problem that has been used to

propose a key agreement protocol and a public-key cryptosystem in [K. H. Ko, S.

J. Lee, J. H. Cheon, J. W. Han, J. S. Kang and C. S. Park, "New public-key

cryptosystem using braid groups", Advances in Cryptology - Proceedings of

Crypto 2000, LNCS 1880(2000) 166—183] called the Diffie-Hellman type

conjugacy problem in G with respect to a commuting pair (J, K) as follows:

Instance: A 3-tuple (x, y, z) e G x G x G such that y = H(/^"\ x,j) and z =

H(k^' x, k) for some (j, k) e Jx K

Objective: Find an element w e G such that U(w)= U(H(f H(k^' x, k), j)).

The decomposition problem and the conjugacy search problem is harder

than their corresponding problems of Diffie-Hellman type but it is not know the

former is strictly harder than the latter. The Diffie-Hellman type conjugacy

problem in G with respect to a commuting pair (J, K) is a special case of the

Diffie-Hellman type decomposition problem in G with respect to a pairwise commuting 4-tuple (J, K, J', K' ) where J = J' and K = K', j' = and k ' = k^" . Thus

an oracle that is able to solve the Diffie-Hellman type decomposition problem also

solves the Diffie-Hellman type conjugacy search problem in the same group.

The security of the key agreement protocol and the public-key cryptosystem in [K.

H. Ko, S. J. Lee, J. H. Cheon, J. W. Han, J. S. Kang and C. S. Park, "New public-

key cryptosystem using braid groups", Advances in Cryptology - Proceedings of

Crypto 2000, LNCS 1880(2000) 166—183] which is incorporated herein by

reference is based actually on Diffie-Hellman type decomposition problem and

therefore the key agreement protocol and the public-key cryptosystem in the

present invention is theoretically more secure.

There are several implementations of pair-wise commuting 4-tuples in the

present invention, depending on algebraic platforms.

If the working platform G is an Artin group corresponding to a Dynkin

diagram, a pair-wise commuting 4-tuple (J, K, J', K') is produced by choosing a

pair of subgroups (J, K) corresponding a pair of disjoint subdiagrams of the

Dynkin diagram and by choosing .a pair (J', K' ) corresponding another pair of

disjoint subdiagrams.

If the working platform G is the braid group B_n, a pair-wise commuting 4-

tuple (J, K, J', K' ) is produced by taking subgroups J, K generated by two disjoint

subsets of {σι,...,σ_n--ι} and J', regenerated by another two disjoint subsets of

{σ--ι,...,σ_π-ι}.

If the working platform G is the image of the n-braid group in an algebra

such as the Hecke algebra of type A i, the Temperley-Lieb algebra, the Birman-

Murakami-Wenzl algebra, and the quantum groups over various Lie algebras, the image of a pair-wise commuting 4-tuple in the n-braid group as explained in the

previous paragraph is a pair-wise commuting 4-tuple in G.

4. An encryption function E and a decryption function D

Two functions E and D are used to build the public-key cryptosystem of

the present invention. Let G be a semi-group, M be a space of messages and S

be a space of cipher texts. Then E : G x M → S and D : G x S -> M are feasible

functions satisfying the following properties.

(P1 ) For any xeG and meM, D(x, E(x, m)) = m.

(P2) E is a one-way function. Thus, it is infeasible to find x or m from £(x,

m).

There are two types of implementations of encryption and decryption

functions in the present invention, depending on algebraic operations.

If G is a group and the group multiplication is used, then M = S = G and

for fixed integers rand s that are not zero simultaneously, E(x, m) = H(x^r, m, X^s),

D(x, m) = H(x^'r, m, x^'s) where H is a factor-hiding procedure.

If G is a semi-group and the bit operation θ is used, then M = S = {0, 1}*

and for a fixed hash function h from G to {0, 1}¹, £(x, m)=D(x, m)= h(x) θ m.

5. A family {F_a} _ae G of homomorphic functions associated to an element a of

a semi-group G with a cryptographically feasible matching-pair decision problem.

A homomorphic function associated to an element a of a semi-group G

with a cryptographically feasible matching-pair decision problem is a feasible

function F_a from G to G satisfying the following properties:

(P1 ) F_a is a homomorphism, that is, F_a(xy) = F_a(x)F_a(y) for any element x, yof G. (P2) A pair (x, u) in GxG is called a related pair if u = F_a(x) for some a in

G. A randomly chosen pair (x, u) is not a related pair with

overwhelming probability.

(P3) The following matching related pair search problem is infeasible.

Instance: A related pair (x, u) in GxG

Objective: Find a related pair (y, v) in GxG such that y is not a power of x

and (W(x, y), W(u, v)) is a related pair for any word 11 written on two

letters

(P4) There is a cryptographically feasible algorithm P for the related-pair

decision problem, that is, for x, u e G, P(x, u) = YES, if (x, u) is a

matching pair and P(x, w) = NO otherwise where the terminology

"cryptographically" means that an algorithm is capable to output correct

answers with overwhelming probability.

A necessary condition for the property (P3) is that the following relater

search problem is infeasible.

Instance: A related pair (x, u) in GxG

Objective: Find an element h in G such that F,(x) = u

Thus the function F : GxG - GxG defined by F(a, x) = (x, F_a(x)) is an

one-way function. The difference of difficulty between the matching related-pair

(or relater) search problem and the related-pair decision problem constitutes an

essential property to compose the digital signature scheme in the present

invention.

In the present invention, a homomorphic function F_a associated to an

element a of a group G with a cryptographically feasible related-pair decision problem is defined by F_a(x) = H(a^'^, x, a) where H is a factor-hiding procedure in

G. In this case the related-pair decision problem, the matching related-pair

search problem, and the relater search problem are called the conjugacy decision

problem, the matching conjugate-pair search problem, and the conjugacy search

problem, respectively. The conjugacy search problem is clearly harder than the

matching conjugate-pair search problem although it is not known whether the

former is strictly harder than the latter. Therefore a homomorphic function F_a can

be implemented on any group where the conjugacy search problem is infeasible

but the conjuagcy decision problem is cryptographically feasible. Most of infinite

non-commutative groups mentioned above including algebras as multiplicative

groups have mathematically hard conjugacy search problems and have efficient

representations into matrix groups over numeric fields and so the conjugacy

decision problems are cryptographically feasible.

For a homomorphic function F_a defined by F_a(x) = H(a^'1, x, a) in a finitely

presented non-commutative group G, a cryptographically feasible algorithm P for

the conjugacy decision problem in the present invention computes and compares

one or more conjugacy invariants of u and x to decide whether u = F (x) or not.

The following are conjugacy invariants of a group G.

If G has a representation into GL(V) for a vector space Vover a field k,

then the characteristic polynomial of the image of an element in G under the

representation is a conjugacy invariant.

If G is a matrix group over a field k then the characteristic polynomial of a

matrix is a conjugacy invariant.

If G is an algebra over a field k then any irreducible summand of G can be regarded as a matrix group over a field and the characteristic polynomial of a

matrix represented by an element of G is a conjugacy invariant.

If G is a deformed algebra such as Hecke algebras, or a quantized hopf

algebra such as quantum groups, then any irreducible summand of G can be

regarded as a matrix group over or a polynomial ring over deformed or quantized

parameters and the characteristic polynomial (or its evaluation) of a matrix

represented by an element of G is a conjugacy invariant.

If G is an n-braid group, G has various representations into algebras such

as the Temperley-Lieb algebra, the Hecke algebra, the Birman-Murakami-Wenzl

algebra, and the quantum groups and the conjugacy invariants of these algebras

are conjugacy invariants of G. In particular the characteristic polynomials of the

Burau matrix or the Begelow-Krammer-Lawrence matrix (or their evaluation) are

conjugacy invariants.

If G is an n-braid group, the closure of an n-braid is a link and any link

invariants of the closure is a conjugacy invariants of the n-braid. These link

invariants include various polynomial invariants, finite-type invariants, Milnor's link

concordance invariants.

If a finitely presented group G has a fast and efficient solution to the word

problem via a unique canonical form, then a cryptographically feasible algorithm

P that solves the conjugacy decision problem corresponding to the matching

conjugate-pair search problem can be alternatively given as follows: For matching

pairs (x, u) and (y, v) in GxG and a word W written over two letters, the algorithm

P ask whether

\W(u, v)^N\ ≤ \W(x, y)^N\ + \a '\ + \b\ where u = F_a(x), v = F_b(y) and \w\ denotes the canonical length of w. If the

answer is affirmative for a large enough positive integer N, then P outputs YES.

If the answer is negative for some positive integer N, then P outputs NO.

Using the cryptographic primitives defined, the three fundamental

cryptosystems, key agreement protocol, public key cryptosystem and digital

signature scheme, are now established.

Fig. 1 shows a schematic step diagrams of the processor systems which

are used in the present invention.

Fig. 2 shows a basic procedure that can be utilized with a key agreement

protocol as described above. In this embodiment, it is assumed that Bob is a

use of processor system 105 and Alice is a user of processor system 155. Alice

and Bob exchange their keys through channel 50, for example, the Internet.

Fig. 3 shows a basic procedure that can be utilized with a public key

encryption system, and refers to routines illustrated by other referenced flow

diagrams which describe features in accordance with an embodiment of the

present invention. Step 310 represents the generating of the public key and

private key information, and the publishing of the public key. The routine of an

embodiment hereof is described in conjunction with the flow diagram of Fig. 4.

In the present embodiment, it is assumed that the operation is performed at

processor system 105. The public key information can be published; that is,

made available to any member of the public or to any desired group from whom

the private key holder desires to receive encrypted messages. Generally,

although not necessarily, the public key may be made available at a central public

key library facility or website where a directory of public key holders and their public keys are maintained. In the present embodiment, it is assumed that the

user (Alice) of processor system 155 wants to send a confidential message to the

user (Bob) of processor system 105, and that the user (Alice) of processor

system 155 knows the published public key of the user (Bob) of processor system

105.

Step 340 represents the routine that can be used by the message sender

(that is, in this embodiment, Alice) to encode the plaintext message using the

public key of the intended message recipient. This routine, in accordance with

an embodiment of the invention, is described in conjunction with the flow diagram

of Fig. 5. The encrypted message is then transmitted over channel 50, for

example, the Internet. (Fig. 1) However, channel 50 also may include various

communication network which acts as a similar role to the Internet, for example,

Intranet, local computer network, wide area computer network, radio

communication network.

Step 360 of Fig. 3 represents the routine for the decoding of the

encrypted message to recover the plaintext message. In the present

embodiment, it is assumed that this function is performed by the user (Bob) of the

processor system 105, who employs the private key information. The decoding

routine, for an embodiment of the invention, is described in conjunction with the

flow diagram of Fig. 6.

Key Agreement Protocol

The key agreement protocol according to the present invention is

composed of three cryptographical primitives in a non-commutative semi-group G

explained above, namely, a factor-hiding procedure H, a unique expression procedure U, and a pair-wise commuting 4-tuple (J, K, J, K').

The key agreement between two users, Alice and Bob, proceeds in the

following steps.

[One time setup]

Choose x e G. (Step 210)

[Key Agreement step]

Alice chooses randomly (j,j' ) e Jx J'and sends y_A=H(j, x,j' ) to Bob.

(Step 220)

Bob chooses randomly (k, k' ) e Kx 'and sends

x, k') to Alice.

(Step 230)

Alice receives y_s and computes K = U(j yβj') (Step 240).

Bob receives y_A and computes K = U(k y_A k' ) (Step 250).

Since j y^' = j (k x k' )j = k (jxj' ) k= ky_AW in a semi-group G, Alice and

Bob share the same key. The security of the present key agreement protocol is

precisely based on the decomposition problem described above.

Public-key Cryptosystem

A Public-key cryptosystem according to the present invention is

composed of four cryptographical primitives in a non-commutative semi-group G

explained above, namely, a factor-hiding procedure H, a pair-wise commuting 4-

tuple (J, K, J', K' ), an encryption function £, and a decryption function D.

Referring to Fig. 4, there is shown a flow diagram of the routine, as

represented by step 310 of Fig. 3, for generating the public and private keys. It

is assumed that the routine can be performed, in the present embodiment, for programming processor 110 of processor system 105 or a certification authority.

Processor 110 and the certification authority may have a program storage device

readable by a machine such as a computer, tangibly embodying a program of

instructions executable by the machine to perform the following steps.

[Key generation]

Choose a fixed x e G (Step 410).

Choose (/,/') ≡ J x J' randomly (Step 420).

Construct y = H(j, x, j' ) (Step 430).

Retain (j,j') as a private key (Step 440).

Publish (x, y) as a public key (Step 450).

In the above, the randomly choosing steps can be implemented by use of

random generator (not illustrated) of processor system (105).

Fig. 5 is a flow diagram, represented generally by step 340 of Fig. 3, of a

routine for programming a processor, such as processor 160 of processor system

155 to implement encoding of a plaintext message m.

[Encryption]

Given a message m e M. (Step 510)

Choose (k, k') e Kx K' randomly (Step 520).

Construct c = H(k, x, k' ) (Step 530).

Construct d = E(H(k, y, W ), m) (Step 540).

Ciphertext is (c, d) (Step 550).

Fig. 6 represents a flow diagram, represented generally by step 360 of

Fig. 3, of a routine for programming a processor, such as processor 110 of

processor system 105 to implement decoding of an encoded message. [Decryption]

Given ciphertext (c,d) (Step 610)

Calculate e = H(j, c,j') (Step 620).

Calculate m = D(e, d) (Step 630).

Since e = H(j, c, j' ) = H(j, H(k x k') ,j' ) = H(k, H(j xj' ) , k' ) = H(k, y, k' ),

we have

D(e, of) = D(e, E(H(k, y, k'), m)) = D(e, E(e, m)) = m.

Thus, the original message m is recovered in the decryption step. The

security of the present public-key cryptosystem is precisely based on the Diffie-

Hellman type decomposition problem described above.

If the encryption function E and the decryption function D are defined

using a hash function h and the bit operation Θ, that is, £(x, m)=D(x, m)= h(x) θ

m as explained earlier, the public-key cryptosystem in the present invention is

already "semantically secure" or "indistinguishable against chosen plaintext

attacks" and therefore the present public-key cryptosystem can be easily modified

to provable public-key cryptosystems according to Fusisaka-Okamoto's scheme

[E. Fusisaka and T. Okamoto, "How to enhance the security of public-key

encryption at minimum cost", PKC 99, LNCS 1560, Springer-Veriag, 1999, 53-68]

or Pointcheval's scheme [D. Pointcheval, "Chosen-ciphertext security for any

one-way cryptosystem", PKC 2000 LNCS 1751 , Springer-Veriag, 2000, 129-146]

so that the "indistinguishability against adaptive chosen-ciphertext attacks" is

equivalent to either a computational version or a decisional version of the Diffie-

Hellman type decomposition problem.

Digital Signature Scheme The Digital Signature Scheme according to the present invention is

composed of a cryptographical primitives in a non-commutative semi-group G

explained above, namely, a family {F_a} _ae G of homomorphic functions with a

cryptographically feasible algorithm P for the matching-pair decision problem,

together with a hash function h such that for a message m and a random nonce r,

h(m, r) is an element of G.

If G is the n-braid group, such a hash function h can be build by a keyed

hash function (MAC) using m as an input and ras a key followed by a procedure

converting bit strings to /i-braids.

Fig. 7 shows a flow diagram of transmitting encoded message with digital

signature. In the present embodiment, it is assumed that step 710 in which

public and private keys are generated and the public key is published is

performed by a certification authority or by processor system (105). Step 710 is

performed as illustrated in Fig. 8.

[Key Generation]

Choose elements x and a in G (Step 810).

Compute u = F_a(x) (Step 820).

Retain a as a private key (Step 830).

Publish (x, u) as a public key.

Fig. 9 shows a flow diagram of generating digital signature on processor

system 105 and sending message with the digital signature. Fig. 10 shows a

flow diagram of accepting signature by processor system 155.

[Signature Generation]

Given a message m e M (Step 910). Choose a random nonce r and compute y = h(m, r) (Step 920).

Determine whether y is a power of x or not (Step 930).

Go back to the previous step if y is a power of x.

Compute v = F_a(y) if y is not a power of x (Step 940).

Send (v, r) with the message m (Step 950).

[Signature Verification]

Receive the signature (v, r) and the message m (Step 1010)

Compute y = h(m, r) (Step 1020).

Determine whether y is a power of x or not (Step 1030).

If y is a power of x, the signature is rejected (Step 1080). Otherwise,

determine whether P(y, v) is "No" or not (Step 1040).

If P(y, v) is "No," the signature is rejected (Step 1080). Otherwise,

choose randomly a word W written on two letters (Step 1050).

Determine whether P(W(x, y), W(u, v)) is "YES" or not (Step 1060).

If P(W(x, y), W(u, v)) is "NO," the signature is rejected (Step 1080).

Otherwise, accept the signature (Step 1070).

Since F_a(W(x, y)) = W(F_a(x), F_a (y)) = W(u, v) by the homomorphic

property of F_a, that is, (W(x, y), W(u, v)) is a matching pair, a legitimate signature

is accepted. The security of the present digital signature scheme is precisely

based on the matching related-pair search problem described above.

[INDUSTRIAL APPLICABILITY]

As described so far, the present invention introduces a general method

with which a new key agreement, a new pubic-key cryptosystem and a new

digital signature scheme can be constructed using non-commutative algebraic structures including braid groups and deformed algebras. The security and

efficiency of cryptosystems in the present invention are theoretically better than

most of conventional cryptosystems based on commutative algebraic structures

such as large finite fields.

Claims

[CLAIMS]

1. A method for key agreement between two parties, Alice and Bob, comprising

the steps of:

selecting a non-commutative semi-group G ;

selecting a factor-hiding procedure H in G ;

selecting a unique expression procedure U in G ;

selecting a pair-wise commuting 4-tuple (J, K, J', K') of subsets in G ;

choosing an element x in a semi-group G ;

Alice choosing a random pair (j,j' ) <= J x J'and sending y_A=H(j, x,j' ) to Bob;

Bob choosing a random pair (k, k' ) e K x K' and sending y_B=H(k, x, k' ) to

Alice;

Alice receiving ys and computing = U(j yβj' ) for a shared secret key;

Bob receiving y_A and computing r = U(k y_A k' ) for said shared secret key.

2. The method according to claim 1 , wherein said non-commutative semi-group

G is an n-braid group.

3. The method according to claim 2, wherein said factor-hiding procedure H is

the conversion of the product of input braids into its canonical form, and

wherein said unique expression procedure U is the identity function.

4. The method according to claim 2 or 3, wherein said pair-wise commuting 4-

tuple (J, K, J', K' ) consists of two subgroups J, K generated by two disjoint

subsets of {σι,...,cr_n-ι} and two subgroup J', regenerated by another two disjoint subsets of {σι,...,σ_π-ι}.

5. The method according to claim 2, wherein said non-commutative semi-group

G is the image of the n-braid group in the Hecke algebra of type A?-ιl said

factor-hiding procedure H is the list of the coefficients of a unique linear

combination of the product of inputs; and said pair-wise commuting 4-tuple (J,

K, J, K') consists of the images of a pair-wise commuting 4-tuple of the n-

braid group.

6. The method according to claim 2, wherein said non-commutative semi-group

G is the image of the n-braid group in the Temperley-Lieb algebra.

7. The method according to claim 2, wherein said non-commutative semi-group

G is the image of the n-braid group in the Birman-Murakami-Wenzl algebra.

8. The method according to claim 2, wherein said non-commutative semi-group

G is the image of the n-braid group in the quantum groups over various Lie

algebras.

9. The method according to claim 2, wherein said factor-hiding procedure H is

the image of the product of input braids under any representation or any

character of said n-braid group.

10. The method according to claim 2, wherein said factor-hiding procedure H is the image of the product of input braids under any polynomial invariant of

closures of n-braids.

11.The method according to claim 2, wherein said non-commutative semi-group

G is an Artin group corresponding to a Dynkin diagram, and said pair-wise

commuting 4-tuple (J, K, J', K') is produced by choosing a pair of subgroups

(J, K) corresponding a pair of disjoint subdiagrams of the Dynkin diagram and

by choosing a pair (J', K') corresponding another pair of disjoint subdiagrams

of the Dynkin diagram.

12. The method according to claim 1 , wherein said non-commutative semi-group

G is an automatic group, and said factor-hiding procedure H is the conversion

of the product of inputs into its unique normal form in a regular language.

13. The method according to claim 1 , wherein said non-commutative semi-group

G is a finitely generated semi-group.

14. The method according to claim 13, wherein said factor-hiding procedure H is

the result obtained by applying a random sequence of defining relations to the

product of inputs, and wherein said unique expression procedure U is the

image of an input braid under a numerical representation of G.

15.The method according to claim 1 , wherein said non-commutative semi-group

G is a matrix group.

16. The method according to claim 15, wherein said factor-hiding procedure H is

the matrix multiplication of inputs, and wherein said unique expression

procedure U is the identity function.

17. A method for encoding and decoding a digital message m in public-key

cryptosystem, comprising the steps of:

selecting a non-commutative semi-group G ;

selecting a factor-hiding procedure H in G ;

selecting a unique expression procedure U in G ;

selecting a pair-wise commuting 4-tuple (J, K, J', K' ) of subsets in G ;

selecting an encryption function £ ;

selecting a decryption function D ;

choosing a fixed x e G ;

choosing a random pair (j, j' ) e J x J' ;

producing a private key (j,j' ) ;

producing a public key (x, y) by constructing y = H( , x, y' ) ;

choosing a random pair (k, k' ) e K x K' ;

producing an encoded message (c, d) from a message m by constructing c =

H(k, x, k' ) and constructing αf = E(H(k, y, W ), m) ;

decoding an encoded message (c, d) to recover the message m by computing

e = H(j, c, j' ) and computing m = D(e, d).

18. The method according to claim 17, wherein said non-commutative semi-group G is the n-braid group.

19. The method according to claim 18, wherein said factor-hiding procedure H is

the conversion of the product of input braids into its canonical form, and

wherein said unique expression procedure U is the identity function.

20. The method according to claim 19, wherein said pair-wise commuting 4-tuple

(J, K, J', K' ) consists of two subgroups J, r generated by two disjoint subsets

of {σι, ...,σ_π-ι} and two subgroup J', regenerated by another two disjoint

subsets of {σι,...,σ_π-ι}.

21.The method according to claim 20, wherein said encryption function £ and

said decryption function D are given by £(x, m)=D(x, m)= h(x) θ m where θ

denotes the exclusive-or operation n is a hash function from G to the set of bit

strings of the same length as m.

22. The method according to claim 20, wherein said encryption function £ and

said decryption function D are given by £(x, m) = H(x^r, B(m), X^s), D(x, m) =

H(x^'r, B(m), x^'s) where B is any function converting bit strings to an element of

G.

23. The method according to claim 17, wherein said non-commutative semi-group

G is the image of the n-braid group in the Hecke algebra of type A_n._\-

24. The method according to claim 23, wherein said factor-hiding procedure H is

the list of the coefficients of a unique linear combination of the product of

inputs, and wherein said pair-wise commuting 4-tuple (J, K, J, K' ) consists of

the images of a pair-wise commuting 4-tuple of the n-braid group.

25. The method according to claim 17, wherein said non-commutative semi-group

G is the image of the n-braid group in the Temperley-Lieb algebra.

26. The method according to claim 17, wherein said non-commutative semi-group

G is the image of the n-braid group in the Birman-Murakami-Wenzl algebra.

27. The method according to claim 17, wherein said non-commutative semi-group

G is the image of the n-braid group in the quantum groups over various Lie

algebras.

28. The method according to claim 18, wherein said factor-hiding procedure H is

the image of the product of input braids under any representation or any

character of said n-braid group.

29. The method according to claim 18, wherein said factor-hiding procedure H is

the image of the product of input braids under any polynomial invariant of

closures of n-braids.

30. The method according to claim 18, wherein said non-commutative semi-group G is a Artin group corresponding to a Dynkin diagram, and said pair-wise

commuting 4-tuple (J, K, J', K') is produced by choosing a pair of subgroups

(J, K) corresponding a pair of disjoint subdiagrams of the Dynkin diagram and

by choosing a pair (J', K' ) corresponding another pair of disjoint subdiagrams

of the Dynkin diagram.

31. The method according to claim 17, wherein said non-commutative semi¬

groups G is a matrix group, said factor-hiding procedure H is the matrix

multiplication of inputs, and said unique expression procedure U is the identity

function.

32. A method for digital signature to sign on a digital message m and verify the

signature, comprising the steps of:

selecting a non-commutative semi-group G ;

selecting a factor-hiding procedure H in G ;

selecting a family {F_a} _ae G of homomorphic functions with a cryptographically

feasible algorithm P for the matching-pair decision problem;

selecting a hash function h such that for a message m and a random nonce r,

h(m, r) is an element of G ;

choosing elements x and a in G ;

producing a private key a ;

producing a public key (x, u) by constructing u = F_a(x) ;

selecting a random nonce r until y is not a power of x where y = h(m, r) ;

producing a digital signature (v, r) for a digital message m by constructing v = Fa(y) ; verifying a digital signature (v, r) for a digital message m by rejecting it if y is a

power of x or P(y, v) = NO or P(W(x, y), W(u, v)) = NO for some W written on

two letters, accepting it otherwise.

33. The method according to claim 32, wherein said non-commutative semi-group

G is the n-braid group.

34. The method according to claim 33, wherein said factor-hiding procedure H in

G is the conversion of the product of input braids into its canonical form.

35. The method according to claim 33 or 34, wherein said family {F_a} _ae Q of

homomorphic functions with a cryptographically feasible algorithm P for the

matching-pair decision problem is given by F_a(x) = H(a^"1, x, a) where P(u, x) =

YES if one or more conjugacy invariants of u and x are equal and P(u, x) =

NO if at least one conjugacy invariant of u and x are distinct.

36. The method according to claim 35, wherein said cryptographically feasible

algorithm P is given by P(W(x, y), W(u, v)) = YES if the inequality \W(u, v)^N\ ≤

\W(x, y)^N\ + |a^"1| + |j | holds for a large enough positive integer N and P(W(x,

y), W(u, v)) = NO if the inequality does not hold for a positive integer N when

said cryptographically feasible algorithm P is applied to two elements W(x, y),

W(u, v) of a special type where u = F_a(x), v = F_b(y), W is a word written over

two letters, and |w| denotes the canonical length of w.

37. The method according to claim 35, wherein said conjugacy invariants are

conjugacy invariants of the Hecke algebra such as the characteristic

polynomials of the Burau matrix or its evaluations.

38. The method according to claim 35, wherein said conjugacy invariants are

conjugacy invariants of the Birman-Murakami-Wenzl algebra such as the

characteristic polynomials of the Begelow-Krammer-Lawrence matrix or its

evaluations.

39. The method according to claim 35, wherein said conjugacy invariants are

conjugacy invariants of the quantum group over various Lie algebra.

40. The method according to claim 35, wherein said conjugacy invariants are

polynomial invariants of closures of n-braids.

41. The method according to claim 40, wherein said conjugacy invariants are

selected from the group consisting of the Alexander polynomial, the Jones

polynomial, the two-variable Jones polynomial, the Kaufman polynomial,

finite-type invariants, and Milnor's link concordance invariants.

42. The method according to claim 33, wherein said non-commutative semi-group

G is a deformed algebra such as Hecke algebras, or a quantized hopf algebra

such as quantum groups.

43. The method according to claim 42, wherein said factor-hiding procedure H is

the list of the coefficients of a unique linear combination of the product of

inputs, and said conjugacy invariant is any (irreducible) representation of G

which can be regarded as a matrix group over a polynomial ring in deformed

or quantized parameters and in particular said conjugacy invariant can be

takes as the characteristic polynomial (or its evaluation) of a matrix

represented by an element of G.

44. The method according to claim 43, wherein said non-commutative semi-group

G is an semi-simple algebra over a field k, and said conjugacy invariant is any

irreducible representation of G which can be regarded as a matrix group over

k and in particular said conjugacy invariant can be takes as the characteristic

polynomial of a matrix represented by an element of G.

45. The method according to claim 32, wherein said non-commutative semi-group

G is a matrix group.

46. The method according to claim 45, wherein said factor-hiding procedure H is

the matrix multiplication of inputs, and wherein said conjugacy invariant is the

characteristic polynomial of a matrix.

47. The method according to claim 32, wherein said non-commutative semi-group

G is an automatic group.

48. The method according to claim 47, wherein said factor-hiding procedure H is

the conversion of the product of inputs into its unique normal form in a regular

language, and wherein said conjugacy invariant is the characteristic

polynomial of the image of or a character of an element under any

representation of G.

49. A program storage device readable by a machine, tangibly embodying a

program of instructions executable by the machine to perform method steps

for generating a left canonical form of an n-braid, said method steps

comprising:

receiving an input xιx₂...x_/ that is a concatenation of k canonical factors;

operating for each y from k to 2 either ony^"/2 pairs x-ιx₂, x₃x , . . ., Xy-ιXyfor even/

simultaneously in one clock or on (j - 1 )/2 pairs x₂x₃, x Xs, . . ., Xy-iX for odd/

simultaneously in one clock, if k is even; and

operating for each y from / -1 to 2 either ony^'/2 pairs X1X2, X3X4, ■ ■ ■, Xy-iXy for

even / simultaneously in one clock or on (/ - 1 )/2 pairs X_{2 3}, X₄X₅ xy-i y for

odd/ simultaneously in one clock, if k is odd.

50. A program storage device readable by a machine, tangibly embodying a

program of instructions executable by the machine to perform method

steps for generating a left canonical form of an n-braid, said method steps

comprising:

receiving an input x-ιx₂...Xk that is a concatenation of k canonical factors, performing operations to make pairs of consecutive factors left (right);

operating for each / from / to 2 either ony/2 pairs Xy.-|Xy, Xy+ιXy+₂, . . ., X_k-tXk

for even / simultaneously in one clock or on (j - 1 )/2 pairs X-iXy, xy₊ιXy₊₂,. . .,

X/-₂X/_C-1 for odd / simultaneously in one clock, if k is even; and

operating for each / from k to 2 either on (k -j + 1 )/2 pairs Xy.ιX, Xy+ιXy+2,. . ., X_k-

₂ ^1 for even / simultaneously in one clock or on (k -/ + 2)12 pairs Xy.-|Xy,

xy₊₁xy₊₂₎. . ., _/f.-iX_/c for odd / simultaneously in one clock, if A" is odd.

51.A method of generating a public key and a private key for public-key

cryptosystem, said method comprising the steps of:

selecting a non-commutative semi-group G ;

selecting a factor-hiding procedure H in G ;

selecting a unique expression procedure U in G ;

selecting a pair-wise commuting 4-tuple (J, K, J', K' ) of subsets in G ;

selecting an encryption function £ ;

selecting a decryption function D ;

choosing a fixed x e G ;

choosing a random pair (j, j' ) e J J'

producing a private key (/,/' ) ;

producing a public key (x, y) by constructing y = /-/( , x, /' ).

52. A program storage device readable by a machine, tangibly embodying a

program of instructions executable by the machine to perform method steps

for generating cryptographic keys for use by a pair of communicating parties, said method steps comprising:

selecting a non-commutative semi-group G ;

selecting a factor-hiding procedure H in G ;

selecting a unique expression procedure U in G ;

selecting a pair-wise commuting 4-tuple (J, K, J', K') of subsets in G ;

selecting an encryption function £ ;

selecting a decryption function D ;

choosing a fixed x e G ;

choosing a random pair (j, j' ) e J x J' ;

producing a private key ( , /' ) ;

producing a public key (x, y) by constructing y = H( , x, /' ).