Revisiting the Spymasters: The Double Agent Problem
Best of Both Worlds
Revisiting the Spymasters Double Agent Problem
Anasuya Acharya
Carmit Hazay
Oxana Poburinnaya
Muthuramakrishnan Venkitasubramaniam
Bar-Ilan University
Bar-Ilan University
Georgetown University
Motivation: Bringing People of Different Beliefs
2
Motivation: Resistance to Future Attacks
3
Motivation: David Versus Many Goliaths [CDG87]
4
When is MPC
Feasible?
ℿ
Together: Impossible in the plain model
Security from Unbounded Adversaries
possible for honest majority
Security from Arbitrary Corruption
possible for PPT adversaries
5
One Protocol
Secure in the presence of
●
Unbounded adversary for a limited
adversary structure
●
Fall-back -
PPT adversary corrupting
any subset of the parties
similar notion considered in [Cha89]
MPC with
Fallback Security
ℿ
ℿ
6
Related Work
2PC with one unbounded and one PPT corruption – round optimal protocols
[KM20, KO04, GMPP16, BPS22]
David versus Multiple Goliaths
[CDG87]
●
Semi-Honest unconditional security for a
designated party
and arbitrary PPT corruption
The Spymaster’s Double Agent Problem
[Cha89]
●
Semi-Honest security for
<n/2
unbounded corruption and arbitrary PPT corruption
●
Malicious security for
<n/3
unbounded corruption and
<n/2
PPT corruption
7
Our Results
Theorem.
Assuming broadcast,
any n-party functionality
can be realized by a protocol with
malicious fallback security
for adversary structure
Z with semi-honest security
for unbounded
adversaries.
Remark 1. Malicious security for
semi-honest adversary structure
– security with abort, broadcast
Remark 2.
Black-box in underlying assumptions
– improves over [Cha89, CDG87]
Remark 3. Asymptotically
optimal round complexity
– improves over [CDG87] round complexity
8
Does this Solve our Problems?
9
Semi-Honest Fallback Security
10
Any Functionality
S
e
m
i
-
H
o
n
e
s
t
S
e
c
u
r
e
U
n
b
o
u
n
d
e
d
A
:
a
l
l
-
b
u
t
-
P
n
P
P
T
A
:
a
n
y
s
u
b
s
e
t
C
1
=Enc(pk,x
1
)
{C}Ev(
f
,
{C})
C
2
C
3
C
n-1
C
n
David vs Multiple Goliaths – TFHE
11
pk, [sk]
pk, [sk]
pk, [sk]
pk, [sk]
pk, [sk]
P
1
P
2
P
3
P
n-1
P
n
Any Functionality
S
e
m
i
-
H
o
n
e
s
t
S
e
c
u
r
e
U
n
b
o
u
n
d
e
d
A
:
a
l
l
-
b
u
t
-
P
n
P
P
T
A
:
a
n
y
s
u
b
s
e
t
G
b
(
f
)
→
G
r
1
r
2
r
3
r
n-1
G
Δ
=
x
⊕
𝝀
OT
labels
Δ
X
f(x) = Ev(G, X)
12
David vs Multiple Goliaths – Dist. GC
P
1
P
2
P
3
P
n-1
P
n
Compiling to
Fallback Security
n-Party Protocol
Compiler
S
e
m
i
-
H
o
n
e
s
t
S
e
c
u
r
e
U
n
b
o
u
n
d
e
d
A
:
<
n
/
2
p
a
r
t
i
e
s
P
P
T
A
:
a
n
y
s
u
b
s
e
t
13
ℿ
[ ]
[ ]
[ ]
[ ]
ℿ
Malicious Fallback Security
14
Protocol in the Online-Offline Paradigm
n
-
P
a
r
t
y
O
f
f
l
i
n
e
P
r
o
t
o
c
o
l
Authenticated Multiplication Triples
n
-
P
a
r
t
y
O
n
l
i
n
e
P
r
o
t
o
c
o
l
Functionality F using Authenticated Triples
n
-
P
a
r
t
y
C
o
m
m
i
t
m
e
n
t
F
c
o
m
Maliciously
Fallback
Secure
n
-
P
a
r
t
y
C
o
m
m
i
t
m
e
n
t
Maliciously
Fallback
A
u
t
h
e
n
t
i
c
a
t
e
d
T
r
i
p
l
e
s
Semi-Honest
Fallback
15
Maliciously
Fallback
Secure
Inspired by [HVW20]
Malicious
Unbounded
Secure
D
i
s
h
o
n
e
s
t
M
a
j
o
r
i
t
y
i
n
t
h
e
F
c
o
m
-
h
y
b
r
i
d
[DPSZ12]
Fallback Secure
Commitment Protocol
n-Party
Commitment
Protocol
M
a
l
i
c
i
o
u
s
l
y
S
e
c
u
r
e
U
n
b
o
u
n
d
e
d
A
:
a
n
y
s
u
b
s
e
t
i
n
Z
S
P
P
T
A
:
a
n
y
s
u
b
s
e
t
x
16
F
com
x
Fallback Secure Commitment Protocol
17
Hiding
Binding
2
-
p
a
r
t
y
S
t
a
t
i
s
t
i
c
a
l
l
y
H
i
d
i
n
g
C
o
m
m
i
t
m
e
n
t
s
Extractable using Statistical
ZK Arguments
2
-
p
a
r
t
y
S
t
a
t
i
s
t
i
c
a
l
l
y
B
i
n
d
i
n
g
C
o
m
m
i
t
m
e
n
t
s
2
-
p
a
r
t
y
S
t
a
t
i
s
t
i
c
a
l
l
y
B
i
n
d
i
n
g
C
o
m
m
i
t
m
e
n
t
s
Extractable using ZK
Proof of Knowledge
S
e
c
r
e
t
S
h
a
r
i
n
g
18
Fallback Secure Commitment Protocol
x, r, { [x]i
}, r
i
Com
SB
([x]
i
;r
i
)
Com
SH
(x;r)
x
SZKAoK(x,r; c)
ZKPoK([x]
i
,r
i
; c
i
)
used in look-ahead trapdoor commitment scheme [PW09]
Share
Zs
(x)→ { [x]i
}
Future Work
Best-of-both-worlds for
GOD and security with abort
[Kat07, IKK+11, PRS20]
19
Unbounded
Adversary
(Security with Abort)
This Work
PPT Adversary
(Security with Abort)
Guaranteed Output
Delivery
Thank You!
https://ia.cr/2023/1013
20
Delve into the intriguing world of spymaster tactics with a focus on the double agent problem and the feasibility of secure multiparty computation protocols. Explore motivations, related works, and groundbreaking results in this complex domain.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Best of Both Worlds Revisiting the Spymasters Double Agent Problem Anasuya Acharya Carmit Hazay Oxana Poburinnaya Muthuramakrishnan Venkitasubramaniam Bar-Ilan University Bar-Ilan University Georgetown University
When is MPC Feasible? Security from Unbounded Adversaries possible for honest majority Security from Arbitrary Corruption possible for PPT adversaries Together: Impossible in the plain model 5
MPC with Fallback Security One Protocol Secure in the presence of Unbounded adversary for a limited adversary structure Fall-back - PPT adversary corrupting any subset of the parties similar notion considered in [Cha89] 6
Related Work 2PC with one unbounded and one PPT corruption round optimal protocols [KM20, KO04, GMPP16, BPS22] David versus Multiple Goliaths [CDG87] Semi-Honest unconditional security for a designated party and arbitrary PPT corruption The Spymaster s Double Agent Problem [Cha89] Semi-Honest security for <n/2 unbounded corruption and arbitrary PPT corruption Malicious security for <n/3 unbounded corruption and <n/2 PPT corruption 7
Our Results Theorem. Assuming broadcast, any n-party functionality can be realized by a protocol with malicious fallback security for adversary structure Z with semi-honest security for unbounded adversaries. Remark 1. Malicious security for semi-honest adversary structure security with abort, broadcast Remark 2. Black-box in underlying assumptions improves over [Cha89, CDG87] Remark 3. Asymptotically optimal round complexity improves over [CDG87] round complexity 8
David vs Multiple Goliaths TFHE pk, [sk] pk, [sk] P1 Pn Cn C1=Enc(pk,x1) pk, [sk] P2 C2 {C} Any Functionality Semi-Honest Secure Unbounded A : all-but-Pn PPT A : any subset pk, [sk] P3 C3 Ev(f, {C}) pk, [sk] Pn-1 Cn-1 11
David vs Multiple Goliaths Dist. GC r1 P1 Pn G P2 r2 = x ? Gb(f) G Any Functionality Semi-Honest Secure Unbounded A : all-but-Pn PPT A : any subset P3 r3 OT labels X Pn-1 f(x) = Ev(G, X) rn-1 12
Compiling to Fallback Security [ ] [ ] [ ] [ ] n-Party Protocol Compiler Semi-Honest Secure Unbounded A : < n/2 parties PPT A : any subset 13
Protocol in the Online-Offline Paradigm n-Party Offline Protocol Authenticated Multiplication Triples n-Party Online Protocol Functionality F using Authenticated Triples Maliciously Fallback Secure Inspired by [HVW20] Malicious Unbounded Secure Dishonest Majority in the Fcom-hybrid [DPSZ12] Authenticated Triples n-Party Commitment n-Party Commitment Fcom Maliciously Fallback Semi-Honest Fallback Maliciously Fallback Secure 15
Fcom Fallback Secure Commitment Protocol x x n-Party Commitment Protocol Maliciously Secure Unbounded A : any subset in ZS PPT A : any subset 16
Fallback Secure Commitment Protocol 2-party Statistically Hiding Commitments 2-party Statistically Binding Commitments Hiding Secret Sharing Binding Extractable using Statistical ZK Arguments 2-party Statistically Binding Commitments Proof of Knowledge Extractable using ZK 17
Fallback Secure Commitment Protocol x ComSH(x;r) SZKAoK(x,r; c) ShareZs(x) { [x]i} ComSB([x]i;ri) ZKPoK([x]i,ri; ci) x, r, { [x]i}, ri used in look-ahead trapdoor commitment scheme [PW09] 18
PPT Adversary (Security with Abort) Future Work Best-of-both-worlds for GOD and security with abort [Kat07, IKK+11, PRS20] This Work Unbounded Adversary (Security with Abort) Guaranteed Output Delivery 19
Thank You! https://ia.cr/2023/1013 20
