A Practical, Secure, and Verifiable Cloud Computing for Mobile Systems










privacy preserving

search for nearest bank/ATM










Privacy Preserving Search for the Nearest Bank/ATM


To evaluate our secure cloud computing approach for mobile systems, we consider the privacy preserving search application of finding the nearest bank/ATM, which is described as follows:


  1. Problem: Find the nearest bank/ATM from the mobile client.


  1. Goal: preserve the privacy of: (i) mobile client's input location, (ii) computed nearest bank/ATM location, and (iii) computed distance.


  1. Case study: An area of Salt Lake City, UT consisting of 104 blocks, bounded by Main St., 1300 East St., South Temple St., 800 South St.

Note: Main St. and South Temple St. represent 0 East St. and 0 South St. respectively.


  1. Area consists of Chase, Well Fargo bank/ATM locations (Source: www.chase.com, www.wellsfargo.com).


  1. Any East/South coordinate in this area represented using bits.


  1. Distance between the mobile client at an intersection and any bank/ATM location corresponds to the Manhattan distance metric, since the streets in the case study area are arranged in a grid pattern:



  1. We create the Boolean circuit for the computation using a combination of SUB, ADD, CMP, MUX, and a tree of MIN blocks [Slides].


  1. Our circuit has XOR, AND gates respectively, where





In the figures below, we have shown the server-side and client-side cost for our privacy preserving search application.



Server-side cost: For example, when n=4 cloud servers are used, these servers exchange about 126 GB of information to construct the garbled circuit, which demonstrates feasibility of our approach for real-world privacy preserving computations, from the perspective of the server-side cost.




Client-side cost: For example, when n=4 servers are used, the mobile client generates and exchanges with these cloud servers, less than 60 kilo bits of information to preserve its location privacy. Furthermore, the client-side cost grows much slowly with the number of servers, in comparison to the server-side cost.