Anonymous transactions in computer networks

Abstract

We present schemes for providing anonymous transactions while privacy and anonymity are preserved, providing user's anonymous authentication in distributed networks such as the Internet. We first present a practical scheme for anonymous transactions while the transaction resolution is assisted by a Trusted Authority. This practical scheme is extended to a theoretical scheme where a Trusted Authority is not involved in the transaction resolution. Both schemes assume that all the players interact over anonymous secure channels. Given authority that generates for each player hard to produce evidence EVID (e.g., problem instance with or without a solution) to each player, the identity of a user U is defined by the ability to prove possession of aforementioned evidence. We use zero-knowledge proof techniques to repeatedly identify U by providing a proof that U has evidence EVID, without revealing EVID, therefore avoiding identity theft.

In both schemes the authority provides each user with a unique random string. A player U may produce a unique user name and password for each other player S using a one-way function over the random string and the IP address of S. The player does not have to maintain any information in order to reproduce the user name and password used for accessing a player S. Moreover, the player U may execute transactions with a group of players S^U in two phases; in the first phase the player interacts with each server without revealing information concerning its identity and without possibly identifying linkability among the servers in S^U. In the second phase the player allows linkability and therefore transaction commitment with all servers in S^U, while preserving anonymity (for future transactions).

References

1. Bach, E. and Shallit, J. 1996. Algorithmic Number Theory in Volume 1: Efficient Algorithms. MIT Press.
2. Beimel, A. and Dolev, S. 2003. Buses for anonymous message delivery. J. Crypt. 16, 25--39.
3. Belenkiy, M., Chase, M., Kohlweiss, M., and Lysyanskaya, A. 2007. Non-Interactive anonymous credentials. IACR Cryptology ePrint Archive, rep. 2007/384.
4. Camenisch, J. and Lysyanskaya, A. 2005. A formal treatment of onion routing. In Proceedings of the Annual International Cryptology Conference (CRYPTO'05). 169--187.
5. Camenisch, J. and Lysyanskaya, A. 2002. Dynamic accumulators and application to efficient revocation of anonymous credentials. In Proceedings of the Annual International Cryptology Conference (CRYPTO'02). Lecture Notes in Computer Science, vol. 2442. Springer.
6. Camenisch, J. and Michels, M. 1998. Proving in zero knowledge that a number is the product of two safe primes. Basic Res. Comput. Sci. Rep. Series.
7. Cooperative Computing Awards. 2012. http://w2.eff/org/awards/coop.php
8. Dolev, A. and Ostrovsky, R. 2000. Xor-Trees for efficient anonymous multicast and reception. ACM Trans. Inf. Syst. Secur. 3, 2, 63--84.
9. Dolev, S. and Kopeetsky, M. 2009. Anonymous transactions in computer networks. In Proceedings of the 11^th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS'09). 297--310.
10. Feige, U., Fiat, A., and Shamir, A. 1988. Zero-Knowledge proofs of identity. J. Crypt. 1, 2. Springer, New York.
11. Gabber, E., Gibbons, P., Matias, Y., and Mayer, A. 1997. How to make personalized web browsing simple, secure, and anonymous. In Proceedings of the 1^st International Conference on Financial Cryptography (FC'97).
12. Golle, P., Jakobsson, M., Juels, A., and Syverson, P. 2004. Universal re-encryption for mixnets. In Proceedings of the Cryptographer's Track at the RSA Conference. 163--178.
13. Goldreich, O. 2003. Foundations of Cryptography, Volume 1. Cambridge University Press.
14. Goldreich, O. 2003. Foundations of Cryptography, Volume 2. Cambridge University Press.
15. Lamport, L. 1981. Password authentication with insecure communication. Comm. ACM 24, 11.
16. Le, T. V., Nguyen, K. Q., and Varadharajan, V. 1999. How to prove that a committed number is prime. In Proceedings of the International Conference on the Theory and Applications of Cryptology and Information Security Advances in Cryptology (ASIACRYPT'99). Lecture Notes in Computer Science, vol. 1716. Springer, 208--218.
17. Lysyanskaya, A., Rivest, R. L., Sahai, S., and Wolf, S. 2001. Pseudonym systems. In Selected Areas in Cryptography. 184--199.
18. Naor, M., Ostrovsky, R., Venkatesan, R., and Yung, M. 1993. Perfect zero-knowledge arguments for NP using any one-way permutation. In Proceedings of the Conference on Advances in Cryptology (CRYPTO'92). Lecture Notes in Computer Science, vol. 740. Springer.
19. Stallings, W. 2007. Network Security Essentials: Applications and Standards. Prentice-Hall.
20. Stinson, D. R. 2006. Cryptography. Theory and Practice, 3^rd ed. Chapman and Hall/CRC Press.

Index Terms

• Security and privacy

  • Network security