computer science

Non-commutative cryptography

Non-commutative cryptography is a computer science topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand Non-commutative cryptography rather than just read about it. In short: Non-commutative 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 non-commutative. One of the earliest applications of a non-commutative algebraic structure for cryptographic purposes was the use of braid groups to develop cryptographic protocols.

Key takeaways

Non-commutative cryptography belongs to computer science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Non-commutative cryptography to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Non-commutative cryptography from memory before moving on to harder problems.

Reference excerpt

Non-commutative 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 non-commutative. One of the earliest applications of a non-commutative algebraic structure for cryptographic purposes was the use of braid groups to develop cryptographic protocols. Later several other non-commutative structures like Thompson groups, polycyclic groups, Grigorchuk groups, and matrix groups have been identified as potential candidates for cryptographic applications. In contrast to non-commutative cryptography, the currently widely used public-key cryptosystems like RSA cryptosystem, Diffie–Hellman key exchange and elliptic curve cryptography 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, encryption-decryption, and authentication. 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 wa 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 K for Alice and Bob.

An element w of G is published. Two subgroups 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 wa to Bob. Alice keeps a private. Bob chooses an element b from B and sends wb to Alice. Bob keeps b private. Alice computes K = (wb)a = wba. Bob computes K' = (wa)b=wab. 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 a1, a2, . . . , ak, b1, b2, . . . , bm from G are selected and published. Alice picks a private x in G as a word in a1, a2, . . . , ak; that is, x = x( a1, a2, . . . , ak ). Alice sends b1x, b2x, . . . , bmx to Bob. Bob picks a private y in G as a word in b1, b2, . . . , bm; that is y = y ( b1, b2, . . . , bm ). Bob sends a1y, a2y, . . . , aky to Alice. Alice and Bob share the common secret key K = x−1y−1xy. Alice computes x ( a1y, a2y, . . . , aky ) = y−1 xy. Pre-multiplying it with x−1, Alice gets K. Bob computes y ( b1x, b2x, . . . , bmx) = x−1yx. 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 over a finite field.

Let G be a public non-abelian finite group. 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 = ambn to Bob. Bob picks two random numbers r < N and s < M and sends v = arbs to Alice. The common key shared by Alice and Bob is K = am + rbn + s. Alice computes the key by K = amvbn. Bob computes the key by K = arubs.

Protocols for encryption and decryption This protocol describes how to encrypt a secret message and then decrypt 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 = xb as his public key. Alice chooses a random r from B and computes t = zr. The encrypted message is C = (xr, H(t) ⊕ {\displaystyle \oplus } m), where H is some hash function and ⊕ {\displaystyle \oplus } denotes the XOR operation. Alice sends C to Bob. To decrypt C, Bob recovers t as follows: (xr)b = xrb = xbr = (xb)r = zr = t. The plain text message send by Alice is P = ( H(t) ⊕ {\displaystyle \oplus } m ) ⊕ {\displaystyle \oplus } 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′ = wr to Alice. Alice sends the response w′′ = (w′)s to Bob. Bob checks if w′′ = tr. 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 = ux, 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 = ux, that is, such that v = x−1 ux. If no algorithm is known to solve the conjugacy search problem, then the function x → ux can be considered as a one-way function.

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

… excerpt ends here. Continue reading the full article.

Worked examples

Example 1 — a first encounter with Non-commutative cryptography

Start with the simplest possible case. Write down what Non-commutative cryptography claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In computer science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Non-commutative cryptography before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Non-commutative cryptography ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Non-commutative cryptography

In research: Non-commutative cryptography appears in computer science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Non-commutative cryptography in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Non-commutative cryptography is common in secondary-school and first-year university syllabi. It links to neighbouring topics Public-key cryptography, so understanding it makes those chapters shorter.
In everyday life: Look for Non-commutative cryptography outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study Non-commutative cryptography in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Non-commutative cryptography means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Non-commutative cryptography out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Non-commutative cryptography in simple terms?

Why does Non-commutative cryptography matter?

Because it connects several computer science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Non-commutative cryptography?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Non-commutative cryptography.