1 of 32

Meta-Complexity Reading Group @ Warwick

November 13, 2024

2 of 32

Algorithmica

​

Heristica

  • NP is hard in the worst case (NP ⊈ BPP), but
  • NP is easy on average (DistNP ⊆ HeurBPP)

Pessiland

  • NP is hard on average (DistNP ⊈ HeurBPP), but
  • Private-key cryptography does not exist (∄ one-way functions)

MiniCrypt

​

Cryptomania

  • Public-key cryptography exists

“Algorithmic”

“Secure”

Impagliazzo’s Five Worlds

3 of 32

Impagliazzo’s Five Worlds

Algorithmica

  • All NP problems are easy (NP ⊆ BPP)

Heristica

  • NP is hard in the worst case (NP ⊈ BPP), but
  • NP is easy on average (DistNP ⊆ HeurBPP)

Pessiland

  • NP is hard on average (DistNP ⊈ HeurBPP), but
  • Private-key cryptography does not exist (∄ one-way functions)

MiniCrypt

  • Private-key cryptography exists (∃ one-way functions), but
  • Public-key cryptography does not exist

Cryptomania

  • Public-key cryptography exists

“Algorithmic”

“Secure”

4 of 32

Impagliazzo’s Five Worlds

Algorithmica

  • All NP problems are easy (NP ⊆ BPP)

Heristica

  • NP is hard in the worst case (NP ⊈ BPP), but
  • NP is easy on average (DistNP ⊆ HeurBPP)

Pessiland

  • NP is hard on average (DistNP ⊈ HeurBPP), but
  • Private-key cryptography does not exist (∄ one-way functions)

MiniCrypt

  • Private-key cryptography exists (∃ one-way functions), but
  • Public-key cryptography does not exist

Cryptomania

  • Public-key cryptography exists

“Algorithmic”

“Secure”

5 of 32

Average-Case Complexity

 

Definition (DistNP ⊆ HeurBPP):

 

6 of 32

Impagliazzo’s Five Worlds

Algorithmica

  • All NP problems are easy (NP ⊆ BPP)

Heristica

  • NP is hard in the worst case (NP ⊈ BPP), but
  • NP is easy on average (DistNP ⊆ HeurBPP)

Pessiland

  • NP is hard on average (DistNP ⊈ HeurBPP), but
  • Private-key cryptography does not exist (∄ one-way functions)

MiniCrypt

  • Private-key cryptography exists (∃ one-way functions), but
  • Public-key cryptography does not exist

Cryptomania

  • Public-key cryptography exists

“Algorithmic”

“Secure”

7 of 32

 

 

Easy

Hard

One-Way Functions

8 of 32

One-Way Functions

Definition (One-Way Functions):

​

 

 

9 of 32

One-way functions [Diffie-Hellman’76] are both sufficient and necessary for

Private-key encryption [GM84]

Zero-knowledge proofs [GMW89]

Authentication schemes [FS90]

Pseudorandom generators [HILL99]...

Pseudorandom functions [GGM84]

Digital signitures [Rompel90]

Commitment schemes [Naor90]

One-Way Functions

Whether one-way functions exist is the most important question in cryptography.

10 of 32

Impagliazzo’s Five Worlds

Algorithmica

  • All NP problems are easy (NP ⊆ BPP)

Heristica

  • NP is hard in the worst case (NP ⊈ BPP), but
  • NP is easy on average (NP ⊆ HeurBPP)

Pessiland

  • NP is hard on average (DistNP ⊈ HeurBPP), but
  • Private-key cryptography does not exist (∄ one-way functions)

MiniCrypt

  • Private-key cryptography exists (∃ one-way functions), but
  • Public-key cryptography does not exist

Cryptomania

  • Public-key cryptography exists

“Algorithmic”

“Secure”

11 of 32

Impagliazzo’s Five Worlds

Algorithmica

  • All NP problems are easy (NP ⊆ BPP)

Heristica

  • NP is hard in the worst case (NP ⊈ BPP), but
  • NP is easy on average (NP ⊆ HeurBPP)

Pessiland

  • NP is hard on average (DistNP ⊈ HeurBPP), but
  • Private-key cryptography does not exist (∄ one-way functions)

MiniCrypt

  • Private-key cryptography exists (∃ one-way functions), but
  • Public-key cryptography does not exist

Cryptomania

  • Public-key cryptography exists

“Algorithmic”

“Secure”

12 of 32

Impagliazzo’s Five Worlds

“Algorithmic”

“Secure”

Algorithmica

  • All NP problems are easy (NP ⊆ BPP)

Heristica

  • NP is hard in the worst case (NP ⊈ BPP), but
  • NP is easy on average (NP ⊆ HeurBPP)

Pessiland

  • NP is hard on average (DistNP ⊈ HeurBPP), but
  • Private-key cryptography does not exist (∄ one-way functions)

MiniCrypt

  • Private-key cryptography exists (∃ one-way functions), but
  • Public-key cryptography does not exist

Cryptomania

  • Public-key cryptography exists

13 of 32

Impagliazzo’s Five Worlds

Excluding Heristica

​

 

 

 

Excluding Pessiland

​

Excluding Algorimica

​

14 of 32

Computational Complexity Theory versus Kolmogorov Complexity Theory

  • NP vs BPP

​

  • NP vs HeurBPP

​

  • Existence of OWFs

​

​

​

Theory of

Kolmogorov Complexity

Why? Import methods and perspectives from Kolmogorov complexity; investigate relations between main open problems from complexity theory, etc.

Meta-Complexity

15 of 32

Complexity Theory:

Fruitful applications in

Cryptography:

[Hir18], [Hir20a], [Hir20b], [Hir21], [CHV22], [GKLO22], [LOZ22], [LP22a], [Hir22a], [Hir22b], [San23],...

[LP20], [LP21a], [LP21b], [RS21] [IRS21], [LP22b], [AHT23], [Hir23], [HILNO23], [LP23], [BLMP23],...

Learning:

[CIKK16], [HN21], [GK23], [HN23],...

Meta-Complexity

16 of 32

Excluding Pessiland

Pessiland

  • NP is hard on average, and
  • Private-key cryptography does not exist (∄one-way functions)

 

Problem (Excluding Pessiland):

​

NP is hard on average

17 of 32

There is a meta-complexity problem whose average-case tractability over poly-time samplable distributions can be used to characterize both

  • non-existence of (i.o.) one-way functions and

  • DistNP ⊆ HeurBPP,

while considering different time regimes in the measure of time-bounded Kolmogorov complexity.

Theorem [L.-Santhanam’24; informal]:

18 of 32

 

 

 

 

Kolmogorov Complexity

 

Kolmogorov Complexity:

19 of 32

 

 

 

 

Kolmogorov Complexity:

Kolmogorov Complexity

 

 

 

 

 

 

 

20 of 32

 

 

 

 

 

Conditional Kolmogorov Complexity:

Kolmogorov Complexity

21 of 32

 

 

Time-Bounded Kolmogorov Complexity

22 of 32

Randomized Kolmogorov Complexity

 

 

23 of 32

Conditional Randomized Kolmogorov Complexity

 

Definition [Conditional Randomized Time-Bounded Kolmogorov Complexity]:

24 of 32

Conditional Kolmogorov Complexity

 

Simplified Problem for Illustration:

25 of 32

Conditional Polynomial-Time Kolmogorov Complexity

 

 

 

26 of 32

Conditional Sublinear-TimeKolmogorov Complexity

 

 

 

27 of 32

∄ (i.o.) one-way functions

Conditional randomized time-bounded Kolmogorov complexity in the polynomial-time regime can be computed on average over poly-time distributions.

Characterizations via Conditional Randomized Kolmogorov Complexity

Theorem [L.-Santhanam’24; feat. Hirahara-L.-Nanashima’24]:

DistP ⊆ HeurBPP

Conditional randomized time-bounded Kolmogorov complexity in the sublinear-time regime can be computed on average over poly-time distributions.

28 of 32

 

Theorem [L.-Santhanam’24; feat. Hirahara-L.-Nanashima’24]:

29 of 32

 

Theorem [L.-Santhanam’24; feat. Hirahara-L.-Nanashima’24]:

30 of 32

 

Theorem [Following Ilango-Ren-Santhanam’22]:

31 of 32

 

Theorem [Hirahara’22]:

32 of 32

 

Corollary [Informal]:

Excluding Pessiland