多方安全计算模拟器构建与安全性证明教程

版权申诉

5星 · 超过95%的资源 95 浏览量更新于2024-07-08 1 收藏 1.88MB PDF 举报

身份认证购VIP最低享 7 折!

30元优惠券

"多方安全计算+安全性证明+模拟器构造方案 A Tutorial on the Simulation Proof Technique" 在密码学领域，多方安全计算（Multiparty Computation, MPC）是一种允许多个参与方在不泄露各自输入的情况下共同计算特定函数的技术。这种计算方式在保护数据隐私，尤其是在涉及敏感信息的场景中显得尤为重要。安全性证明是验证一个协议是否真正安全的关键步骤，而模拟器构造方案则是其中的核心工具。本教程由Yehuda Lindell撰写，旨在指导读者如何构建模拟器并使用模拟证明方法来验证多方安全计算的安全性。 1. 引言引入模拟证明技术的主要目的是确保协议在实际应用中的安全性。模拟器是一种理论上的计算实体，它可以模拟攻击者的行为，同时保持与真实执行的协议难以区分。通过比较真实世界执行和模拟执行的结果，可以证明协议在面对潜在攻击时的抗攻击性。 2. 预备知识和符号表示在理解模拟器构造和安全性证明之前，需要对安全加密、零知识证明以及安全计算的基本概念有一定的了解。安全加密保证了信息的机密性，零知识证明则允许一方证明自己知道某种信息而无需揭示该信息本身，安全计算是这两者的结合，使得数据在计算过程中保持隐私。 3. 基本范式：语义安全语义安全是衡量加密方案安全性的一个基本标准，它要求即使攻击者可以观察到加密后的密文，也无法获得关于明文的任何有效信息。模拟器在语义安全的证明中起到关键作用，通过构造一个与真实解密过程难以区分的模拟解密过程，证明加密方案的不可破译性。 4. 安全计算：模拟器方法在多方安全计算中，模拟器不仅需要模拟单个参与者的行动，还要处理多个参与者之间的交互。安全性的证明通常涉及构建一个“无知识”模拟器，这个模拟器能够在不知道某些输入或内部状态的情况下，生成与真实执行相同的行为。这表明即使有攻击者存在，协议仍然能够提供预期的安全属性。关键词：安全计算，模拟技术，教程本教程的内容涵盖了从基本的安全计算概念到如何构建和分析模拟器的细节，对于想要深入理解多方安全计算和安全性证明的初学者来说是一份宝贵的资源。它还强调了模拟证明在理论和实践中的重要性，以及在Oded Goldreich的密码学基础教程系列中的地位。通过学习这篇教程，读者将能够更好地掌握如何为新的安全计算协议设计和验证安全性的方法。

资源详情

资源推荐

4.3 Oblivious Transfer for Semi-Honest Adversaries

In this section, we consider a standard two-party functionality, where both parties have private

inputs and wish to compute an output. We will show how to securely compute the bit obli v iou s

transfer functionality, deﬁned by f((b

, b

), σ) = (λ, b

), where b

, b

, σ ∈ {0, 1} [35, 16]. Stated i n

words, P

has a pair of input bits (b

, b

) and P

has a choice bit σ. The function is such that P

receives no output (denoted by the empty string λ), and in particular learns nothing about σ. In

contrast , P

receives the bit of its choice b

and learns n ot hi n g about the other bit b

1−σ

. This is

called “oblivious transfer” since the ﬁrst party has two in pu t s and sends exactly one of the inputs

to the receiver, according to the receiver’s choice, without knowing which is sent . We present the

protocol of [16] in Protocol 4.2, which relies on enhanced trapdoor permutations .

Background – enhanced trapdoor permutations [18, Appendi x C.1]. Informally, a family

of trapdoor permutation s is a family of bijective functions with the property that randomly-sampled

functions are hard to invert on randomly sampled values (in its range). However , there exists a

trapdoor so that given the trapdoor, the function can be eﬃciently inverted. Enhanced trapdoor

permutation have the additional property that it is possible to sample values from the range , so

that it is hard to invert t he function on these values e ven when given the coins used for sampling.

Formally, a collection of trapdoor permutations i s a collection of function s {f

}

accompanied by

four pr obab il i st i c -polynomial t i me algorithms I, S, F, F

−1

such that:

1. I(1

) selects a random n-bit index α of a permut at i on f

along with a corresponding trap-

door τ. De not e by I

) the α-part of the output.

2. S(α) samples an (al mos t unifor m) element in the domain (equivalently, the range) of f

. We

denote by S(α; r) the output of S(α) with random tape r; for simplicity we assume that

r ∈ {0, 1}

3. F (α, x) = f

(x), for α in the range of I

and x in the range of S(α).

4. F

−1

(τ, y) = f

−1

(y) for y in the range of f

and (α, τ) in the range of I.

Then, the family is a collection of enhanced trapdoor permutations if for every non-uniform probabilistic-

polynomial time adversary A there exists a negligible func ti on µ such that for every n,

A(1

, α, r) = f

−1

(S(α; r))

(

≤ µ(n)

where α ← I

) and r ∈

{0, 1}

is random. Ob se rve that given α and r, A can compute

y = S(α; r). Thus, A’s task is to invert y, when it is also given the random coins used by S to

sample y. See [18, Appendi x C.1] for more discussion on the deﬁnition and for constructions of

enhanced trapdoor permut at ion s.

We wi l l also refer to a hard-core predicate B of a family of enhanced trapdoor permutations

[17, Section 2.5]. We say that B is a hard-core predicate of (I, S, F, F

−1

) if for every non- un if or m

probabilistic-polynomial time adversary A there exists a negligible function µ such that for every n,

A(1

, α, r) = B

α, f

−1

(S(α; r))

≤

+ µ(n).

The protocol idea. The idea behind the protocol is that P

chooses an enhanced trapdoor

permutation, and sends the permutat ion description (without the trapdoor) to P

. Then, P

samples two elements y

, y

where it knows the preimage of y

but does not know the preimage of

1−σ

. Party P

sends y

, y

to P

, who inverts them both using the trapdoor, and send s b

masked

by the hard-core bit of f

−1

), and b

masked by the hard-core bit of f

−1

). Party P

is able

to obtain b

since it knows f

−1

), but is unable to obtain b

1−σ

since it does not know f

−1

1−σ

)

and so cannot guess its hard-core bit with probability non-ne gl igi b l y greater than 1/2. In addition ,

sees only y

, y

which are identically distributed (even though P

generates them diﬀerently),

and so learns nothing about P

’s bit σ. See Protocol 4.2 for the protocol description.

PROTOCOL 4.2 (Oblivious Transfer [16])

• Inputs: P

has b

, b

∈ {0, 1} and P

has σ ∈ {0, 1}. (Both parties have (I, S, F, F

−1

)

deﬁning a collection of enhanced trapdoor permutations and a hard-core predicate B.)

• The protocol:

1. P

runs I(1

) to obtain a permutation-trap d oor pair (α, τ). P

sends α to P

2. P

runs S(α) twice; denote the ﬁrst value obtained by x

and the second by y

1−σ

Then, P

computes y

= F (α, x

) = f

), and sends y

, y

to P

3. P

uses the trapdoor τ and computes x

= F

−1

(α, y

) = f

−1

) and x

−1

(α, y

) = f

−1

). Then, it computes β

= B(α, x

) ⊕ b

and β

= B(α, x

) ⊕ b

where B is a hard-core predicate of f. Finally, P

sends (β

, β

) to P

4. P

computes b

= B(α, x

) ⊕ β

and outputs the result.

We prove the following theorem:

Theorem 4.3 Assume that (I, S, F, F

−1

) constitutes a family of enhanced trapdoor permutations

with a hard-core predicate B. Then, Protocol 4.2 securely computes the functionality f((b

, b

), σ) =

(λ, b

) in the presence of static semi-honest adversaries.

Proof: Since this is the ﬁrst proof in this t u tor i al , we prove it in excruciating detail; in later

proofs we will not necessarily work through all the ﬁne d et ai l s. The oblivious transfer f un ct i on ali ty

is deterministic, and t hus it su ﬃc es to use the simpler formulation of security. Corre ct n es s is

immediate, and we therefore proceed to the simulation. We construct a sep arat e simul at or for each

party (S

for P

’s vie w and S

for P

’s vie w, as in Deﬁnition 4.1).

Consider ﬁrst the case that P

is corrupted. Observe that P

receives no output. Thus, we

merely need to show that a simulator can generate the view of the incoming messages received by

. In th e protocol, P

receives a single message consisting of a pair of values y

, y

in the domain

of f

. Formally, S

is given (b

, b

) and 1

and works as follows:

1. S

chooses a uniformly distributed random tape r for P

(of the length required, whi ch is

what is needed to run I).

2. S

computes (α, τ) ← I(1

; r), using the r from above.

3. S

runs S(α) twice with independent randomness to sample values y

, y

4. Finally, S

outputs ((b

, b

), r; (y

, y

)); the pair (y

, y

) simulates the incoming message from

to P

in the protocol.

Note that S

cannot sampl e y

, y

in the same way as the honest P

since it does not know P

’s input

σ. Nevertheless, the deﬁnition of a collection of trapdoor permutation states that S(α) out p ut s a

value that is al m ost uniformly distributed in the domain of f

(and the domain equals the range,

since it i s a permutation). Thus, it follows that the distribution over F (α, S(α)) is statistically

close t o the distribution over S(α). This implies that

{(F (α , x

), y

)}

≡ {(y

, y

)}

≡ {(y

, F (α, x

))}

where α is in the range of I, and x

, x

, y

are all samples of S(α). The vi e w of P

includes a

pair as above, along with a uniformly generated tape . Note that the pair (F (α, x

), y

) is exactly

what P

sees when P

has input σ = 0, that the pair (y

, y

) is the simulator-generated view, and

that the pair (y

, F (α, x

)) is exactly what P

sees when P

has input σ = 1. Thus, we conclude

that for every σ ∈ {0, 1},

, (b

, b

))}

≡ {view

((b

, b

), σ)}

as requi r ed .

Next, we proceed to the case that P

is corrupted, and const r uc t a simulator S

. In this case, we

need to do something very diﬀerent in the simu l ati on . In particular, we need to construct a view so

that t he output deﬁned by that view equ als the real output of the protocol. (Observe that a party’s

view includes its input, random tape, and all incoming messages. Thus, by running the protocol

instructions on this view, an output is obtained. This output has to be the “correct” one, or the

distinguisher can easily see that it is not t he view of a real execution.) Recall that S

receives P

’s

input and output, and thus is able to achieve the above. In this protocol, this is achi e ved by having

set β

= B(α, x

) ⊕ b

, like the real P

. In contrast, S

is unable to compute β

1−σ

correctly,

since i t does not know b

1−σ

Simulat or S

receives for input 1

plus P

’s inp ut and output bits (σ, b

). Then:

1. S

chooses a uniform random tape for P

. Since P

’s randomness is for running S(α ) twice,

we denote the random tape by r

, r

2. S

runs I(1

) and obtains (α, τ ).

3. S

computes x

= S(α; r

) and y

1−σ

= S(α; r

1−σ

), and sets x

1−σ

= F

−1

(τ, y

1−σ

4. S

sets β

= B(α, x

) ⊕ b

, where b

is P

’s outp ut received by S

5. S

sets β

1−σ

= B(α, x

1−σ

6. S

outputs (σ, r

, r

; α, (β

, β

)).

First, note that by putting the “σ-value” ﬁrst, the real view of P

in an execution can be written as:

view

((b

, b

), σ) =

σ, r

, r

; α, (B(α, x

) ⊕ b

, B(α, x

1−σ

) ⊕ b

1−σ

)

where x

= S(α; r

) and x

= S(α; r

). In contrast, the output of the simul at or written in this way is:

, σ, b

) =

σ, r

, r

; α, (B(α, x

) ⊕ b

, B(α, x

1−σ

))

In almost all cases, the simulation begins by the simulator choosing a uniform random tape for the party.

剩余64页未读，继续阅读

chenxin0215

粉丝: 26
资源: 17

多方安全计算模拟器构建与安全性证明教程

论文研究-标准模型下基于双线性对的短签名方案 .pdf

A tutorial on support vector regression.Statistics and Computing,2004

How To Simulate It – A Tutorial on the Simulation Proof Technique

[4]Shlens J. A Tutorial on Principal Component Analysis[J]. arXiv preprint arXiv:1404.1100, 2014.的标准文献参考名

a tutorial on learning with bayesian networks

161204_mastering_the_freertos_real_time_kernel-a_hands- on_tutorial_guide

Ifogsim usage tutorial

c++ standard library, the: a tutorial and reference pdf 下载

arena simulation software tutorial documentation

can you give me a tuotrial on using models on huggingface?

从2-3个平台搜集10偏左右的关于chatgpt的高质量文档给我

fluent tutorial pdf 下载

tutorial master 2下载

gdscript astar demo

computational fourier optics: a matlab tutorial pdf下载

j2ee tutorial中文版

ros2 rviz learn line

给我设计一个基于arduino的矩阵键盘1602的数字密码锁，输入密码正确后打开

最新资源