I want to know but I don’t want to reveal
A big challenge for enterprise benchmarking is that KPIs are sensitive and confidential, even within a single company. Confidentiality is of the utmost importance in benchmarking, since KPIs allow the inference of sensitive information. Companies are therefore hesitant to share their business performance data, due to the risk of losing a competitive advantage.
However, companies are still interested in learning the result of a statistical function applied to the individual values of their competitors KPIs, such as mean, average or median, as this can allow to improve and optimize their own business. The median, for instance, is a ranked-based statistic that consists of computing the middle-ranked element in a dataset. It is a robust statistic as it gives a meaningful information of a typical value in the data set.
Ranked-based statistics also have application in auctions, when a bidder receives useful bid data from other participating buyers in the auction, for instance the minimum value he would have had to bid in order to win that auction, whether he lost or won. Also in case of auctions, the confidentiality is crucial because of the greater number of parties involved.
Solutions do exist
The confidentiality issue can be addressed using multiparty computation, an interactive cryptographic model that allows many parties to compute a function on their encrypted inputs such that only the computation’s result is revealed. This guarantees that no party will learn more than the output of the computation, and the other parties’ inputs remain confidential, protecting participants’ privacy from each other.
There exist well known secure multiparty computation protocols that can be used for keeping KPIs or bids confidential while comparing them. They require to establish a communication channel between each pair of input parties. We refer to this approach as the standard model (Figure 1). Unfortunately, protocols for securely compute rank-based statistics in the standard model do not scale easily to many parties, as they require a communication channel between any pair of parties and are highly interactive, resulting in high latency. Moreover, they are difficult to deploy, as special arrangements are required between each pair of parties to establish a secure connection.
Figure 1 The Standard Model involves communication and connectivity between all participants. Each party is potentially malicious, no individual party can see other parties’ data.
The server model
A promising approach for overcoming the limitations of the standard model is to use a server model. In this model, the input parties (the clients) delegate the computation to a set of servers that make their computational resources available. The servers are to be considered untrusted, so they must do the computation without knowing the inputs, nor the outputs. To ensure the confidentiality, this model relies on multiple non-colluding servers, which means the servers cannot be under the control of the same administrator. The provider of such a privacy-preserving service requires a business model that shares benefits with the servers offering their computational power.
All for one and one for all
The SAP security researchers Anselme Tueno, Yordan Boev, Mubashir Qureshi, in collaboration with professor F. Kerschbaum from University of Waterloo and professor S. Katzenbeisser from University of Passau, have developed a multiparty computation model consisting of clients (with private inputs) and only one server (Figure 2) which ensures the same confidentiality than the multi-server model.
In this model, the server makes its computational resources available to the clients, does not know the inputs and does not learn the output. Moreover, it is a centralized communication pattern: there are communication channels only between each client and the server i.e., it is a star network. As a result, the clients will only communicate with the server, but never directly amongst each other. This model naturally fits with the client-server architecture of Internet applications and allows a service provider to play the server’s role. It can simplify the secure protocol and improve its performance and scalability.
Figure 2 One-Server Model: The server can be untrusted; it does not need to know anything to perform the computation.
The basic idea of our protocol is to pairwise compare clients’ inputs with the help of the server, but without revealing any information on the inputs to any party (including the server). The result of each pair of comparison is represented as a bit and revealed encrypted to the server using an additively homomorphic encryption. The server then homomorphically adds up this encrypted comparison bits to get the encrypted rank of each input. Finally, the server homomorphically selects the result and sends it to each client for decryption.
This idea has been implemented as a proof-of-concept solution and evaluated using several machines connected via WAN. For up to 50 clients, our protocol runs within few seconds while requiring only a moderate communication size, i.e., the amount of data (in bits) sent during the computation.
Our solution does not only provide a business opportunity for a cloud provider, but it also leverages the server to reduce the complexity of the computation and to keep the number of round low and constant. A large number of rounds increases the overhead of a multiparty computation protocol. Moreover, our solution provides collusion-resistance (ability to tolerate collusion of few clients without violating the security of the non-colluding ones) and fault-tolerance (ability to tolerate failure of few clients without preventing the proper termination of the computation).
For more details you are invited to read the full paper which has been published and presented by the SAP security researcher Anselme Tueno at the Financial Cryptography and Data Security (FC) conference in February 2020, in Kota Kinabalu, Malaysia.
Reference of the scientific publication:
A. Tueno, F. Kerschbaum, S. Katzenbeisser, Y. Boev and M. Qureshi. Secure Computation of the kth-Ranked Element in a Star Network. Proceedings of Financial Cryptography and Data Security (FC), 2020 https://fc20.ifca.ai/preproceedings/101.pdf
Discover how SAP Security Research serves as a security thought leader at SAP, continuously transforming SAP by improving security.