Paper 2026/925

LogVOLE: Succinct and Efficient Chosen-Input VOLE for ZK and Beyond

Abstract

Random Vector Oblivious Linear Evaluation (VOLE) correlations can be generated efficiently for zero-knowledge proofs and secure computation. Applications that need correlations on the receiver’s actual input typically derandomize random VOLE by sending a linear-size vector, a main communication bottleneck. We study chosen-input VOLE (CI-VOLE), where the receiver privately chooses a large vector \(\mathbf{x}\), the sender fixes \(\Delta\), and the parties obtain shares of \(\mathbf{x}\cdot\Delta\) without communicating a linear-size object. This work presents LogVOLE, a concretely efficient CI-VOLE protocol with polylogarithmic end-to-end communication under Ring-LWE. The construction uses a recursive shrink/expand design: it authenticates short digests of the chosen input and then uses a succinct telescope to expand those relations back to the full vector. The protocol has \(O(\lambda\log^2(|\mathbf{x}|+m_{\mathsf{msg}}))\) one-time setup and query communication and \(O(|\mathbf{x}|/n)\) ring operations. Here, \(n\) is the underlying ring degree, \(\lambda\) is the computational security parameter, and \(m_{\mathsf{msg}}\) is the size of the shares. LogVOLE also supports a public-key non-interactive mode: for a fixed \(\Delta\), the sender publishes reusable parameters, and a receiver sends one compact \(\mathbf{x}\)-dependent message to obtain the matching VOLE shares. This gives a route to non-interactive VOLE-based ZK with polylogarithmic communication for arbitrary circuits. We also give a malicious-security extension in the random oracle model. Using LogVOLE, we construct the first concretely efficient VOLE-based designated-verifier ZK protocol for arbitrary circuits with polylogarithmic communication. At 128-bit computational and 40-bit statistical security, our implementation achieves online throughput of 13.9 million \(\mathbb{Z}_p\) correlations/s and 12.9 million ZK multiplication gates/s using 16 CPU cores per party. With golden-seed optimization and reusable setup, our GPU implementation processes 532.3 million \(\mathbb{Z}_p\) correlations/s and 451.7 million ZK multiplication gates/s online on an H200 GPU. With one CPU thread per party, our implementation proves \(1024\times1024\) matrix multiplication in about 4 seconds online, with 226 kB of online communication.