Benjamin Wesolowski

Ryan Williams

Lower bounds for the depth of modular squaring

Keywords: Verifiable delay function, circuit, modular squaring, RSA

The modular squaring operation has attracted significant attention due to its potential in constructing cryptographic time-lock puzzles and verifiable delay functions. In such applications, it is important to understand precisely how quickly a modular squaring operation can be computed, even in parallel on dedicated hardware. We use tools from circuit complexity and number theory to prove concrete numerical lower bounds for squaring on a parallel machine, yielding nontrivial results for practical input bitlengths. For example, for n = 2048, we prove that every logic circuit (over AND, OR, NAND, NOR gates of fan-in two) computing modular squaring on all n-bit inputs (and any modulus that is at least 2 n-1 ) requires depth (critical path length) at least 12. By a careful analysis of certain exponential Gauss sums related to the low-order bit of modular squaring, we also extend our results to the average case. For example, our results imply that every logic circuit (over any fan-in two basis) computing modular squaring on at least 76% of all 2048-bit inputs (for any RSA modulus that is at least 2 n-1 ) requires depth at least 9.

Introduction

Which computational problems are inherently sequential, and cannot be efficiently parallelized? This is the intuitive question behind the P versus NC problem, one of the major open problems in computational complexity theory and computer science. It is widely conjectured that P = NC, which would show that there are (natural) problems solvable in n O(1) time in a sequential computational model that cannot be solved in (log n) O(1) parallel time (a.k.a. (log n) O(1) depth) in a parallel computational model with n O(1) processors. Very little is known about the depth complexity of functions in P: the best known depth lower bounds for any function in P (or NP for that matter) only show that depth must be at least c log n where c ≤ 3.

In cryptography, certain problems have been proposed as candidates for being inherently sequential. In this paper, we focus on the problem of integer modular squaring, which was first proposed by Rivest, Shamir, and Wagner [START_REF] Ronald L Rivest | Time-lock puzzles and timed-release crypto[END_REF] in the context of time-lock puzzles. It has recently received renewed attention, when it was shown in [START_REF] Wesolowski | Efficient verifiable delay functions[END_REF][START_REF] Pietrzak | Simple verifiable delay functions[END_REF] that it allows to build verifiable delay functions [START_REF] Boneh | Verifiable delay functions[END_REF] (or VDF ), a cryptographic primitive key to a wide variety of exciting applications, notably for secure decentralised systems.

Repeated Modular Squaring (RMS):

Given an n-bit x, a parameter T , and an n-bit modulus m ∈ [2 n-1 , 2 n -1], calculate x 2 T mod m.

Typically, we think of T as "large". If m is prime, one can calculate x 2 T mod m very efficiently by first reducing the exponent k = 2 T mod m -1, then computing x k mod m for k < m. More generaly, knowing φ(m) (or equivalently, the factorisation of m) allows to compute x 2 T mod m in about log 2 (T ) multiplications in Z/mZ. However, if the factorisation of m is unknown, one cannot reduce the exponent, and there is no known method to compute x 2 T mod m faster than squaring T times sequentially. In this situation, Rivest, Shamir and Wagner suggest that the depth of computing x 2 T mod m is roughly T times the depth of squaring modulo m, when T ≤ 2 n o(1) (when T is sufficiently large, it becomes advantageous to factor m first).

The parallel setting is critical here: for applications of VDFs, it is important to have a good estimate of the wall-clock time required for computing RMS: what is the depth of the shallowest circuit an adversary can build? Naively, one might conjecture that every (reasonably defined) parallel machine computing RMS requires at least Ω(T + log n) depth, where the Ω omits division by polylogarithmic factors. However, noting that the input length to RMS is only m ≤ O(log T + log n), such a conjecture would imply a 2 Ω(m) circuit depth lower bound, but it is well-known that every function on m-bit input has a (non-uniform) circuit of 2 m size and O(m) depth. So for such a conjecture to make sense, we also need to bound the size/work of the parallel computation as well, to be (for example) polynomial in T and log n.

Other constructions with lower depth are known, such as [START_REF] Bernstein | Modular exponentiation via the explicit chinese remainder theorem[END_REF], but require models whose practicality has been called into question [START_REF] Can Mert | Low-latency asic algorithms of modular squaring of large integers for vdf evaluation[END_REF], with high fan-in and fan-out. To this day, the most successful attempts at building fast hardware for RMS still boil down to efficient modular squaring [START_REF] Öztürk | Design and implementation of a low-latency modular multiplication algorithm[END_REF][START_REF] Can Mert | Low-latency asic algorithms of modular squaring of large integers for vdf evaluation[END_REF].

In this article, we focus on modular squaring, and ask the relaxed question: what unconditional lower bounds can be proved for modular integer squaring? Can it be rigorously proved that even computing certain bits of x 2 already requires an interesting level of depth complexity?

Our Results

In this paper, we focus on the following problem.

Modular Squaring (MS):

Given an n-bit x and an n-bit modulus m ∈ [2 n-1 , 2 n ], calculate x 2 mod m.

Our goal is to prove unconditional, concrete depth lower bounds for MS. That is, we want to be able to plug in values of n arising in practice, and obtain unconditionally true facts about the required time delays of any logic circuit computing MS on n-bit numbers. To this end, we prove interesting worst-case lower bounds and average-case lower bounds on the depth complexity of MS. We state our results in terms of Boolean logic circuits over OR, AND, NAND, and NOR, each of fan-in two, with "free" NOT gates having cost 0. (We believe this choice of gates is reasonable for practice, because the other possible two-bit gates XOR and EQUALS 1 in modern hardware are, to the best of our knowledge, always implemented in terms of the other gates.) In circuit complexity terminology, this corresponds to proving circuit lower bounds over the basis U 2 (all unate functions on two bits [START_REF] Wegener | The complexity of Boolean functions[END_REF][START_REF] Jukna | Boolean Function Complexity -Advances and Frontiers[END_REF]).

Worst-Case Lower Bounds. Our primary worst-case lower bound is the following.

1 An EQUALS gate takes two bits x and y and outputs 1 if and only if x = y. EQUALS is simply the complement of XOR.

Theorem 1 (Worst-Case Lower Bound). For every n, every logic circuit (over the basis U 2 ) computing MS on n-bit integers requires depth at least 2 log 2 (n-1)-2 log 2 (log 2 (n-1)-1)-4.

In particular, we show that "middle bits" of the output of MS require such depth complexity. The depth complexity of Theorem 1 is stated rather precisely, so that it is possible to plug in concrete numbers and yield interesting results. For example, when n = 1024 and n = 2048, in which case Theorem 1 yields a depth lower bounds of at least 10 and 12, respectively (note that the depth must be an integer). Thus, Theorem 1 allows us to make concrete statements about the delays of logic circuits computing MS, such as the following:

Every logic circuit with a 10 picosecond delay per gate must take at least 1200 picoseconds to compute a modular squaring operation on 2048-bit integers.

The lower bound of Theorem 1 proceeds by an efficient reduction from the SUM problem from n bits to O(log n) bits, defined as:

SUM(x 1 , . . . , x n ) := i x i .
That is, SUM simply outputs a binary representation of the sum of the 1s in its input. It is known that SUM has circuits of depth at most 4.14 log 2 (n) [START_REF] Sergeevich | Complexity and depth of formulas for symmetric boolean functions[END_REF] and every circuit for SUM must have depth at least 2 log 2 (n) [START_REF] Vm Krapchenko | Asymptotic estimation of addition time of parallel adder[END_REF]. Our reduction can be stated as follows.

Theorem 2. If SUM requires depth at least c log 2 (n) for constant c ≥ 2, then MS on n-bit integers requires depth at least c log 2 (n -1) -c log 2 (log 2 (n -1) -1) -2c.
As a corollary, under the reasonable hypothesis that SUM requires depth 4 log 2 (n), MS on 2048-bit integers has depth complexity at least 23.

Average-Case Lower Bounds.

For cryptographic reasons, it is interesting to ask if the above lower bounds hold for circuits that are only required to compute MS on a decent fraction of n-bit inputs. In this case we can also prove non-trivial depth lower bounds for squaring with an RSA modulus, but they are weaker than what we can prove in the worst case.

Theorem 3. Let n ≥ 38, and let m be the product of two primes in [2 n/2-1 , 2 n/2 ). Every logic circuit computing (x 2 mod m) correctly on at least 76% of all n-bit integers x (over the basis U 2 or B 2 ) requires depth at least log 2 (n/4 -7.2).

Corollary 1. Every logic circuit (even with XOR and EQUALS gates) computing (x 2 mod m) correctly on at least 76% of all n-bit integers x requires depth at least 9, when m is the product of two 1024-bit primes, both of which are at least 2 1023 .

An interesting aspect of Theorem 3 is that the depth lower bound holds even over circuits from B 2 , the full binary basis: our gates may be any possible function that takes two bits as input and outputs a bit. (This point is not necessarily relevant to practice; it just turns out that the proof works in that case.)

We believe that the depth complexity of MS in the average case should be roughly as hard as the worst case. However, our worst-case proofs reasoning about the "middle bit" of MS do not extend to the average case (they modify the input too much to yield "typical" inputs), so we take a different approach. We show that computing the low-order bit of MS is difficult on average. This is interesting, because the low-order bit of normal integer squaring, without modular reduction, is trivial (the low-order bit of the output only depends on the low-order bit of the input). Thus modular reduction plays a crucial role in the average-case lower bound of Theorem 3.

In order to establish Theorem 3, we prove a result regarding the sensitivity of modular squaring on random inputs, and show how such sensitivity results yield size and depth lower bounds. (Here in the introduction, we will keep the discussion at an informal level.) The sensitivity of a function f at a binary input x measures how many distinct input bits could be "flipped" such that the value of f changes. When f is the low-order bit of the MS function on n-bit integers, we use bounds on exponential sums to show (in Theorems 10 and 11) that there are at least n/4 input bits x i such that, when an n-bit x is chosen uniformly at random, the probability that the value of f (x) flips is at least 1/2 -o(1). We show how such sensitivity results can be applied to prove lower bounds on the depths of all circuits computing MS even on a decent fraction of inputs, culminating in Theorem 3.

Preliminaries

Notation and Definitions. Let n ≥ 1 be an integer, and let [n] := {1, . . . , n}. We define the function IS : {0, 1} → {0, 1} (Integer Squaring) to map n-bit integers x to 2n-bit integers x 2 .

Let m ≤ 2 n -1 be an odd integer, and let Z/mZ = {0, 1, . . . , m -1}. We view (x mod m) as a function from Z to the set Z/mZ. Define MS-MOD2 n,m : {0, 1} n → {0, 1} as the function which construes its n-bit input x as an integer in [0, 2 n -1], and outputs ((x 2 mod m) mod 2). This is the least significant bit of the function M S(x) = (x 2 mod m) as defined in the introduction.

We use basic notions from circuit complexity [START_REF] Wegener | The complexity of Boolean functions[END_REF][START_REF] Jukna | Boolean Function Complexity -Advances and Frontiers[END_REF]. Let B be a set of functions of the form f : {0, 1} k → {0, 1} where k ∈ {1, 2}. Typical choices are B 2 , the set of all functions on at most two inputs, and U 2 , the set of all unate functions on at most two inputs (a unate function g is a monotone function with signs on some of its inputs, so for example g(x, y, z) = f (¬x, y, ¬z) is unate when f is monotone). It is easy to verify that B 2 = U 2 ∪ {XOR, EQU ALS}.

As is standard, an n-input, m-output, s-size circuit over the basis B is represented as a directed acyclic graph with n sources and s other nodes which include m sinks. Each node is called a gate, has indegree at most two (a.k.a. fan-in at most two), and is labelled with some f ∈ B.

More background on circuit complexity will be covered in Section 3.

Prior Work. As far as we can tell, there is scant literature on proving numerical and unconditional lower bounds for circuit depth. Meyer and Stockmeyer [START_REF] Stockmeyer | Cosmological lower bound on the circuit complexity of a small problem in logic[END_REF] proved such results for circuit size: concretely, they showed that deciding the truth of formulas of length at most 610 from the language WS1S (a problem known to require extremely high asymptotic time complexity) requires circuits containing at least 10 125 gates. On a technical level, the work most related to ours concerns depth lower bounds for PRAMs (parallel random access machines). It has long been known that sensitivity is tied to running time for parallel machines (a.k.a. circuit depth) [START_REF] Wegener | The complexity of Boolean functions[END_REF]. For example, the work of Cook, Dwork, and Reishuk [START_REF] Cook | Upper and lower time bounds for parallel random access machines without simultaneous writes[END_REF] implies that for so-called CREW (Concurrent Read Exclusive Write) PRAMs, the minimal running time for computing a function f is at least Ω(log S(f )) where S(f ) is the sensitivity of f , and the recently celebrated proof of the Sensitivity Conjecture by Huang [START_REF] Huang | Induced subgraphs of hypercubes and a proof of the sensitivity conjecture[END_REF] implies (among other results) that CREW PRAM running time is bounded from above by O(log S(f )). Among this literature, the reference most related to our work is that of Shlarpinski and von zur Gathen [START_REF] Von | The CREW PRAM complexity of modular inversion[END_REF], who used bounds on exponential sums and sensitivity to show that modular inversion requires depth Ω(log 2 (n)) on n-bit integers in the worst case, with a leading constant at most 1/2 in the Ω(•). To contrast, our results for modular squaring are worst-case with a leading constant of (at least) 2, and average-case with a leading constant 1 in front of the log 2 (n) term, allowing us to conclude interesting numerical lower bounds.

Useful Notions from Circuit Complexity

In this section, we generalize some known concepts and theorems from circuit complexity which will be useful in our average-case depth lower bounds. Two good general references on the subject are [START_REF] Wegener | The complexity of Boolean functions[END_REF][START_REF] Jukna | Boolean Function Complexity -Advances and Frontiers[END_REF]. In the following, let f : {0, 1} n → {0, 1} be a Boolean function. For a point x ∈ {0, 1} n and index i ∈ [n], we define x (i) to be x with the i-th bit flipped to the opposite value. All of the following results hold over any basis of fan-in two Boolean functions, including B 2 .

Non-Degeneracy

Roughly speaking, a function f is non-degenerate if it depends on all of its inputs.

Definition 1. A function f is non-degenerate if for all i ∈ [n], there is an a ∈ {0, 1} n such that f (a) = f (a (i) ).
That is, f is non-degenerate if, for all i, there is at least one input a such that flipping the i-th bit of a changes the value of f . A function f is degenerate if it is not non-degenerate. Intuitively, a degenerate function has at least one variable that does not affect the output: there is an i ∈ [n] such that for all assignments a, f (a) = f (a (i) ). Therefore the i-th bit of input does not affect the output.

It is not difficult to prove the following relation between non-degeneracy and circuit size. (We omit the proof, as we will prove a stronger result in a moment.) Proposition 1 (Folklore, [START_REF] Wegener | The complexity of Boolean functions[END_REF]). Every non-degenerate f has circuit complexity at least n -1, over the basis of all Boolean functions on two inputs.

Corollary 2. The AND, OR, and PARITY functions on n-bit inputs require circuits of size at least n -1.

Proposition 2 (Folklore). Every non-degenerate f has depth complexity at least log 2 (n), over the basis of all Boolean functions on two inputs.

Proof. The proof is by contrapositive. Consider any circuit C of depth d < log 2 (n). Since C has fan-in two and depth d, the circuit C can be converted into an equivalent formula F , with at most 2 d ≤ n -1 leaves. This equivalent formula F can read at most n -1 distinct inputs, so the function computed by F is degenerate (the missing input cannot affect the output of f ).

Corollary 3. The AND, OR, and PARITY functions on n-bit inputs require circuits of depth at least log 2 (n).

In the proofs of average-case lower bounds, we will require a natural generalization of the classic non-degeneracy concept, and its application to circuit complexity.

Definition 2. Let k ∈ {0, 1, . . . , n}. A function f is degenerate in k variables if there are k distinct i 1 , . . . , i k ∈ [n] such that for all a ∈ {0, 1} n and j ∈ [k], f (a) = f (a (ij ) ).
That is, f is degenerate in k variables if there are k different input indices i such that flipping the i-th bit of a does not change the value of f , for all inputs a. The following generalizes Proposition 1. Proposition 3. Let k ∈ {0, 1, . . . , n}. Every minimal fan-in two circuit with at most (n -1) -k gates is degenerate in (at least) k variables.

Proof. We prove the contrapositive. Let s be the number of gates in a minimal circuit for an f that is not degenerate in k variables. First, there must be at least n -k inputs in the circuit that have at least one outgoing wire. Otherwise, f would trivially be degenerate in (at least) k variables: k of the inputs have no outgoing wire, so flipping any of their values cannot change the circuit's output on any input. Note that each of the s gates have at least one outgoing wire: otherwise, that gate could be removed without changing the circuit's functionality, contradicting minimality.

Therefore the number of wires in a minimum circuit for f is at least n -k + s -1: there are at least n -k wires coming out of the inputs, and s -1 wires coming out of the interior gates (subtracting one for the output gate, which has no outgoing wire). Since each gate also has fan-in two (two edges coming into it), the number of wires in the circuit is at most 2s. Therefore 2s

≥ n -k + s -1, implying s ≥ (n -1) -k.
The following is analogous to the proof of Proposition 2.

Corollary 4. Every f that is degenerate in at most k variables has depth complexity at least log 2 (n -k), over the basis of all Boolean functions on two inputs.

Sensitivity

We also use the classical concept of the sensitivity of a function.

Definition 3 ([Weg87]). The sensitivity of f at x ∈ {0, 1} n is the number of indices i ∈ [n] such that f (x (i) ) = f (x).
For concrete examples, note the PARITY function on n-bit inputs has sensitivity n at every point (flipping any bit changes the parity), and the AND function has sensitivity n at the all-ones input but sensitivity 0 at the all-zeroes input. A basic result about sensitivity is the following proposition: Proposition 4 ([CDR86, Weg87]). Suppose a function f : {0, 1} n → {0, 1} has sensitivity at least k at some point x. Then f requires at least k -1 gates and log 2 (k) depth, even over B 2 .

Proof. We prove the contrapositive. Suppose f has a minimal-size circuit C with at most k -2 gates. By the same argument as in Proposition 3, there must be at least v input nodes in C that do not have an outgoing wire, where k -2 = (n -1) -v. Noting that v = n -k + 1, this means that circuit C's output only ever depends on at most n -v = k -1 of the inputs. Therefore f has sensitivity at most k at every point. The depth lower bound of at least log 2 (k) follows analogously to the proof of Proposition 2.

Worst-Case Lower Bounds for Modular Squaring

In this section, we present worst-case depth lower bounds for squaring n-bit integers. We study the "middle bits" of the output, show they can efficiently compute symmetric Boolean functions, and use this information to prove an overall depth lower bound. Our approach proceeds by adapting a reduction of Furst-Saxe-Sipser [START_REF] Furst | Parity, circuits, and the polynomial-time hierarchy[END_REF], who showed how to reduce the PARITY function to MULTIPLICATION in constant depth. Recall that IS maps n-bit integers x to 2n-bit integers x 2 . We will show that low-depth circuits for IS can be used to obtain somewhat-low-depth circuits for the function SUM(x 1 , . . . , x Now we turn to the reduction. Let ∈ Z >0 . Consider the bits

) → i x i for ≥ Ω(n/ log n).
x i ∈ {0, 1} defined by x = -1 i=0 x i 2 i . Define the degree-(2 -1) polynomial p(x 0 , . . . , x -1 , y) := -1 i=0 y i + -1 i=0 x i • y +i .
In the following, we will construe p as a univariate polynomial in y, with coefficients which are polynomials in the x i .

Claim. The degree-(

2 -1) coefficient of p(x 0 , . . . , x -1 , y) 2 equals 2 -1 i=0 x i .
Proof. For notational simplicity, let c m be the degree-m coefficient of p(x 0 , . . . , x -1 , y). The degree-m coefficient is the sum of all products c i c j over ordered pairs (i, j) ∈ {0, 1, . . . , k} 2 such that i + j = m. Now let m = 2 -1. WLOG, consider the case where i < j. Then for each j there is exactly one i < j such that i + j = 2 -1, and i < < j. Thus c i c j = x j-, and the coefficient is 2 2 -1 j= x j-= 2 i x i by double-counting the pairs (i, j) and (j, i).

Set k := 2 + log 2 ( ) , and consider the polynomial q(x 0 , . . . , x -1 ) := p(x 0 , . . . , x -1 , 2 k ).

We claim that, for all a ∈ {0, 1} , the binary representation of q(a) 2 contains i a i as a substring. By Claim 4, 2 i x i is the coefficient of y 2 -1 in p 2 . For j = 0, . . . , 2 -1, note that each coefficient of y j in p(a, y) 2 is at most j + 1, since the coefficients of p(a, y) (in the variable y) are in {0, 1}. Thus by setting y := 2 k > 2 , each coefficient c j of y j in p(a, y) 2 is less than y, for j = 0, . . . , 2 -1. It follows that each such coefficient c j appears as a binary substring in the bit representation of q(a) 2 . In particular, the sum of all terms of degree less than 2 -1 in p(a, y)

2 contributing to q(a) 2 is 2 -2 j=0 c j y j ≤ 2 -2 j=0 (j + 1) • 2 jk < 2 (2 -1)k .
Moreover, all terms of degree greater than 2 -1 in p(a, y) 2 appearing in q(a) 2 are multiplied by

y 2 = 2 2 k > 2 • 2 (2 -1)k ≥ (2 i x i )y 2 -1 .
Therefore 2 i a i appears as a substring in the output, i.e., the substring representing i a i followed by a 0.

We have shown the output of IS(q(a)) contains the quantity i a i in binary. Given a circuit C for integer squaring on b bits, we can "implement" q(a) by simply plugging in appropriate zeroes into the inputs of C. We have proven the following. Thus, lower bounds for SUM imply lower bounds for IS. We will utilize the following classical lower bound of Krapchenko [START_REF] Wegener | The complexity of Boolean functions[END_REF].

Proposition 6 (Krapchenko 1972). Every circuit for SUM on -bits requires depth at least 2 log 2 ( ).

Proof. The least significant bit of SUM is the PARITY function on bits, for which Krapchenko showed a 2 log 2 ( ) depth lower bound.

Applying Proposition 6 and Theorem 4 yields a worst-case lower bound for IS.

Theorem 5. For every circuit with AND and OR gates (and NOT gates for free), IS on n-bit integers requires depth at least 2 log 2 (n) -2 log 2 log 2 (n) -2.

Proof. Given any depth-d circuit for IS on integers of bitlength n := 4 + 2 log 2 ( ), Theorem 4 and its corollary show that we get a depth-d circuit for SUM on -bit inputs. But the least significant bit of SUM is precisely PARITY, so we also obtain a depth-d circuit for PARITY. Observe that for all ≥ 1, we have ≥ n/(2 log 2 (n)). Therefore by Proposition 6, we must have

d ≥ 2 log 2 ( ) ≥ 2(log 2 (n) -log 2 log 2 (n) -1).
Combining Theorem 5 and Proposition 5, we obtain the desired worst-case lower bounds for MS.

Reminder of Theorem 1. For every n, every logic circuit over U 2 computing MS on n-bit integers requires depth at least 2 log 2 (n -1) -2 log 2 (log 2 (n -1) -1) -4.

Corollary 5. For every circuit with AND and OR gates (and NOT gates for free), MS on 2048-bit integers requires depth at least 12.

A Generalization. The above approach gives a reduction from IS to SUM, and appeals to lower bounds on computing SUM. The best-known depth lower bound for SUM (in fact, for any symmetric function) is only 2 log n (see [START_REF] Gál | Cubic formula size lower bounds based on compositions with majority[END_REF]) and this has been the state-of-the-art since the 1970s [START_REF] Vm Krapchenko | Asymptotic estimation of addition time of parallel adder[END_REF].

We observe a generalization of the above reduction that strongly suggests the possibility of larger depth lower bounds. Recall that a symmetric Boolean function f : {0, 1} n → {0, 1} has the property that its output is determined solely by the number of 1's in its input. In other words, f is symmetric if there is a "spectrum" function g : {0, 1, . . . , n + 1} → {0, 1} such that for all a ∈ {0, 1} n , f (a) = g( i a i ). Classic examples of symmetric functions include OR, AND, MAJORITY, PARITY, and MODm (which outputs 1 if and only if the sum of its inputs is divisible by m). Theorem 6. Suppose there is a symmetric Boolean function f : {0, 1} n → {0, 1} with depth complexity at least c log 2 (n), such that its spectrum function g has a depth-d(n) circuit on input of length 1 + log 2 (n) . Then, IS has depth complexity at least c(log

2 (n) - log 2 log 2 (n) -2) -d(n/(2 log n)).
The depth d(n) of the spectrum function is typically very small, as the input to the spectrum function is only about log(n) bits. For example, with the PARITY function, the spectrum function g has a depth-zero circuit: we only have to output the least significant bit of the input. For the MAJORITY function, when the number of input bits is a power of two, we only have to output the most significant bit of the input. (When the number of inputs is not a power of two, we have to check that the input number is at least a fixed number, which can be done in O(log log n) depth, with small constant in the big-O.) In general, we expect d(n) to be at most O(log log n) for natural symmetric functions.

Proof of Theorem 6. Given any circuit of depth D for IS on n-bit inputs, we first obtain a depth D circuit for SUM on -bit inputs, for ≥ n/(2 log 2 n) as described above. The output of SUM is 1 + log 2 ( ) bits, encoding an integer in {0, 1, . . . , }. If the spectrum function g has depth d( ), then we can compute f from the SUM in only d( ) additional depth. Thus we get a circuit for f on -bit inputs of depth D + d( ). Assuming f has depth complexity at least c log 2 ( ), we have D ≥ log 2 ( ) -d( ).

For SUM, the lowest-depth circuits over AND/OR/NOT known still have depth larger than 4 log 2 (n); when XOR gates are included, the depth is still greater than 3 log 2 (n). In particular, it is known how to construct circuits for SUM with depth 4.14 log 2 (n) (over AND/OR/NOT) and 3.02 log 2 (n) (over AND/OR/NOT/XOR); the current best known result seems to be by Sergeev [START_REF] Sergeevich | Complexity and depth of formulas for symmetric boolean functions[END_REF]. Thus there is still a fairly wide gap (2 log n versus 4.14 log n) between lower bounds and upper bounds on the depth complexity of SUM, and we might expect to improve our concrete lower bound for MS by another factor of two, as follows.

Corollary 6. If SUM on n bits requires depth 4 log n over AND/OR/NOT, then IS on n bits requires depth 4 log 2 (n) -4 log log(n) -4. For n = 2048, the depth lower bound is at least 26.

The following is immediate, using the reduction from IS to MS of Proposition 5.

Reminder of Theorem 2. Suppose SUM requires depth at least c log 2 (n) for a constant c > 2. Then MS on n-bit integers requires depth at least c log 2 (n -1) -c log 2 (log 2 (n -1) -1) -2c.

Discussion

The above results show how to lower bound the depth of integer squaring (IS) using a lower bound on SUM. One might think there could be significant "loss" in reducing IS to a simple-looking problem like SUM, but surprisingly, this is not actually the case. It is also known that the depth of multiplication can be upper bounded by low-depth circuits for SUM, so the two problems are in fact tightly correlated in terms of depth complexity.

Theorem 7 [START_REF] Vm Krapchenko | Asymptotic estimation of addition time of parallel adder[END_REF] as cited in [START_REF] Sergeevich | Complexity and depth of formulas for symmetric boolean functions[END_REF]). Given a depth-d circuit for SUM on n-bit input, there is a circuit for multiplication of two n-bit numbers of depth at most d + log 2 (n).

Applying the results of [START_REF] Sergeevich | Complexity and depth of formulas for symmetric boolean functions[END_REF] to this theorem, the lowest-depth circuits known for multiplication (and thus squaring) have depth 4.02 log 2 (n) over all fan-in two gates, and depth 5.14 log 2 (n) over AND/OR/NOT gates.

The arguments of this section proving for worst-case depth lower bounds do not look directly helpful for trying to prove an average case lower bound against IS or modular squaring. In particular, when we reduce from SUM to IS, the resulting distribution of inputs is far from nice and uniform: starting from an n-bit input to a symmetric Boolean function, we insert many zeroes in specific places in the corresponding input to IS. We will need a different sort of argument to prove average-case lower bounds.

Average-Case Lower Bounds

We now turn to proving average-case lower bounds for MS, where our discussion will culminate in the proof of Theorem 3.

Reminder of Theorem 3. Let n ≥ 38, and let m be the product of two primes in [2 n/2-1 , 2 n/2 ). Every logic circuit computing (x 2 mod m) correctly on at least 76% of all n-bit integers x (over the basis U 2 or B 2 ) requires depth at least log 2 (n/4 -7.2).

Our proof will rely critically on sensitivity arguments, as defined and described in Section 3. As a warm-up, let us begin with a short argument that the n-th output of IS (integer squaring without modular reduction) requires about log(n) depth in the worst case, via a sensitivity argument. Note that this bound is worse than that proved in the previous section, but it will be motivating for the average case. Theorem 8. There is an n-bit x such that the n-th output bit of IS has sensitivity at least n/2 -1 at the point x.

Proof. For simplicity assume n is even, and let x := n-1 j=n/2+1 2 j . Observe x2 has a 0 in the n-th output of IS, because x 2 = j,k≥n/2+1 2 j+k , and j + k > n for all j, k.

For every i = 0, . . . , n/2 -2, there is exactly one j

∈ [n/2 + 1, n -1] such that i + j = n -1. Therefore (x (i) ) 2 = (x + 2 i ) 2 = j,k≥n/2+1 2 j+k + n-1 j=n/2+1 2 i+j+1 + 2 2i
has a 1 in the n-th output (all i + j + 1's are distinct, larger than 2i, and smaller than the j + k's).

Applying Proposition 4 directly, we get a (weak) depth lower bound for IS.

Corollary 7. The n-th output bit of IS on n-bit integers requires depth at least log

2 (n/2 - 1) ≥ log 2 (n) -2.
We would like to extend such an argument to hold for the average case, showing that any circuit that can approximately compute IS still requires an interesting level of depth. The first obvious problem is that the "bad" input x being chosen in the proof of Theorem 8 is not at all "random"! What we would like to show is that sensitivity of IS on random points is high. Given such a result, we could then use it to prove that all small circuits cannot approximate IS well in the average case.

The Framework. Let δ ∈ (0, 1] and ε ∈ (0, 1/2) in the following.

Definition 4 ((δ, ε)-sensitivity). A function

f : {0, 1} n → {0, 1} is (δ, ε)-sensitive if there are at least δn distinct values i ∈ {0, 1, . . . , n -1} such that Pr x∼{0,1} n f (x) = f x (i) ≥ 1/2 -ε.
For small ε > 0, (δ, ε)-sensitivity means that there are at least δn input indices such that, for approximately half of the possible inputs x, f is sensitive at x on all of those input indices. For our lower bounds, we will want ε to be as small (close to 0) as possible, and we want δ to be as large (close to 1) as possible. 2 The utility of (δ, ε)-sensitivity is captured by the following theorem.

Theorem 9. Let ε ∈ (0, 1/2) and δ ∈ (0, 1]. Assume f is (δ, ε)-sensitive. Then for all n ≥ 1, every fan-in two circuit with at most δn -2 gates fails to compute f on at least a (1/4 -ε/2)-fraction of all n-bit inputs. A similar statement hold for any (fan-in two) circuit with depth at most log 2 (δn -1).

Proof. Let C be any n-input circuit with δn -2 gates. First of all, note if δn -2 < 1 then the theorem is trivial. Without loss of generality, C is minimal (otherwise, let us take a minimum-size circuit equivalent to C). Recall that Proposition 3 (Section 3) shows that every minimal fan-in two circuit with at most (n -1) -k gates is degenerate in at least k variables. Thus our circuit C is degenerate in at least n + 1 -δn variables (for example, if δ = 1, then C is degenerate in at least one variable). Thus there are variable indices i 1 , . . . , i n+1-δn ∈ [n] such that For every x ∈ {0, 1} n and j = 1, . . . , n + 1 -δn, C(x) = C(x (ij ) ).

(1)

We show that, under the hypotheses, that C fails to compute f correctly on at least a 1/4 -ε/2 fraction of all n-bit inputs. The key observation is that, if f is (δ, ε)-sensitive, then there are at least

δn distinct i ∈ [n] such that Pr x∼{0,1} n [f (x) = f (x (i) )] ≥ 1/2 -ε, (2)
but there are also at least n + 1 -δn values in [n] such that C(x) = C(x (ij ) ) is true for all x. By the pigeonhole principle, there must be an index i ∈ [n] such that both C(x) = C(x (i) ) holds for all x, and (2) is true.

Fix such an i, and pair up all inputs in {0, 1} n into the 2 n-1 disjoint pairs (x,

x (i) ). Define S := {(x, x (i) ) | f (x) = f (x (i) )}. Since f is (δ, ε)-sensitive, there are at least (1/2 -ε) • 2 n distinct x ∈ {0, 1} n such that the pair (x, x (i) ) has f (x) = f (x (i) ). This implies |S| ≥ (1/2 -ε) • 2 n-1 .
By our choice of i, we also have C(x) = C(x (i) ) for all x. Because f (x) = f (x (i) ) for all (x, x (i) ) ∈ S, it follows that C computes f correctly on exactly one string in each pair (x, x (i) ) ∈ S. Therefore there are at least (1/2 -ε) • 2 n-1 = (1/4 -ε/2) • 2 n inputs y such that C(y) = f (y), so the circuit C errs on at least a 1/4 -ε/2 fraction of all inputs.

The depth lower bound follows analogously to the proof of Proposition 2.

Applying the Framework. We would like to apply Theorem 9 to obtain Theorem 3. This requires us to study the (δ, ε)-sensitivity of bits of modular squaring. On a number-theoretic level, it is easier to work with the situation of picking x at random from Z/mZ, but for the purposes of applying Theorem 3, we need to consider the case where x is a uniform random n-bit string (viewed as an integer in {0, 1, . . . , 2 n -1}). To this end, consider the experiment when we pick x ∈ {0, 1} n at random, and let x (i) be the i-th bit flipped. More formally, if x = (x n-1 , . . . , x 0 ) ∈ {0, 1} n , we can define

x (i) := x + (1 -2x i )2 i .
Note that under this definition, x (i) = x + 2 i if the i-th bit of x i is 0, and otherwise equals x -2 i . We observe an easy proposition.

Proposition 7. The distribution of outputs of (x mod m) over x ∼ Z/mZ and the distribution of (x mod m) over x ∼ {0, 1, . . . , 2 n -1} are identical, up to additive 1/2 n factors in the probabilities.

Proof. Consider the distribution D which chooses a uniform random x ∈ {0, 1, . . . , 2 n -1}, and outputs (x mod m) ∈ {0, . . . , m -1}. This distribution D partitions {0, . . . , 2 n -1} of cardinality 2 n into m equivalence classes, where each class contains at least 2 n /m -1 elements and at most 2 n /m + 1 elements. Thus for all t ∈ Z/mZ, we have

Pr x∼{0,1,...,2 n -1} [(x mod m) = t] ∈ [1/m -1/2 n , 1/m + 1/2 n ]. Hence Pr x∼{0,1,...,2 n -1} [(x mod m) = t] -Pr x∼Z/mZ [(x mod m) = t] ≤ 1/2 n .
Therefore, the two distributions of outputs of (x 2 mod m) mod 2 (over x ∼ Z/mZ and x ∼ {0, 1, . . . , 2 n -1}) are also identical up to 1/2 n as well, so proving (δ, ε)-sensitivity results for x chosen at random from Z/mZ imply analogous results for x chosen at random from {0, 1} n (construed as a non-negative integer).

The following two results are proved in Section 6 and Section 6.1. Keeping in mind Proposition 7, these results are immediate corollaries of Theorem 12 and Theorem 13, respectively.

Theorem 10 (Squaring Sensitivity Theorem 1). For all odd 2 n-1 ≤ m ≤ 2 n -1, and all ε > 0, the function MS-MOD2 n,m is 1/4 + log 2 (ε) n + o(1), ε -sensitive, where o(1) does not depend on ε and lim n→∞ o(1) = 0.

To obtain concrete lower bounds, one should explicitly estimate the o(1) term appearing in Theorem 10. When m is an RSA modulus (the case of interest in all modular squaring applications we are aware of) we obtain the following explicit result.

Theorem 11 (Squaring Sensitivity Theorem 2). For all n ≥ 38, let p, q be primes in

[2 n/2-1 , 2 n/2 ). For all ε > 0, the function MS-MOD2 n,pq is 1/4 + log 2 (ε)-log 2 (5.8) n , ε - sensitive.
Putting the pieces together, we can complete the proof of Theorem 3.

Proof of Theorem 3. Let C be a circuit computing MS correctly on at least 76% of all n-bit integers, modulo an RSA modulus m as specified in the theorem. By Theorem 11, the least significant output bit of C is 1/4 + log 2 (ε)-log 2 (5.8) n , ε -sensitive. By Theorem 9, every fan-in two circuit with at most δn -2 gates fails to compute f on at least a (1/4 -ε/2)fraction of all n-bit input, where δ = 1/4 + log 2 (ε)-log 2 (5.8) n . Setting ε = 1/50, the fraction becomes 24%, and δn = n/4 + log 2 (1/50) -log 2 (5.8) > n/4 -8.2. Therefore the circuit size lower bound is at least n/4 -8.2, and the resulting depth lower bound is at least log 2 (n/4 -7.2) (by an analogous argument as the proof of Proposition 2).

Discussion

Before we move to the proofs of the Squaring Sensitivity Theorems, it is worth noting why we had to introduce a notion of (δ, ε)-sensitivity, to prove what we did. It would be natural to conjecture (and we originally did) that for all indices i ∈ [n], the loworder bit of (x 2 mod m) differs from the low-order bit of ((x (i) ) 2 mod m) with probability approximately 1/2, over a uniform random choice of x ∼ Z/mZ. Conjecture 1 (A Bad Squaring Sensitivity Conjecture). For all fixed constant ε > 0, for all large enough n, for all odd (square-free) 2 n-1 ≤ m ≤ 2 n -1, and for all i ∈ {0, 1, . . . , n -1},

Pr x∼Z/mZ [(x 2 mod m) mod 2 = ((x (i) ) 2 mod m) mod 2] ≥ 1/2 -ε.
That is, Conjecture 1 posits that the parity of (x 2 mod m) differs from the parity of ((x (i) ) 2 mod m) with probability very close to 1/2, when x is chosen uniformly at random from Z/mZ. It turns out that Conjecture 1 is false as stated (reference omitted here to preserve anonymity) and we had to resort to weaker claims where a δ-fraction of the variables are sensitive on random inputs for some δ < 1.

The Least Significant Bit of Modular Squaring

Let m be any odd, positive integer. Recall we identify Z/mZ with {0, . . . , m -1}, so that x mod m denotes the least positive residue of x modulo m. For the rest of this section, let f : Z/mZ → C × be the function induced by MS-MOD2 n,m , i.e.,

f (x) = 0 if x mod m is even, 1 if x mod m is odd,
For any integer i, and any x ∈ Z/mZ, let x (i) be the class of x mod m with the i-th bit flipped. The goal of this section to prove the following theorem, which states that for any integer i ∈ [0, log 2 (m)(1/4 + o(1))], the least significant bits of x 2 and (x (i) ) 2 are essentially independent, when x ∈ Z/mZ is uniformly distributed.

Theorem 12. We have

#{x ∈ Z/mZ | f (x 2 ) = f ((x (i) ) 2 )} m - 1 2 = 2 2i m 1/2+o(1) .
Notation. For any x ∈ R, let e(x) = e 2πix . For any integer a, define the character χ a of Z/mZ as χ a (x) = e ax m . For any integer x, let x m = min(x mod m, (-x) mod m) be the distance of x to the closest multiple of m. The function log is the natural logarithm, in base e.

We now prove Theorem 12, and in Section 6.1, we specialise it to the case of RSA moduli and obtain explicit bounds. Let f (i) (x) be the i-th least significant bit of x mod m. In particular, for our function f we have f = f (0) . These functions f (i) are useful to study how flipping the i-th bit affects the output of any function g : Z/mZ → C, since

g x (i) = f (i) (x)g(x -2 i ) + (1 -f (i) (x))g(x + 2 i ). (3)
In particular, these bit functions can be used to compute the size of the set in Theorem 12.

Lemma 1. We have

#{x ∈ Z/mZ | f (x 2 ) = f ((x (i) ) 2 )} = 2A -4C + ε, where |ε| ≤ 2 i+2 , A = x f (x 2 ), and C = x f (i) (x)f (x 2 )f ((x -2 i ) 2 ).
Proof. We have

#{x ∈ Z/mZ | f (x 2 ) = f ((x (i) ) 2 )} = x f (x 2 ) + x f ((x (i) ) 2 ) -2 x f (x 2 )f ((x (i) ) 2 ).
Applying Equation (3) to the function g : x → f (x 2 ), we have

f ((x (i) ) 2 ) = f (i) (x)f ((x -2 i ) 2 ) + f ((x + 2 i ) 2 ) -f (i) (x)f ((x + 2 i ) 2 ). Let A = x f (x 2 ), B α = x f (i) (x)f ((x + α) 2 ), C α = x f (i) (x)f (x 2 )f ((x + α) 2 ), D α = x f (x 2 )f ((x + α) 2 ), for α = ±2 i . Then, #{x ∈ Z/mZ | f (x 2 ) = f ((x (i) ) 2 )} = 2A -(B 2 i -B -2 i ) + 2(C 2 i -C -2 i ) -2D 2 i . Let us estimate |B 2 i -B -2 i |. With S = {x | f (i) (x + 2 i+1 ) = f (i) (x)}, we have B -2 i = x f (i) (x)f ((x -2 i ) 2 ) = x f (i) (x + 2 i+1 )f ((x + 2 i ) 2 ) = x f (i) (x)f ((x + 2 i ) 2 ) + x∈S (f (i) (x + 2 i+1 ) -f (i) (x))f ((x + 2 i ) 2 ) = B 2 i + x∈S (1 -2f (i) (x))f ((x + 2 i ) 2 ). Since #S ≤ 2 i+1 , we deduce |B 2 i -B -2 i | ≤ 2 i+1 . Now, with T = {x | f (i) (x + 2 i ) = 1 -f (i) (x)}, C -2 i = x f (i) (x)f (x 2 )f ((x -2 i ) 2 ) = x f (i) (x + 2 i )f ((x + 2 i ) 2 )f (x 2 ) = x (1 -f (i) (x))f ((x + 2 i ) 2 )f (x 2 ) + x∈T (2f (i) (x) -1)f ((x + 2 i ) 2 )f (x 2 ) = D 2 i -C 2 i + x∈T (2f (i) (x) -1)f ((x + 2 i ) 2 )f (x 2 ). Since #T ≤ 2 i , we deduce that |C 2 i + C -2 i -D 2 i | ≤ 2 i . 2A + (B -2 i -B 2 i ) + 2(C 2 i -C -2 i ) -2D 2 i = 2A -4C -2 i + ε, where ε = (B -2 i -B 2 i ) + 2(C 2 i + C -2 i -D 2 i ), so |ε| ≤ 2 i+2 .
Fourier decomposition of the bit functions. It remains to estimate the terms A and C from Lemma 1. To do so, we decompose the bit functions f (i) as character sums.

Proposition 8. We have the Fourier decomposition

f (x) = 1 m χ∈ Z/mZ c χ χ(x),
with c χ0 = m-1 2 and c χ = -1 1+χ(1) for any χ = χ 0 .

Proof. We have

f (x) = 1 m χ c χ χ(x), where c χ = x∈Z/mZ f (x)χ(x). Let T = {x ∈ Z/mZ | f (x) = 1}. We have c χ0 = |T | = m-1 2 . Now, c χ = x∈T χ(x) = x∈T χ(x + 2) + χ(1) -χ(m) = c χ χ(2) + χ(1) -1. We deduce that c χ = -(1 -χ(1))/(1 -χ(2)) = -1/(1 + χ(1)) for any χ = χ 0 .
The following lemma allows to bound the Fourier coefficients c χ , as well as the coefficients of the functions f (i) , in Proposition 9.

Lemma 2. For any integers a and b, we have

1 |1+χa(b)| ≤ m 2(m-2 ab m ) .
Proof. Observe that, for any x ∈ [0, 1], we have 1 + cos(2πx) ≥ 2(2x -1) 2 . So for any x ∈ [0, 1], we have

1 |1+e(x)| = 1 √ 2+2 cos(2πx) ≤ 1 2|2x-1|
. Therefore, for any integers a and b,

1 |1+χa(b)| ≤ m 2|2(ab mod m)-m| = m 2(m-2 ab m ) .
Proposition 9. For all i ∈ [n], we have the Fourier decomposition

f (i) (x) = 1 m χ∈ Z/mZ c (i) χ χ(x), with c (i) χ0 -m 2 ≤ 2 i-1 and c (i) χa ≤ m2 i 2(m-2 a2 i m) . Proof. Let T (i) = {x ∈ Z/mZ | f (i) (x) = 1}. First, we have c (i) χ0 = |T (i) |, and
|T (i) | -m 2 ≤ 2 i-1 . Now, for any character χ, c (i) χ = x∈T (i) χ(x) = x∈T (i) χ(x + 2 i+1 ) + 2 i+1 -1 x=2 i χ(x) - x∈T (i) |x+2 i+1 ≥m χ(x + 2 i+1 ). Let [z, z ] = [0, 2 i -1] ∩ {x + 2 i+1 -m | x ∈ T (i)
and x + 2 i+1 ≥ m}. For any non-trivial χ, we have χ(2 i+1 ) = 1 (recall that m is odd), so

c (i) χ = 1 1 -χ(2 i+1 )   z x=z (χ(x + 2 i ) -χ(x))   = -1 1 + χ(2 i )   z x=z χ(x)   . It follows that c (i) χa ≤ m2 i 2(m-2 a2 i m) .
Notation 1. In the rest of the paper, we use the notation c χ and c (i) χ for the Fourier coefficients of f and f (i) given in Propositions 8 and 9 respectively.

Gauss sums. Observe that

A = x f (x 2 ) = 1 m χ c χ x χ(x 2
), and x χ(x 2 ) is a Gauss sum. Generalised Gauss sums also appear in C, and play an important role in our estimates of these two quantities. Estimating A. Here we estimate the term A from Lemma 1.

Lemma 4. For any odd positive integer h,

h-1 k=0 1 h-2 k h ≤ log(h) + 2.31. Proof. The result is immediate if h = 1. For h > 1, we have h-1 k=0 1 h -2 k h = (h-1)/2 k=1 2 2k -1 + 1 h ≤   2 + (h-1)/2 k=1 1 k   ≤ log(h -1) + 3 -log(2) ≤ log(h) + 2.31,
where the penultimate inequality uses

n k=1 1 k ≤ log(n) + 1.
Proposition 10. We have

A - m + 1 2 ≤ √ m 2 g|m,g =m 1 √ g (log(m/g) + 2.31) .
Proof. For any integer a, define the character χ a (x) = e(ax/m). We get

A = x f (x 2 ) = 1 m a c χa x χ a (x 2 ) = 1 m a c χa G(a, 0, m) = m + 1 2 + 1 m a =0
G(a, 0, m) 1 + χ a (1) .

Applying Lemma 3, we get

A - m + 1 2 = 1 m a =0 G(a, 0, m) 1 + χ a (1) ≤ 1 √ m a =0 (a, m) |1 + χ a (1)| (4) = 1 √ m g|m,g =m √ g k∈(Z/(m/g)Z) × 1 |1 + χ gk (1)| . ( 5
)
With h = m/g, and applying Lemmata 2 and 4, we have

k∈(Z/hZ) × 1 |1 + χ gk (1)| ≤ h-1 k=0 h 2(h -2 k h ) ≤ h 2 (log(h) + 2.31) ,
We conclude by applying the above inequality to Equation (5).

Estimating C. We turn to estimating the term C from Lemma 1. We have

C = x f (i) (x)f ((x -2 i ) 2 )f (x 2 ) = 1 m 3 a,b,c c (i) χa c χ b c χc x χ a (x)χ b ((x -2 i ) 2 )χ c (x 2 ).
With d = b + c = kg where g = gcd(d, m), and f = a -b2 i+1 = g , we get

C = 1 m 3 a,b,c c (i) χa c χ b c χc e b2 2i m G(b + c, a -2b2 i , m) = 1 m 3 b,d,e c (i) χ f +b2 i+1 c χ b c χ d-b e b2 2i m G(d, f, m) = g|m b∈Z/gZ E(g, b),
where

E(g, b) = 1 m 3 k∈(Z/(m/g)Z) × n, ∈Z/(m/g)Z c (i) χ g+b2 i+1 c χ ng+b c χ kg-b e b2 2i m G(kg, g, m).
Applying Lemma 3, we get

|E(g, b)| ≤ √ m m 3 k∈(Z/(m/g)Z) × n, ∈Z/(m/g)Z |c (i) χ g+b2 i+1 c χ ng+b c χ kg-b | √ g
Fixing a divisor g of m, and a non-zero element b ∈ Z/gZ, the quantity |E(g, b)| is at most

√ mg2 i 8   m/g-1 =0 1 m -2 ( g + b2 i+1 )2 i m     m/g-1 n=0 1 m -2 ng + b m     m/g-1 k=0 1 m -2 kg -b m   .
Lemma 5. For any divisor g of m and any integer b, we have

m/g-1 k=0 1 m -2 kg + b m ≤ 1 g -2 b g + log(m/g) + 2.31 g .
Proof. Without loss of generality, b = b g ≤ (g -1)/2. There is at most one k-value such that m -2 kg -b m < g. It is the value k = (m/g -1)/2, for which we have m -2 kg -b m = g -2 b g . Splitting the sum around this value, we have

m/g-1 k=0 1 m -2 kg + b m = 1 g -2 b g + (m/g-1)/2-1 k=0 1 m -2 kg + b m + m/g-1 k=(m/g-1)/2+1 1 m -2 kg + b m ≤ 1 g -2 b g + (m/g-1)/2-1 k=0 1 m -2 (k + 1)g m + m/g-1 k=(m/g-1)/2+1 1 m -2 kg m = 1 g -2 b g + 1 g m/g-1 k=1 1 (m/g) -2 (k + 1) m/g ≤ 1 g -2 b g + log(m/g) + 2.31 g ,
where the last inequality comes from Lemma 4.

Let L(g) = log(m/g)+2.31 g for g = m and L(m) = 0.

Proposition 11. For any g | m, we have

g-1 b=1 |E(g, b)| ≤ √ mg2 i-3 (L(g) + 2.83),
where L(g) = L(g) 3 log(g) + 6.93 + 3(g -1)L(g) + (g -1)L(g) 2 . If 2 2i < g/12, we have

g-1 b=1 |E(g, b)| ≤ √ mg2 i-3 L(g) + 5.66 + 2 2i+3 g .
Proof. We have

|E(g, b)| ≤ √ mg2 i 8 1 g -2 b2 2i+1 g + L(g) 1 g -2 b g + L(g) 2 , ≤ √ mg2 i 8 L(g) 3 g -2 b g + 3L(g) + L(g) 2 + 1 g -2 b2 2i+1 g 1 (g -2 b g ) 2 .
Now let us sum these terms for all non-zero values of b ∈ Z/gZ. Applying Lemma 4,

g-1 b=1 3 g -2 b g + 3L(g) + L(g) 2 ≤ 3(log(g) + 2.31) + 3(g -1)L(g) + (g -1)L(g) 2
It remains to estimate

g-1 b=1 1 g -2 b2 2i+1 g 1 (g -2 b g ) 2 = 2 (g-1)/2 b=1 1 g -2 (2b -1)2 2i g 1 (2b -1) 2 . First, we have 2 (g-1)/2 b=1 1 g -2 (2b -1)2 2i g 1 (2b -1) 2 ≤ 2 (g-1)/2 b=1 1 (2b -1) 2 = 2 (g-1)/2-1 b=0 1 (2b + 1) 2 ≤ 2 1 + 1 4 ∞ b=1 1 b 2 = 2 + π 2 12 ≤ 2.83.
Finally, suppose that 2 2i < g/12. Let κ the largest integer such that b ≤ κ implies (2b -1)2 2i < g/4. On one hand,

κ b=1 1 g -2 (2b -1)2 2i g 1 (2b -1) 2 ≤ κ b=1 2 g 1 (2b -1) 2 ≤ 2.83 g .
On the other hand,

(g-1)/2 b=κ+1 1 g -2 (2b -1)2 2i g 1 (2b -1) 2 ≤ ∞ b=κ+1 1 (2b -1) 2 ≤ 1 4 1 κ -1 ≤ 2 2i+2 g ,
where the last two inequalities use the fact that 2 2i < g/12 (in particular, κ > 1).

Corollary 8. We have g|m

g-1 b=1 |E(g, b)| = m 1/2+o(1) 2 2i .
Proof. By Proposition 11, we have It remains to deal with the terms where b = 0.

Proposition 12. We have E(m, 0) -m 8 ≤ 2 i 8 , and for any g | m, g = m,

|E(g, 0)| ≤ g -1 2 √ mg L(g) m 2 + 2 i-1 + m2 i L(g) . Proof. First, we have E(m, 0) = c (i) χ 0 c 2 χ 0 m 2 . Since c χ0 = m-1 2 and c (i) χ0 -m 2 ≤ 2 i-1 , we get c (i) χ 0 c 2 χ 0 m 2 -m 8 ≤ (m+2 i ) 8 -m 8 ≤ 2 i
8 , and we deduce the first part of the proposition. Now suppose that g = m. We have

|E(g, 0)| ≤ √ mg m 3   ∈Z/(m/g)Z |c (i) χ g |   n∈Z/(m/g)Z c χng   k∈(Z/(m/g)Z) × |c χ kg |   .
Using the fact that Re(c χ ) = -1/2 and that c χ-a = c χa for any a, we get n∈Z/(m/g)Z

c χng = c χ0 - (m/g-1)/2 n=1 (c χa + c χ-a ) = m -1 2 - m/g -1 2 = m(g -1) 2g .
In particular, E(1, 0) = 0. From Lemma 4, we have

m/g-1 k=1 |c χ kg | ≤ m m/g-1 k=1 1 m -2 kg m ≤ m g (log(m/g) + 2.31) = mL(g).
Similarly,

m/g-1 =0 |c (i) χ g | ≤ |c (i) χ0 | + m2 i L(g) ≤ m 2 + 2 i-1 + m2 i L(g),
and the second part of the proposition follows.

Proof of Theorem 12. By Proposition 12, we have g|m,g =m |E(g, 0)| = m 1/2+o(1) 2 i . Together with Corollary 8, we obtain C -m 8 = m 1/2+o(1) 2 2i . By Proposition 10, we have

A -m 2 = m 1/2+o(1) . Recall from Lemma 1 that #{x ∈ Z/mZ | f (x 2 ) = f ((x (i) ) 2 )} = 2A -4C + ε,
where and |ε| ≤ 2 i+2 . Theorem 12 follows.

Application to RSA moduli

Theorem 13. Let p, q ∈ [2 b-1 , 2 b ) be two prime numbers of b bits, and suppose that b ≥ 19.

Then, for any non-negative integer i ≤ b/2,

#{x ∈ Z/mZ | f (x 2 ) = f ((x (i) ) 2 )} m - 1 2 ≤ 5.8 • 2 i 2 b/2 . Proof. Recall that #{x ∈ Z/mZ | f (x 2 ) = f ((x (i) ) 2 )} m - 1 2 ≤ 2 i+2 m + 2 m A - m 2 + 4 m C - m 8 .
Let us bound each of the three terms. First,

2 i+2 m ≤ 2 b/2+2 2 2b-2 ≤ 1 2 b/
m A - m 2 ≤ 1 √ m (log(m) + 2.41) ≤ 1 2 b-1 (2b log(2) + 2.41) ≤ 1 2 b/2 • 0.08. Now, we have 4 m C - m 8 ≤ 4 m E(m, 0) - m 8 + p-1 b=0 |E(p, b)| + q-1 b=0 |E(q, b)| + m-1 b=1 |E(m, b)| ≤ 2 i-1 m + 4 m p-1 b=0 |E(p, b)| + q-1 b=0 |E(q, b)| + m-1 b=1 |E(m, b)| . First, 2 i-1 m ≤ 1 2 b/2 • 1 2 18 .
+ q-1 b=1 |E(q, b)| ≤ 4 √ m ( √ p + √ q)2 i-3 2.84 ≤ 2 i • 5.68 2 b/2 .
We also have for g ∈ {p, q} that We deduce that 4 m C -m 8 ≤ 2 -18 +2 i •5.68+0.0002+0.0009+2 i •0.03

4 m |E(g, 0)| ≤ 2(g -1) m √ mg L(g) m 2 + 2 i-1 + m2 i L(g) ≤ log(m/g) + 2.31 √ mg 1 + 2 i m + 2 i+1 (log(m/g) + 2.31) g ≤ 1 2 b/2 b log(2) + 2.31 2 b-1.5 1 + 1 2 3b/2-2 + 4(b log(2) + 2.31) 2 b/2 ≤ 1 2 b/2 • 0.0001. Since i ≤ b/2 and b ≥ 19, we have 2 2i < m/12, therefore 4 m m-1 b=1 |E(m, b)| ≤ 2 i-1 L(m) + 5.66 + 2 2i+3 m ≤ 2 i-1 L(m)
2 b/2 ≤ 5.71•2 i +0.0012 2 b/2
. Finally,

#{x ∈ Z/mZ | f (x 2 ) = f ((x (i) ) 2 )} m - 1 2 ≤ 1 2 b/2
1 2 15 + 0.08 + 5.71 • 2 i + 0.0012 , and the result follows.

Conclusion

We have proven concrete time-delay results for modular squaring computations. Of course, one would like to prove more: that repeated squarings should also require higher depth. As discussed in the introduction, this seems extremely difficult to prove without making some unproven conjectures. Very recently, several papers [RS20, KLX20] have made significant progress on conditional lower bound results for repeated modular squaring. Still, there are several interesting open issues to consider, which do not seem too arduous to tackle. Below, we discuss two in detail.

Extending the Average-Case Lower Bounds. Considering Theorems 1 and 3 together, they suggest that for proving stronger average-case lower bounds, it may be fruitful to try proving an average-case lower bound for the "middle bits" of modular squaring, rather than a lower bound on the least significant bit of modular squaring, as is done in this paper. Perhaps a different (more involved) case analysis than the above can yield a 2 log 2 (n) depth lower bound for modular squaring in the average case, for all moduli m? It is known that the PARITY function on n bits requires depth 2 log(n) -O(1) to compute, even in the average case of uniform random input (see the discussion in [START_REF] Komargodski | Average-case lower bounds for formula size[END_REF]); this should be useful.

Modular Squaring in Other Representations. We have shown lower bounds for modular and integer squaring in the binary representation. In practice, one can convert a given integer into a different representation where repeated squaring is easier. Can similar lower bounds be proved for modular squaring in other number representations, such as redundant representations (as is used in some state-of-the-art modular multipliers [Özt20]) or the Chinese Remainder Representation?

Let us consider the latter, and sketch the challenges involved. In CRR, inputs are vectors x = (x 1 , . . . , x t ) where each x i ∈ Z/p i Z is written in binary for distinct co-prime p i , t ≤ O(n/ log n), each p i is O(log n) bits (so that i p i = Ω(2 n )). Letting int(x) be the non-negative integer representation of x, we wish to know the depth complexity of computing (int(x) 2 mod m) in Chinese Remainder Representation (CRR). This output would be a vector y = (y 1 , . . . , y t ) where each y i ∈ Z/p i Z is written in binary. Now, x < i p i can be squared, by squaring each component x i mod p i individually, which can be done in O(log log n) depth because each p i is only O(log n) bits. Correspondingly, the sensitivity of each output bit of integer squaring is only O(log n) for all integers in {0, 1, . . . , i p i }. However, for large x, we believe the modular reduction back to {0, 1, . . . , m -1} should be very sensitive to the CRR. For example, if some p i = 2, our CRR must track the parity of f (x) := (int(x) 2 mod m). It is natural to conjecture that f is highly sensitive even for x written in CRR: for each component x i of x, there should be many bits of x i such that flipping any of them changes the parity of some outputs, just as it changes x itself. (This is in line with the results we have proven about the parity of squaring modulo m.) If we can show that a random input has many sensitive indices (say, n/4) with nonzero probability, we will obtain interesting average-case depth lower bounds.

Open Problem Bounties

The Ethereum Foundation is offering first-come-first-served bounties for four specific open problems. If you believe you have a solution and wish to claim the bounty, contact information can be found at https://rsa.cash, or through the authors.

1. $5,000 Prove that for all n ≥ 128, SUM on n-bit inputs requires depth at least c log 2 (n) for some c > 2. (That is, improve upon Krapchenko's lower bound for SUM [START_REF] Vm Krapchenko | Asymptotic estimation of addition time of parallel adder[END_REF].) 2. $5,000 Prove that for all n ≥ 128, SUM on n-bit inputs requires depth at least 4 log 2 (n). (That is, prove the "reasonable hypothesis" stated immediately after Theorem 2. This $5,000 bounty is in addition to the $5,000 bounty above.)

3. $2,000 Prove that there is a c < 4 such that for all n ≥ 128, SUM has circuits of depth at most c log 2 (n). (That is, refute the "reasonable hypothesis", and do so for all large enough input lengths n.)

4. $3,000 Improve the average-case depth lower bound (Theorem 3) to c log 2 (n) for some c > 1, for any algorithm computing MS-MOD2 on at least 51% of the inputs.

  Let m ∈ Z >0 be our modulus. If we only consider integers x ∈ [0, √ m -1 ], then clearly (x 2 mod m) = IS(x), and our problem reduces to proving a depth lower bound for IS on integers x which are b bits long, where b = log(m -1)/2 . Let us record this simple observation. Proposition 5. Let m ≥ 2 be an integer. If IS requires depth-d circuits on b-bit input, where b = log(m -1)/2 , then computing (x 2 mod m) on b-bit input requires depth-d as well.

Theorem 4 .

 4 Let ∈ Z >0 . Given a depth-d circuit for IS on integers of bitlength b := 2 • k = 4 + 2 log 2 ( ), we can construct a depth-d circuit for SUM(a 1 , . . . , a ) = i a i on -bit inputs.

Definition 5 .Lemma 3 .t

 53 For any integers a, b, m, the generalised Gauss sum is G(a, b, m) = x∈Z/mZ e ax 2 + bx m . We have |G(a, b, m)| = (a, m)m if (a, m) | b, 0 otherwise. . Proof. This is a classical result; we include a proof for completeness. We have Since t e as+b m t is m if as + b ≡ 0 mod m and 0 otherwise. We conclude by counting the number of solutions of as + b ≡ 0 mod m.

  b)| = O σ0 (m) + log(m)σ -1/2 (m) + log(m) 2 σ-3/2 (m) m 1/2 2 2i , where σ x (m) = d|m d x is the divisor function and σx (m) = σ x (m) -1. The corollary follows from σ0 (m) + log(m)σ -1/2 (m) + log(m) 2 σ-3/2 (m) = m o(1) .

  Then, by Proposition 11, for any g | m, we haveg-1 b=1 |E(g, b)| ≤ √ mg2 i-3 (L(g) + 2.83). Moreover, for any integer x of at least 19 bits, we have L(x) ≤ 0.01.|E(p, b)|

Please note that the (δ, ε)-sensitivity of f is not at all the same as the concept in the literature of the "average sensitivity of f ", which is the expected value of the sensitivity of f at uniform random input.

Acknowledgements. We are grateful to Justin Drake and Dankrad Feist for approaching us, motivating us to work on this problem, and for useful discussions and references, as well as Simon Peffers and Erdinc Ozturk. Benjamin Wesolowski was supported by the Ethereum Foundation Grants program, through Grant FY19-0151. Ryan Williams was supported by NSF CCF-1909429 "Average-Case Fine-Grained Complexity" and the Ethereum Foundation.