Why subtraction is commutative

When you add two numbers together, it does not matter which order you add them. You will get the same result either way. For example, 5 + 7 = 12 and 7 + 5 = 12. The same is true when you multiply two numbers: 5 × 12 = 60 and 12 × 5 = 60. For this reason, we say that addition and multiplication are commutative operations.

Subtraction is not commutative, but it has a property that is very similar to commutativity. If you start with a number, and subtract two other numbers from it, then you can subtract the two numbers in either order. For example, (12 − 3) − 4 = 9 − 4 = 5, while (12 − 4) − 3 = 8 − 3 = 5. The functions "subtract 3" and "subtract 4" commute with each other.

An operation is quasi-commutative if it satisfies (ab)c = (ac)b for all a, b, c. The familiar operations of addition, subtraction, multiplication, division, and exponentiation are all quasi-commutative:

• (a + b) + c = (a + c) + b
• (a − b) − c = (a − c) − b
• (a × b) × c = (a × c) × b
• (a / b) / c = (a / c) / b
• (aᵇ)ᶜ = (aᶜ)ᵇ

Can you think of an operation that is commutative but not quasi-commutative?

Applications to cryptography

Suppose that several people want to sign a digital document. They wish to remain anonymous, but they also need to be able to prove at a later date that they signed the document. This can be achieved using a quasi-commutative hash function.

Let h be a function that satisfies h(h(x, y₁), y₂) = h(h(x, y₂), y₁) for all x, y₁, y₂. Assume that h has the following "one-way" property: Given x, y, y' with y' ≠ y, it must be impractical to find x' so that h(x, y) = h(x', y'). Such a function is called a quasi-commutative hash function, or an accumulator.

Now suppose that three people wish to sign a document x. The signers are identified by the numbers y₁, y₂, and y₃, and the document is signed with the value z = h(h(h(x, y₁), y₂), y₃). The same value z is obtained regardless of the order of y₁, y₂, and y₃.

The first signer calculates the value z₁ = h(h(x, y₂), y₃), and keeps it secret. At a later date, she can present the values z₁ and y₁, and her signature is verified by calculating that h(z₁, y₁) = z. In a similar manner, the second signer calculates z₂ = h(h(x, y₁), y₃), and the third signer calculates z₃ = h(h(x, y₁), y₂). Importantly, each person can prove that they signed the document without revealing the identities of the other signers.

Although I described this protocol for the case of three signers, it obviously works for any number of signers. For example, it could be used to prove that a person's vote was counted in a national election. It is also the basis of the proposed Zerocoin protocol, which would make bitcoin transactions anonymous and untraceable.

Diffie-Hellman key exchange is another application of the quasi-commutative property. Suppose that Amy and Bob want to agree on a secret encryption key, but they don't have a private means of communication. Here is how they do it. They agree on two numbers, g and M, which need not be secret. Then Amy chooses a secret number A, calculates x = (g^A) mod M, and sends the result to Bob. Similarly, Bob chooses a secret number B, calculates y = (g^B) mod M, and sends the result to Amy.

Now, the secret encryption key is z = (g^(AB)) mod M. Bob can calculate this value because z = x^B mod M, and Amy can calculate it because z = y^A mod M. But nobody else can figure out the encryption key, even if they know g, M, x, and y. This scheme works because (g^A)^B = (g^B)^A, which is another way of saying that exponentiation is quasi-commutative. It also depends on the difficulty of the discrete logarithm problem: in the equation g^A = x (mod M), there is no easy way to solve for the exponent A, even if you know the values of g, x, and M.

A formula for counting quasi-commutative functions

Given the importance of functions with the quasi-commutative property, it is interesting to ask how many such functions exist. That is, if X has m elements and Y has n elements, then how many functions h : X × Y → X satisfy the identity h(h(x, y₁), y₂) = h(h(x, y₂), y₁) for all x in X and all y₁, y₂ in Y?

This property is equivalent to assuming that the functions obtained by fixing the second argument of h commute with one another. That is, if h₁(x) ≡ h(x, y₁) and h₂(x) ≡ h(x, y₂) then h₁ ○ h₂ = h₂ ○ h₁. It follows that the number of quasi-commutative functions from X × Y to X is equal to the number of sequences of n commuting functions from X to itself.

To count these sequences, I turned to graph theory. Construct a graph whose vertices correspond to functions from X to X. Two vertices are joined by an edge if and only if the corresponding functions commute with each other. Then I obtained a formula for the number of quasi-commutative functions, based on the number of cliques of each size in the graph. (A clique is a set of vertices, all of which are connected by edges.) The actual formula is

f(m, n) = ∑ {k=1..n} k! * Stirling2(n, k) * c(m, k)

where c(m, k) is the number of sets of k commuting functions from X to itself, i.e. the number of k-cliques in our graph, and Stirling2 refers to Stirling numbers of the second kind.

The figure at the top of the article shows the graph for the case m = 3. I have omitted the identity vertex, which is connected to all other vertices.

Results

Using this formula, I have calculated that the number of quasi-commutative binary operations on a set of n elements is 1, 1, 10, 573, 136528, 115511945, 365045461056 for n=1 to 6. This is sequence A322654 in the On-Line Encyclopedia of Integer Sequences.

Reference

J. Benaloh and M. de Mare, One-Way Accumulators: A Decentralized Alternative to Digital Signatures, in: Tor Helleseth, Advances in Cryptology — EUROCRYPT '93, Springer-Verlag Berlin Heidelberg, 1994, 274-285. [Link to PDF]