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:

See other events that are part of the CIS Seminar Series 2023 - 2024.

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