Vector Oblivious Linear Evaluations with Succinct Communication

Abstract

In a vector oblivious linear evaluation (VOLE) scheme, the sender inputs a long input vector $\vec{x}$, and the receiver inputs a scalar $y$. After the scheme, they are required to obtain additive shavings of $\vec{x} \cdot y$. In view of succinctness, we require the overall communication to grow sub-linearly with $|\vec{x}|$. 

In this work, we study a 2-round realization of VOLE. Priorly, the receiver is able to pre-select an input scalar $y$ and a seed $\vec{s}$, along with the pseudorandom vector $\vec{v}$ generated by $\vec{s}$. During the execution, the sender chooses an input vector $\vec{x}$, transmits a message to the receiver, and receives a corresponding response to obtain its VOLE output $\vec{w}= \vec{x}\cdot y + \vec{v}$. 

We propose two constructions for succinct VOLE: (1) a DBDH-based scheme with $O(|\vec{x}|^{2/3}\lambda)$ communication; (2) an LWE-based scheme with $\poly(\log |\vec{x}|, \lambda)$ communication. We further show that succinct VOLE has interesting applications in constructing constraint PRFs and 2PC protocols. 

Biography

Liqiang Liu is currently a PhD candidate at the Center on Frontiers of Computing Studies (CFCS), Peking University, under the supervision of Tianren Liu. His research focuses on cryptography, with recent work primarily on secure multi-party computation (MPC), such as garbled circuits (GC) and homomorphic secret sharing (HSS).