How Do I Book a Seat at the Edinburgh Festival Without Giving You My Name, Address, and Any Other Detail?
Okay. I tricked you there into reading something about Crypto, as you thought it was something to do with the Edinburgh Festival ... but please read on ...
How can I generate a receipt of a purchase but not give away my identity or the details of my booking? For this let's take an example of booking a seat in a theatre at the Edinburgh Festival.
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.
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 theatre company cannot determine which seat I have, but I will have the receipt of my booking.
So here is an example where the threatre encrypts all the seats with it's key, the person then selects one, and encrypts with their key, and sends them all back again. Then the threatre decrypts the one that has changed, and send it back for the person to decrypt, and the have the booking. The theatre thus does not know who has booked the seat:
All this is made possible with Commutative encryption:
and where we can encrypt and decrypt in any order. One method is to use the RSA method to generate the keys required, but for everyone to share a common p and q value (and thus a shared N value).