- Hard Languages in NP ∩ coN...
- Edit Event
- Cancel Event
- Preview Reminder
- Send Reminder
- Other events happening in October 2023

## Hard Languages in NP ∩ coNP and NIZK Proofs from Unstructured Assumptions

**Speaker:**
Alexis Korb
, UCLA

**Date:**
Friday, October 13, 2023

**Time:**
10:30 AM to 12:00 PM
** Note: all times are in the Eastern Time Zone**

**Public:**
Yes

**Location:**
G-882, Hewlett Room

**Event Type:**
Seminar

**Room Description:**

**Host:**
Vinod Vaikuntanathan , CSAIL MIT

**Contact:**

**Relevant URL:**

**Speaker URL:**
None

**Speaker Photo:**

None

**Reminders to:**
seminars@lists.csail.mit.edu, cis-seminars@csail.mit.edu

**Reminder Subject:**
TALK: Hard Languages in NP ∩ coNP and NIZK Proofs from Unstructured Assumptions

The existence of “unstructured” hard languages in NP ∩ coNP is an

intriguing open question. Bennett and Gill (SICOMP, 1981) asked

whether P is separated from NP ∩ coNP relative to a random oracle,

a question that remained open ever since. While a hard language

in NP ∩ coNP can be constructed in a black-box way from a one-

way permutation, for which only few (structured) candidates exist,

Bitansky et al. (SICOMP, 2021) ruled out such a construction based

on an injective one-way function, an unstructured primitive that is

easy to instantiate heuristically. In fact, the latter holds even with a

black-box use of indistinguishability obfuscation.

We give the first evidence for the existence of unstructured hard

languages in NP ∩ coNP by showing that if UP ⊈ RP, which follows

from the existence of injective one-way functions, the answer to

Bennett and Gill’s question is affirmative: with probability 1 over

a random oracle O, we have that PO ≠ NPO ∩ coNPO . Our proof

gives a constructive non-black-box approach for obtaining candidate

hard languages in NP ∩ coNP from cryptographic hash functions.

The above conditional separation builds on a new construction

of non-interactive zero-knowledge (NIZK) proofs, with a computa-

tionally unbounded prover, to convert a hard promise problem into

a hard language. We obtain such NIZK proofs for NP, with a uni-

formly random reference string, from a special kind of hash function

which is implied by (an unstructured) random oracle. This should

be contrasted with previous constructions of such NIZK proofs that

are based on one-way permutations or other structured primitives,

as well as with (computationally sound) NIZK arguments in the

random oracle model.

Join Zoom Meeting

https://mit.zoom.us/j/99316064630

**Research Areas:**

**Impact Areas:**

Created by Megan F Farmer at Saturday, September 30, 2023 at 3:39 PM.