BEGIN:VCALENDAR
VERSION:2.0
PRODID:icalendar-ruby
CALSCALE:GREGORIAN
METHOD:PUBLISH
BEGIN:VTIMEZONE
TZID:America/New_York
BEGIN:DAYLIGHT
DTSTART:20230312T030000
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
RRULE:FREQ=YEARLY;BYDAY=2SU;BYMONTH=3
TZNAME:EDT
END:DAYLIGHT
BEGIN:STANDARD
DTSTART:20231105T010000
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
RRULE:FREQ=YEARLY;BYDAY=1SU;BYMONTH=11
TZNAME:EST
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20240301T063354Z
UID:4597425c-4667-4c31-940b-43fa3ad27096
DTSTART;TZID=America/New_York:20231013T103000
DTEND;TZID=America/New_York:20231013T120000
CREATED:20230930T153935
DESCRIPTION:The existence of “unstructured” hard languages in NP ∩ co
NP is an\nintriguing open question. Bennett and Gill (SICOMP\, 1981) asked
\nwhether P is separated from NP ∩ coNP relative to a random oracle\,\na
question that remained open ever since. While a hard language\nin NP ∩
coNP can be constructed in a black-box way from a one-\nway permutation\,
for which only few (structured) candidates exist\,\nBitansky et al. (SICOM
P\, 2021) ruled out such a construction based\non an injective one-way fun
ction\, an unstructured primitive that is\neasy to instantiate heuristical
ly. In fact\, the latter holds even with a\nblack-box use of indistinguish
ability obfuscation.\nWe give the first evidence for the existence of unst
ructured hard\nlanguages in NP ∩ coNP by showing that if UP ⊈ RP\, whi
ch follows\nfrom the existence of injective one-way functions\, the answer
to\nBennett and Gill’s question is affirmative: with probability 1 over
\na random oracle O\, we have that PO ≠ NPO ∩ coNPO . Our proof\ngives
a constructive non-black-box approach for obtaining candidate\nhard langu
ages in NP ∩ coNP from cryptographic hash functions.\nThe above conditio
nal separation builds on a new construction\nof non-interactive zero-knowl
edge (NIZK) proofs\, with a computa-\ntionally unbounded prover\, to conve
rt a hard promise problem into\na hard language. We obtain such NIZK proof
s for NP\, with a uni-\nformly random reference string\, from a special ki
nd of hash function\nwhich is implied by (an unstructured) random oracle.
This should\nbe contrasted with previous constructions of such NIZK proofs
that\nare based on one-way permutations or other structured primitives\,\
nas well as with (computationally sound) NIZK arguments in the\nrandom ora
cle model.\n\nJoin Zoom Meeting\nhttps://mit.zoom.us/j/99316064630
LAST-MODIFIED:20231006T135302
LOCATION:G-882\, Hewlett Room
SUMMARY:Hard Languages in NP ∩ coNP and NIZK Proofs from Unstructured As
sumptions
URL:https://calendar.csail.mit.edu/events/269834
END:VEVENT
END:VCALENDAR