Provable Security Basics

Modern Cryptography:

  • Confidentiality
  • Integrity
  • Authentication

Provable Security:

  • Precisely specify threat model
  • Propose a construction
  • Write a formal proof(reduction)

One-way function:

f(x) is polynomial-time computable for all x

For all PPT algorithm A\mathcal{A}

Pr[InvertA,f(n)=1]≤ϵ(n)Pr[Invert_{\mathcal{A},f}(n)=1]\le \epsilon(n)

Discrete Logarithm Problem

Let G\mathcal{G} be a neneric, polynomial-time, group generation algorithm

Input 1n1^n, output G,q,g∈GG,q,g\in G

DLogA,G(n)DLog_{\mathcal{A,G}}(n)

1.Generate (G,q,g)←G(1n)(G,q,g)\leftarrow \mathcal{G}(1^n)

2.Choose a uniform h←Gh\leftarrow G

3.Obtain x←A(G,q,g,h)x\leftarrow \mathcal{A}(G,q,g,h)

4.Return 1 iff gx=hg^x=h

CDH vs DL

Theorem: if the CDH problem is hard relative to G\mathcal{G} then discrete logarithm problem is also hard relative to G\mathcal{G}

image-20240515162032528

MPC

安全多方计算

安全多方计算的分类

image-20240529162700168

2-move Two-party Computation

  1. Encode a by using pk
  2. Compute f(a,b) over encoded inputs
  3. Decode c by using sk, botain f(a,b)

Elgamal is IND-CPA Secure

If the DDH problem is hard relative to G\mathcal{G},then the Elgamal encryption scheme is IND-CPA secure