Non-commutative cryptography is the area of
cryptology
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or '' -logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adve ...
where the
cryptographic primitive
Cryptographic primitives are well-established, low-level cryptographic algorithms that are frequently used to build cryptographic protocols for computer security systems. These routines include, but are not limited to, one-way hash functions and ...
s, methods and systems are based on
algebraic structure
In mathematics, an algebraic structure consists of a nonempty set ''A'' (called the underlying set, carrier set or domain), a collection of operations on ''A'' (typically binary operations such as addition and multiplication), and a finite set of ...
s like
semigroup
In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative internal binary operation on it.
The binary operation of a semigroup is most often denoted multiplicatively: ''x''·''y'', or simply ''xy'', ...
s,
group
A group is a number of persons or things that are located, gathered, or classed together.
Groups of people
* Cultural group, a group whose members share the same cultural identity
* Ethnic group, a group whose members share the same ethnic iden ...
s and
ring
Ring may refer to:
* Ring (jewellery), a round band, usually made of metal, worn as ornamental jewelry
* To make a sound with a bell, and the sound made by a bell
:(hence) to initiate a telephone connection
Arts, entertainment and media Film and ...
s which are
non-commutative
In mathematics, a binary operation is commutative if changing the order of the operands does not change the result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it. Most familiar as the name of ...
. One of the earliest applications of a non-commutative algebraic structure for cryptographic purposes was the use of
braid group
A braid (also referred to as a plait) is a complex structure or pattern formed by interlacing two or more strands of flexible material such as textile yarns, wire, or hair.
The simplest and most common version is a flat, solid, three-strande ...
s to develop cryptographic protocols. Later several other non-commutative structures like
Thompson groups
In mathematics, the Thompson groups (also called Thompson's groups, vagabond groups or chameleon groups) are three groups, commonly denoted F \subseteq T \subseteq V, that were introduced by Richard Thompson in some unpublished handwritten notes i ...
,
polycyclic group
In mathematics, a polycyclic group is a solvable group that satisfies the maximal condition on subgroups (that is, every subgroup is finitely generated). Polycyclic groups are finitely presented, which makes them interesting from a computational ...
s,
Grigorchuk group In the mathematical area of group theory, the Grigorchuk group or the first Grigorchuk group is a finitely generated group constructed by Rostislav Grigorchuk that provided the first example of a finitely generated group of intermediate (that is, fa ...
s, and
matrix group In mathematics, a matrix group is a group ''G'' consisting of invertible matrices over a specified field ''K'', with the operation of matrix multiplication. A linear group is a group that is isomorphic to a matrix group (that is, admitting a fait ...
s have been identified as potential candidates for cryptographic applications. In contrast to non-commutative cryptography, the currently widely used
public-key cryptosystem
Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic alg ...
s like
RSA cryptosystem
RSA (Rivest–Shamir–Adleman) is a public-key cryptosystem that is widely used for secure data transmission. It is also one of the oldest. The acronym "RSA" comes from the surnames of Ron Rivest, Adi Shamir and Leonard Adleman, who publicly ...
,
Diffie–Hellman key exchange
Diffie–Hellman key exchangeSynonyms of Diffie–Hellman key exchange include:
* Diffie–Hellman–Merkle key exchange
* Diffie–Hellman key agreement
* Diffie–Hellman key establishment
* Diffie–Hellman key negotiation
* Exponential key exc ...
and
elliptic curve cryptography
Elliptic-curve cryptography (ECC) is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. ECC allows smaller keys compared to non-EC cryptography (based on plain Galois fields) to provide e ...
are based on number theory and hence depend on commutative algebraic structures.
Non-commutative cryptographic protocols have been developed for solving various cryptographic problems like
key exchange
Key exchange (also key establishment) is a method in cryptography by which cryptographic keys are exchanged between two parties, allowing use of a cryptographic algorithm.
If the sender and receiver wish to exchange encrypted messages, each m ...
,
encryption
In cryptography, encryption is the process of encoding information. This process converts the original representation of the information, known as plaintext, into an alternative form known as ciphertext. Ideally, only authorized parties can decip ...
-decryption, and
authentication
Authentication (from ''authentikos'', "real, genuine", from αὐθέντης ''authentes'', "author") is the act of proving an assertion, such as the identity of a computer system user. In contrast with identification, the act of indicati ...
. These protocols are very similar to the corresponding protocols in the commutative case.
Some non-commutative cryptographic protocols
In these protocols it would be assumed that ''G'' is a
non-abelian group. If ''w'' and ''a'' are elements of ''G'' the notation ''w''
''a'' would indicate the element ''a
−1wa''.
Protocols for key exchange
Protocol due to Ko, Lee, et al.
The following protocol due to Ko, Lee, et al., establishes a common
secret key
A key in cryptography is a piece of information, usually a string of numbers or letters that are stored in a file, which, when processed through a cryptographic algorithm, can encode or decode cryptographic data. Based on the used method, the key c ...
''K'' for
Alice and Bob
Alice and Bob are fictional characters commonly used as placeholders in discussions about cryptographic systems and protocols, and in other science and engineering literature where there are several participants in a thought experiment. The A ...
.
#An element ''w'' of ''G'' is published.
#Two
subgroup
In group theory, a branch of mathematics, given a group ''G'' under a binary operation ∗, a subset ''H'' of ''G'' is called a subgroup of ''G'' if ''H'' also forms a group under the operation ∗. More precisely, ''H'' is a subgroup ...
s ''A'' and ''B'' of ''G'' such that ''ab'' = ''ba'' for all ''a'' in ''A'' and ''b'' in ''B'' are published.
#Alice chooses an element ''a'' from ''A'' and sends ''w
a'' to Bob. Alice keeps ''a'' private.
#Bob chooses an element ''b'' from ''B'' and sends ''w
b'' to Alice. Bob keeps ''b'' private.
#Alice computes ''K'' = (''w''
''b'')
a = ''w''
''ba''.
#Bob computes ''K = (''w''
''a'')
''b''=''w''
''ab''.
#Since ''ab'' = ''ba'', ''K'' = ''K. Alice and Bob share the common secret key ''K''.
Anshel-Anshel-Goldfeld protocol
This a key exchange protocol using a non-abelian group ''G''. It is significant because it does not require two commuting subgroups ''A'' and ''B'' of ''G'' as in the case of the protocol due to Ko, Lee, et al.
#Elements ''a''
1, ''a''
2, . . . , ''a''
''k'', ''b''
1, ''b''
2, . . . , ''b''
''m'' from ''G'' are selected and published.
#Alice picks a private ''x'' in ''G'' as a
word
A word is a basic element of language that carries an semantics, objective or pragmatics, practical semantics, meaning, can be used on its own, and is uninterruptible. Despite the fact that language speakers often have an intuitive grasp of w ...
in ''a''
1, ''a''
2, . . . , ''a''
''k''; that is, ''x'' = ''x''( ''a''
1, ''a''
2, . . . , ''a''
''k'' ).
#Alice sends ''b''
1''x'', ''b''
2''x'', . . . , ''b''
''m''''x'' to Bob.
#Bob picks a private ''y'' in ''G'' as a
word
A word is a basic element of language that carries an semantics, objective or pragmatics, practical semantics, meaning, can be used on its own, and is uninterruptible. Despite the fact that language speakers often have an intuitive grasp of w ...
in ''b''
1, ''b''
2, . . . , ''b''
''m''; that is ''y'' = ''y'' ( ''b''
1, ''b''
2, . . . , ''b''
''m'' ).
#Bob sends ''a''
1''y'', ''a''
2''y'', . . . , ''a''
''k''''y'' to Alice.
#Alice and Bob share the common secret key ''K'' = ''x''
−1''y''
−1''xy''.
#Alice computes ''x'' ( ''a''
1''y'', ''a''
2''y'', . . . , ''a''
''k''''y'' ) = ''y''
−1 ''xy''. Pre-multiplying it with ''x''
−1, Alice gets ''K''.
#Bob computes ''y'' ( ''b''
1''x'', ''b''
2''x'', . . . , ''b''
''m''''x'') = ''x''
−1''yx''. Pre-multiplying it with ''y''
−1 and then taking the inverse, Bob gets ''K''.
Stickel's key exchange protocol
In the original formulation of this protocol the group used was the group of
invertible matrices
In linear algebra, an -by- square matrix is called invertible (also nonsingular or nondegenerate), if there exists an -by- square matrix such that
:\mathbf = \mathbf = \mathbf_n \
where denotes the -by- identity matrix and the multiplicati ...
over a
finite field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...
.
#Let ''G'' be a public non-abelian
finite group
Finite is the opposite of infinite. It may refer to:
* Finite number (disambiguation)
* Finite set, a set whose cardinality (number of elements) is some natural number
* Finite verb, a verb form that has a subject, usually being inflected or marked ...
.
#Let ''a'', ''b'' be public elements of ''G'' such that ''ab'' ≠ ''ba''. Let the orders of ''a'' and ''b'' be ''N'' and ''M'' respectively.
#Alice chooses two random numbers ''n'' < ''N'' and ''m'' < ''M'' and sends ''u'' = ''a''
''m''''b''
''n'' to Bob.
#Bob picks two random numbers ''r'' < ''N'' and ''s'' < ''M'' and sends ''v'' = ''a''
''r''''b''
''s'' to Alice.
#The common key shared by Alice and Bob is ''K'' = ''a''
''m'' + ''r''''b''
''n'' + ''s''.
#Alice computes the key by ''K'' = a
''m''''vb''
''n''.
#Bob computes the key by ''K'' = ''a''
''r''''ub''
''s''.
Protocols for encryption and decryption
This protocol describes how to
encrypt
In cryptography, encryption is the process of encoding information. This process converts the original representation of the information, known as plaintext, into an alternative form known as ciphertext. Ideally, only authorized parties can decip ...
a secret message and then
decrypt
In cryptography, encryption is the process of encoding information. This process converts the original representation of the information, known as plaintext, into an alternative form known as ciphertext. Ideally, only authorized parties can decip ...
using a non-commutative group. Let Alice want to send a secret message ''m'' to Bob.
#Let ''G'' be a non-commutative group. Let ''A'' and ''B'' be public subgroups of ''G'' such that ''ab'' = ''ba'' for all ''a'' in ''A'' and ''b'' in ''B''.
#An element ''x'' from ''G'' is chosen and published.
#Bob chooses a secret key ''b'' from ''A'' and publishes ''z'' = ''x''
''b'' as his public key.
#Alice chooses a random ''r'' from ''B'' and computes ''t'' = ''z''
''r''.
#The encrypted message is ''C'' = (''x''
''r'', ''H''(''t'')
''m''), where ''H'' is some
hash function
A hash function is any function that can be used to map data of arbitrary size to fixed-size values. The values returned by a hash function are called ''hash values'', ''hash codes'', ''digests'', or simply ''hashes''. The values are usually u ...
and
denotes the
XOR
Exclusive or or exclusive disjunction is a logical operation that is true if and only if its arguments differ (one is true, the other is false).
It is symbolized by the prefix operator J and by the infix operators XOR ( or ), EOR, EXOR, , ...
operation. Alice sends ''C'' to Bob.
#To decrypt ''C'', Bob recovers ''t'' as follows: (''x''
''r'')
''b'' = ''x''
''rb'' = ''x''
''br'' = (''x''
''b'')
''r'' = ''z''
''r'' = ''t''. The plain text message send by Alice is ''P'' = ( ''H''(''t'')
''m'' )
''H''(''t'') = ''m''.
Protocols for authentication
Let Bob want to check whether the sender of a message is really Alice.
#Let ''G'' be a non-commutative group and let ''A'' and ''B'' be subgroups of ''G'' such that ''ab'' = ''ba'' for all ''a'' in ''A'' and ''b'' in ''B''.
#An element ''w'' from ''G'' is selected and published.
#Alice chooses a private ''s'' from ''A'' and publishes the pair ( ''w'', ''t'' ) where ''t'' = ''w''
''s''.
#Bob chooses an ''r'' from ''B'' and sends a challenge ''w'' ' = ''w''
''r'' to Alice.
#Alice sends the response ''w'' ' ' = (''w'' ')
''s'' to Bob.
#Bob checks if ''w'' ' ' = ''t''
''r''. If this true, then the identity of Alice is established.
Security basis of the protocols
The basis for the security and strength of the various protocols presented above is the difficulty of the following two problems:
*The ''
conjugacy decision problem'' (also called the ''conjugacy problem''): Given two elements ''u'' and ''v'' in a group ''G'' determine whether there exists an element ''x'' in ''G'' such that ''v'' = ''u''
''x'', that is, such that ''v'' = ''x''
−1 ''ux''.
*The ''conjugacy search problem'': Given two elements ''u'' and ''v'' in a group ''G'' find an element ''x'' in ''G'' such that ''v'' = ''u''
''x'', that is, such that ''v'' = ''x''
−1 ''ux''.
If no algorithm is known to solve the conjugacy search problem, then the function ''x'' → ''u''
''x'' can be considered as a
one-way function
In computer science, a one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input. Here, "easy" and "hard" are to be understood in the sense of computational complexity theory, spe ...
.
Platform groups
A non-commutative group that is used in a particular cryptographic protocol is called the platform group of that protocol. Only groups having certain properties can be used as the platform groups for the implementation of non-commutative cryptographic protocols. Let ''G'' be a group suggested as a platform group for a certain non-commutative cryptographic system. The following is a list of the properties expected of ''G''.
#The group ''G'' must be well-known and well-studied.
#The
word problem in ''G'' should have a fast solution by a deterministic algorithm. There should be an efficiently computable "normal form" for elements of ''G''.
#It should be impossible to recover the factors ''x'' and ''y'' from the product ''xy'' in ''G''.
#The number of elements of length ''n'' in ''G'' should grow faster than any polynomial in ''n''. (Here "length ''n''" is the length of a word representing a group element.)
Examples of platform groups
Braid groups
Let ''n'' be a positive integer. The braid group ''B''
''n'' is a group generated by ''x''
1, ''x''
2, . . . , ''x''
''n''-1 having the following presentation:
:
Thompson's group
Thompson's group is an infinite group ''F'' having the following infinite presentation:
: