We consider the problem of designing secure and private codes for distributed matrix-matrix multiplication. A master server owns two private matrices and hires worker nodes to help compute their product. The matrices should remain information-theoretically private from the workers. Some of the workers are malicious and return corrupted results to the master. We design a framework for security against malicious workers in private matrix-matrix multiplication. The main idea is a careful use of Freivalds' algorithm to detect erroneous matrix multiplications. Our main goal is to apply this security framework to schemes with adaptive rates. Adaptive schemes divide the workers into clusters and thus provide flexibility in trading decoding complexity for efficiency. Our new scheme, SRPM3, provides a computationally efficient security check per cluster that detects the presence of one or more malicious workers with high probability. An additional per worker check is used to identify the malicious nodes. SRPM3 can tolerate the presence of an arbitrary number of malicious workers. We provide theoretical guarantees on the complexity of the security checks and simulation results on both, the missed detection rate as well as on the time needed for the integrity check.
翻译:我们考虑为分布式矩阵矩阵乘法设计安全和私人代码的问题。主服务器拥有两个私人矩阵,并雇用工人节点帮助计算其产品。矩阵应该保持对工人的信息-理论私密性。有些工人恶意并将腐败的结果归还给主机。我们设计了一个框架,防止恶意工人在私人矩阵矩阵矩阵乘法中出现危险。我们的主要想法是谨慎地使用Freivalds的算法来检测错误的矩阵乘法。我们的主要目标是将这一安全框架应用于适应率计划。适应性计划将工人分为一组,从而在效率交易解码复杂性方面提供灵活性。我们的新计划SRPM3提供了每组检测一个或多个恶意工人存在的可能性很高的计算高效的安全检查。每组检查一次工人就用来识别恶意节点。SRPM3可以容忍任意存在的恶意工人数量。我们从理论上保证安全检查和模拟结果的复杂性,两者的检测率缺失以及完整性检查所需的时间。