The Communication Complexity of Private Simultaneous Messages, Revisited
The Communication Complexity of Private Simultaneous Messages, Revisited
复制标题
重新审视私人同步消息的通信复杂性
作者：
Benny Applebaum;Thomas Holenstein;M. Mishra;O. Shayevitz
私人同时消息(PSM)协议是由Feige，Kilian和Naor(STOEC‘94)提出的用于信息论三方安全计算的最小非交互模型。虽然已知每个函数f：{0，1}k×{0，1}k→{0，1}documentclass[12pt]{minimal}的usepackage{amsath}usepackage{wa ysym}usepackage{amsFonts}usepackage{amsbsy}usepackage{mathsfs}usepackage{upgreek}setlong{oddsidemargin}{-69pt}例如{Document}$$f：{0，1}^k imes{0，1}^k
Ightarrow{0，1}$$end{Document}允许2k/2Documentclass[12pt]{Minimum}usepackage{amsath}usepackage{wa ysym}usepackage{amsfonts}usepackage{amssymb}usepackage{amsbsy}usepackage{mathsfs}usepackage{upgreek}setlong{oddsidemargin}{-69pt}例如{Document}$2^{k/2}$$end{Document}(Beimel等人，TCC‘14)，最已知的(非显式)下限是3k-O(1)Documentclass[12pt]{Minimum}usepackage{amsath}usepackage{wa ysym}usepackage{amsfonts}usepackage{amsbsy}usepackage{mathsfs}usepackage{upgreek}setlong{oddsidemargin}{-69pt}，例如在{Document}$$3k-O(1)$end{Document}bit中。为了证明这一下限，FKN确定了一组简单的要求，证明了满足这些要求的任何函数都符合3k-O(1)Documentclass[12pt]{Minimum}usepackage{amsath}usepackage{wa ysym}usepackage{amssymb}usepackage{amsbsy}usepackage{amsbsy}usepackage{upgreek}setlong{oddsidemargin}{-69pt}，例如{Document}$3k-O(1)$end{Document}下界，并证明了随机函数很可能满足这些要求。我们重新考察了FKN的下界，并证明了以下结果：(反例)我们构造了一个满足FKN要求的函数，但是它有一个PSM协议，其通信为2k+O(1)DocentClass[12pt]{Minimum}usepackage{amsath}usepackage{wa ysym}usepackage{amsfonts}usepackage{amssymb}usepackage{amsbsy}usepackage{matrsfs}usepackage{upgreek}setlong{oddsidemarin}{-69pt}例如in{Document}$2k+O(1)$end{Document}bit，揭示了FKN证明中的一个缺口。(PSM下界)我们证明了，通过施加额外的要求，FKN参数可以被修复，从而导致3k-O(Logk)Documentclass[12pt]{Minimum}usepackage{amsath}usepackage{wa ysym}usepackage{amssymb}usepackage{amsbsy}usepackage{amsbsy}usepackage{upgreek}setlong{oddsidemargin}{-69pt}，例如in{Document}$$3k-O(Logk)$end{Document}。我们还得到了可以由多项式大小的电路(甚至在标准复杂性理论假设下的多项式时间图灵机)计算的函数的类似下界。这产生了显式布尔函数的第一个非平凡的下界，部分地解决了数据的公开问题Prabhakaran和Prabhakaran(Crypto‘14，IEEE信息理论’16)。我们进一步将这些结果推广到可能存在微小正确性或隐私错误的不完美PSM协议的设置。(CDS下界)我们证明了原始的FKN论据适用于某些弱形式的PSM协议，这些协议与有条件的秘密公开(CDS)设置密切相关。这种连接产生了用于建立线性Ω(K)文档类[12pt]{Minimum}usepackage{amsath}usepackage{amsFonts}usepackage{amssymb}usepackage{amsbsy}usepackage{matrsfs}usepackage{upgreek}setlong{oddsidemargin}{-69pt}例如{Document}$$varOmega(K)$End{Document}位CDS下界的简单组合准则。作为推论，我们解决了内积谓词解决Gay，Kerenidis和Wee(Crypto‘15)的一个公开问题的复杂性。
Private simultaneous message (PSM) protocols were introduced by Feige, Kilian, and Naor (STOC ’94) as a minimal non-interactive model for information theoretic three-party secure computation. While it is known that every function f:{0,1}k×{0,1}k→{0,1}documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$f:{0,1}^k imes {0,1}^k
ightarrow {0,1}$$end{document} admits a PSM protocol with exponential communication of 2k/2documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$2^{k/2}$$end{document} (Beimel et al., TCC ’14), the best known (non-explicit) lower-bound is 3k-O(1)documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$3k-O(1)$$end{document} bits. To prove this lower-bound, FKN identified a set of simple requirements, showed that any function that satisfies these requirements is subject to the 3k-O(1)documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$3k-O(1)$$end{document} lower-bound, and proved that a random function is likely to satisfy the requirements. We revisit the FKN lower-bound and prove the following results: (Counterexample) We construct a function that satisfies the FKN requirements but has a PSM protocol with communication of 2k+O(1)documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$2k+O(1)$$end{document} bits, revealing a gap in the FKN proof. (PSM lower-bounds) We show that by imposing additional requirements, the FKN argument can be fixed leading to a 3k-O(logk)documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$3k-O(log k)$$end{document} lower-bound for a random function. We also get a similar lower-bound for a function that can be computed by a polynomial-size circuit (or even polynomial-time Turing machine under standard complexity-theoretic assumptions). This yields the first non-trivial lower-bound for an explicit Boolean function partially resolving an open problem of Data, Prabhakaran, and Prabhakaran (Crypto ’14, IEEE Information Theory ’16). We further extend these results to the setting of imperfect PSM protocols which may have small correctness or privacy error. (CDS lower-bounds) We show that the original FKN argument applies (as is) to some weak form of PSM protocols which are strongly related to the setting of Conditional Disclosure of Secrets (CDS). This connection yields a simple combinatorial criterion for establishing linear Ω(k)documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$varOmega (k)$$end{document}-bit CDS lower-bounds. As a corollary, we settle the complexity of the inner-product predicate resolving an open problem of Gay, Kerenidis, and Wee (Crypto ’15).