Multi-party protocols, information complexity and privacy

DOI10.4230/LIPICS.MFCS.2016.57MaRDI QIDQ4608620zbMATH OpenOpenAlexFDO

Authors Iordanis Kerenidis, Adi Rosén, Florent Urrutia

Publication date 21 March 2018

Full work available at URL https://arxiv.org/abs/1606.06872

zbMATH Keywords

communication complexityinformation theorymulti-party private computation (MPC)multi-party protocolsrandomness

Mathematics Subject Classification ID

Network protocols (68M12) Data encryption (aspects in computer science) (68P25) Cryptography (94A60) Authentication, digital signatures and secret sharing (94A62)

Abstract: We introduce a new information theoretic measure that we call Public Information Complexity (PIC), as a tool for the study of multi-party computation protocols, and of quantities such as their communication complexity, or the amount of randomness they require in the context of information-theoretic private computations. We are able to use this measure directly in the natural asynchronous message-passing peer-to-peer model and show a number of interesting properties and applications of our new notion: the Public Information Complexity is a lower bound on the Communication Complexity and an upper bound on the Information Complexity; the difference between the Public Information Complexity and the Information Complexity provides a lower bound on the amount of randomness used in a protocol; any communication protocol can be compressed to its Public Information Cost; an explicit calculation of the zero-error Public Information Complexity of the $k$-party, $n$-bit Parity function, where a player outputs the bit-wise parity of the inputs. The latter result also establishes that the amount of randomness needed by a private protocol that computes this function is $Omega(n)$.

Recommendations

• Multi-Party Protocols, Information Complexity and Privacy
• Privacy and Communication Complexity
• scientific article; zbMATH DE number 1024014
• Randomness complexity of private computation
• Lower and upper bounds on the randomness complexity of private computations of AND

Cited in

(8)

• The complexity of multiparty PSM protocols and related models
• Public vs. private randomness in simultaneous multi-party communication complexity
• Multi-party PSM, revisited: improved communication and unbalanced communication
• scientific article; zbMATH DE number 1024014 (Why is no real title available?)
• scientific article; zbMATH DE number 7319029 (Why is no real title available?)
• scientific article; zbMATH DE number 7559107 (Why is no real title available?)
• Multi-Party Protocols, Information Complexity and Privacy
• Advances in Cryptology - EUROCRYPT 2004

This page was built for publication: Multi-party protocols, information complexity and privacy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4608620)