Cryptology ePrint Archive: Report 2016/093

Valiant's Universal Circuit is Practical

Ágnes Kiss and Thomas Schneider

Abstract: Universal circuits (UCs) can be programmed to evaluate any circuit of a given size $k$. They provide elegant solutions in various application scenarios, e.g. for private function evaluation (PFE) and for improving the flexibility of attribute-based encryption (ABE) schemes. The optimal size of a universal circuit is proven to be $\Omega(k\log k)$. Valiant (STOC'76) proposed a size-optimized UC construction, which has not been put in practice ever since. The only implementation of universal circuits was provided by Kolesnikov and Schneider (FC'08), with size $\mathcal{O}(k\log^2 k)$.

In this paper, we refine the size of Valiant's UC and further improve the construction by (at least) $2k$. We show that due to recent optimizations and our improvements, it is the best solution to apply in the case for circuits with a constant number of inputs and outputs. When the number of inputs or outputs is linear in the number of gates, we propose a more efficient hybrid solution based on the two existing constructions. We validate the practicality of Valiant's UC, by giving an example implementation for PFE using these size-optimized UCs.

Category / Keywords: cryptographic protocols / Universal circuit, size-optimization, private function evaluation

Original Publication (with minor differences): IACR-EUROCRYPT-2016

Date: received 2 Feb 2016, last revised 19 Feb 2016

Contact author: agnes kiss at crisp-da de

Available format(s): PDF | BibTeX Citation

Note: Number of copy gates revised in Tables 1 and 3

Version: 20160219:095026 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]