Parallel Reducibility for Information-Theoretically Secure Computation
Parallel Reducibility for Information-Theoretically Secure Computation
复制标题
信息理论上安全计算的并行可归约性
DOI：
10.1007/3-540-44598-6_5
复制
发表时间：
2000
影响因子：
5
通讯作者：
S. Micali
中科院分区：
文献类型：
--
作者：
Y. Dodis;S. Micali
安全功能评估(SFE)协议的设计非常困难，简约性被认为是SFE协议的一个非常理想的性质。非正式地说，可缩减性(有时称为模块化组合)是将复杂的SFE协议设计分解成几个更简单的、单独安全的组件的自动能力。尽管做了很多努力，但只有最基本的可降解性类型，顺序可降解性(一次只能运行一个子协议)已经被考虑并被证明适用于特定类别的SFE协议。不幸的是，顺序可约性不允许节省轮次(通常是分布式环境中最昂贵的资源)，并且实现更一般的概念并不容易(确实，某些SFE概念可以被证明享有顺序可约性，但不能享受更一般的概念)。
在本文中，对于信息论SFE协议，我们形式化了并行可归约的概念，其中子协议可以同时运行；·阐明了并行可归约有两种不同的形式：*并发可归约，它适用于子协议调用的顺序不重要的情况(与顺序可归约相比，它显著降低了轮次复杂性)；以及*同步可归约，它适用于子协议必须同时执行时(并且它允许在顺序可归约甚至不适用的情况下进行模块化设计)。·证明一大类超临界流体萃取协议(即，满足Micali和Rogaway原始定义的略微修改的协议)可证明享有(两种形式的)平行可降解性。
Secure Function Evaluation (SFE) protocols are very hard to design, and reducibility has been recognized as a highly desirable property of SFE protocols. Informally speaking, reducibility (sometimes called modular composition) is the automatic ability to break up the design of complex SFE protocols into several simpler, individually secure components. Despite much effort, only the most basic type of reducibility, sequential reducibility (where only a single sub-protocol can be run at a time), has been considered and proven to hold for a specific class of SFE protocols. Unfortunately, sequential reducibility does not allow one to save on the number of rounds (often the most expensive resource in a distributed setting), and achieving more general notions is not easy (indeed, certain SFE notions provably enjoy sequential reducibility, but fail to enjoy more general ones).
In this paper, for information-theoretic SFE protocols, we • Formalize the notion of parallel reducibility, where sub-protocols can be run at the same time; • Clarify that there are two distinct forms of parallel reducibility: * Concurrent reducibility, which applies when the order of the sub-protocol calls is not important (and which reduces the round complexity dramatically as compared to sequential reducibility); and * Synchronous reducibility, which applies when the sub-protocols must be executed simultaneously (and which allows modular design in settings where sequential reducibility does not even apply). • Show that a large class of SFE protocols (i.e., those satisfying a slight modification of the original definition of Micali and Rogaway) provably enjoy (both forms of) parallel reducibility.