# How many polynomials are used in Secure Multiparty Computation?

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 ?

• Every secret-sharing-based MPC protocol works by generating independent shares of the inputs. You seem to be having trouble understanding how computations can be carried out on independent shares. I suggest consulting some lecture notes or videos on the BGW protocol. – Mikero Nov 12 '15 at 3:59
• The question is too broad, in the sense that the only answer can be "as many as your algorithm or protocol requires". It is like asking "how many stones do you need to build a house?" without stating the size or the number of appartments. – tylo Feb 4 '16 at 16:07

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.

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.

• What if you have multiple texts? Do you use one global polynomial or a unique one per text? – mikeazo Nov 11 '15 at 14:16
• @mikeazo It depends on duplication existence. If you want to hide duplication you have to use different polynomials. Consider keyword search, If you have two sets of keywords extracted from two texts, using a single polynomial will reveal duplication of keywords. – MH Samadani Nov 11 '15 at 14:28
• @MHSamadani the above does not answer my question, The answer is more generic. The reference is also not related to SMC. – sashank Nov 12 '15 at 0:13
• @sashank I have answered the general problem with your example. Also, are you seeing SMC just as general constructions? How you categorize the reference? – MH Samadani Nov 12 '15 at 3:30