The report contains an overview of the results of the last period of UaESMC, pertaining to secure multiparty computation techniques. The studies of these techniques have been directed by the example problems selected during the first year, as well as by the desire to have a comprehensive framework of privacy-preserving computation techniques by the end of the project. In this deliverable, we report of the following findings and advances:
- We give protocols for solving systems of linear equations in privacy-preserving manner. Our protocols constitute a nice example of adapting existing algorithms for running on private (secret-shared) data.
- On the other hand, we show that certain transformation-based techniques cannot in general give us privacy-preserving protocols for solving linear equation systems. The situation here is more complex than for linear programming, though, and for certain sets of possible systems of equations, some transformation-based methods may have acceptable privacy guarantees and good performance.
- We provide a novel protocol transformation that turns any passively secure multiparty computation protocol with honest majority to a protocol where any misbehaviour is detected after the execution. Our transformation is significantly more efficient than the one we've proposed in the previous reporting period. It is also more widely applicable, including protocols over rings, not fields. Hence it can be applied to the protocols of Sharemind.
- We show how the security property for SMC protocols can be decomposed into several ones, one of which is privacy. We show that privacy is also composable and aiming for this property only can give us more efficient SMC protocols. We also show that security can be recovered by composing a private protocol with a simple secure protocol.
- We give protocols for obliviously reading many elements of a private vector in parallel, and for obliviously writing many values into a private vector in parallel. Our protocols are more efficient than the existing implementations of Oblivious RAM (ORAM) on top of SMC. Our protocols allow any efficient algorithm for the Parallel Random Access Machine (PRAM) to be transformed to a privacy-preserving computation, as long as the control ow of that algorithm does not depend on private data.