单个置换构建的超越生日安全域保全伪随机函数

194 浏览量更新于2024-07-15 收藏 638KB PDF 举报

"Beyond-birthday secure domain-preserving PRFs from a single permutation" 本文主要探讨了如何从伪随机置换（PRPs）构建伪随机函数（PRFs）这一基础的密码学问题。作者证明了SUMPIP（即P⊕P^(-1)，一个PRP与其逆的异或）以及EDMDSP（Mennink和Neves在CRYPTO 2017中提出的Encrypted Davies-Meyer方案的“对偶”的单置换变体）在最多2^(2n/3)/n次敌手查询下是安全的PRFs。据作者所知，SUMPIP是首个并行化、基于单个置换、保持域且超越生日安全界限的PRP到PRF转换方法。关键词包括PRP-to-PRF（从PRP到PRF的转换）、Beyond birthday bound（超越生日边界）和Domain preserving（域保持）。数学分类涉及94A60（密码学）和68P25（信息处理的理论）。在密码学中，PRFs和PRPs是核心组件，广泛用于加密和认证协议。PRFs具有与真正随机函数相同的不可预测性，而PRPs则具有可逆的特性，可用于构造如AES等块密码。通常，构建PRFs的方法是从PRPs扩展而来，因为PRPs的安全性已经得到了很好的理解。 SUMPIP和EDMDSP的提出是PRP到PRF转换领域的创新。SUMPIP的独特之处在于它仅使用一个置换，同时保持了域的不变性，这意味着输入空间的大小在转换过程中不会改变。此外，其并行化能力使得在多处理器系统中的计算效率得以提高。而EDMDSP则是基于Davies-Meyer构造的“对偶”，这个构造通常用于构造流密码和哈希函数。超越生日边界的安全性是指，攻击者在进行超过一定数量的查询后，其成功概率才会显著增加。在传统的生日攻击中，攻击者在大约平方根级别的查询后可能找到两个输入的碰撞。而这里提出的方案能够在超过这个界限的情况下仍保持安全性，这在实际应用中是非常重要的，因为它增加了攻击的难度。该研究对于理解和设计高效且安全的密码学构造有深远的影响，特别是在资源有限的环境或者需要高并发查询处理的场景下。这样的进展有助于推动密码学理论的发展，同时对实际应用中的加密算法设计提供了新的思路。

Beyond-birthday secure domain-preserving PRFs 1301

20 25 30 35 40 45 50

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

Birthday Bound

EDMSP[15]

SUMPIP

EDMDSP

Fig. 2 Comparing the bounds: n = 64

55 60 65 70 75 80 85

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

Birthday Bound

EDMSP[15]

SUMPIP

EDMDSP

Fig. 3 Comparing the bounds: n = 128

1.5 Organization

In Sect. 2 we establish conventions, provide deﬁnitions, and present an introduction to the

sum-capture theorem. Next, in Sects. 3 and 4, we give the security proofs for SUMPIP and

EDMDSP respectively. Section 5 concludes the paper and discusses open problems. Finally,

our alternative proof for EDMSP is given in Appendix A.

2 Preliminary

2.1 Notations

For integers 1 ≤ b ≤ a, we write (a)

= a(a −1)...(a −b +1) and (a)

= 1 by convention.

For a ﬁnite set

X , X

←− X denotes selecting an element from X uniformly at random and

123

1302 C. Guo et al.

|X | denotes its cardinality. Throughout this paper, we ﬁx an integer n as the input bit size of

permutations, and denote by N = 2

2.2 PRF security

We denote by F(n) the set of all n-to-n-bit functions, and by P(n) the set of all n-bit per-

mutations. Let C

∈ F(n) be a function built upon an n-bit permutation P. Then, for any

distinguisher D, its advantage of breaking the prf-security of C

is deﬁned as

Adv

prf

(A) =





←− P(n) : D

= 1



− Pr



←− F(n) : D

= 1





This deﬁnition focuses on the information-theoretic setting, in which the permutation P

underlying C

is regarded as secret and random. We note such results can be easily general-

ized to the complexity-theoretic setting, where the permutation P is instantiated as E

for a

blockcipher E under a secret key k uniformly selected from the key space, with an additional

loss of Adv

prp

, i.e., the prp security bound of the blockcipher E.

2.3 The H-coefficients technique

We give here all the necessary background on the H-coefﬁcient technique [10,35]. The proof

paradigm used in this paper resembles that of Chen and Steinberger [10].

Transcript We summarize the interaction of D with its oracles in what we call the queries

transcript τ of the attack. More precisely, τ contains all pairs (x, z) ∈{0, 1}

×{0, 1}

such

that D makes a query x to the function oracle a nd receives a response z. We sometimes also

call such pairs “queries” for simplicity. Note that queries are recorded in an unordered fashion.

Since we always assume D is computationally unbounded and hence deterministic

,thereis

a one-to-one mapping between this representation and the raw transcript of the interaction

of D with its oracles.

With respect to some ﬁxed distinguisher D, a queries transcript is attainable, if it indeed

can be obtained in the “ideal” world, i.e. there exists a random function F such that the

interaction of D with F yields this transcript. We denote by

T the set of attainable transcripts.

In all the following, we denote T

,resp.T

, the probability distribution of the transcript τ

induced by the real world, resp. the ideal world (note that these two probability distributions

depend on the distinguisher).

The Main Lemma The approach to upper bounding the advantage of the distinguisher is

as follows: we will partition the set of attainable transcripts

T into two disjoint subsets T

good

and T

bad

,andT = T

good

∪ T

bad

. T

good

is a set of “good” ones such that the probabilities to

obtain transcripts in

good

are close in the real and in the ideal world. T

bad

is a set of “bad”

transcripts such that the probability to obtain any τ ∈

bad

is small in the ideal world. More

precisely, we will use the following lemma from [11].

Lemma 1 Fix a distinguisher D. Let

T = T

good

∪T

bad

be a partition of the set of attainable

transcripts. Assume that there exists ε

and ε

such that:

(i) Pr[T

∈ T

bad

]≤ε

, and

(ii) for any τ ∈

good

, one has

Probabilistic distinguishers can be derandomized with the optimal random coins.

123

剩余25页未读，继续阅读

weixin_38628362

粉丝: 6
资源: 899

单个置换构建的超越生日安全域保全伪随机函数

从标准假设中保留属性的哈希函数_Property-Preserving Hash Functions from Standard

An efficient multi-party scheme for privacy preserving collaborative

Fast algorithms for hiding sensitive high-utility itemsets in privacy-preserving utility mining

high-resolution u-net: preserving image details for cultivated land extracti

A secure and privacy-preserving mobile wallet with outsourced verification in cloud computing

A blockchain-based location privacy-preserving crowdsensing system

-wangyingwwyy-Privacy-Preserving-Federated-Learning-I:我的“最后一年”项目的源代码-隐私保护联合学习（I）

Privacy-Preserving Optimization of Cross-Domain Firewalls with Dynamic Rule Updates

Block Cipher Modes of Operation-Methods for Format-Preserving Encryption.pdf

Low-Cost and Confidentiality-Preserving Data Acquisition for Internet of Multimedia Things

最新资源