# Collusion resistant computing of same function by two servers

Is there a secure way of computing same hash function of replicated data by two servers. I mean that both servers host the same version of replicated data and they should output h(M) without colluding, i.e., both of them really compute the specified function.

• Who wants to verify that they actually hold the same data? They among themselves? Any (anonymous) external user? Can the verifier be assumed to also have a copy of the file? What do you mean by "collusion", ie can you be more specific about your situation / what you don't want the servers to do? – SEJPM May 23 '18 at 19:06
• A third party who does not know the data verifies that they actually hold the same data. By collusion I mean that one server outputs h(M) without really having M, by using the computation of the other server – Reyhan May 23 '18 at 20:48
• While not an answer, this paper from 2013 may be of interest to you. – SEJPM May 23 '18 at 21:11
• What if the ‘two servers’ are actually just one server, holding two telephones in two separate hands to and speaking in alternate funny voices to pretend that there are two of them? – Squeamish Ossifrage May 24 '18 at 1:37

In certain cases, if the function allows, data masking can be used.

This involves altering the replicated data so each server instead gets a masked version for which they do not know the mask value.

Then servers cannot help each other since their calculation does not aid the other.

## Simple example

Function: one-time-pad encryption using key 10010010

Original data: 00101001

Server 1 get $m_1$ = 00101001 $\oplus$ 10010100 and computes $c_1$ = $m_1$ $\oplus$ 10010010

Server 2 get $m_2$ = 00101001 $\oplus$ 00100101 and computes $c_2$ = $m_2$ $\oplus$ 10010010

The corresponding mask can then be used to obtain the correct output of the function.

• Thank you, but my question is about hash functions, both servers host the same version of replicated data and they should output h(M), how to avoid colluding? how to be sure that both of them really computed h(M)? – Reyhan May 23 '18 at 13:11
• Your right, this would not work for a hash function. sorry – Jackoson May 24 '18 at 12:33

Collusion is not easy to solve, unless you want to admit some additional assumptions.

For example, if you assume you can monitor and control all communication channels between the two servers, then you can prevent collusion by not allowing them to talk to each other.

Also, if you have some "trusted" hardware or software module on the servers, then you can let the trusted modules to do the hashing and without worrying about collusion.

Or if you assume the servers are operated by different companies who are rational, perhaps you can use some economic incentives to prevent collusion, like this paper.

It sounds like what you really want is a Proof of Replication, where you can have multiple servers prove that they each have their own copy of a file.

The servers must each prove that they've been hosting their own redundant copy of file the whole time, and that they haven't just downloaded it just-in-time in order to create the proof. If you upload a file to a cloud service that claims they'll host N redundant copies of the file, they can use proofs of replication in order to confirm that they are in fact keeping N copies and not just one.

Protocol Labs (developer of IPFS and Filecoin) has developed a strategy for proofs of replication. Page 8 of the Filecoin Primer has a short description and diagram overviewing the strategy, and their Proof of Replication paper is more in-depth.

The basic idea is that each server is given a unique "sealed" replica of the data. The data may be easily recoverable from the sealed version. Creating (or recreating) the sealed version takes a predictable amount of time and may be done by anyone. The verifier can issue a challenge to a server that can only be answered by using that server's uniquely-sealed version of the data, and the verifier expects the server to answer within a timeout period that's shorter than the amount of time it would take for the server to download the data from another server and recreate the seal.