International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Thomas Schneider

Publications

Year
Venue
Title
2020
JOFC
Efficient and Scalable Universal Circuits
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)$$ Ω ( 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 $${\sim }\,5n\log _2n$$ ∼ 5 n log 2 n and $${\sim }\,4.75n\log _2n$$ ∼ 4.75 n log 2 n , 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 implementation. 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)$$ 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. Both algorithms use only $${\mathcal {O}}(n)$$ 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. (ASIACRYPT’19) that reduces the asymptotic size of the 4-way UC to  $${\sim }\,4.5n\log _2n$$ ∼ 4.5 n log 2 n . Furthermore, we include their optimization in the implementation of our 2/4-hybrid UC which yields the smallest UC construction known so far.
2019
EUROCRYPT
Efficient Circuit-Based PSI with Linear Communication 📺
We present a new protocol for computing a circuit which implements the private set intersection functionality (PSI). Using circuits for this task is advantageous over the usage of specific protocols for PSI, since many applications of PSI do not need to compute the intersection itself but rather functions based on the items in the intersection.Our protocol is the first circuit-based PSI protocol to achieve linear communication complexity. It is also concretely more efficient than all previous circuit-based PSI protocols. For example, for sets of size $$2^{20}$$ it improves the communication of the recent work of Pinkas et al. (EUROCRYPT’18) by more than 10 times, and improves the run time by a factor of 2.8x in the LAN setting, and by a factor of 5.8x in the WAN setting.Our protocol is based on the usage of a protocol for computing oblivious programmable pseudo-random functions (OPPRF), and more specifically on our technique to amortize the cost of batching together multiple invocations of OPPRF.
2018
EUROCRYPT
2017
ASIACRYPT
2017
JOFC
2016
EUROCRYPT
2015
EUROCRYPT
2015
EUROCRYPT
2010
CHES
2009
ASIACRYPT

Program Committees

Eurocrypt 2018
Eurocrypt 2016