How many polynomials are used in Secure Multiparty Computation?

Question

Secure Multiparty Computation based on Samir Secret sharing methods rely on Polynomials. Imagine corpus of data should be outsourced to bunch of untrusted servers for any computations. Now the data could be split by a trusted client using Secret Sharing and distributed among the multiple untrusted servers. Subsequently any operations on the data could done using Secure Multiparty Computation protocols such that no single untrusted server has access to complete data in clear.

If the corpus of data are confidential documents and the client tokenizes them into each word then secret shares those words into say three shares. Distribute them to three untrusted servers. So that subsequently the client could search the documents for keyword using some SMC protocol.

Should the client use different polynomials for each word (or collection of words) or same polynomial could be used for entire corpus of document

Precisely,

1. If same polynomial is used for secret sharing all the words then searching the corpus with the share of keyword would be easy. But then the secret shares of each word would be pretty deterministic and frequency analysis could be launched to identify the words.
2. If different polynomial is used then how is the search for keywords work on the entire corpus ?

The same might hold good not only for search , for any other operation including arithmetic. Any help ?

Answer 1

For "standard" Shamir secret sharing you use a new random polynomial for each secret you want to share (including when you use Shamir secret sharing in SMC). I.e., you would use different polynomials for each secret. Note, that Shamir secret sharing does not directly work on "words" but rather elements of some field. You would have to translate your data into field elements and then share those elements individually.

There is, however, a variant of Shamir secret sharing called "packed secret sharing". In this variant you are able to share a "block" of $l$ secrets using a single polynomial. This means you would be using a factor $l$ less polynomials. There are SMC schemes that rely on this kind of sharing as well, although they are somewhat more complicated than those using standard Shamir secret sharing (an example of such a scheme can be found here: iacr eprint link).

As to how search would work, this is really not something that is standardized. The SMC allows you to compute any arithmetic circuit over the shared data. You can essentially express any function, including keyword search, as an arithmetic circuit. However, exactly how to do this is not trivial to figure out.

In fact, for this particular task you may be better off picking a different SMC technique, based on Boolean circuits instead of arithmetic circuits. This is because keyword search probably involves a lot of comparisons. Something that Boolean circuits are much more well suited for.

Answer 2

We have two kind of search while outsourcing: keyword search and text search.

In the keyword search you choose some keywords in your text and preprocess them before outsourcing. In the server(s), there is just one instance of each keyword so there is no duplication problem. There is the literature of searchable encryption that mostly covers this kind of search. Note that in this case you are not able to find anything other that preprocessed keywords even if they exist in the text.

In this case you can simple use one single polynomial. There are many secure protocols to solve this case.

In the text search you cannot or simply do no want to choose some keywords. For example in DNA datasets there is no such keywords to be chosen and there is a stream of characters. In this case, there are lots of duplication in the server(s) that can be used to reveal the entire text through statistical analysis.

In this case, you cannot use a single polynomial because of duplication. In the other hand, you cannot use several polynomials and keep your query's communication order less than $O(|text|)$.

The best know solution to this kind of search is Outsourced pattern matching, S.Fuast, et al., 2014. However they work is still somehow keyword search.