【免费】安全多方计算学习资料-6篇专著及论文

共6个文件

pdf：6个

课程资源

需积分: 0 41 浏览量 2023-06-15 19:07:07 上传评论 1 收藏 5.54MB ZIP 举报

资源推荐

资源详情

资源评论

收起资源包目录

安全多方计算学习资料.zip （6个子文件）

2022Concretely_efficient_secure_multi-party_computatio-冯登国.pdf 2.01MB

2022Secure Multi-Party Computation Meets Machine Learning.pdf 1.91MB

2001Secure Multi-Party Computation Problems and Their Applications A Review and Open Problems .pdf 232KB

2002Secure Multi-Party Computation-Oded Goldreich.pdf 838KB

2022A Pragmatic Introduction toSecure Multi-Party Computation.pdf 1.21MB

2020Secure Multiparty Computation-Yehuda Lindell.pdf 533KB

Security and Safety, Vol. 1, 2021001 (2022)

https://doi.org/10.1051/sands/2021001

sands.edpsciences.org

Information Network

Concretely eﬃcient secure multi-party computation

protocols: survey and more

Dengguo Feng

1,2

and Kang Yang

1,∗

State Key Laboratory of Cryptology, Beijing 100878, China

State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences,

Beijing 100190, China

Received: 11 October 2021 / Revised: 5 November 2021 / Accepted: 6 December 2021 / Published online: 14 June 2022

Abstract Secure multi-party computation (MPC) allows a set of parties to jointly compute

a function on their private inputs, and reveals nothing but the output of the function. In the

last decade, MPC has rapidly moved from a purely theoretical study to an object of practical

interest, with a growing interest in practical applications such as privacy-preserving machine

learning (PPML). In this paper, we comprehensively survey existing work on concretely

eﬃcient MPC protocols with both semi-honest and malicious security, in both dishonest-

majority and honest-majority settings. We focus on considering the notion of security with

abort, meaning that corrupted parties could prevent honest parties from receiving output

after they receive output. We present high-level ideas of the basic and key approaches for

designing diﬀerent styles of MPC protocols and the crucial building blocks of MPC. For

MPC applications, we compare the known PPML protocols built on MPC, and describe the

eﬃciency of private inference and training for the state-of-the-art PPML protocols. Further-

more, we summarize several challenges and open problems to break though the eﬃciency of

MPC protocols as well as some interesting future work that is worth being addressed. This

survey aims to provide the recent development and key approaches of MPC to researchers,

who are interested in knowing, improving, and applying concretely eﬃcient MPC protocols.

Keywords Secure multi-party computation, Privacy-preserving machine learning, Secret

sharings, Garbled circuits, Oblivious transfer and its arithmetic generalization

Citation Feng D and Yang K. Concretely eﬃcient secure multi-party computation proto-

cols: survey and more. Security and Safety 2022; 1: 2021001. https://doi.org/10.1051/sands/

2021001

1 Introduction

Secure multi-party computation (MPC) allows a set of parties to jointly compute a function on their

private inputs without revealing anything but the output of the function. Speciﬁcally, MPC allows n

parties to jointly compute the following function:

, . . . , y

) ← f(x

, . . . , x

where every party P

holds an input x

, obtains an output y

, and can learn nothing except for (x

, y

, f ),

and function f is often modeled as a Boolean or arithmetic circuit. MPC is a foundation of cryptography,

and is also a core technology to protect privacy of data for cooperative computing in the big data era.

Corresponding author (email: yangk@sklc.org)

This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0),

which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Security and Safety, Vol. 1, 2021001

In the late 1980s, it was shown that MPC protocols for any function can be constructed [1–6], which

demonstrates the feasibility of MPC. However, signiﬁcant improvements are necessary to make MPC

suﬃciently eﬃcient to be used in practice. In the last decade, MPC has been developed from a theoretical

ﬁeld to a practical one, and is starting to see real-life deployments. A series of open-sourced libraries

for MPC (e.g., ABY [7], EMP-toolkit [8], FRESCO [9], JIFF [10], MP-SPDZ [11], MPyC [12], SCALE-

MAMBA [13], Bogdanov et al. [14], and TinyGable [15]) have been developed, and further promote the

applications and deployment of MPC. We refer the reader to [16, 17] for more MPC libraries and the

comparison of known libraries. Many applications can be built upon MPC to protect the privacy of data,

including machine learning (see, e.g., [18–31] and references therein), federated learning (see, e.g., [32–

36]), data mining [37–40], auction [41–43], genomic analysis [44–46], securing databases (see [47] and

references therein), and blockchain [48–53]. In addition, some techniques underlying MPC protocols can

also be used to construct non-interactive zero-knowledge (ZK) proofs [54–61] based on the MPC-in-the-

head paradigm, scalable ZK proofs [62–71], threshold cryptography (see [72–79] and references therein),

and private set intersection (PSI) (see, e.g., [80–85]).

Secure multi-party computation guarantees privacy (meaning that the protocol reveals nothing but

the output) and correctness (meaning that the correct function is computed), among others (e.g., inde-

pendence of inputs, meaning that a party cannot choose its input as a function of the other parties’

inputs). The security properties must be guaranteed in the presence of adversarial behaviors. We mainly

consider two classic adversaries:

• Semi-honest: Semi-honest adversaries (a.k.a., passive adversaries) follow the protocol speciﬁcation

but may try to learn more than allowed from the protocol transcript;

• Malicious: Malicious adversaries (a.k.a., active adversaries) can run an arbitrary attack strategy

in its attempt to break the protocol.

According to the maximum number t of corrupted parties, there are typically two settings considered

in the literature: dishonest majority (n/2 ≤ t < n, particularly we often adopt t = n −1) and honest

majority (t < n/2), where n is the total number of parties. In addition to the basic properties (privacy

and correctness), some applications might further require fairness meaning that if one party obtains

output then so do all, or guaranteed output delivery (GOD) meaning that all parties always receive

output. To obtain better eﬃciency, we often consider a relaxed security notion, called security with

abort, which allows corrupted parties to prevent honest parties from receiving output after the corrupted

parties received their output. This security notion is standard in the dishonest-majority setting, as not all

functions can be computed fairly without an honest majority [86]. We focus on considering the notion of

security with abort and the static adversary that determines the set of corrupted parties at the onset of

protocol, which allows to achieve the best eﬃciency. In this paper, we mainly consider concretely eﬃcient

MPC protocols, and ignore the MPC protocols that have a good asymptotic complexity or optimal round

complexity, but their concrete eﬃciency is very low.

There are two main approaches for designing MPC protocols [87]: (1) the secret-sharing approach

(followed by [2–4]) that makes the parties interact for every non-linear gate of the circuit, and has a low

communication bandwidth but a number of rounds linear to the circuit depth; (2) the garbled-circuit

approach (followed by [1, 6]) that lets the parties construct an encrypted version of the circuit allowing to

be computed only once, and has a constant number of rounds but a large communication bandwidth. In

general, the secret-sharing approach is more suitable for low-latency networks such as local area network

(LAN), while the garbled-circuit approach will perform better in high-latency networks such as wide area

network (WAN).

There are a lot of concretely eﬃcient MPC protocols that have been proposed, and these MPC

protocols give a diﬀerent trade-oﬀ in terms of security and eﬃciency. Thus, it is not easy to make the

best choice of MPC protocols in concrete applications for non-experts. In addition, many techniques have

been developed for MPC, which makes it diﬃcult for new researchers to understand the techniques in a

short period. Through this survey, we aim to help the researchers, who are interested in MPC, rapidly

understand the recent development and some basic/key ideas of concretely eﬃcient MPC protocols, and

be able to make a better choice in terms of applying MPC protocols.

Page 2 of 43

Security and Safety, Vol. 1, 2021001

1.1 Our contribution

In this paper, we comprehensively survey the known work on concretely eﬃcient MPC protocols with

both semi-honest and malicious security. This survey not only covers the work in the dishonest-majority

setting, but also concerns on the recent development in the honest-majority setting. Our survey involves

not only secret-sharing based MPC but also garbled-circuit based MPC. We present the basic approaches

for designing concretely eﬃcient MPC protocols, and give the high-level ideas for the key techniques

underlying these MPC protocols. In particular, we give a uniform framework and view of MPC protocols

based on additive, Shamir, and replicated secret sharings. We also provide a high-level view of the recent

approach with sublinear communication to design correlated oblivious transfer (COT) that is a crucial

building block for dishonest-majority MPC. In addition, we describe one important application of MPC

(i.e., privacy-preserving machine learning, or PPML in short), and summarize the known PPML protocols

in terms of functionality, security, techniques and neural-network architectures as well as discussing

several key techniques for designing concretely eﬃcient PPML protocols. Furthermore, we propose several

challenges and interesting open problems to break through the eﬃciency of diﬀerently ﬂavored MPC

protocols, and also present some future work that need to be addressed for developing or deploying MPC.

Comparison with other MPC surveys. Recently, Lindell [88] presented a short MPC survey, which

gives an overview of the security of MPC, a summarization of MPC feasible results, an honest-majority

MPC framework based on Shamir secret sharing, two speciﬁc MPC protocols (i.e., PSI and threshold

RSA), a very short overview of dishonest-majority MPC, and several application examples of MPC. This

survey focuses on the notion and security of MPC and how MPC is being currently used, and does not

involve the recent development of MPC protocols which is addressed by our survey. Besides, Orsini [89]

gave a survey for only SPDZ-style MPC protocols in the dishonest-majority malicious setting. Compared

to the two surveys [88, 89], our survey is more comprehensive, presents an important MPC application

(i.e., PPML) and also gives interesting future work for MPC.

1.2 Organization

In Section 2, we deﬁne the necessary notation to be used in the subsequent main body, and then describe

the security and communication models for MPC and give a sketch of several basic building blocks of

MPC. We describe the development and the key techniques for MPC based on secret sharings (resp.,

garbled circuits) in Section 3 (resp., Section 4). We present the crucial building blocks for dishonest-

majority MPC in Section 5. In Section 6, we summarize the protocols that apply MPC to realize private

inference and training of machine learning, as well as several key techniques for PPML applications.

Finally, we conclude this survey, and propose open problems and future work for MPC.

2 Preliminaries

2.1 Notation

We use κ and ρ to denote the computational and statistical security parameters, respectively. In the

known MPC implementations, we often adopt κ = 128 and ρ = 40, where sometimes we also consider

ρ = 64 or ρ = 80. For two integers a, b with a < b, we denote by [a, b] the set {a, . . . , b} and by [a, b) the set

{a, . . . , b −1}. We use x ← S to denote sampling x uniformly at random from set S and x ← D to denote

sampling x according to distribution D. For bit-string x, we use lsb(x) to denote the least signiﬁcant bit

of x. For row vector x, we use x

to denote the ith component of x with x

the ﬁrst entry, and denote

by HW(x) the Hamming weight of x (i.e., the number of non-zero entries in vector x). For two families

of distributions X = {X

}

κ∈N

and Y = {Y

}

κ∈N

, we write X

≈ Y if X and Y are computationally

indistinguishable.

We use F to denote a ﬁnite ﬁeld deﬁned by a prime or a power of prime, and denote by |F| the size

of ﬁeld F. In particular, we often consider a binary ﬁeld F = F

and an arithmetic ﬁeld F = F

for a

large prime p. Let K be a ﬁeld extension of F of degree k. We ﬁx some monic, irreducible polynomial

f(X) of degree k and write K

∼

F[X]/f(X). Then, we can denote every element y ∈ K by a polynomial

+ y

· X + ··· + y

k−1

· X

k−1

over F, and view y as a vector (y

, y

, . . . , y

k−1

) ∈ F

. When we write

Page 3 of 43

Security and Safety, Vol. 1, 2021001

arithmetic expressions involving both elements of F and elements of K, it means that values in F are

viewed as polynomials lying in K with only constant terms. Speciﬁcally, we use F

to denote the degree-

κ extension ﬁeld of F

. In the context of MPC for Boolean circuits, we often use {0, 1}

, F

and F

interchangeably, and thus addition in F

or F

corresponds to XOR in {0, 1}

Most of the known MPC protocols model a function as a circuit. Speciﬁcally, circuit C over an arbi-

trary ﬁeld F is deﬁned by a set of input wires and output wires along with a list of gates of the form

(α, β, γ, T ), where α, β are the indices of the input wires of the gate, γ is the index of the output

wire of the gate, and T ∈ {ADD, MULT} is the type of the gate. If F = F

, then C is a Boolean

circuit with ADD = ⊕ and MULT = ∧. Otherwise, C is an arithmetic circuit where ADD/MULT cor-

responds to addition/multiplication in ﬁeld F. We let |C| denote the number of MULT gates in the

circuit.

We will use n and t to denote the number of total parties and the number of corrupted parties

respectively, unless otherwise speciﬁed. Sometimes, we call t as the corruption threshold.

2.2 Security and communication models

Security model. All security properties for MPC can be formalized in an Ideal/Real paradigm [90, 91],

which provides a modular way to prove security. The real-world execution where the parties interact with

semi-honest/malicious adversary A and execute a protocol Π is compared to the ideal-world execution

where the parties interact with a simulator S and an ideal functionality F. In the ideal word, F plays the

role of an incorruptible trusted party, and captures the security of MPC protocols. We use P

, . . . , P

denote n parties running a protocol. In the multi-party setting (i.e., n > 2), we often consider a rushing

adversary A, meaning that A is allowed to receive its incoming messages in a round before it sends its

outgoing message. If the adversary is allowed to be computationally unbounded, the protocol is said to be

information-theoretically secure. If the adversary is bounded to (non-uniform) probabilistic polynomial

time (PPT), the protocol satisﬁes the computational security.

The known MPC protocols mainly use two types of simulation models: stand-alone setting [91, 92] and

universal composability (UC) [90]. Compared to stand-alone model, UC model additionally involves an

environment Z which can determine the inputs of honest parties and receive the outputs from the honest

parties. This may make security proofs of MPC protocols somewhat more complex. While stand-alone

model only guarantees the security under the sequential composition, UC model has the property that

the protocols maintain their security, even though running concurrently with other (in)secure protocols.

According to the result from [93], we obtain that any MPC protocol in the stand-alone model, which is

proven secure with a black-box straight-line simulator and has the property the inputs of all parties are

ﬁxed before the protocol execution begins (referred as to start synchronization or input availability), is

also secure under concurrent composition.

Communication model. The default method of communication for MPC is authenticated channel,

which can be implemented in practice using the known standard techniques. In the multi-party setting,

all parties are also connected via point-to-point channels, and sometimes need also a broadcast channel. A

broadcast channel can be eﬃciently implemented using a standard 2-round echo-broadcast protocol [94],

as we only consider security with abort. The communication overhead of this broadcast protocol can

be signiﬁcantly improved by letting all parties send the hash outputs of received messages and aborting

if an inconsistent hash value is detected. Sometimes, the parties need to communicate over a private

channel, meaning that the messages sent over such channel are kept conﬁdential and authenticated. As

such, private channel can be established using the standard techniques.

2.3 Oblivious transfer and oblivious linear-function evaluation

Informally, oblivious transfer (OT) [95, 96] involves two parties where a sender inputs two messages

, m

) and a receiver inputs a choice bit b, and allows the receiver to obtain m

while keeping b

secret against the sender and m

1−b

conﬁdential against the receiver. We use an OT extension protocol to

generate a large number of OT correlations (see Section 5). Oblivious linear-function evaluation (OLE)

is an arithmetic generalization of OT to a large ﬁeld F, and is a special case of oblivious polynomial

Page 4 of 43

Security and Safety, Vol. 1, 2021001

evaluation introduced in [97]. Speciﬁcally, OLE is a two-party protocol between a sender and a receiver,

where the sender inputs u, v ∈ F, and the receiver inputs x ∈ F and obtains an output y = u · x + v ∈ F.

We discuss the development of OT/OLE and their variants in Section 5.

2.4 Commitment and coin-tossing

Commitment. In the dishonest-majority setting, MPC protocols often need a commitment scheme to

commit a value while keeping it secret (the hiding property), and then to open the value while keeping it

consistent with the one that has been committed (the binding property). To achieve high eﬃciency, the

commitment scheme is often constructed in the random-oracle model by deﬁning Commit(x) = H(x, r),

where x is a message, r is a randomness, and H : {0, 1}

∗

→ {0, 1}

2κ

is a cryptographic hash function

modeled as a random oracle.

Coin-tossing. A lot of MPC protocols with malicious security require the parties to generate mul-

tiple public randomness by executing a coin-tossing protocol, while guaranteeing that no malicious

parties can control the randomness or make them deviate from uniform distribution. In the dishonest-

majority setting, the coin-tossing protocol is constructed by that (1) every party P

commits a

random seed s

and then opens the seed; (2) every party computes s :=

i∈[n]

and then gen-

erates the public randomness with s and a pseudorandom generator (PRG) modeled as a random

oracle. In the honest-majority setting, the coin-tossing protocol is constructed in a totally diﬀerent

way. Speciﬁcally, all parties generate multiple random shares, and then open these shares as the pub-

lic randomness, where random shares can be generated very eﬃciently when a majority of parties are

honest.

3 MPC protocols based on secret sharings

Based on the secret-sharing approach, the concretely eﬃcient MPC protocols enable the parties to

send small messages per non-linear gate, but has a number of rounds linear to the depth of the

circuit being computed. For now, concretely eﬃcient MPC protocols mainly adopt three kinds of

linear secret-sharing schemes (LSSSs): additive secret sharing, Shamir secret sharing [98], and repli-

cated secret sharing (a.k.a., CNF secret sharing) [99, 100], where additive secret sharing is mainly

used for MPC protocols in the dishonest-majority setting, while Shamir and replicated secret shar-

ings are adopted for honest-majority MPC protocols. We ﬁrst recall the constructions of these LSSSs

in a uniform view. To achieve malicious security, additive secret sharing needs to be equipped with

information-theoretic message authentication codes (IT-MACs), and thus we deﬁne two types of IT-

MACs used in MPC with dishonest majority. Note that IT-MACs are unnecessary for Shamir/replicated

secret sharing in the honest-majority setting. Then, based on LSSSs, we describe how to con-

struct semi-honest MPC protocols with a uniform structure. Finally, we present how to transform

semi-honest MPC protocols to maliciously secure MPC protocols using the state-of-the-art checking

techniques.

3.1 Linear secret-sharing schemes

All the three kinds of LSSSs used in MPC are (n, t)-threshold secret sharing schemes, which enable

n parties to share secret x among the parties, such that no subset of t parties can obtain any infor-

mation on secret x, while any subset of t + 1 parties can reconstruct secret x. Additive secret sharing

can only be made for t = n − 1, while Shamir/replicated secret sharing allows any t < n (we often

adopt t < n/2 for honest-majority MPC). The three kinds of LSSSs are deﬁned over a ﬁeld F. While

additive/replicated secret sharing allows an any-sized ﬁeld (including F

), Shamir secret sharing requires

|F| > n. Below, we describe the constructions of these LSSSs and the useful procedures for designing MPC

protocols.

• Share(x): For x ∈ F, a dealer generates n shares x

, . . . , x

. By [x], we denote the sharing of x.

(a) Additive secret sharing: This is the simplest LSSS as far as we know. To share a value x ∈ F,

the dealer samples x

← F for i ∈ [1, n] such that

i∈[1,n]

= x, and sends x

to P

Page 5 of 43

评论收藏

内容反馈

隐私无忧

粉丝: 1w+
资源: 20

安全多方计算学习资料 - 6篇专著及论文

最新资源

安全多方计算学习资料 - 6篇专著及论文

PCA方面的资料，有专著也有Lecture

安全多方计算框架论文合集（持续更新）

论文研究-一种有效的信任协商多方安全计算模型.pdf

论文翻译 安全多方计算、混淆电路、隐私增强技术

安全多方计算及其在机器学习中的应用

安全多方计算及其在机器学习中的应用.docx

三维数据场可视化---清华大学学术专著

2021最新幼儿园管理档案-近三年发表（获奖）论文出版专著情况统计表.doc

参考资料-国家社科基金项目成果通讯鉴定表（专著类）.zip

论文研究-基于安全多方计算的隐私保护聚类挖掘 .pdf

6-4联邦学习与安全多方计算.pdf

GB-7713-87-科学技术报告、学位论文和学术_论文的编写格式

论文研究-基于《工业互联网安全体系理论与方法》的学术专著向教学资源转化探讨 .pdf

IEEE无线通信专著

科研信息检索平台设计与实现-计算机专业-毕业设计-毕业论文.doc

毕业论文资料查找技巧、盲审、评定与论文文献参考、摘要写法等常见问题

“联邦学习 区块链”多方安全计算引擎系统研究.pdf

人工智能-机器学习-安全多方量子计算理论与应用研究.pdf

ng-book2-angular-6-r68

RISC-V学习资料 RISC-V开放架构设计之道 The RISC-V Reader

毕业设计-JSP论文管理系统-毕业论文.doc

最新资源

论文翻译安全多方计算、混淆电路、隐私增强技术

“联邦学习区块链”多方安全计算引擎系统研究.pdf