Revisiting Time-Space Tradeoffs for Function Inversion

Speaker: Spencer Peters

Date: Friday, November 18, 2022

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

Public: Yes

Location: G-882

Event Type: Seminar

Room Description:

Host: Vinod Vaikuntanathan

Contact: Felicia Raton, fraton@csail.mit.edu

Relevant URL: https://eccc.weizmann.ac.il/report/2022/145/

Speaker URL: https://www.cs.cornell.edu/~speters/

Speaker Photo:
None

Reminders to: cis-seminars@csail.mit.edu

Reminder Subject: TALK: Revisiting Time-Space Tradeoffs for Function Inversion

Function inversion is a fundamental problem in cryptography and in
theoretical computer science more broadly. Given a function f: [N] \to
[N] from a finite domain to itself, the goal is to construct a small
data structure, so that for any point y in the image of f, you can
recover an inverse of y using few evaluations of f.
First, I will describe a modification to Fiat and Naor's classic
function inversion algorithm [STOC '91] that improves the time-space
tradeoff in the regime where the number of evaluations T exceeds the
data structure bitlength S. Then I'll present the first (barely)
non-trivial non-adaptive algorithm for function inversion (a
non-adaptive algorithm chooses all the points it will evaluate f on
before seeing any of the results). This algorithm resolves a question
posed by Corrigan-Gibbs and Kogan [TCC'19], and I'll show that the
tradeoff it achieves is tight for a natural class of non-adaptive
algorithms. Both results are joint work with Alexander Golovnev, Siyao
Guo, and Noah Stephens-Davidowitz.

Research Areas:
Security & Cryptography

Impact Areas:

See other events that are part of the Cryptography and Information (CIS) Seminar 2022.

Created by Megan F Farmer at Tuesday, October 25, 2022 at 10:14 AM.