Paper 2019/348

Efficient and Scalable Universal Circuits

Masaud Y. Alhassan, 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 inputs. It provides elegant solutions in various application scenarios, e.g., for private function evaluation (PFE) and for improving the flexibility of attribute-based encryption schemes. The asymptotic lower bound for the size of a UC is $\Omega(n \log n)$ and Valiant (STOC'76) provided two theoretical constructions, the so-called 2-way and 4-way UCs (i.e., recursive constructions with 2 and 4 substructures), with asymptotic sizes $5n \log_2n$ and $4.75n \log_2n$, respectively. In this article, we present and extend our results published in (Kiss and Schneider, EUROCRYPT'16) and (Günther et al., ASIACRYPT'17). We validate the practicality of Valiant's UCs, by realizing the 2-way and 4-way UCs in our modular open-source implementations. We also provide an example implementation for PFE using these size-optimized UCs. We propose a 2/4-hybrid approach that combines the 2-way and the 4-way UCs in order to minimize the size of the resulting UC. We realize that the bottleneck in universal circuit generation and programming becomes the memory consumption of the program since the whole structure of size $\mathcal{O}(n \log n)$ is handled by the algorithms in memory. In this work, we overcome this by designing novel scalable algorithms for the UC generation and programming. We show that the generation, which involves topological ordering of the UC as well, can be designed to be performed block by block from top to bottom, while the programming can be performed subcircuit by subcircuit. Both algorithms use only $\mathcal{O}(n)$ memory at any point in time. We prove the practicality of our scalable design with a scalable proof-of-concept implementation for generating Valiant's 4-way UC. We note that this can be extended to work with optimized building blocks analogously. Moreover, we substantially improve the size of our UCs by including and implementing the recent optimization of Zhao et al. (ePrint 2018/943) that reduces the asymptotic size of the 4-way UC to $4.5n\log_2n$. Furthermore, we include their optimization in the implementation of our 2/4-hybrid UC which yields the smallest UC construction known so far.

Note: grammar corrections

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published by the IACR in JOC 2020
Keywords
Universal circuitprivate function evaluationfunction hidingscalability
Contact author(s)
kiss @ encrypto cs tu-darmstadt de
History
2020-04-20: last of 3 revisions
2019-04-03: received
See all versions
Short URL
https://ia.cr/2019/348
License
Creative Commons Attribution
CC BY

BibTeX

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