Valiant's Universal Circuit is Practical

Ágnes Kiss; Thomas Schneider

Paper 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 $Ω (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 $O (k \log^{2} k)$ . In this paper, we refine the size of Valiant's UC and further improve the construction by (at least) . 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.

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

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: A minor revision of an IACR publication in EUROCRYPT 2016
Keywords: Universal circuit size-optimization private function evaluation
Contact author(s): agnes kiss @ crisp-da de
History: 2016-02-19: last of 3 revisions; 2016-02-02: received; See all versions
Short URL: https://ia.cr/2016/093
License: CC BY

BibTeX

@misc{cryptoeprint:2016/093,
      author = {Ágnes Kiss and Thomas Schneider},
      title = {Valiant's Universal Circuit is Practical},
      howpublished = {Cryptology {ePrint} Archive, Paper 2016/093},
      year = {2016},
      url = {https://eprint.iacr.org/2016/093}
}