Logic Programming is a simple, yet powerful formalism suitable for programming and knowledge representation1. A logic program is represented by a set of facts, and rules describing how new facts can be generated from existing ones.
Logic programming allows the developer to focus on devising facts an rules of a logical derivation, and not on algorithms and their optimizations, which are delegated to the underlying deduction engine of logic programming platform. The most striking feature of logic programming for the newcomer is how much simpler the programs look than in other languages2. Prolog and Datalog are among the most famous logic programming languages, which have quite similar syntax, but differ in scope of supported functionality and deduction strategy.
As an example, let us show how to construct Prolog script for a simple market application. First of all, we need to come up with a list of facts. We have a set of buyers and a set of sellers (these sets may overlap). Each seller declares which products they sell at which price.
sells(bob, garlic, 30). sells(bob, onions, 40). sells(chris, garlic, 70).
Similarly, each buyer declares which product they want to buy at which price.
buys(alice, onions, 50). buys(alice, garlic, 40). buys(dave, carrots, 70).
We want to express a rule bargain(X,Y,Z), which is true if and only if X can buy from Y product Z. First, we write down the rule head, i.e. the statement whose truthfulness we check.
bargain(X,Y,Z) :-
Now list the conditions that need to be satisfied for bargain(X,Y,Z) to be true. A bargain between a buyer X and a seller Y w.r.t. product Z is considered successful if the money P1 that X is ready to spend is at least the price P2 at which Y sells the product Z.
buys(X,Z,P1), sells(Y,Z,P2), P1 >= P2.
Finally, state a question that Prolog engine has to answer. Let us ask who can sell garlic to Alice.
?- bargain(alice, Y, garlic).
Based on the facts and rules above, Prolog answers that one (and the only one) potential seller is Bob.
Y = bob
Indeed, there is Chris selling garlic as well, but only Bob's price 30 is good enough for Alice who is ready to spend 40. The garlic of Chris with price 70 is too expensive for Alice.
This market application becomes more interesting if the underlying data can be sensitive. For example, buyers may want to keep their proposed amount of money secret, so that the seller would not increase the price after seeing that the potential buyer is ready to spend more. It is also possible that a seller does not want to keep his product name public unless someone is directly interested in buying it. Finally, both buyers and sellers may want to keep their identities secret as far as there is no agreement on a certain bargain. We want to answer a Prolog query while preserving the privacy of any involved data, including the inputs to the query.
A privacy-preserving application can be build on top of Sharemind platform, which is developed by Cybernetica (sharemind.cyber.ee). With Sharemind, all input data are encrypted at the data source. Each individual value is split into random pieces that are distributed among several Sharemind Application Server computation nodes. None of the individual pieces provide any information about the original value. This process is called secret sharing and can be thought as encryption without a key. No plaintext value leaves data owner's premises unencrypted.
The basic programming language for writing Sharemind applications is SecreC, which is C-like imperative programming language. While declarative languages like Prolog allow to write programs in a manner "what should be computed", in an imperative language developer has to describe "how the result should be computed". It is difficult to write efficient algorithms for Sharemind, since developer needs to take into account the complexity of underlying cryptographic protocols that implement different operations. If one comes up with an optimal public algorithm (i.e. without preserving privacy), it is not necessarily optimal for Sharemind. It would be easier to write the program in Prolog, delegating all optimizations to an automated tool.
Let us see how a privacy-preserving Prolog script would look like. Instead of listing all instances of the facts 'buys' and 'sells' with public arguments, we would describe only the structure of underlying data. Similarly, in the query statement, we do not write the name of the buyer and the product in plain.
:-type(sells(seller_name:private string, item:private string, price:private int)). :-type(buys(buyer_name:private string, item:private string, price:private int)). bargain(X,Y,Z) :- buys(X,Z,P1), sells(Y,Z,P2), P1 >= P2. ?- bargain(input_buyer_name:private string, Y, input_item:private string).
The database of buyers and sellers is uploaded into Sharemind in secret-shared manner in advance, using special data upload functionality of Sharemind. An automated tool transforms privacy-preserving Prolog script to SecreC code, which can then be executed on Sharemind platform. In the beginning of computation, Alice provides secret-shared inputs 'input_buyer_name' and 'input_item'. In the end of computation, Alice receives a valuation of Y, which is reconstructed from shares on Alice's side, so that Sharemind servers will not know that the final result was 'bob'.
Translating Prolog script to a Sharemind application gives us certain advantages. Sharemind supports several protection domains, giving different privacy guarantees and suitable for different settings. We can make use of abundant efficient Sharemind protocols without needing to build the underlying cryptography from scratch, which would be necessary if we developed our own secure computation platform. Composition of Sharemind protocols allows to build provably secure applications without needing to prove the security of all composed programs separately. The ETAG grant PSG497 is devoted to developing and optimizing a translator from Prolog and Datalog scripts to Sharemind applications.
1 Krzysztof R. Apt. From logic programming to Prolog. Prentice Hall International series in computer science. Prentice Hall, 1997.
2 Bramer, Max. Logic Programming with Prolog. Springer Science & Business Media, 2005.
Written by Alisa Pankova