Bounded Size-Hiding Private Set Intersection

Tatiana Bradley; Sky Faber; Gene Tsudik

Paper 2016/657

Bounded Size-Hiding Private Set Intersection

Tatiana Bradley, 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.

Note: Fixed reference numbering and other typos.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. Minor revision. Security and Cryptography for Networks 2016
Keywords: Private Set Intersection Size Hiding Bounded Input Cryptographic Accumulators SDH Problem
Contact author(s): fabers @ uci edu
History: 2016-06-28: revised; 2016-06-28: received; See all versions
Short URL: https://ia.cr/2016/657
License: CC BY

BibTeX

@misc{cryptoeprint:2016/657,
      author = {Tatiana Bradley and Sky Faber and Gene Tsudik},
      title = {Bounded Size-Hiding Private Set Intersection},
      howpublished = {Cryptology {ePrint} Archive, Paper 2016/657},
      year = {2016},
      url = {https://eprint.iacr.org/2016/657}
}