Paper 2026/925

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

Abstract

Random Vector Oblivious Linear Evaluation (VOLE) correlations are a widely used backend for zero-knowledge proofs and secure computation, and can now be generated with strong concrete efficiency. Many applications, however, need correlations on the receiver’s actual input. They therefore start from random VOLE and send a linear-size derandomization vector, which remains 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 \(\textsf{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_{\mathrm{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_{\mathrm{msg}}\) is the size of the shares. \(\textsf{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 \(\textsf{LogVole}\), we obtain the first concretely efficient VOLE-based ZK protocol with polylogarithmic communication for arbitrary circuits. At 128-bit computational and 40-bit statistical security, our implementation reaches 12.9 million \(\mathbb{Z}_p\) inputs/s, 9.0 million ZK multiplication gates/s on a 16-core machine, and proves \(1024 \times 1024\) matrix multiplication in about 4s with single-thread computation and 226 KB communication.