Paper 2019/1084

Distributed Vector-OLE: Improved Constructions and Implementation

Phillipp Schoppmann, Adrià Gascón, Leonie Reichert, and Mariana Raykova


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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. ACM Conference on Computer and Communications Security (CCS '19)
secure computationcorrelation generatorsOLEFSScuckoo hashing
Contact author(s)
schoppmann @ informatik hu-berlin de
adriagascon @ gmail com
leonie reichert @ hu-berlin de
mpr2111 @ columbia edu
2019-12-13: revised
2019-09-24: received
See all versions
Short URL
Creative Commons Attribution


      author = {Phillipp Schoppmann and Adrià Gascón and Leonie Reichert and Mariana Raykova},
      title = {Distributed Vector-OLE: Improved Constructions and Implementation},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1084},
      year = {2019},
      doi = {10.1145/3319535.3363228},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.