Generic Group Delay Functions Require Hidden Order Groups

Generic Group Delay Functions Require Hidden Order Groups-PDF Download

  • Date:31 Jul 2020
  • Views:5
  • Downloads:0
  • Pages:23
  • Size:611.44 KB

Share Pdf : Generic Group Delay Functions Require Hidden Order Groups

Download and Preview : Generic Group Delay Functions Require Hidden Order Groups


Report CopyRight/DMCA Form For : Generic Group Delay Functions Require Hidden Order Groups


Transcription:

1 Introduction 1,1 1 Our Contributions 1,1 2 Related Work 2. 1 3 Overview of Our Approach 3,1 4 Paper Organization 7. 2 Preliminaries 8,2 1 Generic Groups and Algorithms 8. 2 2 Generic Group Delay Functions 9,3 Our Impossibility Result 10. 4 Extending Our Impossibility Result to the Multilinear Setting 12. 4 1 Generic Multilinear Groups 13,4 2 Proof of Theorem 4 1 14.
5 Additional Extensions 17,References 18, A Fast Internal Computation via Smith Normal Forms 20. 1 Introduction, The classic notion of a time lock puzzle introduced by Rivest Shamir and Wagner RSW96 and the. recent notion of a verifiable delay function introduced by Boneh et al BBB 18 are instrumental. to a wide variety of exciting applications such as randomness beacons resource efficient blockchains. proofs of replication and computational timestamping Underlying both notions is the basic notion of. a cryptographic delay function For a delay parameter T evaluating a delay function on a randomly. chosen input should require at least T sequential steps even with a polynomial number of parallel. processors and with a preprocessing stage yet the function can be evaluated on any input in time. polynomial in T e g 2T or T 4 1, A delay function can be easily constructed by iterating a cryptographic hash function when. modeled as a random oracle for proving its sequentiality However the complete lack of structure. that is offered by this construction renders its suitability for realizing time lock puzzles or verifiable. delay functions rather unclear Specifically for time lock puzzles iterating a cryptographic hash. function in general does not enable sufficiently fast generation of input output pairs Similarly for. verifiable delay functions iterating a cryptographic hash function in general does not able sufficiently. fast verification although asymptotically such verification can be based on succinct non interactive. arguments for NP languages Kil92 Mic94 GW11 as suggested by D ttling et al DGM 19 and. Boneh et al BBB 18, The only known construction of a delay function that offers both a useful structure for realizing. time lock puzzles or verifiable delay functions and a realistic level of practicality is the iterated. squaring construction underlying the time lock puzzle of Rivest et al RSW96 which was recently. elegantly extended by Pietrzak Pie19 and Wesolowski Wes19 to additionally yield a verifiable. delay function The iterated squaring construction however is based on rather strong assumptions. in groups of hidden orders such as the RSA group or the class group of an imaginary quadratic. number field Unfortunately RSA groups require a trusted setup stage as the factorization of the. RSA modulus serves as a trapdoor enabling fast sequential evaluation RSW96 Pie19 Wes19 and. the class group of an imaginary quadratic number field is not as well studied from the cryptographic. perspective as other more standard cryptographic groups BBF18 Sec 6. Thus a fundamental goal is to construct delay functions in groups of known orders giving rise to. a variety of well studied instantiations In such groups the security of delay functions can potentially. be proved either based on long standing cryptographic assumptions or within the generic group model. as a practical heuristic,1 1 Our Contributions, In this work we prove that there are no constructions of generic group delay functions in cyclic groups.
of known orders Roughly speaking we show that for any delay function that does not exploit any. particular property of the representation of the underlying group there exists an attacker that breaks. the function s sequentiality when given the group s order As any time lock puzzle and verifiable. delay function give rise to a delay function our result holds for these two notions as well Moreover. our impossibility result holds even if the underlying group is equipped with a d linear map for any. constant d 2 and even for super constant values of d under certain conditions as discussed below. Our result Attacking delay functions in known order groups Generic group algorithms. have access to an oracle for performing the group operation and for testing whether two group. We refer the reader to Section 2 for a formal definition of a delay function obtained as a natural relaxation of. both a time lock puzzle and a verifiable delay function. elements are equal and the efficiency of such algorithms is measured mainly by the number of oracle. queries that they issue Nec94 Sho97 BL96 MW98 Mau05 In the context of generic group delay. functions we view generic group algorithms as consisting of parallel processors and we measure the. number of such processors together with the number of sequential queries that are issued by each. such processor In addition we measure the amount of any internal computation that is performed. by our attacker and this enables us to prove an impossibility result that is not only of theoretical. significance in the generic group model but is also of practical significance. The following theorem presents our main result in an informal and simplified manner that focuses. on prime order groups without d linear maps and on delay functions whose public parameters inputs. and outputs consist only of group elements2, Theorem informal simplified Let DF be a generic group delay function whose public param. eters inputs and outputs consist of kpp T kin T and kout T group elements respectively. where N is the security parameter and T N is the delay parameter Let QeqEval T denote the. number of equality queries issued by the function s honest evaluation algorithm Then there exists a. generic group attacker A that takes as input the bit order p of the group such that. A correctly computes the function on any input, A consists of kpp kin max kout QeqEval parallel processors each of which issues at most. O kpp kin log p sequential oracle queries, For interpreting our theorem first note that our attacker does not require a preprocessing stage. and is able to correctly compute the function on any input these rule out even an extremely weak. notion of sequentiality, Second note that the number kpp kin max kout QeqEval of parallel processors used by our. attacker is at most polynomial in the security parameter and in the delay parameter T and that. the number O kpp kin log p of sequential queries issued by each processor is polynomial in. and essentially independent of the delay parameter T Specifically for delay functions underlying. time lock puzzles and verifiable delay functions the parameters kpp kin and kout are all polynomials. in and log T for the iterated squaring delay function for example it holds that kpp QeqEval 0. and kin kout 1 3 Therefore in these cases the number of sequential queries issued by each. processor is at most polynomial in and log T, An additional interpretation of our result is as follows The term max kout QeqEval lower bounds.
the time to compute Eval without parallelism even though it could be much smaller as for the. iterated squaring function Optimally an speedup that is computing the function times faster. than without parallelism is obtained by using parallel processors We show that an at least. speedup can be obtained by using O kpp kin 2 log p parallel processors. 1 2 Related Work, Various cryptographic notions that share a somewhat similar motivation with delay functions have. been proposed over the years such as the above discussed notions of time lock puzzles and verifiable. delay functions e g RSW96 BGJ 16 BBB 18 BBF18 Pie19 Wes19 EFK 19 DMP 19 as. As discussed in Section 1 3 we prove our result also to groups of composite order to groups equipped with a. d linear map and to delay functions whose public parameters inputs and outputs consist of both group elements and. arbitrary additional values, For time lock puzzles this follows from the requirement that an input output pair can be generated in time. polynomial in and log T and for verifiable delay functions this follows from the requirement that the verification. algorithm runs in time polynomial in and log T, well as other notions such as sequential functions and proofs of sequential work e g MMV11. MMV13 CP18 It is far beyond the scope of this work to provide an overview of these notions. and we refer the reader to the work of Boneh et al BBB 18 for an in depth discussion of these. notions and of the relations among them, A generic group candidate for a function that requires more time to evaluate than to verify was. proposed by Dwork and Naor DN92 based on extracting square roots modulo a prime number p see. also the work of Lenstra and Wesolowski LW15 on composing several such functions However. the time required to sequentially evaluate this function as well as the gap between the function s. sequential evaluation time and its verification time both seem limited to O log p and thus cannot be. flexibly adjusted via a significantly larger delay parameter T As noted by Boneh et al BBB 18. this does not meet the notion of a verifiable delay function or our less strict notion of a delay. In the random oracle model D ttling Garg Malavolta and Vasudevan DGM 19 and Mah. moody Smith and Wu MSW19 proved impossibility results for certain classes of verifiable delay. functions and thus in particular for certain classes of delay functions Before describing their. results we note that whereas D ttling et al and Mahmoody et al captured restricted classes of ver. ifiable delay functions within the random oracle model our work captures all constructions of delay. functions a more relaxed notion within the incomparable generic group model Most importantly. in the random oracle model a delay function can be easily constructed by iterating the random oracle. however as discussed above this does not seem practically useful for realizing time lock puzzles or. verifiable delay functions, The work of D ttling et al rules out constructions of verifiable delay functions with a tight gap.
between the assumed lower bound on their sequential evaluation time and their actual sequential. evaluation time Specifically they proved that there is no construction that cannot be evaluated. using less than T sequential oracle queries even with parallel processors but can be evaluated. using T O T sequential oracle queries for any constant 0 where T is the delay parameter. Note however that this does not rule out constructions that cannot be evaluated using less than T. sequential oracle queries but can be evaluated say using 4T or T log T sequential oracle queries In. addition to their impossibility result D ttling et al showed that any verifiable delay function with. a prover that runs in time O T and has a natural self composability property can be generically. transformed into a verifiable delay function with a prover that runs in time T O 1 based on. succinct non interactive arguments for NP languages Kil92 Mic94 GW11. The work of Mahmoody et al rules out constructions of verifiable delay functions that are sta. tistically sound with respect to any oracle4 That is they consider verifiable delay functions whose. soundness property holds for unbounded adversaries and holds completely independently of the ora. cle As noted by Mahmoody et al this suffices for example for ruling out verifiable delay functions. that are permutations However for such functions that are not permutations this strong soundness. property does not necessarily hold as the security of constructions in the random oracle model is. based based on the randomness of the oracle and does not hold with respect to any oracle. 1 3 Overview of Our Approach, In this section we give an informal technical overview of our approach We start by reviewing the. generic group model in which our lower bound is proven and then move on to describe our attack. first in simplified settings and then gradually building towards our full fledged attack Finally. we illustrate how this attack can be extended to rule out generic group delay functions in groups. equipped with multilinear maps, In fact as pointed out by Mahmoody et al their impossibility result holds also for proofs of sequential work. The framework We prove our impossibility result within the generic group model introduced by. Maurer Mau05 which together with the incomparable model introduced by Shoup Sho97 seem to. be the most commonly used approaches for capturing generic group computations At a high level. in both models algorithms have access to an oracle for performing the group operation and for testing. whether two group elements are equal The difference between the two models is in the way that. algorithms specify their queries to the oracle In Maurer s model algorithms specify their queries. by pointing to two group elements that have appeared in the computation so far e g the 4th and. the 7th group elements whereas in Shoup s model group elements have an explicit representation. sampled uniformly at random from the set of all injective mappings from the group to sufficiently. long strings and algorithms specify their queries by providing two strings that have appeared in the. computation so far as encoding of group elements, Jager and Schwenk JS08 proved that the complexity of any computational problem that is de. fined in a manner that is independent of the representation of the underlying group e g computing. discrete logarithms in one model is essentially equivalent to its complexity in the other model How. ever not all generic cryptographic constructions are independent of the underlying representation. In the random oracle model D ttling Garg Malavolta and Vasudevan DGM 19 and Mah moody Smith and Wu MSW19 proved impossibility results for certain classes of veri able delay functions and thus in particular for certain classes of delay functions

Related Books