The Mix-and-Cut Shuffle: Small-Domain Encryption Secure against N Queries
The Mix-and-Cut Shuffle: Small-Domain Encryption Secure against N Queries
复制标题
Mix-and-Cut Shuffle：针对 N 查询的小域加密
DOI：
10.1007/978-3-642-40041-4_22
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Scott Yilek
中科院分区：
文献类型：
--
作者：
Thomas Ristenpart;Scott Yilek
我们提供了一种新的混洗算法，称为 Mix-and-Cut，即使对手可以观察到所有 N = 2 n 域点的加密，它也可以提供可证明安全的分组密码。这种完全安全的密码对于保留格式的加密非常有用，其中小域（例如，n = 30）很常见，并且数据库很可能包含几乎所有密文的示例。 Mix-and-Cut 源自一个通用框架，用于从完全安全的伪随机分隔符 (PRS) 构建完全安全的伪随机排列 (PRP)。后者是我们第一次处理的新原语。我们的框架受到 Granboulin 和 Pornin 的特定密码的启发，并使用了其中的想法。为了使用该框架实现混合和剪切的完全安全性，我们给出了一个简单的证明，证明对 (1 − e)N 查询安全的 PRP（最近由 Hoang、Morris 和 Rogaway 的交换或不交换密码有效实现）会产生对 N 查询安全的 PRS。
We provide a new shuffling algorithm, called Mix-and-Cut, that provides a provably-secure block cipher even for adversaries that can observe the encryption of all N = 2 n domain points. Such fully secure ciphers are useful for format-preserving encryption, where small domains (e.g., n = 30) are common and databases may well include examples of almost all ciphertexts. Mix-and-Cut derives from a general framework for building fully secure pseudorandom permutations (PRPs) from fully secure pseudorandom separators (PRSs). The latter is a new primitive that we treat for the first time. Our framework was inspired by, and uses ideas from, a particular cipher due to Granboulin and Pornin. To achieve full security for Mix-and-Cut using this framework, we give a simple proof that a PRP secure for (1 − e)N queries (recently achieved efficiently by Hoang, Morris, and Rogaway’s Swap-or-Not cipher) yields a PRS secure for N queries.