About Me!
This blog is about my musings and thoughts. I hope you find it useful, at most, and entertaining, at least.
Other Pages
Presence Elsewhere
The Use of Ring Signature to Enable Anonymous Usage of Services
Date: 2013-07-03
Tags: ideas cryptography anonymity public_transit
Many transit agencies have moved or are moving to the use of smart cards, cards with magnetic strips, or another stored-value system for fare payment. While agencies still do, and should, accept cash as fare, these technologies allow for the speedy loading and unloading of passengers. They has have convinces for the riders as it frees them from having to carry change, can be filled at unmanned kiosks via cash or credit, and in some cases can be refilled online.
There is one major disadvantage to using stored-value systems: the loss of anonymity. Because the cards necessitate being link to an account, which itself is normally linked via a credit card number to the rider, the transit agency gains the ability to track the movements of the rider. While this may, for the moment, be inevitable with an auto-debit system, where each use of the card debits the account associated with the card, for the use of monthly, weekly, or yearly passes there may be a method to preserve anonymity and prevent free duplication of passes, to the same extent as SIM cards anyway.
To start, let’s examine a simple system. Each rider is given a Key Store (KS) by the Transit Agency (TA) containing the key for the type of pass given; each rider having the same key. This KS would support the following operations:
- Retrieve the public key
- Encrypt message with public key
- Sign message with private key
- Decrypt with private key
- Verify signature with public key
The KS is inserted into a (possibly non-TA) Signer card. The Signer, with the KS, calculates a signature for a nonce the fare-box (FB) and the FB would verify the signature, and hence the pass type. This method will anonymizes the rider, however, it requires us to trust the TA to give each person the same key. Not wanting to trust the TA is the very concern that lead to the discussion of anonymous passes originally.
The Signer would also need to be able to be provided by third parties, i.e. not the TA, in order for them to be able to be audited by the rider.
In 2001, Rivest1, Shamir, and Tauman released a paper entitled How to Leak a Secret (local mirror) in which they describe a “ring signature.” A ring signature allows an individual who is part of an arbitrary group of persons to sign a document to show that they belong to said group, but their identity cannot be ascertained in a reasonable amount of time.
To use a ring signature, the TA generates, in advance of the sales period, a multitude public/private key pairs, say three million. The public keys are publicly disseminated and each pair is written to a KS.
Additionally, a Public Key Library (PKL) would be loaded with the public keys for the pass-type bought. For instance, if the rider purchases a monthly pass, they would have to download all the public keys for all the monthly passes. The PKL, like the KS, would be inserted into the Signer.
To use the pass on a transit vehicle, the KS and PKL would be placed into Signer, which need not, but may be, provided by the transit agency. The Signer, when placed into a FB, receives a nonce. The Signer then randomly selects a large number public keys, and uses them and the private key stored in the KS to create ring signature for the nonce. The Signer passes the signature back to the station, which is able to verify that all the public keys used in the signature are of the same pass type and which pass type they are. Once the station verifies the public keys are of a valid pass type, it can assess if the signature is valid for the group. If the signature is valid, then the rider is permitted on the vehicle.
This scheme allows for rider-provided Signers, ensuring that the rider is able to verify for himself that the Signer is not compromising his identity. As such, the transit agency is still able to quickly load and unload passes and in theory the pass could be renewable such that the key pair would be included in the next months batch of published public keys. Additionally, it provides the rider with the anonymity of cash fares, but the convince of a pass.
I believe this system of pass verification based on ring signatures provides the most convenient, most anonymous, and most secure method of using smart cards to pay fare on transit vehicles with a pass.