Querying Databases Privately A New Approach to Private Information Retrieval

The Internet and the World Wide Web (WWW) play an increasingly imp- tant role in our today's activities. More and more we use the Web to buy goods and to inform ourselves about cultural, political, economical, medical, and scienti'c developments. For example, accessing ?ight schedules, me- cal data, or retrieving stock information become common practice in today's world. Many people assume that there is no one who "watches" them when accessing this data. However, sensitive userswho accesselectronic shops(e-shops) might have observedthat this assumptionoften isnot true. In many cases, E-shopstrack the users'"accessbehavior"when browsingthe Web pagesof the e-shopthus deriving "accesspatterns" for individual shoppers. Therefore, this knowledge on access behavior and access patters allows the system to tailor access to Webpagesforthatusertohis/herspeci'cneedsinthefuture.Thistrackingof usersmightbeconsideredharmlessand"acceptable"inmanycases.However, in cases when this information is used to harm a person - for example about the person's health problems - or to violate his/her privacy (for example ?nding out about his/her ?nancial situation), he/she would like to be sure that such tracking is impossible to protect the user's rights.