How to fool an unbounded adversary with a short key
How to fool an unbounded adversary with a short key
复制标题
DOI：
10.1109/tit.2005.864438
复制
发表时间：
2006-03-01
影响因子：
2.5
通讯作者：
Wang, H
中科院分区：
文献类型：
--
作者：
Russell, A;Wang, H
当两个方必须安全地传输带有简短共享秘密密钥的消息m时，会与计算无限的对手一起考虑对称加密问题。由于对手是无限的，因此任何加密方案都必须泄漏有关M的信息；特别是，M及其密文之间的相互信息不能为零。尽管如此，提出了一个加密方案的家族，该家族保证在{0，1}（1}（n）中具有最小熵n -l的任何消息空间，对于任何布尔函数h：{0，1}（n） - > { 0，1}，没有对手可以从M的密文中预测H（M），其优势超过1/N（W（1））；这是用长度L + W（log n）的键来实现的。通常，长度为l + s的键在优势上产生2（-theta（s））的结合。这些加密方案不依赖未经证实的假设，并且可以有效地实施。讨论了基于复杂性理论假设的密码系统的应用，此外，还提供了Goldwasser和Micali的基本“ Elision Lemma”的简化证明。
The symmetric encryption problem which manifests itself when two parties must securely transmit a message m with a short shared secret key is considered in conjunction with a computationally unbounded adversary. As the adversary is unbounded, any encryption scheme must leak information about m; in particular, the mutual information between m and its ciphertext cannot be zero. Despite this, a family of encryption schemes is presented that guarantee that for any message space in {0, 1}(n) with minimum entropy n - l and for any Boolean function h : {0, 1}(n) -> {0, 1}, no adversary can predict h(m) from the ciphertext of m with more than 1/n(w(1)) advantage; this is achieved with keys of length l + w(log n). In general, keys of length l + s yield a bound of 2(-Theta(s)) on the advantage. These encryption schemes rely on no unproven assumptions and can be implemented efficiently. Applications of this to cryptosystems based on complexity-theoretic assumptions are discussed and, in addition, a simplified proof of a fundamental "elision lemma" of Goldwasser and Micali is provided.