Polynomial Runtime and Composability
Polynomial Runtime and Composability
复制标题
多项式运行时和可组合性
作者：
D. Hofheinz;Dominique Unruh;J. Müller
提出了一种适用于基于仿真的多方密码协议安全性分析的多项式运行时的概念。有些令人惊讶的是，多项式运行时的简单概念缺乏反应性任务的表现力和/或导致了不自然的基于模拟的安全概念。事实上，这个问题在以前的工作中已经被认识到了，并且已经提出了几个多项式运行时的概念。然而，我们的新概念被称为反应多项式时间，它是第一个结合了以下性质的概念：它足够简单，足以支持简单的安全/运行时分析；它是直观的，因为所有直觉上可行的协议和攻击(并且只有那些)都被认为是多项式时间；它在通用合成定理的意义上支持协议的安全合成。我们在通用可组合性(UC)协议框架中工作。我们注意到，虽然UC框架已经具有普遍的合成定理，但我们开发了新的技术来证明在反应性多项式时间协议和攻击的情况下的安全合成。
We devise a notion of polynomial runtime suitable for the simulation-based security analysis of multi-party cryptographic protocols. Somewhat surprisingly, straightforward notions of polynomial runtime lack expressivity for reactive tasks and/or lead to an unnatural simulation-based security notion. Indeed, the problem has been recognized in previous works, and several notions of polynomial runtime have already been proposed. However, our new notion, dubbed reactive polynomial time, is the first to combine the following properties: it is simple enough to support simple security/runtime analyses,it is intuitive in the sense that all intuitively feasible protocols and attacks (and only those) are considered polynomial-time,it supports secure composition of protocols in the sense of a universal composition theorem. We work in the Universal Composability (UC) protocol framework. We remark that while the UC framework already features a universal composition theorem, we develop new techniques to prove secure composition in the case of reactively polynomial-time protocols and attacks.