Cryptology ePrint Archive: Report 2019/1084

Distributed Vector-OLE: Improved Constructions and Implementation

Phillipp Schoppmann and AdriÓ Gascˇn and Leonie Reichert and Mariana Raykova

Abstract: 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 sublinear communication, 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.

Category / Keywords: cryptographic protocols / secure computation, correlation generators, OLE, FSS, cuckoo hashing

Original Publication (with minor differences): ACM Conference on Computer and Communications Security (CCS '19)

Date: received 23 Sep 2019, last revised 13 Dec 2019

Contact author: schoppmann at informatik hu-berlin de, adriagascon at gmail com, leonie reichert at hu-berlin de, mpr2111 at columbia edu

Available format(s): PDF | BibTeX Citation

Version: 20191213:124657 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]