University Of California, San Diego (Calit2)
Three recently proposed schemes use secret sharing to support privacy-preserving data outsourcing. Each secret in the database is split into n shares, which are distributed to independent data servers. A trusted client can use any k shares to reconstruct the secret. These schemes claim to offer security even when k or more servers collude, as long as certain information such as the finite field prime is known only to the client. The authors present a concrete attack that refutes this claim by demonstrating that security is lost in all three schemes when k or more servers collude.