Unconditionally secure disjointness tests for private datasets (Q1017546)

From MaRDI portal
Revision as of 11:00, 30 July 2024 by Openalex240730090724 (talk | contribs) (Set OpenAlex properties.)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
Unconditionally secure disjointness tests for private datasets
scientific article

    Statements

    Unconditionally secure disjointness tests for private datasets (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    12 May 2009
    0 references
    Summary: We present two unconditional secure protocols for private set disjointness tests. In order to provide intuition of our protocols, we give a naive example that applies Sylvester matrices. Unfortunately, this simple construction is insecure as it reveals information about the intersection cardinality. More specifically, it discloses its lower bound. By using the Lagrange interpolation, we provide a protocol for the honest-but-curious case without revealing any additional information. Finally, we describe a protocol that is secure against malicious adversaries. In this protocol, a verification test is applied to detect misbehaving participants. Both protocols require \(O(1)\) rounds of communication. Our protocols are more efficient than the previous protocols in terms of communication and computation overhead. Unlike previous protocols whose security relies on computational assumptions, our protocols provide information theoretic security. To our knowledge, our protocols are the first ones that have been designed without a generic secure function evaluation. More important, they are the most efficient protocols for private disjointness tests in the malicious adversary case.
    0 references
    private matching
    0 references
    private set disjointness
    0 references
    secret sharing
    0 references
    secure multiparty computation
    0 references
    information theoretic security
    0 references
    cryptography
    0 references
    unconditional secure protocols
    0 references
    honest-but-curious
    0 references
    malicious adversaries
    0 references

    Identifiers