Anonymous authentication

1. A method for anonymous purchase by a first user device, the method comprising performing in the first user device:

obtaining an anonymized token, data string T, by performing the following steps:

selecting a random number r;

deriving a result, R, by performing a one-way function on the random number r;

sending R from the first user device to a second user device, the second user device sending R to a service provider, the service provider storing R with a data string T and returning a digitally signed R and T to the second user device, thereby providing the data string T to the second user device;

storing r;

receiving, from the second user device, R and T at the first user device, thereby ensuring that the identity of the first user device remains unknown to the service provider;

using T to execute an anonymous purchase of a service by performing the following steps:

opening a communication channel between the first user device and the service provider;

sending the service provider the stored r and the received T from the first user device to the service provider via the communication channel along with a request for the service provider to provide a service; and

receiving the requested service from the service provider.

2. The method according to claim 1 wherein the one-way function is a modular square function, so that R=r 2 : mod N, and N is a prime number in a field Z.

3. The method according to claim 1 wherein the one-way function is a hash function, so that R=HASH(r).

4. The method according to claim 1 wherein the one-way function is a modular logarithm function, so that R=log mod N (r), and N is a prime number in a field Z.

5. The method according to claim 1 and wherein, in exchange for receiving R and T from the second user device, the first user device sends the second user device a value R′ and a data string T′.

6. The method according to claim 1 wherein the communication channel opened with the service provider comprises an anonymous communication channel.

7. The method according to claim 1 wherein before the service provider provides the requested service, the service provider verifies that R is properly a result of a one-way function performed on r.

8. A method performed by a service provider for providing anonymous authentication of a first user device, the method comprising:

receiving a value R from a second user device, where R is a result of a one-way function performed on a random number r selected and stored by a first user device, the first user device sending R to the second device;

storing R with an anonymized token, data string T;

returning a digitally signed R and T to the second user device, thereby providing the data string T to the second user device;

opening a communication channel between the first user device and the service provider;

receiving, via the communication channel, the stored r and T from the first user device, along with a request to provide a service; and

performing the one-way function on the received r thereby determining R;

verifying that the determined R is equivalent to the stored R and the received T is equivalent to the stored T; and

providing the requested service to the first user device in response to a positive result of the verifying, without the service provider needing to know the identity of a user of the first user device.

9. The method according to claim 8 wherein the one-way function is a modular square function, so that R=r 2 mod N, and N is a prime number in a field Z.

10. The method according to claim 8 wherein the one-way function is a hash function, so that R=HASH(r).

11. The method according to claim 8 wherein the one-way function is a modular logarithm function, so that R=log mod N (r), and N is a prime number in a field Z.

12. The method according to claim 8 wherein the communication channel opened with the first user device comprises an anonymous communication channel.

13. A system disposed at a first user device for anonymous purchase, the system comprising:

a processor which selects a random number, r, and derives a result, R, by performing a one-way function on a random number r;

a first data communications port disposed in the first user device configured to send R to a second user device, the second user device being configured to send R to a service provider, which stores R with a data string T and the service provider being configured to return a digitally signed R and T to the second user device, thereby providing the data string T to the second user device;

a data store which stores r;

a second data communications port disposed in the first user device configured to receive R and T from the second user device, thereby ensuring that the identity of the first user device remains unknown to the service provider;

a third data communications port disposed in the first user device configured to open a communication channel between the first user device and the service provider;

the third data communications port configured to send the service provider the stored r and the received T via the communication channel along with an anonymous purchase of a service, the anonymous purchase comprising a request for the service provider to provide the service; and

the third data communications port configured to receive the requested service from the service provider.

14. A system disposed at a service provider for providing anonymous authentication of a first user device, the system comprising:

a first data communications port configured to receive a value R from a second user device, where R is a result of a one-way function performed on a random number r selected by a first user device, the first user device sending R to the second device;

a data storage unit to store R with an anonymized token, data string T;

a second data communications port configured to return a digitally signed R and T to the second user device, thereby providing the data string T to the second user device;

a third data communications port configured to open a communication channel between the first user device and the service provider;

the third data communications port configured to receive, via the communication channel, r and T from the first user device, along with a request to provide a service; and

a processor configured to perform the one-way function on r thereby determining R;

the processor configured to verify that R is stored with the received T; and

the third data communications port configured to provide the requested service to the first user device in response to a positive result of the verifying, without the service provider needing to know the identity of a user of the first user device.