It just occured to me that when this protocol is implemented with RSA, it is subject to a minor (and unlikely) failure that can allow Alice to determine which video Bob has selected (or at least eliminate some of them). If each video keypair has a different modulus and the one Bob selects has a larger modulus than some of the "dummy" videos, then if the encryption of Bob's session key with his selected video public key results in a message that is close to the modulus itself, the keypairs with moduli that are smaller than Bob's message can be trivially eliminated as candidates.

This protocol also assumes that all of the movies (or pieces of information) cost the same amount. Presumably in the video-on-demand business, a most movies would have the same cost or there would be a few 'levels' of costs with many movies in each 'level.' In that case you would only pick random 'padding' videos that have the same price. However, a video store could easily give all of the horror movies one price, all of the comedy ones another, all the pornos another, etc.... and at least be able to determine the general type of video the customer is purchasing. In a general information market type setup, I would expect that the value of different pieces of information would vary greatly. How would payment of the information be made? In a general information market setup, where the bits of information have varrying values you could do something like the following. in the oblivious transfer protocol, if the hardware used is implemented in tamper-proof chips, the price of each piece of information could be encoded with the information. The chip would store a running total of the prices of information successfully decrypted by the customer. At the end of the month, the box would send the total price to the vendor, which will bill the customer. Depending on the number of pieces of information purchased, the vendor would be able to infer more or less information on the types of info bought by the customer... Also, you could randomly purchase very cheap (or free and worthless) bits of information to make it more difficult for the vendor to figure out what you are interested in... andrew