Secure and scalable match: overcoming the universal circuit bottleneck using group programs
Authors: Rajesh Krishnan (Cosocket LLC), Ravi Sundaram (Northeastern University)
Volume: 2015
Issue: 2
Pages: 244–262
DOI: https://doi.org/10.1515/popets-2015-0013
Abstract: Confidential Content-Based Publish/Subscribe (C-CBPS) is an interaction model that allows parties to exchange content while protecting their security and privacy interests. In this paper we advance the state of the art in C-CBPS by showing how all predicate circuits in NC1 (logarithmic-depth, bounded fan-in) can be confidentially computed by a broker while guaranteeing perfect information-theoretic security. Previous work could handle only strictly shalp lower circuits (e.g. those with depth O( log2 n)). We present three protocols—UGP-Match, FSGP-Match and OFSGP-Match—based on 2-decomposable randomized encodings of group programs for circuits in NC1 . UGP-Match is conceptually simple and has a clean proof of correctness but its running time is a polynomial with a high exponent and hence impractical. FSGP-Match uses a “fixed structure” construction that reduces the exponent drastically and achieves efficiency and scalability. OFSGP-Match optimizes the group programs further to shave off a linear factor.
Keywords: secure computation, publish-subscribe, universal circuit, group program, randomized encoding
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 license.
