The Cost of Statistical Security in Interactive Proofs for Repeated Squaring

Speaker: Cody Freitag

Date: Friday, September 09, 2022

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

Public: Yes

Location: Hewlett Room

Event Type: Seminar

Room Description:

Host: Vinod Vaikuntanathan, CSAIL MIT

Contact: Felicia Raton, 401-580-5009, fraton@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: seminars@csail.mit.edu

Reminder Subject: TALK: The Cost of Statistical Security in Interactive Proofs for Repeated Squaring

In recent years, the number of applications of the repeated squaring assumption has been growing rapidly. The assumption states that, given a group element x, an integer T, and an RSA modulus N, it is hard to compute x^(2^T) mod N---or even decide whether y = x^(2^T) mod N---in parallel time less than the trivial approach of computing T sequential squarings. This rise has been driven by efficient interactive proofs for repeated squaring, opening the door to more efficient constructions of verifiable delay functions, various secure computation primitives, and proof systems for more general languages.

In this work, we study the complexity of statistically-sound interactive proofs for the repeated squaring relation. Technically, we consider interactive proofs where the prover sends at most k >= 0 elements per round and the verifier performs generic group operations over the group Z_N^*. As our main contribution, we show that for any one-round proof with a randomized verifier (i.e., an MA proof) the verifier either runs in parallel time Omega(T/(k+1)) with high probability, or is able to factor N given the proof provided by the prover. This shows that either the prover essentially sends p,q such that N = p * q (which is infeasible or undesirable in most applications), or a variant of Pietrzak's proof of repeated squaring (ITCS 2019) has optimal verifier complexity O(T/(k+1)). In particular, it is impossible to obtain a statistically-sound one-round proof of repeated squaring with efficiency on par with the computationally-sound protocol of Wesolowski (EUROCRYPT 2019), with a generic group verifier.

This work was done during an internship at NTT Research and is joint with Ilan Komargodski.

Research Areas:

Impact Areas:

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

Created by Felicia Raton at Thursday, September 08, 2022 at 1:59 PM.