CryptoNet

1

Cryptography

Content Routing

​

Anca Nitulescu

For Privacy

In

Routing

Content

Content Routing: Storage Network

3

Consumer C Provider P

Common interface for content routing:

​

Provide: Make content available for other peers in the network

Resolve: Find the peers storing the content in the network.

Fetch: Fetches content from a provider.

​

Content ID: When you add a file to IPFS, your file is hashed, and given a unique fingerprint called a content identifier (CID). This CID acts as a permanent record of your file as it exists at that point in time.

Routing: When other nodes look up your file, they ask their peer nodes who's storing the content referenced by the file's CID.

​

​

Fetch

Content Routing: Setting

4

Consumer C Provider P

Router R

Actors:

​

• Content Providers P
• Content Consumers C
• Content Routers R

​

- Providers store data D and make it available to Consumers C.

- Providers and consumers find each other through Routers.

- Advertisements or provider records rec include content identifiers CID and propagate them to the Routers.

- Consumers query the routers using CID, getting 0 or corresponding provider records (PIDs).

- Providers and Consumers are “light clients” and Routers do most of the work in the routing system.

​

Content Routing: Challenges

5

Consumer C Provider P

Router R

Content Routing in P2P networks

​

​

• No central entity orchestrating the storage and discovery of content
• No central directory to find how to reach every peer in the network.

​

• The content routing network must hold at least for:
• 10¹⁵ content IDs each
• 10⁹ devices to store the content

​

​

Content Routing: Privacy

6

Consumer C Provider P

Router R

Writer Privacy: Providers P can provide content to some consumers, without unauthorized consumers, routers, or adversaries learning what the provider has published.

​

• identity writer-privacy: adversaries cannot learn who provided some content. Adversaries may see advertisements and learn what data they are associated to, but not learn the identity of the provider.
• content writer-privacy: adversaries cannot learn what content is being provided. Adversaries may detect that a provider is publishing advertisements, but not learn what data the advertisements are about.

​

Content Routing: Privacy

7

Consumer C Provider P

Router R

Reader Privacy: Consumers C can find content (lookup records) without unauthorized providers, routers, or adversaries learning what the consumer has requested.

​

• identity reader-privacy: adversaries cannot learn who is looking for some content. Adversaries may see requests and learn what data they are associated to, but not learn the identity of the consumer.
• content reader-privacy: adversaries cannot learn what content is being searched. Adversaries may detect that a particular consumer is making requests, but not learn what data the requests are about.
• action reader-privacy: adversaries cannot learn that a particular consumer has taken any action. This is difficult to achieve, as solutions tend to require slow round-based protocols that produce lots of noise.
• full reader-privacy: no entity learns what entities request content or what content is being requested, at all. This is extremely difficult.

​

​

Cryptographic Solutions

​

Privacy-Preserving Search

1. Searchable Encryption

9

​

​

​

Deterministic Encryption: exact match

​

Property-Preserving Encryption: approximative match

​

Order-Preserving Encryption: range queries

​

Hiding everything implies accessing the entire data

​

Drawbacks:

Leaks repetitions

Some existing attacks to recover data

Data is encrypted under Consumer’s key…

​

Searchable

Encryption

2. Fully Homomorphic Encryption

10

​

Provider encrypts its data.

The search function is evaluated over encrypted data.

Consumer gets the encrypted result.

​

Avantages:

Privacy from the encryption

No interaction

​

Drawbacks:

Not efficient

Costly communication

Key management ?

Ciphertext

Fully Homomorphic

Encryption

Encrypted result

Query

Data

3. Multi-Party Computation

11

​

​

​

​

​

​

​

​

​

2-Party

Computation

​

​

Provider sends records in clear to Router.

Consumer and Router interact in order to execute the search.

Needs multiple rounds of communication between the two parties.

​

Avantages:

Perfect Security

Performant�

Drawbacks:

Costly in communication

Requires interaction and synchronisation

​

4. Private Information Retrieval

12

​

​

Consumer queries Router while hiding the content she is after.

​

Avantages:

Leaks no info on the index

​

Drawbacks:

May require more than one non-communicating Router with identical copies of the database

​

​

Private Information

Retrieval

Query

Data

?

5. Private Set Intersection

13

​

​

Consumer queries Router Content id

Router privately computes intersection between the queried content id and its record

Avantages:

Small Communication via FHE

​

Drawbacks:

Router may need to pre-process DB (expensive, not updatable)

FHE limitations

​

​

​

Private Information

Retrieval

Query S

Data

?

S

S

1. Searchable Encryption

Index-Based Searchable Encryption

15

Based on keywords and trapdoors

Each query allows for a partial decryption

​

​

Searchable

Encryption

Index-Based Searchable Encryption

16

Based on keywords and trapdoors

Each query allows for a partial decryption

Consumer sends a trapdoor

Router decrypts the index corresponding to the trapdoor

​

Searchable

Encryption

Index-Based Searchable Encryption

17

Based on keywords and trapdoors

Each query allows for a partial decryption

Consumer sends a trapdoor

Router decrypts the index corresponding to the trapdoor

Leakage:

Static DB

- reveals search pattern - repetitions

​

Dynamic DB

- updates leak what record was updated

- deletions leak what record was deleted

​

​

​

​

Searchable

Encryption

Solution for Private Content routing?

18

​

Provider:

- encrypts content id (deterministic/hash)

- encrypts provider id (randomized)

- generates a trapdoor for each content id (decryption key)

​

​

​

Searchable

Encryption

Provider

Fonctionnement - Index-Based Searchable Encryption

19

​

Provider:

- encrypts content id (deterministic/hash)

- encrypts provider id (randomized)

- generates a trapdoor for each content id (decryption key)

​

​

Router:

- has the encrypted table

​

​

​

​

​

Searchable

Encryption

Fonctionnement - Index-Based Searchable Encryption

20

​

Provider:

- encrypts content id (deterministic/hash)

- encrypts provider id (randomized)

- generates a trapdoor for each content id (decryption key)

​

​

Router:

- has the encrypted table

​

Consumer:

- encrypts the content id (hash)

- sends ciphertext and trapdoor

​

​

​

Searchable

Encryption

Fonctionnement - Index-Based Searchable Encryption

21

​

Provider:

- encrypts content id (deterministic/hash)

- encrypts provider id (randomized)

- generates a trapdoor for each content id (decryption key)

​

​

Router:

- has the encrypted table

​

Consumer:

- encrypts the content id (hash)

- sends ciphertext and trapdoor

​

Router:

- trapdoor allows to decrypt the provider id for queried cid

​

​

​

​

Searchable

Encryption

Attacks - Index-Based Searchable Encryption

22

Update the table

Provider

- encrypts the content id (hash)

- adds new indexes

​

​

​

Searchable

Encryption

#22

Attacks - Index-Based Searchable Encryption

23

Update the table

Provider

- encrypts the content id (hash)

- adds new indexes

​

Router

- receives new ciphertexts

​

​

​

Searchable

Encryption

#22

Attacks - Index-Based Searchable Encryption

24

Update the table

Provider

- encrypts the content id (hash)

- adds new indexes

​

Router

- receives new ciphertexts

​

Leakage

- search pattern

- adding new indexes reveals info about Content IDs

​

​

Searchable

Encryption

#22

Attacks - Index-Based Searchable Encryption

25

Update the table

Provider

- encrypts the content id (hash)

- adds new indexes

​

Router

- receives new ciphertexts

​

Leakage

- search pattern

- adding new indexes reveals info about Content IDs

- deleting indexes reveals information about Content IDs

​

​

Searchable

Encryption

#5

References

26

“Oblivious RAMs” [Ost90,GO96]

– Optimal security (even hides access pattern)

– Poly-logarithmic number of rounds

​

“Practical techniques for searches on encrypted data” [SWP00]

– First specific construction (PRGs, PRFs, PRPs)

– Limitations: leaks information; inadequate security definition (IND-CPA)

​

“Secure Indexes” [Goh03]

– IND2-CKA: semantic security against chosen-keyword attacks

– Efficient and IND2-CKA construction (PRFs, Bloom filters)

​

“Privacy Preserving Keyword Searches on Remote Encrypted Data” [CM05]

– Simulation-based security definition

– Two constructions (PRFs,PRPs)

​

“Searchable Symmetric Encryption: Improved Definitions and Efficient Constructions,” [CGKO06]

– Proposed four new security definitions

– Two new efficient constructions for SSE IND2-CKA: Indistinguishability against Chosen-Keyword Attacks

2. Fully

Homomorphic

Encryption

​

FHE

28

​

Encrypt

​

​

​

​

Evaluate

​

​

​

​

​

​

​

Decrypt

Compute on ciphertexts

Ciphertexts

Fully Homomorphic

Encryption

Data

Encrypted result

Encrypted input

Encrypted result

FHE

29

​

Encrypt

​

​

​

​

Evaluate

​

​

​

​

​

​

​

Decrypt

⊕

​

​

=

7

2

13c82ea37b844ed03c

0dc1946c1158e7a9cd

6216d5bb3d78a75f24

9

Compute on ciphertexts

Ciphertexts

Fully Homomorphic

Encryption

Data

Encrypted result

Encrypted input

Encrypted result

6216d5bb3d78a75f24

Limitations of FHE

What model of computation ? - Boolean Circuits

Is this sufficient ? - Yes: {XOR, AND} is Turing-complete

And in practice ? - need to compile any algorithm in a Boolean Circuit

​

Privacy-Preserving Search:

​

Compare two integers A, B (2 bits)

​

​

​

​

​

​

​

​

Limitations of FHE

What model of computation ? - Boolean Circuits

Is this sufficient ? - Yes: {XOR, AND} is Turing-complete

And in practice ? - need to compile any algorithm in a Boolean Circuit

​

Privacy-Preserving Search:

​

Compare two integers A, B (2 bits)

​

​

​

​

​

​

​

​

Limitations of FHE

What model of computation ? - Boolean Circuits

Is this sufficient ? - Yes: {XOR, AND} is Turing-complete

And in practice ? - need to compile any algorithm in a Boolean Circuit

​

Privacy-Preserving Search:

​

Compare two integers A, B (2 bits)

​

A = A₀ A₁

B = B₀ B₁

​

​

​

​

​

​

​

Limitations of FHE

What model of computation ? - Boolean Circuits

Is this sufficient ? - Yes: {XOR, AND} is Turing-complete

And in practice ? - need to compile any algorithm in a Boolean Circuit

​

Privacy-Preserving Search:

​

Compare two integers A, B (2 bits)

​

A = A₀ A₁

B = B₀ B₁

​

Compilation

• expensive to represent as Boolean circuit
• lost in performance in practice

​

​

​

​

​

Better New FHE

​

TFHE: - allow to evaluate a gate MUX

- fast bit-wise comparison

- fast look-up tables

​

0 / 1

1

0

r₀

r₁

r_{0 / 1}

Better New FHE

​

TFHE: - allow to evaluate a gate MUX

- fast bit-wise comparison

- fast look-up tables

​

0 / 1

1

0

r₀

r₁

r_{0 / 1}

I

Comparing two integers A, B (2 bits)

​

A = a₀ a₁

B = b₀ b₁

​

b₁ if a₁ ≠ b₁ b₀ if a₀ ≠ b₀

r₁ = r₀ =

1 else r₁ else

​

r₀ = (A ≤ B )

Better New FHE

Comparing two integers A, B (2 bits)

​

A = a₀ a₁

B = b₀ b₁

​

b₁ if a₁ ≠ b₁ b₀ if a₀ ≠ b₀

r₁ = r₀ =

1 else r₁ else

​

r₀ = (A ≤ B )

I

0

0

​

0

​

I

​

TFHE: - allow to evaluate a gate MUX

- fast bit-wise comparison

- fast look-up tables

​

Better New FHE

​

CKKS: - Numerical method

- Evaluates polynomials on integers

- approximative comparison based on Taylor series

Better New FHE

​

CKKS: - Numerical method

- Evaluates polynomials on integers

- approximative comparison based on Taylor series

Comparing two integers or reels a, b

​

Idea : Write the comparison function using an approximation based on polynomials

→ polynomial degree = precision

→ better precision = bigger cost

→ pays off only by parallelising multiple comparison

→ amortised cost

​

*variable t decides precision

approximation for square root

with

Wilkes Method (1951)

Fully Homomorphic Encryption Landscape

TFHE

BV

• First Schemes (2009-10)
• Gentry-Halevi’11:

→ ad-hoc assumption

→ one bit operation = 30 minutes

• Optimised Circuit FHE (2011-12)
• Brakerski-Vaikuntanathan’11 :

→ assumption: Approximate eigenvector

→ fast bootstrapping (< .1 seconde)

→ unpractical

​

• Gentry-Halevi-Smart’12 :

→ circuit of 30,000 gates = 36 hours

​

• Modern Schemes (2012 - present)
• Brakerski-Gentry-Vaikuntanathan (BGV’12)

→ assumption = RLWE

→ circuit of 30,000 gates = 4 -15 minutes

• Gentry-Sahai-Waters (GSW’13)

→ assumption = LWE

→ encryption of one bit = big matrix

→ compute a NAND gate = matrix multiplication

→ asymmetric multiplication C₁₂ = c₁ ⊗ c₂ and C₂₁ = c₂ ⊗ c₁

→ C₁₂ = C₂₁ (they both encrypt the product b₁b₂= b₂b₁).

→ asymmetric noise - left factor is dominant

• Practical schemes
• Cheon-Kim-Kim-Song (CKKS, 2016)
• Chillotti-Gama-Georgieva-Izabachène (TFHE, 2016)

​

Gentry

BHS

BGV

GSW

2009

2011

2012

2015

CKKS

FHE: Performances for Comparison

Bit-wise comparison with selector

​

​

​

​

TFHE - integers of 32-bits = 3,3 seconds

​

​

Integer comparisons with approximation

​

​

​

​

​

CKKS - total time for 2¹⁶ pairs of 32-bits integers = 230 s

- precision 2^-14 = most significant 14 bits

- amortisation: 3,5 ms per comparison

​

0

0

​

0

​

Boolean Circuit with no selector

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

Schemes BV, GHS, BGV

a₁ a₀ b₁ b₀

​

Libraries FHE

3. MPC

Interactive Solution

MPC - goals

43

x₁ x₂

​

​

​

​

​

​

​

​

Framework for computation between parties who do not trust each other.

​

​

Examples:

• elections,
• auctions,
• distributed data mining,
• database privacy

Multi-Party

Computation

x₃ x₄

f(x₁, x₂, x₃, x₄) = (y₁, y₂ ,y₃ ,y₄ ) = y

​

MPC - goals

44

x₁ x₂

​

​

​

​

​

​

​

​

Framework for computation between parties who do not trust each other.

​

​

Examples:

• elections,
• auctions,
• distributed data mining,
• database privacy

​

Goals: preserve the privacy of each player's inputs and guarantee the correctness of the computation.

Multi-Party

Computation

x₃ x₄

f(x₁, x₂, x₃, x₄) = (y₁, y₂ ,y₃ ,y₄ ) = y

​

MPC - goals

45

​

​

​

​

​

​

​

​

Trusted party:

All of these tasks can be easily computed by a trusted third party

​

Security :

• Same guarantees without involving a trusted third party
• Provide an exact problem definition
• Adversarial power
• Network model
• Meaning of security
• Prove that the protocol is secure - by reduction to an assumed hard problem

Multi-Party

Computation

f(x₁, x₂, x₃, x₄) = (y₁, y₂ ,y₃ ,y₄ ) = y

​

x₁ x₂

x₃ x₄

MPC - goals

​

Preprocessing:

• Independent of x,y
• Typically only depends on size of f
• Uses public key crypto technology (slower)

​

Online:

• Uses only information theoretic tools
• Runs in order of magn. faster

​

Reconstruction:

• The intended parties learn the result of f

​

​

​

​

​

Multi-Party

Computation

Preprocessing

Online

Reconstruction

f(x₁, x₂, x₃, x₄) = (y₁, y₂ ,y₃ ,y₄ ) = y

​

y = f(x)

correlated

randomness

MPC General View

​

Multi-Party

Computation

f(x₁, x₂, x₃, x₄) = y

Preprocessing

Online

Reconstruction

f(x₁, x₂, x₃, x₄) = (y₁, y₂ ,y₃ ,y₄ ) = y

​

y = f(x)

MPC - Example

48

Salary s₁ = 5 000 z₁= 7 400

Mask m = 2 400

z₁ = 2 400 + 5 000

​

Example : Compute the average salary without revealing the salary of each employee.

​

Here Bob runs a MPC protocol with his colleagues to learn the average salary.

​

​

MPC - Example

49

z₂ = 10 400

Salary s₁ = 5 000 z₁= 7 400 Salary 3 000

Mask m = 2 400

z₁ = 2 400 + 5 000 z₂ = 7 400 + 3 000

​

Example : Compute the average salary without revealing the salary of each employee.

​

Here Bob runs a MPC protocol with his colleagues to learn the average salary.

​

​

MPC - Example

50

z₂ = 10 400

z₄ = 18 400

Salary s₁ = 5 000 z₁= 7 400 Salary 3 000

Mask m = 2 400

z₁ = 2 400 + 5 000 z₂ = 7 400 + 3 000

Salary 4 000 Salary 4 000

z₃ = 14 400

z₄ =14 400 + 4 000 z₃ = 10 400 + 4 000

1. Average = z₄/4 = 18 400 /4
2. Average = z₄/4 – m = 18 400 /4 – 2 400
3. Average = ( z₄ – s₁ ) /4 = (18 400 – 5 000 ) /4
4. Average = ( z₄ – m )/4 = (18 400 – 2 400 ) /4

​

Example : Compute the average salary without revealing the salary of each employee.

​

Here Bob runs a MPC protocol with his colleagues to learn the average salary.

​

What computation should Bob make in order to learn the average salary?

​

​

MPC - Example

51

1. Average = z₄/4 = 18 400 /4
2. Average = z₄/4 – m = 18 400 /4 – 2 400
3. Average = ( z₄ – s₁ ) /4 = (18 400 – 5 000 ) /4
4. Average = ( z₄ – m )/4 = (18 400 – 2 400 ) /4

​

Solution : D. Sum of salaries = Masked Sum – Random Mask = z₄ – m

z₂ = 10 400

z₄ = 18 400

Salary s₁ = 5 000 z₁= 7 400 Salary 3 000

Mask m = 2 400

z₁ = 2 400 + 5 000 z₂ = 7 400 + 3 000

Salary 4 000 Salary 4 000

z₃ = 14 400

z₄ =14 400 + 4 000 z₃ = 10 400 + 4 000

​

Example : Compute the average salary without revealing the salary of each employee.

​

Here Bob runs a MPC protocol with his colleagues to learn the average salary.

​

What computation should Bob make in order to learn the average salary?

​

​

MPC - Security

52

z₄ =14 400 + 4 000 z₃ = 10 400 + 4 000

z₂ = 10 400

z₄ = 18 400

z₁= 7 400

z₁ = 2 400 + 5 000 z₂ = 7 400 + 3 000

​

We need to make sure that an adversary cannot learn the private data of the honest parties.

​

We assume that communication channels are private and authenticated.

​

​

​

Security Model: The adversary is inside the system and corrupts some of the parties

• Semi-honest (passive) – Corrupted players follow the protocol but try to learn more → private computation

​

​

z₃ = 14 400

MPC - Security

53

​

We need to make sure that an adversary cannot learn the private data of the honest parties.

​

We assume that communication channels are private and authenticated.

​

​

​

Security Model: The adversary is inside the system and corrupts some of the parties

• Semi-honest (passive) – Corrupted players follow the protocol but try to learn more → private computation

​

• Malicious (active) – Corrupted players can collaborate in any way and misbehave arbitrarily → secure computation

​

z₂ = 10 400

z₄ = 7 000

Salary 4 000 Salary 4 000

z₃ = 14 400

z₄ = 3 000 + 4 000 z₃ = 3 000

Salary s₁ = 5 000 z₁= 7 400 Salary 3 000

Mask m = 2 400

z₁ = 2 400 + 5 000 z₂ = 7 400 + 3 000

z₃ = 3 000

MPC - Security

54

​

Security is defined by the types of attacks considered:

Adversary type:

​

• Semi-honest (passive)

​

​

• Malicious (active)

​

​

Number of corrupted parties t among n

• Honest Majority t < n/2
• Dishonest Majority t ≥ n/2

​

​

Security with Output Delivery

​

/

55

Corrupted parties t

Total parties n

* Shannon Information Theory

​

MPC

from

secret

sharing

MPC - Arithmetic Circuits

57

Model of Computation: Represent the function as Arithmetic/Boolean circuit C

Limiting Factor : Number of multiplications

​

​

MPC from Secret Sharing

The GMW/BGW* Approach:

​

● The (public) function being computed is written as a circuit

​

*[GMW87] Oded Goldreich, Silvio Micali, Avi Wigderson. How to prove all NP- statements in zero-knowledge, and a methodology of cryptographic protocol design.

[BGW88 ] M. Ben-Or, S. Goldwasser, A. Wigderson. Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation.

f (x,y,z)

x

​

y

​

​

z

​

​

MPC from Secret Sharing

59

f (x,y,z)

x

​

y

​

​

z

​

​

z = z₁ + z₂ + z₃

​

x = x₁ + x₂ + x₃

​

​

y = y₁ + y₂ + y₃

​

​

The GMW/BGW* Approach:

​

● The (public) function being computed is written as a circuit

● Each participant secret-shares their private input

​

MPC from Secret Sharing

60

f (x,y,z)

x

​

y

​

​

z

​

​

z = z₁ + z₂ + z₃

​

x = x₁ + x₂ + x₃

​

​

y = y₁ + y₂ + y₃

​

​

x₂

x₃

The GMW/BGW* Approach:

​

● The (public) function being computed is written as a circuit

● Each participant secret-shares their private input

MPC from Secret Sharing

61

f (x,y,z)

x

​

y

​

​

z

​

​

z = z₁ + z₂ + z₃

​

x = x₁ + x₂ + x₃

​

​

y = y₁ + y₂ + y₃

​

​

x₃

x₂

y₃

y₁

The GMW/BGW* Approach:

​

● The (public) function being computed is written as a circuit

● Each participant secret-shares their private input

MPC from Secret Sharing

62

f (x,y,z)

x

​

y

​

​

z

​

​

x₃ y₃ z₃

​

​

z = z₁ + z₂ + z₃

​

​

x = x₁ + x₂ + x₃

​

​

x₁ y₁

​

​

x₂ y₂

​

​

y = y₁ + y₂ + y₃

​

​

z₁

z₂

The GMW/BGW* Approach:

​

● The (public) function being computed is written as a circuit

● Each participant secret-shares their private input

MPC from Secret Sharing

63

f (x,y,z)

x

​

y

​

​

z

​

​

x₃ y₃ z₃

​

​

z

​

x

​

x₁ y₁ z₁

​

​

x₂ y₂ z₂

​

​

y

​

The GMW/BGW* Approach:

​

● The (public) function being computed is written as a circuit

● Each participant secret-shares their private input

● The circuit is evaluated gate-by-gate on the shares (this requires communication between participants)

MPC from Secret Sharing

64

f (x,y,z)

x

​

y

​

​

z

​

​

x₃ y₃ z₃

​

​

x₁ y₁ z₁

​

​

x₂ y₂ z₂

​

​

The GMW/BGW* Approach:

​

● The (public) function being computed is written as a circuit

● Each participant secret-shares their private input

● The circuit is evaluated gate-by-gate on the shares (this requires communication between participants)

MPC from Secret Sharing

65

f (x,y,z)

x₃ y₃ z₃

​

​

S₃ = x₃+ y₃ + z₃

​

​

S₁ = x₁+ y₁ + z₁

​

​

x₁ y₁ z₁

​

​

x₂ y₂ z₂

​

​

S₂ = x₂+ y₂ + z₂

​

​

x₁ + x₂ + x₃ = x

​

y₁ + y₂ + y₃ = y

​

z₁ + z₂ + z₃ = z

​

​

The GMW/BGW* Approach:

​

● The (public) function being computed is written as a circuit

● Each participant secret-shares their private input

● The circuit is evaluated gate-by-gate on the shares (this requires communication between participants)

● Addition is possible without interaction → S_i = x_i+ y_i + z_i

​

MPC from Secret Sharing

66

f (x,y,z)

x₃ y₃ z₃

​

​

S₃ = x₃+ y₃ + z₃

​

​

S₁ = x₁+ y₁ + z₁

​

​

x₁ y₁ z₁

​

​

x₂ y₂ z₂

​

​

S₂ = x₂+ y₂ + z₂

​

​

S₁ = x₁ + y₁ + z₁

S₂ = x₂ + y₂ + z₂

S₃ = x₃ + y₃ + z₃

​

​

​

​

+

S₁+ S₂ + S₃ = x + y + z

x₁ + x₂ + x₃ = x

​

y₁ + y₂ + y₃ = y

​

z₁ + z₂ + z₃ = z

​

​

The GMW/BGW* Approach:

​

● The (public) function being computed is written as a circuit

● Each participant secret-shares their private input

● The circuit is evaluated gate-by-gate on the shares

● Addition is possible without interaction → S_i = x_i+ y_i + z_i → S = x + y + z = S₁+ S₂ + S₃

​

MPC from Secret Sharing

67

f (x,y,z)

x

​

y

​

​

z

​

​

x₃ y₃ z₃

​

​

x₁ y₁ z₁

​

​

x₂ y₂ z₂

​

​

a₃

​

​

a₁

​

​

a₂

​

​

The GMW/BGW* Approach:

​

● The (public) function being computed is written as a circuit

● Each participant secret-shares their private input

● The circuit is evaluated gate-by-gate on the shares (this requires communication between participants)

● Answer is reconstructed from final shares

​

MPC from Secret Sharing

68

The GMW/BGW* Approach:

​

● The (public) function being computed is written as a circuit

● Each participant secret-shares their private input

● The circuit is evaluated gate-by-gate on the shares (this requires communication between participants)

● Answer is reconstructed from final shares

​

MPC from Secret Sharing

69

R = f (x, y , z)

R₁

R₃ = f (x₃, y₃, z₃)

​

​

R₂ = f (x₂, y₂, z₂)

R₁ = f (x₁, y₁, z₁)

​

​

R₃

R = R₁ + R₂ + R₃

The GMW/BGW* Approach:

​

● The (public) function being computed is written as a circuit

● Each participant secret-shares their private input

● The circuit is evaluated gate-by-gate on the shares (this requires communication between participants)

● Answer is reconstructed from final shares

​

​

Yao Garbling Circuits

2PC - Boolean Circuits

71

Model of Computation: Represent the function as Arithmetic/Boolean circuit C

Limiting Factor : Circuit Depth

​

​

​

Depth 3

2PC - Yao Garbling Circuit 1982

72

[Yao82] A. Yao, Protocols for secure computations. In Proceedings of FOCS (1982)

2PC - Yao Garbling Circuit

73

step 1 - Truth table for each logic gate

2PC - Yao Garbling Circuit

74

Step 2 - Generate 2 secret keys for each possible input (one for 0 and another one for 1)

Yao Garbling Circuit

75

Step 3 - Rewrite the Truth Table by replacing 0/1 with their corresponding keys

Yao Garbling Circuit

76

Step 4 - Encrypt with both keys the output of each gate

Yao Garbling Circuit

77

Step 5 - Send this version of the circuit to the Evaluator

Yao Garbling Circuit - Evaluation

78

Step 1 - Use the known keys for your inputs to decrypt each gate value

example - inputs (1, 0, 0, 1)

Yao Garbling Circuit - Evaluation

79

Step 2 - Continue the process for following gates

​

Yao Garbling Circuit - Evaluation

80

Step 2 - Continue the process for following gates

​

Yao Garbling Circuit - Evaluation

81

Step 2 - Continue the process for following gates

​

Yao Garbling Circuit - Evaluation

82

Step 2 - Continue the process for following gates

​

Yao Garbling Circuit - Evaluation

83

Step 4 - Obtain the expected result

Bibliography

[AOR+19] Abdelrahaman Aly, Emmanuela Orsini, Dragos Rotaru, Nigel P. Smart, Tim Wood. Zaphod: Efficiently Combining LSSS and Garbled Circuits in SCALE. In Workshop on Encrypted Computing and Applied Homomorphic Cryptography 2019, 2019.

[BDOZ11] Rikke Bendlin, Ivan Damgaard, Claudio Orlandi, Sarah Zakarias. BDOZ: Semi-homomorphic encryption and multiparty computation. In Advances in Cryptology – EUROCRYPT 2011, 2011, Springer.

[BGW88 ]M. Ben-Or, S. Goldwasser and A. Wigderson. Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation. In the 20th STOC, pages 1–10, 1988.

[BMR90] Donald Beaver, Silvio Micali, and Phillip Rogaway. The round complexity of secure protocols. In 22nd ACM STOC, 1990.

[DPSZ12] Ivan Damgaard, Valerio Pastro, Nigel P. Smart, Sarah Zakarias. SPDZ: Multiparty computation from somewhat homomorphic encryption. In Advances in Cryptology – CRYPTO 2012, Springer.

[GMW87] Oded Goldreich, Silvio Micali, and Avi Wigderson. How to prove all NP- statements in zero-knowledge, and a methodology of cryptographic protocol design. In CRYPTO’86, volume 263 of LNCS, pages 171–185. Springer.

[KRS18] M. Keller, D. Rotaru, N. Smart, and T. Wood, Reducing Communication Channels in MPC. In Security and Cryptography for Networks 11, pp. 181-199, 2018.

[LPSY19] Y. Lindell, B. Pinkas, N. Smart, A. Yanai. Efficient Constant Round Multi-Party Computation Combining BMR and SPDZ. In Journal of Cryptology 32, 2019.

[NNOB12] Jesper Nielsen, Peter Nordholt, Claudio Orlandi, Sai S. Burra. TinyOT: A new approach to practical active-secure two-party computation. In CRYPTO 2012, Lecture Notes in Computer Science, pages 681–700, 2012, Springer

[RT19] D. Rotaru, T. Wood, MArBled Circuits: Mixing Arithmetic and Boolean Circuits with Active Security. In INDOCRYPT 2019, Lecture Notes in Computer Science, Springer-Verlag, 2019

[Yao82] A. Yao, Protocols for secure computations. In Proceedings of FOCS (1982)

4.Private Information Retrieval

Private Information Retrieval

86

​

Trivial solution: Download the entire database

�

Can the problem be solved with less communications?

​

PIR Setting:

Server: - holds n-bit string x

- n is very large

User: - wishes to retrieve value x_i

- to keep i private

​

Private Information

Retrieval

Query i

?

x_i

Private Information Retrieval

87

​

​

• withstand attacks even from an adversary with unlimited computational power �

Information Theoretic

PIR

​

​

• provide weaker guarantees: security is reduced to solving computationally hard problem (bounded adversary) �

Computational

PIR

Private Information Retrieval

88

​

​

• withstand attacks even from an adversary with unlimited computational power �
• # servers: multiple copies of the database k copies
• comm.: more expensive

Information Theoretic

PIR

​

​

• provide weaker guarantees: security is reduced to solving computationally hard problem (bounded adversary) �
• # servers: only one database
• comm.: low

Computational

PIR

Private Information Retrieval

89

​

​

• withstand attacks even from an adversary with unlimited computational power �
• # servers: multiple copies of the database k copies
• comm.: more expensive
• IT-PIR schemes:
• 2 servers – comm. O(n^1/3) [CGKS95]
• k servers – comm. O(n^1/Ω(k)) [CGKS95, Amb9,BIKR02]
• log n servers – comm. O((log n)^a) [BF90, CGKS95]

​

Information Theoretic

PIR

​

​

• provide weaker guarantees: security is reduced to solving computationally hard problem (bounded adversary) �
• # servers: only one database
• comm.: low
• C-PIR schemes are based on the difficulty of:
• Quadratic Residue Problem – comm O(n^ε )
• φ-hiding problem – comm O((log n)^a )
• one-way permutations – comm n - o(n)

​

Computational

PIR

Private Information Retrieval

90

​

​

• withstand attacks even from an adversary with unlimited computational power �
• # servers: multiple copies of the database k copies
• comm.: more expensive
• IT-PIR schemes:
• 2 servers – comm. O(n^1/3) [CGKS95]
• k servers – comm. O(n^1/Ω(k)) [CGKS95, Amb9,BIKR02]
• log n servers – comm. O((log n)^a) [BF90, CGKS95]
• time cost: Expected computation of the servers is ≥ O(n)
• open: Improving time complexity via preprocessing / amortization / off-line computation

Information Theoretic

PIR

​

​

• provide weaker guarantees: security is reduced to solving computationally hard problem (bounded adversary) �
• # servers: only one database
• comm.: low
• C-PIR schemes are based on the difficulty of:
• Quadratic Residue Problem – comm O(n^ε )
• φ-hiding problem – comm O((log n)^a )
• one-way permutations – comm n - o(n)
• time cost: Computation O(n/ log n) public-key operations

​

Computational

PIR

State of the Art

91

This work = EC2022

“Single-Server Private Information Retrieval with Sublinear Amortized Time”

Corrigan-Gibbs,

Henzinger,

Kogan

ia.cr/081

​

✝ public-key operations: n^1/2

​

*This number of per-client queries assumes that the total number of clients, m, grows sufficently large.

Variations of Private Information Retrieval

92

​

• block PIR

– what if Alice wants a block of bits (of size m)?

– can we do better than invoking a PIR protocol m times? �

• robust PIR – what if some of the database copies break down or return false answers (Byzantine failure model)? �
• t-private PIR

– how to ensure that even t colluding databases cannot figure out in which bit Alice is interested in? �

• PIR with preprocessing

– the database usually has to do O(n) computations – can this be cut down?

​

​

Private Information

Retrieval

Query

Data

?

​

5. Private Set Intersection

FHE-based

​

Private Set Intersection

94

Receiver Sender

R = {a, b, c, n} R ∩ S = ? S = {a, b, d, e, f, g, h, i, j, k, l, m}

​

Problem :

Two parties compute their set intersection keeping their sets private

​

Private Set Intersection

95

Receiver Sender

R = {a}

Constructs polynomial F

​

F (a) = 2, F(b)=4, …

2

Encrypts the search a

​

​

​

​

​

a

1

Solution based on FHE :

Private Set Intersection

96

Receiver Sender

R = {a}

Constructs polynomial F of degree |set|

Evaluate F on Enc(a)

​

1

Encrypts the search a

​

​

​

​

​

a

1

Solution based on FHE :

2

Enc(a)

Private Set Intersection

97

Receiver Sender

R = {a}

Constructs polynomial F of degree |set|

Evaluate F on Enc(a)

F (Enc(a)) = Enc(2)

​

​

1

Encrypts the search a

​

​

​

​

​

a

1

Solution based on FHE :

2

Enc(a)

Private Set Intersection

98

Receiver Sender

R = {a}

Constructs polynomial F of degree |set|

Evaluate F on Enc(a)

F (Enc(a)) = Enc(2)

​

​

1

Encrypts the search a

​

​

​

​

​

​

Decrypts and learns value

​

​

​

​

​

a

1

Solution based on FHE :

2

Enc(a)

Encrypted label for a

F( ) =

4

0, 0, t, z

{a, b}

Private Set Intersection

99

Receiver Sender

R = {a}

• Computation = 𝑂(𝑁)
• Depth of FHE circuit = 𝑂(log log 𝑁)
• Communication = 𝑂(log 𝑁)
• No circuit privacy → Much smaller FHE parameters

​

Performance:

Private Set Intersection

100

Receiver Sender

R = {a}

Comparison with Key-word PIR:

FHE-PSI:

​

• 20 seconds and 18MB
• Requires a single server
• Has a large offline computation

​

PIR/MPC:

​

• linear communication
• better running time

Cuckoo Hashing

101

​

h₁(a) = 3, h₂(a) = 2, h₃(a) = 4,

​

​

Receiver Sender

R = {a, b, c, n} S = {a, b, d, e, f, g, h, i, j, k, l, m}

​

Cuckoo Hashing

102

​

h₁(a) = 3, h₂(a) = 2, h₃(a) = 4,

h₁(b) = 2, h₂(b) = 3, h₃(b) = 1,

​

​

Receiver Sender

R = {a, b, c, n} S = {a, b, d, e, f, g, h, i, j, k, l, m}

​