Topic 1 – Private Membership Test
(F-Secure, Trustonic, Aalto, UH)
Android App reputation (WP1-01) and website reputation (WP1-02) service providers possess a database consisting of all reputation information of samples. A user who wants to check the existence of an object (website or App), should query through this database. This query is done by sending a request consisting of an identifier of the object to the database holder. The database holder’s response is a reputation value (or simply True or False), which determines whether the requested service is clean or not.
The nature of a reputation query is to directly hand over a search item (in this case an object identifier) to service providers. This, however, causes a major privacy concern: service providers learn all queries that have been requested by users, therefore gaining personal information about their users. Studies demonstrate that digital records of human behavior, such as websites and applications they are interested in, can expose important personal traits e.g. religion, political views, relationship status etc. Therefore, this research focuses on protecting users of reputation services, from leakage of their private information.
Crypto-based solutions. We propose a practical solution by approaching the problem from an offline/online setting. Specifically, we introduce the following three phases: a base phase where server and client run data-independent precomputation, e.g., agree on the public parameters; a setup phase where query-independent precomputation is performed on server’s input and the results are transferred to clients, who then potentially performs additional computations; and an online phase where the operations dependent on the clients' queries are performed. We aim to shift most of the communication and computation work into the base and setup phases to have an efficient online phase. Take our motivating scenario as an example, after installing the service provided by the malware provider, the client may run the base and setup phases overnight. Then, by running the online phase, the client can check a malware to be installed on its device within a short period of time. Thereafter, updates (i.e., insertion or deletion) on the dictionary is supported by only running the efficient online phase. In the setup phase, the server blinds each element in the database, resulting in a blinded database. Then the server inserts it into a compact data structure (e.g., bloom filter or cuckoo filter) and transfers it to clients. Whenever a client wants to check an element, it runs an oblivious protocol with the server to get its blinded version without revealing any information, after which it can check its existence locally. We investigate four blinding techniques: RSA based, Diffie-Hellman (DH) based, Naor-Reingold (NR) based, and AES-GC based. This work has been published in PETS ’17 .
In addition to the previous solution, we suggest another practical crypto-based solution for the problem of private membership test. We propose a protocol with low communication complexity that utilizes additively homomorphic encryption scheme. The proposed protocol enables a client to perform privacy-preserving queries on a set controlled by a server. We aim to lower the communication complexity as less as possible. We approach the problem by defining a setting that compresses the size of the server’s database by utilizing Bloom filter or Cuckoo filter.
In this setting, the server divides the database into several subsets. Each subset contains elements of the database that start with the same prefix of bits. Server stores each subset into a Bloom filter or Cuckoo filter. Server arranges a matrix and inserts the filters into the matrix. In order to achieve privacy properties, the client encrypts the location of the matrix that he/she is interested in, using an additively homomorphic encryption. We used Paillier encryption scheme to implement this protocol. Client sends the encrypted values to the server. The server performs a series of computations for all the elements of the matrix, using client’s encrypted values and sends the results back to the client. The client decrypts the results, retrieves a filter and performs the membership test on this filter privately. We implement this protocol based on our motivation scenario.
The results show that our proposed protocol has a low communication and computation complexity, such that it is feasible in practice. Moreover, this solution does not need any preprocessing procedure. Therefore, updates can be done instantly. This work has been published in NSS ’17 .
TEE-based solution. Based on studying the feasibility of using trusted computing technologies, we propose a new carousel design pattern by having the TEE continuously circle the dictionary, such that a batch of queries can be answered within a single carousel cycle. Similar to the approach in , the server inserts the database into a compact data structure. Since TEE needs to circle the whole data structure, the choice of data structure has a significant impact on the performance of the system. After experimentally evaluating the performance of several well-known data structures, we chose 4-ary cuckoo filter for our protocol. To process queries, TEE cycles through the data structure and scans its contents in order to answer the received queries. The data structure is divided into several chunks and invoked sequentially with each chunk as input along with waiting queries. Incoming queries are associated with the identifier of the chunk with which they arrived, which is defined as their time of arrival. TEE compares each entry in the chunk with the queries inside its memory and records the results. This process is repeated for each chunk. To avoid information leakage, TEE a) performs constant-time processing for every entry, and b) ensures that every query remains in TEE for exactly one full carousel cycle. This work has been published in AsiaCCS ’17 and got Honorable Mention . It has been selected as one of the top 10 papers from Europe in Applied Research Context at CSAW Europe .
Topic 2 – Private Graph Search
This use case is about a cloud-assisted security service for managing trust relationships (WP1-03). In a large information system, such as an internal network of a big corporation, different users have trust of varying degree on each other. Then there is no need to define (or re-define) policies for each node separately. Instead, trust relationships between different nodes are defined first and policies may be built on top of the concept of trust relationship.
In our model, a trust relation is a quintuple of the form: (source user, sourcehost, fp, target user, targethost).
This expresses that a particular sourceuser@sourcehost can access another targetuser@targethost by using a unique fingerprint fp. A fingerprint is obtained from a public key by which the access attempt is authenticated. The data is in the form of a directed graph with labeled edges. The vertices in the graph are different user-host pairs. The edges are fingerprints that connect these pairs.
The owner of the graph or some other user wants to do queries about the graph using a cloud that stores the data and implements the queries.
We have addressed the user case where one entity owns the trust relationship database and another makes queries to it. The owner of the database calculates the binary matrix that has one in location (i,j) if there is a path from node denoted by i to the node denoted by j in the directed graph. The matrix is encrypted and then sent to the cloud.
When the querier wants to know if there is a path from user-host pair a to user-host pair b, he first finds out which row of the matrix corresponds to a and which column of the matrix corresponds to b. Then, using a private information retrieval protocol he extracts corresponding bit from the encrypted matrix stored in the cloud. After that he employs a blind decryption protocol with the owner of the graph to reveal the answer to the query.
In this protocol the owner of the graph does not learn the query nor the answer to it. The cloud learns nothing because the matrix is encrypted and a PIR protocol is used to make queries to it. The protocol works in reasonable time with realistic database sizes. This work has been submitted to NTMS ’18 .
We have also considered the problem where the trust relation database is constructed of two parts, both parts have different managers, and they do not want to reveal their secrets to other parties. A paper based on our solution to this problem is currently in preparation.
The third problem that we have been considering is the user case where the trust relation database has only one owner but instead of just asking if there is a path of trust relations from one user to another, the querier wants to know what the path is.
Topic 3 – Privacy-preserving Classifiers
(F-Secure, Nokia, Aalto)
As mentioned in Topic 1, Android App reputation (WP1-01) and website reputation (WP1-02) require clients to query the cloud-hosted database in a privacy-preserving way. However, novel App/website reputation service allows clients to extract features of an App/website, and the server runs a machine learning classifier on the features and returns the classification results. This requires an approach to run the classification in a privacy-preserving way such that the server learns nothing about clients’ features, and clients learn nothing about the classifier except the output results. We refer to this technique as privacy-preserving classifiers.
Having an approach for privacy-preserving classifiers also benefits Fake Base Station Detection using Cloud Services (WP1-04), Differential Anomaly Detection (WP1-05).
We targeted neural network classification and presented the first technique that can transform any common neural network model into a privacy-preserving one without any modifications to the training phase. We design oblivious protocols for operations routinely used by neural network designers: linear transformations, popular activation functions and pooling operations. In particular, we use polynomial splines to approximate nonlinear functions (e.g., sigmoid and tanh) with negligible loss in prediction accuracy. None of our protocols require any changes to the training phase of the model being transformed. We only use lightweight cryptographic primitives such as secret sharing and garbled circuits in online prediction phase. We also introduce an offline precomputation phase to perform request-independent operations using additively homomorphic encryption together with the SIMD batch processing technique. We show that our approach outperforms existing work in terms of response latency and message sizes. We demonstrate its wide applicability by transforming several typical neural network models trained from standard datasets. This work has been published in CCS ’17, one of the top tier conferences in security .
 Àgnes Kiss, Jian Liu, Thomas Schneider, N. Asokan, Benny Pinkas. Private Set Intersection for Unequal Set Sizes with Mobile Applications. In Proceedings of the 17th Privacy Enhancing Technologies Symposium (PETs), Minneapolis, USA , Pages 97-117, July 2017.
 Sara Ramezanian, Tommi Meskanen, Masoud Naderpour, Valtteri Niemi. Private Membership Test Protocol with Low Communication Complexity. In International Conference on Network and System Security, pp. 31-45. Springer, Cham, August 2017.
 Sandeep Tamrakar, Jian Liu, Andrew Paverd, Jan-Erik Ekberg, Benny Pinkas, N. Asokan. The Circle Game: Scalable Private Membership Test Using Trusted Hardware. In Proceedings of the 11th ACM on Asia Confer- ence on Computer and Communications Security (ASIA CCS), Abu Dhabi, United Arab Emirates, Pages 31-44, April 2017.
 CSAW Europe https://csaw.engineering.nyu.edu/research/finalists
 Jian Liu, Mika Juuti, Yao Lu, N Asokan. Oblivious Neural Network Predictions via MiniONN Transformations. In Proceedings of the 24th ACM SIGSAC Conference on Computer and Communications Security (CCS), Dallas, Texas, USA, October 2017.
 Sara Ramezanian, Tommi Meskanen, Valtteri Niemi. Privacy Preserving Queries on Directed Graph. submitted to NTMS'2018 - Security Track