First pass review and questions

[JustinDrake]

1) Would it make sense to add an introduction giving some motivation? In particular, explain that we are interested in better understanding the security of the adaptive root assumption for VDFs, batchable accumulators, and polynomial commitments. 2) "no efficient adversary can compute e-th roots a given random group element for a predefined e" => For clarity would it make sense to use the same notation everywhere, replacing e with l? 3) "for a predefined e" => Should this be for a random e? 4) In the definition of the RSA assumption, should the adversary be given l? That is, replace A(G, w) with A(G, w, l)? 5) "In [BFS19] A0 selects w, st randomly, which is probably an error. Also A1 does not take w as input, which does not make sense." => Could you confirm these issues with Benedikt? Ideally he would update the paper to minimise confusion. 6) "it holds for GGen" => Maybe explain a bit more what GGen. 7) In the definition of the QR-strong RSA Assumption, would it make sense to explain what is N, Z_N and QR_N? 8) In the definition of the adaptive root assumption, why did you specify "[with security parameter λ]"? It is not specified in the other definitions. 9) In the definition of the adaptive root assumption, is "G outputs an element w ∈ G" a typo? 10) In the definition of the adaptive root assumption, A1 takes different inputs "A1(w, st)" and "A1(w, l, st)". 11) "The number of primes in Primes(λ) should correspond to the hardness of factoring: it is possible to" => This sentence ends abruptly: it is possible to what? 12) The capitalisation in the bibliography titles seems to be messed up. 13) What is the meaning of the colours in the diagram? 14) In definition 12, what are script A and X? (See w1, w2 ∈ A ∪ X.) 15) For generic groups, you write "It is modelled as an oracle O, who knows the group order n". Isn't the point that we assume the group order is not known? 16) "we reduce u^c to Lemma 2" => What is lemma 2? There's only lemma 1. 17) "Relations among different assumptions in an RSA subgroup" => Why did you write "RSA subgroup" (as opposed to RSA group)? 18) In Theorem 9 are the examples easy enough to construct that they can be specified in the survey? 19) "The Order, RSA, Strong RSA, Discrete Log assumptions are independent" => The word "independent" may be a bit misleading. Indeed, there are relations between these assumptions. 20) "Factoring assumption states that for random safe primes p, q it is difficult to factor N = pq" => What about non-safe primes? The primes generated by the RSA MPC will not be safe. 21) "If the RSA modulus is based on strong primes" => Worth putting the definition of "strong prime". Indeed, Wikipedia suggests there are various definitions. 22) In the fractional root assumption, should we discard trivial solutions (e.g. g = u and l = a)? 23) Should we add a note that the RSA group trivially does not satisfy many of the assumptions, and that we should quotient it out by {1, -1}?

[khovratovich]

1. Done

[khovratovich]

2. Done 3-4. Yes, the adversary gets everything as input. 6.,7 Done

[khovratovich]

8, 11 done

[khovratovich]

9, 10, 12, 13, 14, 15,16,17. Fixed

[khovratovich]

18, 19 elaborated (shortly, no). 20, 21, 22 - fixed.

[khovratovich]

5 - The definition by Wesolowski is similar to mine, so I think it is fine. I will ask the DARK authors at some point. 23 - done.