密码学讲义： provable security与安全协议设计

需积分: 9 147 浏览量更新于2024-07-26 收藏 1.48MB PDF 举报

"这是一份由Shafi Goldwasser和Mihir Bellare编写的密码学讲座笔记，用于加州大学圣地亚哥分校的课程。笔记主要关注可证明安全性和其在设计安全协议中的应用。" 《密码学讲座》是基于加州大学圣地亚哥分校的一门课程，由Shafi Goldwasser和Mihir Bellare两位专家共同授课。这门课程的目的是深入讲解密码学的核心概念，并特别强调可证明安全性（Provable Security）的概念及其在构建安全协议中的重要作用。首先，可证明安全性是密码学中的一个关键理论框架，它允许我们通过数学证明来评估和确保一个加密方案的安全性。这种方法超越了传统的依赖于经验或直觉的安全模型，而是基于严谨的数学分析，可以提供更深入的理解和信任。在这些讲座笔记中，读者将学习如何分析和证明加密算法的安全性，以及如何设计具有这种性质的协议。讲座内容涵盖了多个主题，包括但不限于： 1. 密码学基础：介绍密码学的基本原理，如对称加密、非对称加密（如RSA）、哈希函数和消息认证码（MAC），以及它们在保护信息安全中的应用。 2. 可证明安全性理论：详细阐述如何构造可证明安全的加密算法，包括安全性定义（如IND-CPA，IND-CCA等）以及如何通过安全性减少进行证明。 3. 密码协议设计：探讨如何利用可证明安全性的概念设计安全的通信协议，如密钥交换协议（如Diffie-Hellman）和数字签名算法。 4. 密码分析与安全性评估：介绍密码分析方法，包括穷举攻击、侧信道攻击等，以及如何评估和抵御这些攻击。 5. 随机预言机模型：讲解随机预言机模型在证明安全性中的作用，这是一种抽象的计算模型，用于简化复杂的安全性证明。 6. 零知识证明：介绍零知识证明的概念，它允许一方向另一方证明一个陈述的真实性，而无需透露任何有用的信息。 7. 公开验证的秘密共享：讨论如何在多用户环境中实现秘密的分布式存储，同时保证只有特定组合的参与者才能恢复秘密。这些笔记不仅包含了理论知识，还可能包含了MIT研究生在Shafi Goldwasser教授的密码学和密码分析课程中所记录的实际案例和问题，使得学习更为生动和实用。这份资料对于想要深入了解密码学理论和实践的学者、研究人员或IT专业人士来说，是一份宝贵的资源。它提供了全面的视角，帮助读者理解如何通过严谨的数学方法来确保信息安全。

C h a p t e r 2

One-way and trapdoor functions

One Way functions, namely functions that are “easy” to compute and “hard” to invert, are an extremely

important cryptographic primitive. Probably the best known and simplest use of one-way functions, is for

passwords. Namely, in a time-shared computer system, instead of storing a table of login passwords, one can

store, for each password w, the value f (w). Passwords can easily be checked for correctness at login, but even

the system administrator can not deduce any user’s password by examining the stored table.

In Section 1.3 we had provided a short list of some candidate one-way functions. We now develop a theoretical

treatment of the subject of one-way and trapdoor functions, and carefully examine the candidate one-way

functions proposed in the literature. We will occasionaly refer to facts about number theory discussed in

Chapter C.

We begin by explaining why one-way functions are of fundamental importance to cryptography.

2.1 One-Way Functions: Motivation

In this section, we provide motivation to the deﬁnition of one-way functions. We argue that the existence of

one-way functions is a necessary condition to the existence of most known cryptographic primitives (including

secure encryption and digital signatures). As the current state of knowledge in complexity theory does not allow

to prove the existence of one-way function, even using more traditional assumptions as P 6= NP, we will have

to assume the existence of one-way functions. We will later try to provide evidence to the plausibility of this

assumption.

As stated in the introduction chapter, modern cryptography is based on a gap between eﬃcient algorithms

guaranteed for the legitimate user versus the unfeasibility of retrieving protected information for an adver-

sary. To make the following discussion more clear, let us concentrate on the cryptographic task of secure data

communication, namely encryption schemes.

In secure encryption schemes, the legitimate user is able to decipher the messages (using some private infor-

mation available to him), yet for an adversary (not having this private information) the task of decrypting the

ciphertext (i.e., “breaking” the encryption) should be infeasible. Clearly, the breaking task can be performed by

a non-deterministic p olynomial-time machine. Yet, the security requirement states that breaking should not be

feasible, namely could not be performed by a probabilistic polynomial-time machine. Hence, the existence of se-

cure encryption schemes implies that there are tasks performed by non-deterministic polynomial-time machines

yet cannot be performed by deterministic (or even randomized) polynomial-time machines. In other words, a

necessary condition for the existence of secure encryption schemes is that NP is not contained in BPP (and

hence that P 6= NP).

However, the above mentioned necessary condition (e.g., P 6= NP) is not a suﬃcient one. P 6= NP only implies

Cryptography: Lecture Notes 17

that the encryption scheme is hard to break in the worst case. It does not rule-out the possibility that the

encryption scheme is easy to break in almost all cases. In fact, one can easily construct “encryption schemes”

for which the breaking problem is NP-complete and yet there exist an eﬃcient breaking algorithm that succeeds

on 99% of the cases. Hence, worst-case hardness is a poor measure of security. Security requires hardness on

most cases or at least average-case hardness. Hence, a necessary condition for the existence of secure encryption

schemes is the existence of languages in NP which are hard on the average. Furthermore, P 6= NP is not

known to imply the existence of languages in NP which are hard on the average.

The mere existence of problems (in NP) which are hard on the average does not suﬃce. In order to be able to

use such problems we must be able to generate such hard instances together with auxiliary information which

enable to solve these instances fast. Otherwise, the hard instances will be hard also for the legitimate users and

they gain no computational advantage over the adversary. Hence, the existence of secure encryption schemes

implies the existence of an eﬃcient way (i.e. probabilistic polynomial-time algorithm) of generating instances

with corresponding auxiliary input so that

(1) it is easy to solve these instances given the auxiliary input; and

(2) it is hard on the average to solve these instances (when not given the auxiliary input).

We avoid formulating the above “deﬁnition”. We only remark that the coin tosses used in order to generate the

instance provide suﬃcient information to allow to eﬃciently solve the instance (as in item (1) above). Hence,

without loss of generality one can replace condition (2) by requiring that these coin tosses are hard to retrieve

from the instance. The last simpliﬁcation of the above conditions essentially leads to the deﬁnition of a one-way

function.

2.2 One-Way Functions: Deﬁnitions

In this section, we present several deﬁnitions of one-way functions. The ﬁrst version, hereafter referred to as

strong one-way function (or just one-way function), is the most convenient one. We also present weak one-way

functions which may be easier to ﬁnd and yet can be used to construct strong one way functios, and non-uniform

one-way functions.

2.2.1 (Strong) One Way Functions

The most basic primitive for cryptographic applications is a one-way function. Informally, this is a function

which is “easy” to compute but “hard” to invert. Namely, any probabilistic polynomial time (PPT) algorithm

attempting to invert the one-way function on a element in its range, will succeed with no more than “negligible”

probability, where the probability is taken over the elements in the domain of the function and the coin tosses

of the PPT attempting the inversion.

This informal deﬁnition introduces a couple of measures that are prevalent in complexity theoretic cryptography.

An easy computation is one which can be carried out by a PPT algorithm; and a function ν: N → R is negligible

if it vanishes faster than the inverse of any polynomial. More formally,

Deﬁnition 2.1 ν is negligible if for every constant c ≥ 0 there exists an integer k

such that ν(k) < k

−c

for all

k ≥ k

Another way to think of it is ν(k) = k

−ω (1)

A few words, concerning the notion of negligible probability, are in place. The above deﬁnition and discussion

considers the success probability of an algorithm to be negligible if as a function of the input length the success

probability is bounded by any polynomial fraction. It follows that repeating the algorithm polynomially (in

the input length) many times yields a new algorithm that also has a negligible success probability. In other

words, events which occur with negligible (in n) probability remain negligible even if the experiment is repeated

for polynomially (in k) many times. Hence, deﬁning negligible success as “occurring with probability smaller

than any polynomial fraction” is naturally coupled with deﬁning feasible as “computed within polynomial

18 Goldwasser and Bellare

time”. A “strong negation” of the notion of a negligible fraction/probability is the notion of a non-negligible

fraction/probability. we say that a function ν is non-negligible if there exists a polynomial p such that for all

suﬃciently large k’s it holds that ν(k) >

p(k)

. Note that functions may be neither negligible nor non-negligible.

Deﬁnition 2.2 A function f: {0, 1}

∗

→ {0, 1}

∗

is one-way if:

(1) there exists a PPT that on input x output f(x);

(2) For every PPT algorithm A there is a negligible function ν

such that for suﬃciently large k,

f(z) = y : x

← {0, 1}

; y ← f(x) ; z ← A(1

, y)

≤ ν

(k)

Remark 2.3 The guarantee is probabilistic. The adversary is not unable to invert the function, but has a low

probability of doing so where the probability distribution is taken over the input x to the one-way function

where x if of length k, and the possible coin tosses of the adversary. Namely, x is chosen at random and y is

set to f(x).

Remark 2.4 The advsersary is not asked to ﬁnd x; that would be pretty near impossible. It is asked to ﬁnd

some inverse of y. Naturally, if the function is 1-1 then the only inverse is x.

Remark 2.5 Note that the adversary algorithm takes as input f(x) and the security parameter 1

(expressed

in unary notatin) which corresponds to the binary length of x. This represents the fact the adversary can work

in time polynomial in |x|, even if f (x) happends to be much shorter. This rules out the possibility that a

function is considered one-way merely because the inverting algorithm does not have enough time to print the

output. Consider for example the function deﬁned as f(x) = y where y is the log k least signiﬁcant bits of x

where |x| = k. Since the |f (x)| = log |x| no algorithm can invert f in time polynomial in |f(x)|, yet there exists

an obvious algorithm which ﬁnds an inverse of f(x) in time polynomial in |x|. Note that in the special case of

length preserving functions f (i.e., |f(x)| = |x| for all x’s), the auxiliary input is redundant.

Remark 2.6 By this deﬁnition it trivially follows that the size of the output of f is bounded by a polynomial

in k, since f(x) is a poly-time computable.

Remark 2.7 The deﬁnition which is typical to deﬁnitions from computational complexity theory, works with

asymptotic complexity—what happens as the size of the problem becomes large. Security is only asked to hold

for large enough input lengths, namely as k goes to inﬁnity. Per this deﬁnition, it may be entirely feasible

to invert f on, say, 512 bit inputs. Thus such deﬁnitions are less directly relevant to practice, but useful for

studying things on a basic level. To apply this deﬁnition to practice in cryptography we must typically envisage

not a single one-way function but a family of them, parameterized by a security parameter k. That is, for each

value of the security parameter k there is be a speciﬁc function f : {0, 1}

→ { 0, 1}

∗

. Or, there may be a family

of functions (or cryptosystems) for each value of k. We shall deﬁne such familes in subsequent section.

The next two sections discuss variants of the strong one-way function deﬁnition. The ﬁrst time reader is

encouraged to directly go to Section 2.2.4.

2.2.2 Weak One-Way Functions

One way functions come in two ﬂavors: strong and weak. The deﬁnition we gave above, refers to a strong way

function. We could weaken it by replacing the second requirement in the deﬁnition of the function by a weaker

requirement as follows.

Deﬁnition 2.8 A function f: {0, 1}

∗

→ {0, 1}

∗

is weak one-way if:

Cryptography: Lecture Notes 19

(1) there exists a PPT that on input x output f(x);

(2) There is a polynomial functions Q such that for every PPT algorithm A, and for suﬃciently large k,

f(z) 6= y : x

← {0, 1}

; y ← f(x) ; z ← A(1

, y)

≥

Q(k)

The diﬀerence between the two deﬁnitions is that whereas we only require some non-negligible fraction of the

inputs on which it is hard to invert a weak one-way function, a strong one-way function must b e hard to invert

on all but a negligible fraction of the inputs. Clearly, the latter is preferable, but what if only weak one-way

functions exist ? Our ﬁrst theorem is that the existence of a weak one way function implies the existence of a

strong one way function. Moreover, we show how to construct a strong one-way function from a weak one. This

is important in practice as illustarted by the following example.

Example 2.9 Consider for example the function f : Z × Z 7→ Z where f(x, y) = x · y. This function can be

easily inverted on at least half of its outputs (namely, on the even integers) and thus is not a strong one way

function. Still, we said in the ﬁrst lecture that f is hard to invert when x and y are primes of roughly the same

length which is the case for a polynomial fraction of the k-bit composite integers. This motivated the deﬁnition

of a weak one way function. Since the probability that an k-bit integer x is prime is approximately 1/k, we get

the probability that both x and y such that |x| = |y| = k are prime is approximately 1 /k

. Thus, for all k ,

about 1 −

of the inputs to f of length 2k are prime pairs of equal length. It is believed that no adversary

can invert f when x and y are primes of the same length with non-negligible success probability, and under this

belief, f is a weak one way function (as condition 2 in the above deﬁnition is satisﬁed for Q(k) = O(k

)).

Theorem 2.10 Weak one way functions exist if and only if strong one way functions exist.

Proof Sketch: By deﬁnition, a strong one way function is a weak one way function. Now assume that f is a

weak one way function such that Q is the polynomial in condition 2 in the deﬁnition of a weak one way function.

Deﬁne the function

. . . x

) = f (x

) . . . f(x

)

where N = 2kQ(k) and each x

is of length k.

We claim that f

is a strong one way function. Since f

is a concatenation of N copies of the function f, to

correctly invert f

, we need to invert f(x

) correctly for each i. We know that every adversary has a probability

of at least

Q(k)

to fail to invert f(x) (where the probability is taken over x ∈ {0, 1}

and the coin tosses of the

adversary), and so intuitively, to invert f

we need to invert O(kQ(k)) instances of f. The probability that the

adversary will fail for at least one of these instances is extremely high.

The formal proof (which is omitted here and will be given in appendix) will take the form of a reduction; that is,

we will assume for contradiction that f

is not a strong one way function and that there exists some adversary

that violates condition 2 in the deﬁnition of a strong one way function. We will then show that A

can be

used as a subroutine by a new adversary A that will be able to invert the original function f with probability

better than 1 −

Q(|x|)

(where the probability is taken over the inputs x ∈ { 0, 1}

and the coin tosses of A). But

this will mean that f is not a weak one way function and we have derived a contradiction.

This pro of technique is quite typical of proofs presented in this course. Whenever such a proof is presented it

is important to examine the cost of the reduction. For example, the construction we have just outlined is not

length preserving, but expands the size of the input to the function quadratically.

2.2.3 Non-Uniform One-Way Functions

In the above two deﬁnitions of one-way functions the inverting algorithm is probabilistic polynomial-time.

Stronger versions of both deﬁnitions require that the functions cannot be inverted even by non-uniform families

20 Goldwasser and Bellare

of polynomial size algorithm We stress that the “easy to compute” condition is still stated in terms of uniform

algorithms. For example, following is a non-uniform version of the deﬁnition of (strong) one-way functions.

Deﬁnition 2.11 A function f is called non-uniformly strong one-way if the following two conditions hold

(1) easy to compute: as before There exists a PPT algorithm to compute for f.

(2) hard to invert: For every (even non-uniform) family of polynomial-size algorithms A = {M

}

k∈N

, there

exists a negligble ν

such that for all suﬃciently large k’s

f(z) 6= y : x

← {0, 1}

; y ← f(x) ; z ← M

(y)

≤ ν

(k)

Note that it is redundent to give 1

as an auxiliary input to M

It can be shown that if f is non-uniformly one-way then it is (strongly) one-way (i.e., in the uniform sense). The

proof follows by converting any (uniform) probabilistic polynomial-time inverting algorithm into a non-uniform

family of polynomial-size algorithm, without decreasing the success probability. Details follow. Let A

be a

probabilistic polynomial-time (inverting) algorithm. Let r

denote a sequence of coin tosses for A

maximizing

the success probability of A

. The desired algorithm M

incorporates the code of algorithm A

and the sequence

(which is of length polynomial in k).

It is possible, yet not very plausible, that strongly one-way functions exist and but there are no non-uniformly

one-way functions.

2.2.4 Collections Of One Way Functions

Instead of talking about a single function f : {0, 1}

∗

→ { 0, 1}

∗

, it is often convenient to talk about collections of

functions, each deﬁned over some ﬁnite domain and ﬁnite ranges. We remark, however, that the single function

format makes it easier to prove prop erties about one way functions.

Deﬁnition 2.12 Let I be a set of indices and for i ∈ I let D

and R

be ﬁnite. A collection of strong one way

functions is a set F = {f

: D

→ R

}

i∈I

satisfying the following conditions.

(1) There exists a PPT S

which on input 1

outputs an i ∈ {0, 1}

∩ I

(2) There exists a PPT S

which on input i ∈ I outputs x ∈ D

(3) There exists a PPT A

such that for i ∈ I and x ∈ D

, A

(i, x) = f

(x).

(4) For every PPT A there exists a negligible ν

such that ∀ k large enough

(z) = y : i

← I ; x

← D

; y ← f

(x) ; z ← A(i, y)

≤ ν

(k)

(here the probability is taken over choices of i and x, and the coin tosses of A).

In general, we can show that the existence of a single one way function is equivalent to the existence of a

collection of one way functions. We prove this next.

Theorem 2.13 A collection of one way functions exists if and only if one way functions exist.

Proof: Suppose that f is a one way function.

Set F = {f

: D

→ R

}

i∈I

where I = {0, 1}

∗

and for i ∈ I, take D

= R

= {0, 1}

|i|

and f

(x) = f(x).

Furthermore, S

uniformly chooses on input 1

, i ∈ {0, 1}

, S

uniformly chooses on input i, x ∈ D

= {0, 1}

|i|

剩余288页未读，继续阅读

ntagat

粉丝: 0
资源: 1

密码学讲义： provable security与安全协议设计

Lectures on differential geometry

Lectures on Finite Fields and Galois Ring

Lectures on Mechanics

lectures on network systems

Ten Lectures on Wavelets

Lectures on Quantitative Economy

Feynman Lectures on Computation

TEN LECTURES ON WAVELET

ten lectures on wavelets

Lectures on Quantum Information

最新资源