Fine-grained Cryptography

FSTTCS 2022 Workshop

IIT Madras

December 17, 2022

Overview

Classically, a cryptographic construction is considered secure if and only if there is no polynomial-time attack. This definition is quite convenient and has proven to be extremely useful. However, the distinction between polynomial time and super-polynomial time can seem artificial at times. E.g., in many settings a, say, 2n1/10-time attack would be devastating. In other settings, we cannot hope to (or might not even want to!) rule out, say, n10-time attacks, but we do still want to rule out, say, n2-time attacks.

This leads to the concept of fine-grained cryptography, an off-shoot of the exciting area of fine-grained complexity. At a high level, fine-grained cryptography dispenses with the coarse distinction between polynomial-time attacks and super-polynomial-time attacks and instead focuses on understanding more precisely the exact complexity of attacking certain cryptographic schemes and of related problems.

This workshop will focus on exciting developments in the (still quite new) field of fine-grained cryptography, such as fine-grained cryptographic constructions, fine-grained hardness proofs for computational problems relevant to cryptography, fine-grained worst-case to average-case reductions, and more. The workshop will be accessible to a broad theoretical computer science audience, and no prior knowledge in fine-grained cryptography will be assumed.

Speakers

Amir Abboud

Amir Abboud

Weizmann Institute

Divesh Aggarwal

Divesh Aggarwal

National University of Singapore

Alexander Golovnev

Alexander Golovnev

Georgetown University

Rajendra Kumar

Rajendra Kumar

Weizmann Institute

Subhasree Patro

Subhasree Patro

CWI Amsterdam

Alon Rosen

Alon Rosen

Bocconi University

Sidhant Saraogi

Sidhant Saraogi

Georgetown University

Noah Stephens-Davidowitz

Noah Stephens-Davidowitz

Cornell University

Participation

Registration Fees:

Indian student Indian non-student All Others
Early Registration (till Nov 10 AoE) ₹ 800 ₹ 1500 ₹ 3000 (35 USD)
Regular Registration ₹ 1300 ₹ 2000 ₹ 3500 (40 USD)

For registration and other information please click here.

Schedule

Time Speaker Title Links
8.30AM - 9.30AM Amir Abboud Fine-Grained Complexity of Polynomial Time Problems: An Overview
9.30AM - 10.15AM Sidhant Saraogi Fine Grained Cryptography for Circuits
10.15AM - 10.45AM Coffee Break
10.45AM - 11.45AM Alon Rosen Public-Key Encryption, Local Pseudorandom Generators, and the Low-Degree Method
11.45AM - 12.30PM Subhashree Patro Quantum Fine-Grained Complexity
12.30PM - 2.00PM Lunch
2.00PM - 2.45PM Rajendra Kumar Foundation of Lattice based Cryptography
2.45PM - 3.30PM Noah Stephens-Davidowitz Fine-grained hardness of lattice and coding problems
3.30PM - 4.00PM Coffee Break
4.00PM - 4.45PM Divesh Aggarwal Why we couldn't prove SETH hardness of the Closest Vector Problem for even norms, and of the Subset Sum Problem!
4.45PM - 5.30PM Sasha Golovnev Fine-Grained Worst-Case to Average-Case Reductions

Location

The workshop is being held at ICSR building (Centre for Industrial Consultancy and Sponsored Research), located in the campus of the Indian Institute of Technology Madras (IIT Madras), at Chennai.

Sponsors