Tight Time-Memory Trade-o ↵ s for Symmetric Encryption ‹
Tight Time-Memory Trade-o ↵ s for Symmetric Encryption ‹
复制标题
对称加密的严格时间内存权衡 ←
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Stefano Tessaro
中科院分区：
文献类型：
--
作者：
Joseph Jaeger;Stefano Tessaro
。具体的安全证明给出了攻击者优势的上限，作为其时间/查询复杂性的函数。然而，密码分析表明，其他资源限制（尤其是攻击者的记忆）可能会使可实现的优势变小，因此这些已证明的界限过于悲观。然而，处理内存限制已经避开了现有的安全证明。本文启动了基本对称密码学的时间-记忆权衡的研究。我们表明，随着攻击者内存的减少，诸如受生日界限影响的计数器模式加密等方案变得更加安全（就时间复杂度而言）。这项工作的一个关键步骤是切换引理的概括：对于具有 S 位内存的对手发出 q 个不同的查询，我们证明只要 S ^ q ！ 2 n 。这个结果假设了我们讨论的组合猜想，并且意味着立即对 CTR 和 OFB 加密的确定性、有状态版本进行权衡。我们还展示了基于安全 PRF 的随机 CTR 安全性的无条件时间记忆权衡。通过上述猜想，我们将结果扩展到假设 PRP，假设仅加密单块消息。我们的结果仅依赖于底层分组密码的标准 PRF/PRP 安全性。我们将证明的核心构建在一个可能具有独立兴趣的流算法的不可区分性的通用框架内。
. Concrete security proofs give upper bounds on the attacker’s advantage as a function of its time/query complexity. Cryptanalysis suggests however that other resource limitations – most notably, the attacker’s memory – could make the achievable advantage smaller, and thus these proven bounds too pessimistic. Yet, handling memory limitations has eluded existing security proofs. This paper initiates the study of time-memory trade-o ↵ s for basic symmetric cryptography. We show that schemes like counter-mode encryption, which are a ↵ ected by the Birthday Bound, become more secure (in terms of time complexity) as the attacker’s memory is reduced. One key step of this work is a generalization of the Switching Lemma: For adversaries with S bits of memory issuing q distinct queries, we prove an n -to- n bit random function indistinguishable from a permutation as long as S ˆ q ! 2 n . This result assumes a combinatorial conjecture, which we discuss, and implies right away trade-o ↵ s for deterministic, stateful versions of CTR and OFB encryption. We also show an unconditional time-memory trade-o ↵ for the security of randomized CTR based on a secure PRF. Via the aforementioned conjecture, we extend the result to assuming a PRP instead, assuming only one-block messages are encrypted. Our results solely rely on standard PRF/PRP security of an underlying block cipher. We frame the core of our proofs within a general framework of indistinguishability for streaming algorithms which may be of independent interest.
可证明的时间-内存权衡：对称密码学对抗内存有限的对手
DOI：
--
发表时间：
2018
期刊：
TCC 2018
影响因子：
--
作者：
Tessaro, Stefano;Thiruvengadam, Aishwarya
通讯作者：
Thiruvengadam, Aishwarya