Privacy-Protecting Algorithms for Digraph Shortest Path Queries

Privacy-Protecting Algorithms for Digraph Shortest Path Queries

Sara Ramezanian (University of Helsinki, Helsinki, Finland), Tommi Meskanen (University of Helsinki, Helsinki, Finland) and Valtteri Niemi (University of Helsinki, Helsinki, Finland)
DOI: 10.4018/IJERTCS.2019070106


Trust relation in this work refers to permission that is given to a user at a source-host to access another user at a target-host through an authentication key with a unique fingerprint. The database owner can form a directed graph out of these trust relations, such that user-host pairs are considered nodes and fingerprints as arrows. The authors of this article present a novel protocol to query the shortest path from node A to node B, in a privacy preserving manner. The authors would like to use a cloud to perform such queries, but they do not allow the cloud to learn any information about the graph, nor the query. Also, the database owner is prevented from learning any information about the query, except that it happened.
Article Preview

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 IJERTCS.2019070106.m01 items, and a client who holds an index IJERTCS.2019070106.m02, IJERTCS.2019070106.m03. At the end of the protocol, the client retrieves nothing except the IJERTCS.2019070106.m04 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 IJERTCS.2019070106.m05who holds a message IJERTCS.2019070106.m06 and a signer IJERTCS.2019070106.m07 who has access to a secret signing key IJERTCS.2019070106.m08. At the end of the protocol, IJERTCS.2019070106.m09 receives the signature IJERTCS.2019070106.m10 of IJERTCS.2019070106.m11, while IJERTCS.2019070106.m12 learns nothing about IJERTCS.2019070106.m13 or IJERTCS.2019070106.m14. Bellare et al. (2003) proposed a blind signature scheme based on RSA (Rivest et al., 1978) assumption.

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 11: 4 Issues (2020): 1 Released, 3 Forthcoming
Volume 10: 4 Issues (2019)
Volume 9: 2 Issues (2018)
Volume 8: 2 Issues (2017)
Volume 7: 2 Issues (2016)
Volume 6: 2 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing