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 IntersectionSize HidingBounded InputCryptographic AccumulatorsSDH 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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2016/657}},
      url = {https://eprint.iacr.org/2016/657}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.