Distributed Vector-OLE: Improved Constructions and Implementation

Author: Schoppmann, P., Gascón, A., Reichert, L. , and Raykova, M.
Published in: CCS '19: Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, 1055–1072
Year: 2019
Type: Academic articles
DOI: 10.1145/3319535.3363228

We investigate concretely efficient protocols for distributed oblivious linear evaluation over vectors (Vector-OLE). Boyle et al. (CCS 2018) proposed a protocol for secure distributed pseudorandom Vector-OLE generation using sublinearcommunication, but they did not provide an implementation. Their construction is based on a variant of the LPN assumption and assumes a distributed key generation protocol for single-point Function Secret Sharing (FSS), as well as an efficient batching scheme to obtain multi-point FSS. We show that this requirement can be relaxed, resulting in a weaker variant of FSS, for which we give an efficient protocol. This allows us to use efficient probabilistic batch codes that were also recently used for batched PIR by Angel et al. (S&P 2018). We construct a full Vector-OLE generator from our protocols, and compare it experimentally with alternative approaches. Our implementation parallelizes very well, and has low communication overhead in practice. For generating a VOLE of size $2^20 $, our implementation only takes $0.52$s on 32 cores.

Visit publication


Connected HIIG researchers

Phillipp Schoppmann

Assoziierter Forscher: Daten, Akteure, Infrastrukturen

  • Open Access