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 ?