Cryptology ePrint Archive: Report 2016/657

Bounded Size-Hiding Private Set Intersection

Tatiana Bradley and Sky Faber and Gene Tsudik

Abstract: Private Set Intersection (PSI) and other private set operations have many current and emerging applications. Numerous PSI techniques have been proposed that vary widely in terms of underlying cryptographic primitives, security assumptions as well as complexity. One recent strand of PSI-related research focused on an additional privacy property of hiding participants’ input sizes. Despite some interesting results, only one (comparatively) practical size-hiding PSI (SH-PSI) has been demonstrated thus far [1]. One legitimate general criticism of size-hiding private set intersection is that the party that hides its input size can attempt to enumerate the entire (and possibly limited) domain of set elements, thus learning the other party’s entire input set. Although this “attack” goes beyond the honest-but-curious model, it motivates investigation of techniques that simultaneously hide and limit a participant’s input size. To this end, this paper explores the design of bounded size-hiding PSI techniques that allow one party to hide the size of its input while allowing the other party to limit that size. Its main contribution is a reasonably efficient (quasi-quadratic in input size) bSH-PSI protocol based on bounded keyed accumulators. This paper also studies the relationships between several flavors of the “Strong Diffie-Hellman” (SDH) problem.

Category / Keywords: cryptographic protocols / Private Set Intersection,Size Hiding,Bounded Input,Cryptographic Accumulators, SDH Problem

Original Publication (with minor differences): Security and Cryptography for Networks 2016

Date: received 27 Jun 2016, last revised 27 Jun 2016

Contact author: fabers at uci edu

Available format(s): PDF | BibTeX Citation

Note: Fixed reference numbering and other typos.

Version: 20160628:032338 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]