1 of 37

One-way functions imply �secure multi-party computation in a quantum world, �(continued)

2 of 37

Recall: Oblivious Transfer

 

 

 

 

 

…

OT looks like a simple functionality, but is sufficient to build “multiparty computation”!

[Kil88, CvT95]

3 of 37

 

 

 

 

…

Security Against Malicious Receiver�

4 of 37

Security Against Malicious Receiver�(defined via “simulation”)

 

 

 

 

 

Ideal OT

 

computationally

 

 

 

 

 

…

Sim

 

5 of 37

[Crepeau, Kilian 88], [BBCS 92] Template for OT

 

 

 

 

 

 

 

 

 

 

 

 

 

 

6 of 37

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Set

[Crepeau, Kilian 88], [BBCS 92] Template for OT

 

Sampled from a 2-universal family of hash functions�(this is an information-theoretic object – more later)

7 of 37

 

 

 

 

 

 

 

 

 

 

 

 

Measurement check sub-protocol

 

 

 

 

 

 

 

 

2

4

[Crepeau, Kilian 88], [BBCS 92] Template for OT

8 of 37

 

 

 

 

 

 

 

 

 

 

 

 

Measurement check sub-protocol

 

 

 

 

 

 

 

 

2

4

Check consistency of

outcomes for matching bases

 

[Crepeau, Kilian 88], [BBCS 92] Template for OT

9 of 37

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Measurement check sub-protocol

 

Check consistency of

outcomes for matching bases

2

4

[Crepeau, Kilian 88], [BBCS 92] Template for OT

10 of 37

Aside: universal hash functions and “leftover hash lemma”

 

 

 

 

 

11 of 37

…So, commitments imply OT then?

12 of 37

Recall: Security Against Malicious Receiver�(defined via “simulation”)

 

 

 

 

 

Ideal OT

 

 

computationally

 

 

 

 

 

…

Sim

 

13 of 37

Security against malicious receiver

 

 

 

 

 

 

 

 

 

 

 

Subset of locations

 

 

 

 

 

 

 

 

14 of 37

 

Sim

 

 

Ideal OT

 

 

 

 

 

Security against malicious receiver

BB84 states

BB84 states

. . .

. . .

 

 

Measurement check

sub-protocol

 

 

 

15 of 37

Takeaway so far..

  • [CK88, BBCS92] Template for OT from commitments.

​

  • Security is a bit subtle, and basic commitments might not suffice.

​

  • It is simulation-based, and requires extracting the malicious party’s inputs.

16 of 37

 

17 of 37

Extractable commitments

 

 

 

b

. . .

 

18 of 37

Extractable commitments

 

Ext

 

 

b

. . .

b

 

19 of 37

Equivocal commitments

 

 

 

b

. . .

 

20 of 37

Equivocal commitments

Equiv

 

 

Equiv

. . .

 

21 of 37

Equivocal commitments

Equiv

 

 

Equiv

. . .

 

 

Equiv

 

 

22 of 37

Security against malicious receiver: extract b from R

 

 

Ideal OT

 

 

 

 

 

Sim

BB84 states

BB84 states

. . .

. . .

 

 

Measurement check

sub-protocol

 

 

23 of 37

Security against malicious receiver: extract b from R

 

Sim

 

 

Ideal OT

 

 

 

 

 

A “dummy” encryption

 

24 of 37

 

 

Sim

 

Ideal OT

 

 

 

 

 

25 of 37

 

 

 

 

 

 

 

 

 

 

Subset of locations

 

Sim

 

 

 

 

 

 

 

 

26 of 37

Don’t measure right away!

 

 

 

 

 

 

 

 

 

Subset of locations

 

Sim

Equiv

Equiv

Equiv

Equiv

Equiv

Equiv

Measure only the subset

of test locations, and open to the correct outcome by leveraging equivocality

 

 

 

27 of 37

Recap so far..

  • [CK’88, BBCS’92] Template for OT from commitment.
  • [DFLSS’09] Secure when instantiated with an extractable and equivocal commitment.

So, can such a commitment be built?

28 of 37

Commitments from one-way functions [Naor91]

Equivocal commitment

Extractable commitment

Extractable and equivocal commitment

BCKM’21: Extractable and Equivocal commitment from one-way functions

1. (Black-box) equivocality compiler

2. Equivocal to Extractable transformation� (using quantum communication)

1

1

2

Two building blocks:

29 of 37

[CK88], [BBCS92] Template for commitment

 

 

 

 

 

 

 

 

 

 

 

 

 

 

30 of 37

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Subset of locations

 

 

 

 

 

 

[CK88], [BBCS92] Template for commitment

31 of 37

 

 

 

 

 

 

 

 

 

 

 

 

 

?

 

Maybe we can turn one type of commitment into another…

How is this useful if we need commitments to build commitments?

[CK88], [BBCS92] Template for commitment

32 of 37

From one commitment to another!

 

 

 

 

 

 

 

 

 

 

 

 

 

Subset of locations

Equiv

Equiv

Equiv

Equiv

Equiv

Equiv

33 of 37

 

Ext

 

 

 

 

 

 

 

Subset of locations

 

 

 

Equiv

Equiv

Equiv

Equiv

Equiv

Equiv

 

We have turned an equivocal commitment into extractable!

From one commitment to another!

34 of 37

Commitments from one-way functions [Naor91]

Equivocal commitment

Extractable commitment

Extractable and equivocal commitment

BCKM’21: Extractable and Equivocal commitment from one-way functions

1. (Black-box) equivocality compiler

2. Equivocal to Extractable transformation� (using quantum communication)

1

1

2

Two building blocks:

35 of 37

Notice:

In the final OT protocol, both the sender and the receiver are sending BB84 states!

36 of 37

Notice:

In the final OT protocol, both the sender and the receiver are sending BB84 states!

BB84 states

 

 

 

 

. . .

37 of 37

Notice:

In the final OT protocol, both the sender and the receiver are sending BB84 states!

BB84 states

 

 

 

 

BB84 states

…

. . .