Sophia Yakoubov: The Rise of Paillier: Homomorphic Secret Sharing and Public-Key Silent OT
Abstract:
Joint work with Claudio Orlandi and Peter Scholl.
In this talk, I will describe a simple method for solving the distributed discrete logarithm problem in Paillier groups, allowing two parties to locally convert multiplicative shares of a secret (in the exponent) into additive shares. Our algorithm is perfectly correct, unlike previous methods with an inverse polynomial error probability. I will discuss applications of this to homomorphic secret sharing and generating correlated pseudorandomness, including the following main results:
– Homomorphic secret sharing:
We construct homomorphic secret sharing for branching programs with negligible correctness error and supporting exponentially large plaintexts, with security based on the decisional composite residuosity (DCR) assumption.
– Public-key silent oblivious transfer:
We construct a pseudorandom correlation function (PCF) for oblivious transfer, which allows two parties to obtain a practically unbounded quantity of random oblivious transfers, given a pair of short, correlated keys. We also show how to obtain a public-key setup for the PCF, whereby after independently posting a public key, each party can locally derive its PCF key. This allows completely silent generation of OTs, without any interaction beyond a PKI, based on the quadratic residuosity and DCR assumptions.