密码学盛会：2008 CRYPTO资源分享

需积分: 11 172 浏览量更新于2024-08-02 收藏 9.27MB PDF 举报

"该资源是2008年密码学界的重要会议——CRYPTO的清晰版，对于密码学的研究者和爱好者来说具有很高的价值。数缘社区是一个专注于数学和密码学的在线平台，由山东大学数学院研究生创建，提供丰富的数学电子书、密码学论文、综合讨论区以及实用的网页公式编辑器等功能。社区内有专门的论文库，收录了包括Eurocrypt、Crypto、Asiacrypt等国际知名会议的大量论文，方便用户查找和学习。此外，论坛还设有密码学与网络安全版块，汇聚了一群在该领域有深厚背景的学者和学生，共同探讨相关话题。" 详细知识点解释: 1. **密码学(Cryptography)**: 密码学是一门研究信息安全的学科，涉及到加密、解密、认证、数据完整性以及隐私保护等多个方面。CRYPTO是全球顶尖的密码学会议之一，每年吸引众多学者分享最新的研究成果。 2. **CRYPTO会议**: CRYPTO是国际密码学界最重要的年度会议之一，始于1981年，由国际密码学会(IACR)主办，旨在推动密码学理论和技术的发展。2008年的CRYPTO会议包含的论文和研讨主题可能涵盖了当时最前沿的加密算法、安全协议、量子密码学等内容。 3. **数缘社区(MathMagic CN)**: 数缘社区是一个集数学和密码学为一体的学术交流平台，它提供的资源和服务包括电子书库、论文库、讨论区等，为学习者提供了丰富的学习材料和互动环境。 4. **密码学论文库**: 社区的密码学论文库收集了大量的国内外知名会议论文，如Eurocrypt、Crypto、Asiacrypt等，这些会议是密码学领域的顶级盛会，其论文反映了当前的研究热点和最新进展。 5. **欧密会(Eurocrypt)、美密会(Crypto)、亚密会(Asiacrypt)**: 这三大会议是国际密码学界最重要的学术会议，分别在欧洲、美洲和亚洲举行，对密码学的发展起到了关键推动作用。 6. **信息安全专业**: 提到了山东大学数学院的信息安全专业，该专业涵盖了密码理论、密码技术和网络安全技术三个方向，显示了在教育和研究方面的深度。 7. **网页公式编辑器**: 社区提供的Latex公式编辑器，方便用户在论坛上以图片形式发布数学公式，提高了在线讨论的便利性和专业性。 8. **讨论区**: 数学综合讨论区和密码学与网络安全版块，为用户提供了一个交流思想、提问和解答问题的场所，促进了学术交流和知识共享。 9. **资源目录**: 社区提供电子书库的目录链接，方便用户查找特定的数学书籍，进一步扩展了学习资源。通过这个资源，用户不仅可以了解到密码学的最新动态，还可以深入学习密码学和数学的相关知识，同时在专业论坛中与其他学者互动，提升自己的研究能力。

4 J.-S. Coron, J. Patarin, and Y. Seurin

pseudo-random functions [17], is proven under the classical indistinguishability

notion. Under this notion, the adversary has only access to the input/output of

the Luby-Rackoﬀ (LR) construction, and tries to distinguish it from a random

permutation; in particular it does not have access to the input/output of the in-

ner pseudo-random functions. On the contrary, in our setting, the distinguisher

can make oracle calls to the inner round functions F

’s (see Fig. 2); the indif-

ferentiability notion enables to accommodate these additional oracle calls in a

coherent deﬁnition.

1.1 Related Work

One of the ﬁrst paper to consider having access to the inner round functions

of a Luby-Rackoﬀ is [20]; the authors showed that Luby-Rackoﬀ with 4 rounds

remains secure if adversary has oracle access to the middle two round functions,

but becomes insecure if adversary is allowed access to any other round functions.

In [15] a random permutation oracle was instantiated for a speciﬁc scheme using

a 4-rounds Luby-Rackoﬀ. More precisely, the authors showed that the random

permutation oracle P in the Even-Mansour [14] block-cipher E

(m)=k

⊕

P (m ⊕ k

) can be replaced by a 4-rounds Luby-Rackoﬀ, and the block-cipher E

remains secure in the random oracle model; for this speciﬁc scheme, the authors

obtained a (much) better security bound than our general bound in this paper.

In [12], Dodis and Puniya introduced a diﬀerent model for indiﬀerentiability,

called indiﬀerentiability in the honest-but-curious model. In this model, the dis-

tinguisher is not allowed to make direct calls to the inner hash functions; instead he

can only query the global Luby-Rackoﬀ construction and get all the intermediate

results. The authors showed that in this model, a Luby-Rackoﬀ construction with

a super-logarithmic number of rounds can replace an ideal cipher. The authors also

showed that indiﬀerentiability in the honest-but-curious model implies indiﬀeren-

tiability in the general model, for LR constructions with up to a logarithmic num-

ber of rounds. But because of this gap between logarithmic and super-logarithmic,

the authors could not conclude about general indiﬀerentiability of Luby-Rackoﬀ

constructions. Subsequent work by Dodis and Puniya [13] studied other proper-

ties (such as unpredictability and veriﬁablity) of the Luby-Rackoﬀ construction

when the intermediate values are known to the attacker.

We have an observation about indiﬀerentiability in the honest-but-curious

model: general indiﬀerentiability does not necessarily imply indiﬀerentiability

in the honest-but-curious model. More precisely, we show in Appendix B that

LR constructions with up to logarithmic number of rounds are not indiﬀeren-

tiable from a random permutation in the honest-but-curious model, whereas our

main result in this paper is that 6-rounds LR is indiﬀerentiable from a random

permutation in the general model.

2 Deﬁnitions

In this section, we recall the notion of indiﬀerentiability of random systems,

introduced by Maurer et al. in [18]. This is an extension of the classical notion

The Random Oracle Model and the Ideal Cipher Model Are Equivalent 5

of indistinguishability, where one or more oracles are publicly available, such as

random oracles or ideal ciphers.

We ﬁrst motivate why such an extension is actually required. The classical

notion of indistinguishability enables to argue that if some system S

is indistin-

guishable from some other system S

(for any polynomially bounded attacker),

then any application that uses S

can use S

instead, without any loss of se-

curity; namely, any non-negligible loss of security would precisely be a way of

distinguishing between the two systems. Since we are interested in replacing a

random permutation (or an ideal cipher) by a Luby-Rackoﬀ construction, we

would like to say that the Luby-Rackoﬀ construction is “indistinguishable” from

a random permutation. However, when the distinguisher can make oracle calls

to the inner round functions, one cannot say that the two systems are “indistin-

guishable” because they don’t even have the same interface (see Fig. 2); namely

for the LR construction the distinguisher can make oracle calls to the inner func-

tions F

’s, whereas for the random permutation he can only query the input and

receive the output and vice versa. This contrasts with the setting of the classical

Luby-Rackoﬀ result, where the adversary has only access to the input/output

of the LR construction, and tries to distinguish it from a random permutation.

Therefore, an extension of the classical notion of indistinguishability is required,

in order to show that some ideal primitive (like a random permutation) can be

constructed from another ideal primitive (like a random oracle).

Following [18], we deﬁne an ideal primitive as an algorithmic entity which

receives inputs from one of the parties and delivers its output immediately to

the querying party. The ideal primitives that we consider in this paper are ran-

dom oracles and random permutations (or ideal ciphers). A random oracle [1] is

an ideal primitive which provides a random output for each new query. Identi-

cal input queries are given the same answer. A random permutation is an ideal

primitive that contains a random permutation P : {0, 1}

→{0, 1}

.Theideal

primitive provides oracle access to P and P

−1

.Anideal cipher is an ideal prim-

itive that models a random block cipher E : {0, 1}

×{0, 1}

→{0, 1}

.Each

key k ∈{0, 1}

deﬁnes a random permutation E

= E(k, ·)on{0, 1}

.Theideal

primitive provides oracle access to E and E

−1

;thatis,onquery(0,k,m), the

primitive answers c = E

(m), and on query (1,k,c), the primitive answers m

such that c = E

(m). These oracles are available for any n and any κ.

The notion of indiﬀerentiability [18] is used to show that an ideal primitive P

(for example, a random permutation) can be replaced by a construction C that

is based on some other ideal primitive F (for example, C is the LR construction

based on a random oracle F ):

Deﬁnition 1 ([18]). A Turing machine C with oracle access to an ideal prim-

itive F is said to be (t

,q,ε)-indiﬀerentiable from an ideal primitive P if

there exists a simulator S with oracle access to P and running in time at most

, such that for any distinguisher D running in time at most t

and making at

most q queries, it holds that:







− Pr



P,S





<ε

6 J.-S. Coron, J. Patarin, and Y. Seurin

FPS

Fig. 3. The indiﬀerentiability notion

is simply said to be indiﬀerentiable from F if ε is a negligible function of the

security parameter n, for polynomially bounded q, t

and t

The previous deﬁnition is illustrated in Figure 3, where P is a random permu-

tation, C is a Luby-Rackoﬀ construction LR,andF is a random oracle. In this

paper, for a 6-round Luby-Rackoﬀ, we denote these random oracles F

,...,F

(see Fig. 2). Equivalently, one can consider a single random oracle F and encode

in the ﬁrst 3 input bits which round function F

,...,F

is actually called. The

distinguisher has either access to the system formed by the construction LR and

the random oracle F , or to the system formed by the random permutation P

and a simulator S. In the ﬁrst system (left), the construction LR computes its

output by making calls to F (this corresponds to the round functions F

’s of the

Luby-Rackoﬀ); the distinguisher can also make calls to F directly. In the second

system (right), the distinguisher can either query the random permutation P ,or

the simulator that can make queries to P . We see that the role of the simulator

is to simulate the random oracles F

’s so that no distinguisher can tell whether

it is interacting with LR and F ,orwithP and S. In other words, 1) the output

of S should be indistinguishable from that of random oracles F

’s and 2) the

output of S should look “consistent” with what the distinguisher can obtain

from P . We stress that the simulator does not see the distinguisher’s queries to

P ; however, it can call P directly when needed for the simulation. Note that the

two systems have the same interface, so now it makes sense to require that the

two systems be indistinguishable.

To summarise, in the ﬁrst system the random oracles F

are chosen at random,

and a permutation C = LR is constructed from them with a 6 rounds Luby-

Rackoﬀ. In the second system the random permutation P is chosen at random

and the inner round functions F

’s are simulated by a simulator with oracle access

to P . Those two systems should be indistinguishable, that is the distinguisher

should not be able to tell whether the inner round functions were chosen at

random and then the Luby-Rackoﬀ permutation constructed from it, or the

random permutation was chosen at random and the inner round functions then

“tailored” to match the permutation.

It is shown in [18] that the indiﬀerentiability notion is the “right” notion

for substituting one ideal primitive with a construction based on another ideal

The Random Oracle Model and the Ideal Cipher Model Are Equivalent 7

primitive. That is, if C

is indiﬀerentiable from an ideal primitive P,thenC

can replace P in any cryptosystem, and the resulting cryptosystem is at least

as secure in the F model as in the P model; see [18] or [9] for a proof. Our

main result in this paper is that the 6 rounds Luby-Rackoﬀ construction is

indiﬀerentiable from a random permutation; this implies that such a construction

can replace a random permutation (or an ideal cipher) in any cryptosystem, and

the resulting scheme remains secure in the random oracle model if the original

scheme was secure in the random permutation (or ideal cipher) model.

3 Attack of Luby-Rackoﬀ with 5 Rounds

In this section we show that 5 rounds are not enough to obtain the indiﬀeren-

tiability property. We do this by exhibiting for the 5 rounds Luby-Rackoﬀ (see

Fig. 4) a property that cannot be obtained with a random permutation.

Fig. 4. 5-rounds

Luby-Rackoﬀ

Let Y and Y



be arbitrary values, corresponding to inputs of

(see Fig. 4); let Z be another arbitrary value, corresponding

to input of F

.LetZ



= F

(Y ) ⊕ F



) ⊕ Z,andlet:

X = F

(Y ) ⊕ Z = F



) ⊕ Z



(1)



= F



) ⊕ Z = F

(Y ) ⊕ Z



(2)

From X, X



, Y and Y



we now deﬁne four couples (X

)as

follows:

)=(X, Y ), (X

)=(X



,Y)

)=(X



), (X

)=(X, Y



)

and we let L

R

be the four corresponding plaintexts;

we have:

= Y

⊕ F

)=Y ⊕ F

(X)

= Y

⊕ F

)=Y ⊕ F



)

= Y

⊕ F

)=Y



⊕ F



)

= Y

⊕ F

)=Y



⊕ F

(X)

Let Z

be the corresponding values as input of F

;wehavefrom(1)

and (2):

= X

⊕ F

)= X ⊕F

(Y )=Z, Z

= X

⊕ F

)=X



⊕ F

(Y )=Z



= X

⊕ F

)=X



⊕ F



)=Z, Z

= X

⊕ F

)=X ⊕F



)=Z



Finally, let S

T

be the four corresponding ciphertexts; we have:

= Y

⊕ F

)= Y ⊕F

(Z),S

= Y

⊕ F

)= Y ⊕ F



)

= Y

⊕ F

)=Y



⊕ F

(Z),S

= Y

⊕ F

)=Y



⊕ F



)

We obtain the relations:

⊕ R

=0,S

⊕ S

8 J.-S. Coron, J. Patarin, and Y. Seurin

Thus, we have obtained four pairs (plaintext, ciphertext) such that the xor of the

right part of the four plaintexts equals 0 and the xor of the left part of the four

ciphertexts also equals 0. For a random permutation, it is easy to see that such

a property can only be obtained with negligible probability, when the number

of queries is polynomially bounded. Thus we have shown:

Theorem 1. The Luby-Rackoﬀ construction with 5 rounds is not indiﬀeren-

tiable from a random permutation.

This contrasts with the classical Luby-Rackoﬀ result, where 4 rounds are enough

to obtain a strong pseudo-random permutation from pseudo-random functions.

4 Indiﬀerentiability of Luby-Rackoﬀ with 6 Rounds

We now prove our main result: the Luby-Rackoﬀ construction with 6 rounds is

indiﬀerentiable from a random permutation.

Theorem 2. The LR construction with 6 rounds is (t

,q,ε)-indiﬀerentiable

from a random permutation, with t

= O(q

) and ε =2

·q

,wheren is the

output size of the round functions.

Note that here the distinguisher has unbounded running time; it is only bounded

to ask q queries. As illustrated in Figure 3, we must construct a simulator S such

that the two systems formed by (LR, F )and(P, S) are indistinguishable. The

simulator is constructed in Section 4.1, while the indistinguishability property

is proved in Section 4.2.

4.1 The Simulator

We construct a simulator S that simulates the random oracles F

,...,F

.For

each function F

the simulator maintains an history of already answered queries.

We write x ∈ F

when x belongs to the history of F

, and we denote by F

(x)

the corresponding output. When we need to obtain F

(x)andx does not belong

to the history of F

,wewriteF

(x) ← y to determine that the answer to F

query x will be y; we then add (x, F

(x)) to the history of F

.Wedenotebyn

the output size of the functions F

’s.WedenotebyLR and LR

−1

the 6-round

Luby-Rackoﬀ construction as obtained from the functions F

’s.

We ﬁrst provide an intuition of the simulator’s algorithm. The simulator must

make sure that his answers to the distinguisher’s F

queries are coherent with the

answers to P queries that can be obtained independently by the distinguisher.

In other words, when the distinguisher makes F

queries to the simulator (possi-

bly in some arbitrary order), the output generated by the corresponding Luby-

Rackoﬀ must be the same as the output from P obtained independently by the

distinguisher. We stress that those P queries made by the distinguisher cannot

be seen by the simulator; the simulator is only allowed to make his own P queries

(as illustrated in Fig. 3). In addition, the simulator’s answer to F

queries must

be statistically close to the output of random functions.

剩余604页未读，继续阅读

duolei

粉丝: 1
资源: 1

密码学盛会：2008 CRYPTO资源分享

超级科学星期六：Java密码学项目crypto-SSS详解

C++构建的crypto3密码学套件详解

Fiat-Crypto项目：密码原语代码自动生成工具

CTF密码学CRYPTO.pdf

密码类库Crypto++库

攻防世界密码学crypto，base64题目环境

js 实现记住密码功能 crypto-js.js

一段base64—–奇怪的密码（Crypto–bugku）

Crypto Crypto

Crypto101 密码学

最新资源