Image for post
Image for post
Photo by Andy Li on Unsplash

Privacy-preserving Ticket Booking With Commutative Encryption

I know that the chances of many of us booking a seat at the theatre is quite low, but our world will go back to normal, soon, so let’s look at a bit of privacy-preserving ticketing.

With the ever increasing number of breaches, we are moving to a world where companies should not hold any personally sensitive information, as it is just too risky. So how could we create a trustworthy system, where someone can show up with a ticket, and where we can trust it, without actually revealing any personal information about where the person has booked their seat?

So how can we generate a receipt of the booking, but not give away your identity, or the details of the booking? Let’s take an example of booking a seat in a theatre at the festival, and how your privacy can be respected, but where the theatre will trust the ticket.

Booking a ticket

Well it can be done with commutative encryption.

The steps would be:

  • Initially the theatre company generates 100 receipts for each of the seats, and then encrypts them with its public key.
  • Next when I want to make a booking they send me the encrypted receipts that they have left, and I select one at random, and then encrypt it with my public key.
  • I send them all back, including the one I’ve encrypted.
  • The theatre checks to see which one has been changed, and then decrypts it with its private key, and sends it back to me.
  • I decrypt with my private key, and I can now view the receipt for my booking, and the theater company cannot determine which seat I have, but I will have the receipt of my booking.

So here is an example where the theatre encrypts all the seats with its key, the person then selects one, and encrypts with their key, and sends them all back again. Then the theater decrypts the one that has changed, and sends it back for the person to decrypt, and we have a booking. The theatre thus does not know who has booked the seat:

Image for post
Image for post

Commutative encryption

One classic patent for commutative encryption was written by James Massey and Jim K. Omura created the Massey–Omura Cryptosystem in 1982 [1]. It took over three years to be assigned and was assigned to Omnet Associates [here]:

Image for post
Image for post

It uses exponentiation in the Galois field GF(2^n) for both the encryption and decryption functions. In this, if we have a message of M, the encryption is:

Image for post
Image for post

and

Image for post
Image for post

This are operated on with the Galois field. For this we define e within:

Image for post
Image for post

and we make sure that e does not share a factor with 2^n-1 using:

Image for post
Image for post

The decryption exponent d is defined as:

Image for post
Image for post

This works because the multiplicative group of the Galois field GF(2^n) has order 2^n−1, and where Lagrange’s theorem defines that m^{de}=m for all the values of m in GF(2^n). The coding is here [link]:

import libnum
import random
import sysfrom Crypto.Util.number import getPrime
from Crypto.Random import get_random_bytes
def chunkstring(string, length):
return (string[0+i:length+i] for i in range(0, len(string), length))

def generate_keys(prime):
while True:
e = random.randint(0, prime-2)
if libnum.gcd(e, prime-1) == 1 and e > 2:
break
d = libnum.invmod(e, prime-1) return e,ddef crypt(chunk, key,prime ):
num = 0
for c in chunk:
num *= 256
num += ord(c)
res = pow(num, key, prime)
vect = []
for i in range(0, len(chunk)):
vect.append(chr(res%256))
res = res // 256 return "".join(reversed(vect))primebits=64
msg = "HellHe"if (len(sys.argv)>1):
primebits=int(sys.argv[1])
if (len(sys.argv)>2):
msg=(sys.argv[2])
FRAGMENT_SIZE = primebits//8
msg = msg + " "*((FRAGMENT_SIZE - (len(msg)%FRAGMENT_SIZE))%FRAGMENT_SIZE)res=chunkstring(msg,FRAGMENT_SIZE)
PRIME = getPrime(primebits, randfunc=get_random_bytes)e,d = generate_keys(PRIME)vect=[]
for elem in res:
enc=str(crypt(elem, e,PRIME))
vect.append(enc)enc="".join(vect)dec=[]
for elem in chunkstring(enc, FRAGMENT_SIZE):
dec.append(crypt(elem, d,PRIME))print (f"Msg={msg}")
print (f"e={e}, d={d}")
print("Decrypted: " + "".join(dec))

A sample run is [link]:

Msg=Hello   
e=16153579288865179167, d=10300837874192230633
Decrypted: Hello

The code is here:

One of the advantages of the Massey–Omura Cryptosystem is that we can apply commutative encryption. In this way, Bob may have keys of (e_b,d_b) and Alice has keys of (e_a,d_a). We can then apply the keys in any order, such as encrypting with e_a and then encrypting with e_b, and where we can then decrypt with d_a and then decrypt with d_b, or decrypt with d_b first and then decrypt with d_a (as we would normally do).

To encrypt:

Cipher=E(a_b,E(e_a,M))=E(e_a,E(e_b,M))

To decrypt:

E(d_b,E(d_a,Cipher))=E(d_a,E(d_b,Cipher))

Here is an example:

Conclusions

References

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles…

Prof Bill Buchanan OBE

Written by

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles related to cyber security.

Prof Bill Buchanan OBE

Written by

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles related to cyber security.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store