2
$\begingroup$

Lets consider Secure Multiparty Computation based on Secret Sharing schemes (rather than Garbled Circuits approach). If we have to do regular expression matching on secret shares of words of texts. Trivial solution is to secret share each letter of the word and distribute to different parties and later each party executes the regular expression on the secret shares of each letter.

For example : $SERVER\_01\_LAB$ could be secret shared on each letter "S,E,R,V,E,R,0,1,_,L,A,B" . and for the regular expression $SERVER.*LAB$, we build secret shares of each letter and send the regex of respective shares to individuals for matching.

But this is too trivial and breaks all the security because if we create secret shares of individual letters then adversary can perform simple frequency analysis on shares and break it .

Can we do this better ? Any better approaches exist ?

Improve this question
$\endgroup$
9
  • $\begingroup$ I don't see how frequency analysis is possible, assuming the secret sharing technique is semantically secure (which why would you use one that isn't). $\endgroup$
    – mikeazo
    Commented Oct 29, 2015 at 12:28
  • 1
    $\begingroup$ It would be really cool to see if you could do some indexing to speed up regex search all in MPC. So the indexing and the search is done via MPC. $\endgroup$
    – mikeazo
    Commented Oct 29, 2015 at 12:30
  • $\begingroup$ imagine i have shares of each letter of each word from just one party , why do you think we cannot do frequency analysis ? If the secret shares are not created from same polynomial, i dont think we can do meaningful operations. if they are from same poly then we can do frequency analysis as they are consistent $\endgroup$
    – sashank
    Commented Oct 29, 2015 at 12:34
  • $\begingroup$ I would assume they are from different polynomials. VIFF can do equality check on secret shares from different polynomials. The result is a sharing of either 0 or 1, which the parties can open to reveal the answer. $\endgroup$
    – mikeazo
    Commented Oct 29, 2015 at 12:54
  • 1
    $\begingroup$ You seem to think that there is only one possibly sharing of a value. If you generate secret-sharings of the same value x 5 times, you'll get 5 independent sets of shares. Just like if you encrypt the same message 5 times you'll get 5 different ciphertexts (in a CPA-secure scheme). Otherwise, as you point out, testing for equality is trivial. $\endgroup$
    – Mikero
    Commented Oct 29, 2015 at 16:22

2 Answers 2

Reset to default
3
$\begingroup$

there are some special constructions that could be used. for example see this paper of florain kerschbaum (freely available version). also, you can use some secure DFA evaluation protocols, as any regex can be represented as a DFA.

what you have proposed is not secure and the servers can learn lots of information.

Improve this answer
$\endgroup$
2
$\begingroup$

Yes we can do better. Secure approaches exist.

We implemented regular expression matching in the ShareMonad, which is secure in the semi-honest setting. IIRC, the paper touches on our DFA construction and selected algorithm - which is the hardest part really. Once you know the algorithm it's just a matter of turning the crank.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I did not get exactly what it means "three share servers will know the regular expressions being used" at Page-7. does three servers know the regex as "TOP|SECRET... " or shares of "TOP" ,"SECRET" etc? If NFA/DFA is constructed on shares of the strings then exactly the problem i mentioned isn't it too trivial ? $\endgroup$
    – sashank
    Commented Nov 1, 2015 at 9:58
  • $\begingroup$ In our implementation the regex was known while the corpus was secret. That is to say, there were xor shares so two servers would have random numbers and the third server would have text + random1 + random2 - which is itself indistinguishable from random. $\endgroup$
    – Thomas M. DuBuisson
    Commented Nov 1, 2015 at 14:15
  • $\begingroup$ oh ok , what if the regex should be kept private too from the servers ? any thoughts on approaches $\endgroup$
    – sashank
    Commented Nov 1, 2015 at 14:58
  • $\begingroup$ Sure. I modeled regex as a state machine (DFA) and used shares of a table along with oblivious lookup (that is, oblivious index which represents the token from the corpus and an oblivious table) to perform this task. It's a good bit slower. $\endgroup$
    – Thomas M. DuBuisson
    Commented Nov 1, 2015 at 15:23
  • $\begingroup$ Interesting any references for this oblivious lookup approach ? $\endgroup$
    – sashank
    Commented Nov 1, 2015 at 15:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.