Priced Oblivious Transfer: How to Sell Digital Goods

  • Bill Aiello
  • Yuval Ishai
  • Omer Reingold
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2045)


We consider the question of protecting the privacy of customers buying digital goods. More specifically, our goal is to allow a buyer to purchase digital goods from a vendor without letting the vendor learn what, and to the extent possible also when and how much, it is buying. We propose solutions which allow the buyer, after making an initial deposit, to engage in an unlimited number of priced oblivious-transfer protocols, satisfying the following requirements: As long as the buyer's balance contains sufficient funds, it will successfully retrieve the selected item and its balance will be debited by the item's price. However, the buyer should be unable to retrieve an item whose cost exceeds its remaining balance. The vendor should learn nothing except what must inevitably be learned, namely, the amount of interaction and the initial deposit amount (which imply upper bounds on the quantity and total price of all information obtained by the buyer). In particular, the vendor should be unable to learn what the buyer's current balance is or when it actually runs out of its funds.

The technical tools we develop, in the process of solving this problem, seem to be of independent interest. In particular, we present the first one-round (two-pass) protocol for oblivious transfer that does not rely on the random oracle model (a very similar protocol was independently proposed by Naor and Pinkas [21]). This protocol is a special case of a more general “conditional disclosure” methodology, which extends a previous approach from [11] and adapts it to the 2-party setting.


Homomorphic Encryption Oblivious Transfer Monotone Formula Private Information Retrieval Homomorphic Encryption Scheme 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


  1. 1.
    M. Bellare and S. Micali. Non-interactive oblivious transfer and applications. CRYPTO '89, pp. 547–557, 1989.Google Scholar
  2. 2.
    O. Berthold, H. Federrath, and M. Kohntopp. Project “Anonymity and Unobservability in the Internet”. Conference on Freedom and Privacy, pp. 57–65, 2000.Google Scholar
  3. 3.
    F. Boudot. Efficient proofs that a committed number lies in an interval. EUROCRYPT 2000, pp. 431–444. Springer-Verlag, 2000.Google Scholar
  4. 4.
    G. Brassard, C. Crépeau, and J.-M. Robert. All-or-nothing disclosure of secrets. CRYPTO '86, pp. 234–238, 1987.Google Scholar
  5. 5.
    C. Cachin, S. Micali, and M. Stadler. Computationally private information with polylogarithmic communication. EUROCRYPT '99, pp. 402–414, 1999.Google Scholar
  6. 6.
    R. Canetti. Security and composition of multiparty cryptographic protocols. J. of Cryptology, 13(1), 2000.Google Scholar
  7. 7.
    D. Chaum. Security without identification: Transaction systems to make big brother obsolete. Communications of the ACM, 28(10):1030–1044, 1985.CrossRefGoogle Scholar
  8. 8.
    D. Chaum, A. Fiat, and M. Naor. Untraceable electronic cash. CRYPTO '88, pp. 319–327Google Scholar
  9. 9.
    B. Chor, O. Goldreich, E. Kushilevitz, and M. Sudan. Private information retrieval. FOCS '95, pp. 41–51, 1995.Google Scholar
  10. 10.
    S. Even, O. Goldreich, and A. Lempel. A randomized protocol for signing contracts. C. ACM, 28:637–647, 1985.CrossRefMathSciNetGoogle Scholar
  11. 11.
    Y. Gertner, Y. Ishai, E. Kushilevitz, and T. Malkin. Protecting data privacy in private information retrieval schemes. JCSS, 60(3):592–629, 2000. Preliminary version in STOC '98.zbMATHMathSciNetGoogle Scholar
  12. 12.
    O. Goldreich. Secure multi-party computation., February 1999.
  13. 13.
    O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game. STOC '87, pp. 218–229, 1987.Google Scholar
  14. 14.
    Y. Ishai and E. Kushilevitz. Private simultaneous messages protocols with applications. STOC '97, pp. 174–183, 1997.Google Scholar
  15. 15.
    J. Kilian. Basing cryptography on oblivious transfer. STOC '98, pp. 20–31, 1988.Google Scholar
  16. 16.
    E. Kushilevitz and R. Ostrovsky. Replication is not needed: Single database, computationally-private information retrieval. FOCS '97, pp. 364–373, 1997.Google Scholar
  17. 17.
    E. Mann. Private access to distributed information. Master’s thesis, Technion-Israel Institute of Technology, Haifa, 1998.Google Scholar
  18. 18.
    D. Naccache and J. Stern. A new public key cryptosystem. EUROCRYPT '97, pp. 27–36, 1997.Google Scholar
  19. 19.
    M. Naor and B. Pinkas. Oblivious transfer and polynomial evaluation. STOC '99, pp. 245–254.Google Scholar
  20. 20.
    M. Naor and B. Pinkas. Oblivious transfer with adaptive queries. CRYPTO '99, pp. 573–590.Google Scholar
  21. 21.
    M. Naor and B. Pinkas. Efficient oblivious transfer protocols. SODA 2001.Google Scholar
  22. 22.
    M. Naor and O. Reingold. Number theoretic constructions of efficient pseudorandom functions. FOCS '97.Google Scholar
  23. 23.
    T. Okamoto and S. Uchiyama. A new public key cryptosystem as secure as factoring. EUROCRYPT '98, pp. 308–318, 1998.Google Scholar
  24. 24.
    P. Pallier. Public-key cryptosystems based on composite degree residuosity classes. EUROCRYPT '99, pp. 223–238, 1999.Google Scholar
  25. 25.
    M. O. Rabin. How to exchange secrets by oblivious transfer. Technical Report TR-81, Harvard Aiken Computation Laboratory, 1981.Google Scholar
  26. 26.
    S. von Solms and D. Naccache. On blind signatures and perfect crimes. Computers and Security, 11(6):581–583,1992.CrossRefGoogle Scholar
  27. 27.
    J. P. Stern. A new and efficient all-or-nothing disclosure of secrets protocol. ASIACRYPT '98, pp. 357–371, 1998.Google Scholar
  28. 28.
    A. C. Yao. How to generate and exchange secrets. FOCS '86, pp. 162–167, 1986.Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2001

Authors and Affiliations

  • Bill Aiello
    • 1
    • 2
    • 3
  • Yuval Ishai
    • 1
    • 2
    • 3
  • Omer Reingold
    • 1
    • 2
    • 3
  1. 1.DIMACS and AT&T Labs - ResearchFlorham Park
  2. 2.AT&T Labs - ResearchFlorham Park
  3. 3.AT&T Labs - ResearchFlorham Park

Personalised recommendations