Paper 2017/798

More Efficient Universal Circuit Constructions

Daniel Günther, Ágnes Kiss, and Thomas Schneider

Abstract

A universal circuit (UC) can be programmed to simulate any circuit up to a given size $n$ by specifying its program bits. UCs have several applications, including private function evaluation (PFE). The asymptotical lower bound for the size of a UC is proven to be $\Omega(n\log n)$. In fact, Valiant (STOC'76) provided two theoretical UC constructions using so-called 2-way and 4-way constructions, with sizes $5n\log_2n$ and $4.75n\log_2n$, respectively. The 2-way UC has recently been brought into practice in concurrent and independent results by Kiss and Schneider (EUROCRYPT'16) and Lipmaa et al. (Eprint 2016/017). Moreover, the latter work generalized Valiant's construction to any $k$-way UC. In this paper, we revisit Valiant's UC constructions and the recent results, and provide a modular and generic embedding algorithm for any $k$-way UC. Furthermore, we discuss the possibility for a more efficient UC based on a 3-way recursive strategy. We show with a counterexample that even though it is a promising approach, the 3-way UC does not yield an asymptotically better result than the 4-way UC. We propose a hybrid approach that combines the 2-way with the 4-way UC in order to minimize the size of the resulting UC. We elaborate on the concrete size and depth of all discussed UC constructions and show that our hybrid UC yields on average 3.65% improvement in size over the 2-way UC. We implement the 4-way UC in a modular manner based on our proposed embedding algorithm, and show that our methods for programming the UC can be generalized for any $k$-way construction.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in ASIACRYPT 2017
Keywords
Universal circuitprivate function evaluationfunction hiding
Contact author(s)
agnes kiss @ crisp-da de
History
2017-08-25: received
Short URL
https://ia.cr/2017/798
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/798,
      author = {Daniel Günther and Ágnes Kiss and Thomas Schneider},
      title = {More Efficient Universal Circuit Constructions},
      howpublished = {Cryptology ePrint Archive, Paper 2017/798},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/798}},
      url = {https://eprint.iacr.org/2017/798}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.