Privacy-Protecting Algorithms for Digraph Shortest Path Queries

2. Preliminaries

The necessary background is explained in this section.

Private Information Retrieval (PIR) protocol (Gasarch, 2004) is a two-party protocol between a server who stores a database of items, and a client who holds an index , . At the end of the protocol, the client retrieves nothing except the item from the database, while the server learns nothing about which item was queried by the client.

The notion of blind signature was introduced by Chaum (1983) to protect the privacy of users of an electronic cash system. The blind signature protocol is a two-party protocol between a user who holds a message and a signer who has access to a secret signing key . At the end of the protocol, receives the signature of , while learns nothing about or . Bellare et al. (2003) proposed a blind signature scheme based on RSA (Rivest et al., 1978) assumption.