In a GDPR Era, How Do I Book a Seat at the Edinburgh Festival Without Revealing My Seat Number?

With the ever increasing number of breaches, we are moving to a world where companies should not hold any personally sensitive information…

How Do I Book a Seat Without Revealing My Seat Number?

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 Edinburgh Festival, and how your privacy can be respected, but where the theatre will trust the ticket.

Booking a ticket

Let’s say there are 100 seats in a theatre, and I want to book one of them, but I don’t want the theatre company to know which seat I’ve booked, or my identity. I also want a receipt of purchase that they can verify my booking. One way would be to get a trusted agent to look after the bookings, but I don’t trust them either. So how can we do this?

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:

Commutative encryption

All this is made possible with Commutative encryption and where we can encrypt and decrypt in any order. Commutative encryption allows us to decrypt in any order. For this we can use SRA (Shamir, Rivest and Aldeman) and generate encryption keys which share p, q and N. The following uses two keys (e1, d1) and (e2, d2) with a shared N value.

With maths, operators such as multiplication are commutative, such as:

3 x 5 x 4 = 4 x 5 x 3

In encryption, most operations are non-commutative, so we need to modify the methods. One way is to use RSA, but generate two keys which have shared p, q and N values. So we generate Bob and Alice’s keys using the same two prime numbers (p and q), so that they share the same N value (modulus).

So let’s start with Bob:

Let’s select: P=7, Q=13

The calculation of n and PHI is:

N = 7 x 13 = 91PHI = (P-1)(Q-1) = 72

We need to make sure that our encryption key (e) does not share any factors with PHI (gcd(PHI,e)=1). We can select e as:

e = 5

Next we can calculate d from:

(d x 5) mod  (72) = 1

The answer is 29 [Solve]

d= 29, e=5, N=91
Encryption key [91,5]
Decryption key [91,29]

Now for Alice. We have:

N = 7 x 13 = 91
PHI = (P-1)(Q-1) = 72

We can select e as (and should not share any factors with PHI):

e = 7

Now we must solve:

(7 x d) mod (72) = 1

For this we get 31 [Solve]

Alice’s keys are then:

d= 31, e=7, N=91
Encryption key [91,7]
Decryption key [91,31]

The following is a run with a message of “5”:

e1 =  5  d1=  29
e2 =  7  d2=  31
N =  91
Message =  5
===================
  Cipher result (after Alice encrypt):  31
  Cipher result (after Bob encrypt):  73
===================
  Cipher result (After Bob decrypt) 31
  Cipher result (After Alice decrypt) 5
A -> B -> B -> A: 5
  Cipher result (After Alice decrypt) 47
  Cipher result (After Bob decrypt) 5
A -> B -> A -> B: 5

Real-life code

With commutative encryption, we can decrypt with the keys in any order. Normally we would encrypt with Bob’s key and then encrypt with Alice’s key, and then we must decrypt with Alice’s key and then Bob’s. In commutative encryption, we can decrypt in any order. To make RSA use commutative encryption, Bob and Alice must share a common value of N and which is p×q, and choose different values for their encryption key (e). In the following Alice selects an e value of 65,539 and Bob selects and e of 65,537. They then determine their decryption key as the inverse of e (mod N). In order to stop Bob from decrypting without Alice’s key, the value of e will be kept secret. The code is [here]:

A sample run [here]:

Message=hello
p=852651907763499317
q=745812510383943157
N=635918459812753777283846407136323769
First Bob encrypt, Alice encrypt, Alice decrypt, Bob decrypt
Bob key: d=194849910607746899759497012693375121, e=65537
Alice key: d=70996130097345387886448374455387547, e=65539
Cipher1=346276951573470476021462919534734952
Cipher2=418870736775912205351176794223088302
Decipher1=346276951573470476021462919534734952
decipher=hello
Commutative Encryption: First Bob encrypt, Alice encrypt, Bob decrypt, Alice decrypt
Bob key: d=194849910607746899759497012693375121, e=65537
Alice key: d=70996130097345387886448374455387547, e=65539
Cipher1=346276951573470476021462919534734952
Cipher2=418870736775912205351176794223088302
Decipher1=375365820304942084768113672994830918
decipher=hello

Conclusions

With GDPR we need to move to a point where we have no personally sensitive details on our systems. The method I have shown is just one way that a citizen can preserve their rights to privacy.