Coded Computing for Secure Boolean Computations
Coded Computing for Secure Boolean Computations
复制标题
DOI：
10.1109/jsait.2021.3055341
复制
发表时间：
2021-03
期刊：
影响因子：
--
通讯作者：
Chien-Sheng Yang;A. Avestimehr
中科院分区：
文献类型：
--
作者：
Chien-Sheng Yang;A. Avestimehr
随着现代数据集规模的不断增长，需要将大规模计算拆分为较小的计算，并以分布式方式进行操作。分布式系统中的攻击者故意发送错误数据，以影响计算，从而为自己谋取利益。布尔函数是许多应用程序的关键组成部分，例如区块链系统中的验证函数和加密算法的设计。我们考虑在分布式计算系统中计算布尔函数的问题，特别关注对拜占庭工人的安全性。一般情况下，任何布尔函数都可以建模为一个高次的多元多项式。然而，最近提出的拉格朗日编码计算（LCC）提供的安全阈值（即，可以容忍的对抗性工作的最大数量，从而可以获得正确的结果）可以非常低，如果多项式的程度很高。我们提出了编码代数范式（ANF）、编码析取范式（DNF）和编码多项式阈值函数（PTF）三种不同的格式。所提出的方案的关键思想是将其建模为一些低次多项式和阈值函数的串联。在安全阈值方面，我们通过提供匹配的外边界证明了所提出的编码ANF和编码DNF是最优的。
The growing size of modern datasets necessitates splitting a large scale computation into smaller computations and operate in a distributed manner. Adversaries in a distributed system deliberately send erroneous data in order to affect the computation for their benefit. Boolean functions are the key components of many applications, e.g., verification functions in blockchain systems and design of cryptographic algorithms. We consider the problem of computing a Boolean function in a distributed computing system with particular focus on security against Byzantine workers. Any Boolean function can be modeled as a multivariate polynomial with high degree in general. However, the security threshold (i.e., the maximum number of adversarial workers can be tolerated such that the correct results can be obtained) provided by the recent proposed Lagrange Coded Computing (LCC) can be extremely low if the degree of the polynomial is high. We propose three different schemes called coded Algebraic normal form (ANF), coded Disjunctive normal form (DNF) and coded polynomial threshold function (PTF). The key idea of the proposed schemes is to model it as the concatenation of some low-degree polynomials and threshold functions. In terms of the security threshold, we show that the proposed coded ANF and coded DNF are optimal by providing a matching outer bound.