Adaptive PseudoFree Groups and Applications
This page was last modified on 24 December 2015, at 14:30.

__NUMBEREDHEADINGS__
Contents
 Abstract. In this paper we explore a powerful extension of the notion
of pseudofree groups, proposed by Rivest at TCC 2004. We identify, motivate, and study pseudofreeness in face of adaptive adversaries who may learn solutions to other nontrivial equations before having to solve a new nontrivial equation.
 We present a novel, carefully crafted definition of adaptive pseudofreeness
that walks a fine line between being too weak and being unsatisfiable. We show that groups that satisfy our definition yield, via a generic construction, digital and network coding signature schemes.
 Finally, we obtain concrete constructions of such schemes in the RSA
group by showing this group to be adaptive pseudofree. In particular, we demonstrate the generality of our framework for signatures by showing that most existing schemes are instantiations of our generic construction.
Introduction
Background. The search for abstractions that capture the essential security properties of primitives and protocols is crucial in cryptography. Among other benefits, such abstractions allow for modular security analysis, reusable and scalable proofs. The random oracle model ^{[1]}, the universal composability framework ^{[2]} and variants ^{[3]} ^{[4]} ^{[5]} of the DolevYao models ^{[6]} are results of this research direction. Most such abstractions (the above examples included) tackle mostly primitives and protocols and are not concerned with the more basic mathematical structures that underlie current cryptographic constructions. One notable exception is the work on pseudofree groups, a notion put forth by Hohenberger ^{[7]} and later refined by Rivest ^{[8]}. In this paper we continue the investigation of this abstraction.
Roughly speaking, a computational group G (a group where the group operations have efficient implementations) is pseudofree if it behaves as a free group as far as a computationally bounded adversary is concerned. More specifically, group is pseudofree if an adversary who is given a description of the group cannot find solutions for nontrivial equations. Here, nontriviality means that the equation does not have a solution in the free group.
For instance, in a pseudofree group given a random element it should be hard to find a solution for an equation of the form , when , or for the equation but not for the equation . This last equation is trivial since it can be solved over the free group (it has as solution in the free group) and a solution in the free group immediately translates to a solution over G. The notion of pseudofreeness generalizes the strong RSA assumption (when G is an RSA group) but also numerous other assumptions currently used in cryptography; see ^{[8]} for further details. Rivest’s conjecture that the RSA group is pseudofree was largely settled by Micciancio ^{[9]} who proved that this is indeed the case when the RSA modulus is the product of two safe primes.
In its most basic form that had been studied so far, the notion of pseudofree groups did not lend itself easily to applications. The problem is that in most of the interesting uses of the RSA group the adversary is not only given a description of the group, but often he is allowed to see solutions to nontrivial equations before having to come up with his own new equation and solution. This is the case for example in RSAbased signature schemes where one can think of a signature as the solution to some nontrivial equation. A chosenmessage attack allows the adversary access to an oracle that solves (nontrivial) equations over the group, and a forgery is a solution to a new equation. This problem was recognized early on by Rivest ^{[8]} who also left as open problems the design of a notion of pseudofreeness for adaptive adversaries and, of course, whether such groups exist. In this paper we put forth such a notion, prove that the RSA group is adaptive pseudofree, and exhibit several applications for adaptive pseudofree groups. We detail our results next.
Adaptive pseudofree groups. We first extend the notion of pseudofreeness to adaptive adversaries. Informally, we consider an adversary that can see solutions for some equations and has as goal solving a new nontrivial equation. As explained above, this scenario captures typical uses of groups in cryptography.
Our definition involves two design decisions. The first is to fix the type of equations for which the adversary is allowed to see solutions and how are these equations chosen: too much freedom in selecting these equations immediately leads to potentially unsatisfiable notions, whereas too severe restrictions may not model the expected intuition of what an adaptive adversary is and may not allow for applications. In the definition that we propose, equations are selected from a distribution over the set of equations. Importantly, the distribution depends on a parameter supplied by the adversary. This models the idea that in applications, the adversary may have some control over how the equations are selected. Different choices for this distribution lead to a variety of adversaries from very weak ones where no equation is provided (precisely the setting of pseudofreeness proposed earlier), to a setting where the adversary has no influence on the choice of equations, and ending with the very strong notion where the adversary basically selects the equations on his own.
The second issue is to define what is a nontrivial equation in the adaptive
setting. Indeed, previous definitions of triviality do not apply since in our new
setting the adversary knows additional relations between the group elements
which in turn may help him in solving additional equations. We define nontriviality
in a way motivated by existing uses of groups in cryptography and an
analysis of equations over quotients of free groups. Our definition is for the case
of univariate equations but can be easily extended to multivariate equations as
well as systems of equations.
Generic constructions for signatures. Our definition of pseudofreeness is parametrized by a distribution over equations. We show that for any distribution in a class of distributions that satisfy certain criteria, one can construct secure digital signatures and network coding signature schemes. The requirements on the distribution include the ability to efficiently check membership in the support of the distribution, and a property on the distribution of the exponents in the equation.
Our generic construction for network coding signatures is secure in the vanilla model based only on the adaptive pseudofreeness of the underlying group. Any instantiation of such groups would thus yield network signature schemes secure in the standard model. Indeed, given the instantiation that we discuss below, our framework yields the first RSAbased network coding homomorphic signature scheme secure in the standard model.
The RSA group is adaptive pseudofree. Next, we turn to proving that the RSA group is adaptive pseudofree. We do so for a class of distributions closely related but slightly more general than the distributions that yield signatures schemes. We show that an adversary that contradicts pseudofreeness of the RSA group with respect to the distribution can be used to contradict the strong RSA assumption. We also prove that the RSA group is pseudofree for a weaker version of adaptive adversaries who output their inputs to the distribution nonadaptively, but in this case the proof is for a larger class of distributions.
We do not attempt to prove adaptive pseudofreeness of the RSA group for multivariate equations. While this is potentially an interesting topic for further research, we are not aware of cryptographic applications where such equations are used.
Instantiations. An appealing interpretation of the proof of adaptive pseudofreeness for the RSA group is that it distills the core argument that underlies the typical security proofs for signatures based on the strong RSA assumption.
Each such proof explains how a signature forgery can be used to break strong RSA. In this sense our proof is a generalization to a broader (abstractly defined) set of equations rather than the particular equations that define an individual signature scheme.
Indeed, we show that almost all strong RSA signature schemes are instances of our generic construction. We explain how to obtain the schemes by Cramer and Shoup ^{[10]}, Fischlin ^{[11]}, Camenisch and Lysyanskaya ^{[12]}, Zhu ^{[13]}, Hofheinz 210 D. Catalano, D. Fiore, and B. Warinschi and Kiltz ^{[14]}, and that by Gennaro, Halevi, and Rabin ^{[15]} by instantiating our generic distribution in appropriate ways. The security of all of these schemes follows as a corollary from the security of our generic construction.
Other related work. In ^{[14]} Hofheinz and Kiltz introduced the notion of programmable hash function (PHF), an information theoretic tool that, when used in groups where the discrete logarithm is hard, allows for black box proofs for various cryptographic constructions dealing with adaptive attacks. Among other things they show how to construct generic signatures from the strong RSA assumption. Still, PHF and adaptive pseudo free groups seem to abstract away different aspects of strongRSA based signatures (for instance PHF can deal with bilinear groups while our framework allows to encompass network signatures).
Preliminaries and Notation In our work we use the notion of division intractable functions. Informally, a function H is division intractable if an adversary A cannot find such that: and divides the product of the ’s. It is easy to see that this notion is satisfied by any function that maps inputs to (distinct) prime numbers. Such mappings can be instantiated without making any cryptographic assumptions (see ^{[16]} for a construction), but they are not very efficient in practice.
Gennaro et al. introduced in ^{[15]} the notion of division intractable hash functions and also showed how to get practical implementations of them.
For lack of space, we defer the interested reader to the full version for other standard definitions and notations used throughout the paper.
Static Pseudofree Groups As warm up, we recall the notion of pseudofree groups as introduced by Rivest ^{[8]}. To distinguish it from the notions that we develop in this paper we refer to the older notion as static pseudofree groups.
Free abelian groups. For any set of symbols we write for the set of symbols . Let and be two disjoint sets of variables and constant symbols. An equation over X with constants in A is a pair . We usually write an equation as and looking ahead (we will only consider these equations over abelian groups), we may also write it as where and are integers. Let be an arbitrary abelian group and be an interpretation of the constants in A as group elements. We write for the equation interpreted over via . An evaluation is a solution for if
Any equation over and can be viewed as an equation over the free group via the interpretation that maps to . It can be easily shown ^{[8]} ^{[9]} that the equation has a solution in if and only if , it holds . We call such equations trivial, in the sense that these equations have solutions over the free group. All of the other equations are deemed nontrivial.
Static pseudofree groups. A computational group consists of a (finite) set of representations for the group elements together with efficient implementations for the two group operations. Informally, a computational group is pseudofree if it is hard to find an equation which is unsatisfiable over the free group, together with a solution in the computational group. It is worth noting that if the order of the group is known then finding solutions for nontrivial equations may be easy. Therefore, the notion of pseudofree groups holds for families of computational groups where N is chosen at random from the set of indexes (typically these are the strings of length k) and the corresponding order is hidden to the adversary.
In the following we recall the formal definition given by Micciancio in ^{[9]} (which is similar to that of Rivest ^{[8]}). The adversary that is considered in the following definition is static (in that it is only allowed to see a description of the group, but obtains no further information). To distinguish this class of groups from others that we define in this paper we call them static pseudofree groups.

Adaptive Pseudofree Groups
A rough definition. The notion described above requires an adversary to produce a solution for some nontrivial equation only given some randomly chosen generators to be used in the equation, but no additional information. In contrast, the notion that we develop attempts to capture the idea that an adversary against the computational group gets to see several equations with solutions, and then attempts to solve a new nontrivial equation. A typical cryptographic game that captures this situation involves an adversary who works against a Challenger as follows.



Notice that the above description incorporates an assumption that we make for
simplicity, namely that all equations are univariate. In general, any univariate
equation over A is of the form: . For the case of static pseudofree
groups, this restriction is justified by a lemma that was proved by Micciancio
in ^{[9]}. Informally the lemma says that any (multivariate) equation and solution
can be efficiently transformed into a univariate equation and solution
. Whilst we extend the definition of trivial equations to the multivariate
case (for lack of space it is given in the full version of the paper), it would
be interesting to see if a similar lemma is possible in the context of adaptive
pseudofreeness.
The general definition of pseudofreeness that we sketched above leaves open two important points: 1) How are the equations for which the adversary sees solutions produced? 2) What does “nontrivial equation” mean when other equations and solutions are given?
We discuss and give answers to these two problems in Sections 3.1 and 3.2 respectively.
A Spectrum of Adaptive Adversaries
The second phase of the above generic game requires that adversaries be given nontrivial equations together with their solutions, so we need to clarify how are these equations produced. Here we identify a whole spectrum of possible choices. The weakest definition one might consider is one where the adversary does not have any control over these equations. For instance, this means that, whenever the Challenger is queried in the second phase, the Challenger chooses an equation (more precisely it chooses its exponents ()) and gives and its solution in G, , to the adversary. Unfortunately, in such a game the adversary is not really adaptive: it may receive all the equations and solutions at once. The strongest possible notion, and perhaps the most natural one, would be to consider an adversary that is allowed to choose equations (namely their respective exponents ()) in any way it wants. In particular the choice of the equations can be done in an adaptive way, namely asks for an equation, sees its solutions, then chooses another equation and so on. We call this definition “Strong Adaptive Pseudofreeness”. Unfortunately this choice seems to lead to an unrealizable notion. We therefore settle on an intermediary variant where the adversary is allowed to be adaptive, but still cannot choose the equations in a completely arbitrary way. Instead, we consider a setting where the equations are selected from the set of all equations according to some distribution over which the adversary has some limited control. We formulate this limitation via a parametric distribution over the set of all possible equations. Sampling from such a distribution requires some parameter M of some appropriate length which is provided by the adversary. The distribution then produces a tuple of integers which for expressivity we write . Here is an integer (the exponent for the variable) and is a vector of integers (the exponents for the generators). The idea is that once the parameter is fixed, is some fixed distribution from which are drawn. Notice that the two ends of the spectrum can be modeled via appropriate choices of .
Nontrivial Equation w.r.t. Other Equations
Our definition of adaptive pseudofreeness requires an adversary to find a solution to a nontrivial equation. In the original setting of Rivest, nontriviality of an equation simply meant that the equation has no solution in the free group. In our setting, nontriviality is less clear: the adversary is already given solutions for some equations which may lead to solutions for other equations that are difficult to solve otherwise. In this section we develop a notion of triviality for equations given solutions to other equations. Our ultimate goal is to characterize, using the world and vocabulary afferent to free groups those equations that cannot be solved in the computational group.
General deducibility modulo equations. We frame the discussion in slightly more general terms to obtain a framework suitable for talking about nontriviality of both univariate and multivariate equations.
Let be the free abelian group generated by the set and let be an arbitrary binary relation on that models equalities between words in (equations with solutions can be thought of as such relations). We therefore aim to characterize the set of all equalities that can be derived from . Recall that eventually these equalities are interpreted over computational groups, hence there are two ways for an adversary to derive new equalities. The first is to use the group operations and their properties.
For example, if , then it can also be derived that , where the first equality is obtained by simply multiplying to the known equation, and the second equality follows using the commutativity of and the known equality. The second possibility reflects an ability that computational adversaries have (when working against computational groups). Specifically, if an equality of the form can be derived in a computational group, then the equality can also be derived (provided that q is relatively prime with the order of the group). Furthermore, since we search for an abstraction independent of the order of the group, we have to consider the above possibility for any q. The following definition is motivated by the above discussion.

Next, we derive an explicit description for . Let
Consider the binary relation on defined by: if and only if there exist such that . Here, exponentiation of a word with a rational number is defined (in the obvious way) if and only if q divides . The following proposition states that and are one and the same relation. Its proof is in the full version of the paper.
Trivial equations. Using the notion of deducibility modulo equations developed above we can now specify the class of equations that we consider trivial (given solutions for the equations in some set A). For simplicity, we focus on the case of univariate equations which is more relevant for the cryptographic applications of this paper. The definition easily extends to the case of multivariate equations (for completeness this variation is given in the full version). Assume that we are given a set of equations
together with , their corresponding solutions. (Notice that these are equations in a computational group; solutions for these equations may simply not exist in a free group). Let be the the free abelian group generated by (interpreted as symbols). The equations in induce a binary relation on which (by a slight abuse of notation) we also call . So . The following definition simply is a particular instance of Definition 2 to the case of univariate equations.


A Definition of Adaptive Pseudofree Groups
The definition of adaptive pseudofreeness that we give below is for a set A of generators, a computational group and is parameterized by a distribution as discussed in Section 3.1.
{{DefinitionDefinitionSetup. The Challenger chooses a random instance of the computational group (by picking a random index ) from a family . Then he fixes an assignment for the set A of generators and a specific parametric distribution for the exponents. The adversary is given in input the assignment and the descriptions of the computational group and the parametric distribution .



We restate several of the reasons that justify the above definition. Although
the definition is parametrized by a distribution, we feel this is the right way of
modeling an adversary who is adaptive but not allpowerful. As explained, by
varying the distribution one obtains a large spectrum of potentially interesting
instantiations, starting with static pseudofreeness all the way to strong adaptive
pseudofreeness. Finally, we show that for some fixed distributions adaptive
pseudofreeness implies immediately secure signature schemes.
Applications of Adaptive Pseudofree Groups
In this section we show that adaptive pseudofree groups yield interesting cryptographic applications. Specifically, we prove that any group that is pseudofree with respect to a distribution from a class of of parametric distributions that we specify immediately yields a secure signature scheme. We also explain how to adapt the distribution and the proof to obtain the analogous result for (nonstrongly) unforgeable schemes.
Signatures from Adaptive Pseudofree Groups
The class of parametric distributions .
In this section we introduce a specific class of parametric distributions . For any input M and an integer outputs a tuple such that:
 is a binary string taken according to some efficiently samplable distribution
(that may depend on M), for which collisions happen with at most negligible probability;
 where is a division intractable function
(see Section 1.1) and and are polynomials;
 т.е. for some efficiently samplable distribution
.
Also we require that produces an output for which one can efficiently tell that it belongs to the support of . Formally, we require that is equipped with an efficient algorithm that, on input , outputs 1 if is in the support of and 0 otherwise.
Moreover we require to be such that, for all adversaries the following probability is at most negligible
Signature scheme construction.
We now show how to build a signature scheme from any family of groups G that is adaptive pseudofree w.r.t. . Let be a parametric distribution taken from the class and let G be a family of groups that is adaptive pseudofree w.r.t. . Then we have the following signature scheme
 . Let and be the sets of constants variable
symbols. The key generation algorithm selects a random group from G, fixes an assignment for the symbols in A and finally it sets as the public verification key and as the secret signing key. The input space of is taken as the message space of the signature scheme.
. The signing algorithm proceeds as follows:
Use :* to solve the equation . Let math>\psi : A \rightarrow \mathbb{G} \!</math> be the satisfying assignment for x. The algorithm outputs as the signature for M.
. To verify a signature for a message M, the verification algorithm proceeds as follows:
 Check if and if the equation is
satisfied in by .
 If both the checks are true, output 1, otherwise 0.
Security of the signature scheme. In this section we prove the security of the proposed signature scheme under the assumption that G is adaptive pseudofree w.r.t. . In particular we can state the following theorem (whose proof is omitted for lack of space):

Notice that if one relaxes a bit the requirements on the parametric distribution
, Theorems 1 leads to different flavors of digital signature schemes. For instance,
one might consider the distribution
, which slightly generalizes the parametric
distribution as follows. is exactly as with the only difference that что is
chosen uniformly in ZB for some value . It is easy to rewrite the proof of
Theorem 1 in order to show the following.

Informally what this corollary is saying is that by (slightly) generalizing the parametric distribution one gets a signature scheme where unforgeability is guaranteed only for previously unsigned messages (i.e. the scheme is not strongly unforgeable).
Network Coding Signatures from Adaptive Pseudofree Groups
In this section we show that our framework allows to encompass network coding signature schemes as defined and constructed by ^{[17]}^{[18]}. In particular, by combining previous theorems with ideas from ^{[18]} we construct the first RSAbased network coding homomorphic signature scheme provably secure without random oracle. In the following we will represent files to be signed as collections where each is a ndimensional vector of the form . To sign the signer signs every single vector separately. Informally this is done using a signature scheme that allows some form of (controlled) malleability. In this way, if we interpret signatures as solutions of non trivial equations, one can easily compute solutions for any linear combination of the given equations. This simple observation, when combined with ideas from ^{[18]}, can be used to construct a secure signature scheme for network coding without random oracles.
Our Network Coding Signature Scheme. For lack of space we defer the interested reader to the full version of this paper or to the works ^{[17]}^{[18]} for a background on network coding signatures. Here we describe our network coding signature scheme. First, however, we discuss some additional details required to properly present the scheme. As already mentioned, a file to be signed is expressed as a set of vectors of n components each. Such vectors will be prepended with m unitary vectors (of m components each). Let us denote with the resulting vectors.
Using a similar notation as ^{[18]} we denote with (for some prime q) the set from which coefficients are (randomly) sampled. We denote with L an upper bound on the path length from the source to any target. By these positions denotes the largest possible value of ucoordinates in (honestlygenerated) vectors. Moreover denoting with M an upper bound on the magnitude of the coordinates of initial vectors , we set .
Let be the following parametric distribution. It takes as input some, large enough, random identifier fid, a vector space and a bound . Let be a security parameter and l
be an integer such that , compute
where is a division intractable function. Next, for each it proceeds as follows. First it samples (uniformly and at random) a
bit random integer and outputs . The global
output of is then .
Notice that is a simple extension of distribution described above. It is straightforward to show that it fits the requirements of corollary 1 as well.
Let G be a family of groups that is adaptive pseudofree w.r.t. . Then we have the following signature scheme . Let and be the sets of constants variable symbols. The key generation algorithm selects a random group from G, fixes an assignment for the symbols in A and finally it sets as the public verification key and as the secret signing key. The input space of, is taken as the set of mdimensional vectors whose components are positive integers of magnitude at most M.
. The signing algorithm proceeds as follows. A random identifier fid for the vector space V is chosen. Next, it runs to get back . Finally, for to , it uses to solve the equation
Let be the satisfying assignment for and the signature for . The algorithm outputs as the signature for V.
. To verify a signature for a vector space V , the verification algorithm proceeds as follows
 Check if and if the equations
are all satisfied in by .
 If all the checks are true, output 1, otherwise 0.
. To combine signatures , corresponding to vectors sharing the same fid, a node proceeds as follows.
 It discards any having u coordinates negative or larger than ,
or having coordinates negative or larger than .
 It chooses random , set and it outputs the
signature on w which is obtained by computing
One can easily rewrite the proof of corollary 1 to prove the following.

The RSA Group Is Adaptive Pseudofree
In Section 3 we have defined the notion of adaptive pseudofree groups and in Section 4 have shown a class of parametric distributions (called ) that allows to build signatures from the sole assumption that a family of groups is adaptive pseudofree w.r.t. . At this stage, it is therefore interesting to find a computational group candidate to be proved adaptive pseudofree. As proved by Micciancio in ^{[9]}, the only group that we know to be pseudofree is the RSA group of integers modulo N, where N is the product of two “safe” primes and the sampling procedure takes elements from . Therefore we aim to prove adaptive pseudofreeness for the same group.
A parametric distribution . First of all we need to define the specific parametric distribution for which we will prove adaptive pseudofreeness of the RSA group.
Let us consider the following , where . For any input outputs a tuple that is defined as follows:
 r is a random binary string, taken from some sufficiently large input domain.
 where is a division intractable function.
 .
 is uniformly distributed in .
 For , each is taken with an arbitrary (but efficiently samplable)
distribution in such that the tuple is binding to .
The verification algorithm checks that and that are binding w.r.t. M. It is straightforward to verify that is contained in the class defined in section 4.1.
We state the following theorem (the proof is omitted for lack of space).

As a corollary of the above theorem we can prove adaptive pseudofreeness of
the RSA group w.r.t. two new parametric distributions which still
are within the class defined in section 4.1. In particular is a variant of
, where: and for all to such that p is at most
polynomial in the security parameter (and of course).

The proofs follows from that of Theorem 3. The intuition here is that when the
’s are small they can be guessed in advance with nonnegligible probability.
Instead is a variant of where: and are obtained
as output of a chameleon hash function computed on the parameter M and with randomness R.

The proof is the same as in Corollary 2. The intuition here is that one can use the chameleon property of CH in the simulation to “prepare” the ’s in advance.
Weak adaptive pseudofreeness of the RSA group. One may also consider a weaker notion of adaptive pseudofreeness where the adversary is forced to choose the parameters of its queries at the beginning of the game, i.e. before receiving the description of the group from the challenger. In the full version of the paper we show that the proof of Theorem 3 still holds even w.r.t. a slightly more general distribution than where the entire tuple needs to be bound to M. It is then trivial to see that starting from a weakadaptive pseudofree group our results of section 4.1 lead to the construction of signature schemes that are weaklysecure.
A Framework for Strong RSABased Signatures
In this section we show that, by appropriately instantiating the parametric distribution , Theorems 1 and 3 yield essentially all the known constructions of Strong RSAbased digital signatures in the standard model (to the best of our knowledge). Due to space limits we only briefly summarize these results. Precise details are in the full version.
CramerShoup’s signatures ^{[10]}. While CramerShoup’s scheme seems based on the difficulty of solving a system of two equations, we observe that for only one of these two equations the signing process is required to find a solution (using the secret key) while the other equation is, de facto, a chameleon hash function computed on the message. Their scheme is then a special case of our general framework applying via Corollary 3.
Fischlin’s signatures ^{[11]}. Fischilin’s scheme can be seen as a special case of our framework as the distribution of its exponents fits the case of , for which Theorem 3 applies.
CamenischLysyanskaya’s signatures ^{[12]}. This signature can be seen as an instance of our framework since its distribution is an instance of , for which Corollary 1 applies.
Zhu’s signatures ^{[13]}^{[19]}. Zhu’s scheme is captured by our general framework as the distribution of its exponents is a special instance of .
HofheinzKiltz’s signatures ^{[14]}. Hofheinz and Kiltz show in ^{[14]} how to use programmable hash functions to get a new efficient signature scheme based on Strong RSA. It is not hard to notice that the security of their scheme basic scheme5 emerges from Corollary 2.
GennaroHaleviRabin’s signatures ^{[15]}. The scheme in ^{[15]} fits our framework for weaklysecure signature scheme (see section 5) when using a distribution in which and H is a division intractable hash function.
A new network signature from Strong RSA. It is easy to see that combining the results of Theorem 3 and Theorem 2 we obtain a concrete instantiation of the network coding signature scheme given in Section 4.2 whose security is thus based on Strong RSA in the standard model. We notice that our scheme is not as efficient as the one proposed by Gennaro et al. in ^{[18]}, but it is secure in the standard model.
Conclusion
In this paper we have introduced a formal definition of adaptive pseudofreeness. We have shown that under reasonable conditions the RSA group is adaptive pseudofree for moduli that are products of safe primes, and exhibited the first direct cryptographic applications of adaptive pseudofree groups: under some mild conditions, pseudofree groups yield secure digital signature schemes.
There are several interesting problems that we have not addressed. Here we enumerate some of them. The first obvious one, originally posed by Rivest, is what other groups used in cryptography are pseudofree. A new construction would lead, via our framework, to new signature schemes for example. Our results for RSA are only for univariate equations. It should be interesting to either justify this restriction through an analogue of Micciancio’s Lemma, or, if this is not possible, extend our study to multivariate equations. The onemore RSA inversion problem has a strong flavor of adaptive pseudofreeness but does not fit our framework. In particular, its relation with the strong RSA problem is an interesting open problem. Nevertheless, studying the relation between these two problems within our framework seems to be an interesting direction. Finally, we manage to prove adaptive pseudofreeness for a large class of parametric distributions sufficient for cryptographic applications. It should be interesting to understand how far one can go with the limitations that we impose on the adversary by trying to enlarge this class.
Acknowledgements
We thank Eike Kiltz for clarifications regarding ^{[14]} as well as for useful suggestions. The work described in this paper has been supported in part by the European Commission through the ICT programme under contract ICT2007216676 ECRYPT II.
Cite error:
<ref>
tags exist for a group named "@:", but no corresponding <references group="@:"/>
tag was found, or a closing </ref>
is missing ↑ Bellare, M., Rogaway, P.: Random oracles are practical: A paradigm for designing efficient protocols. In: ACM CCS 1993, Fairfax, Virginia, USA, November 35, pp.62–73. ACM Press, New York (1993)
 ↑ Canetti, R.: Universally composable security: A new paradigm for cryptographicprotocols. In: 42nd FOCS, Las Vegas, Nevada, USA, October 1417, pp. 136–145.IEEE Computer Society Press, Los Alamitos (2001)
 ↑ Abadi, M., Rogaway, P.: Reconciling two views of cryptography (the computational soundness of formal encryption). Journal of Cryptology 20(3), 395 (2007)
 ↑ Backes, M., Pfitzmann, B., Waidner, M.: A composable cryptographic library with nested operations. In: ACM CCS 2003, Washington D.C., USA, October 2730, pp. 220–230. ACM Press, New York (2003)
 ↑ Micciancio, D., Warinschi, B.: Soundness of formal encryption in the presence of active adversaries. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 133–151. Springer, Heidelberg (2004)
 ↑ Dolev, D., Yao, A.C.: On the security of public key protocols. In: FOCS, pp. 350–357 (1981)
 ↑ Hohenberger, S.: The cryptographic impact of groups with infeasible inversion.Master’s thesis, Massachusetts Institute of Technology, EECS Dept. (2003)
 ↑ ^{8.0} ^{8.1} ^{8.2} ^{8.3} ^{8.4} ^{8.5} Rivest, R.L.: On the notion of pseudofree groups. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 505–521. Springer, Heidelberg (2004)
 ↑ ^{9.0} ^{9.1} ^{9.2} ^{9.3} ^{9.4} ^{9.5} Micciancio, D.: The RSA group is pseudofree. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 387–403. Springer, Heidelberg (2005)
 ↑ ^{10.0} ^{10.1} Cramer, R., Shoup, V.: Signature schemes based on the strong RSA assumption.In: ACM CCS 1999, Kent Ridge Digital Labs, Singapore, November 14, pp. 46–51. ACM Press, New York (1999)
 ↑ ^{11.0} ^{11.1} Fischlin, M.: The CramerShoup strongRSA signature scheme revisited. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 116–129. Springer, Heidelberg (2002)
 ↑ ^{12.0} ^{12.1} Camenisch, J., Lysyanskaya, A.: A signature scheme with efficient protocols. In: Cimato, S., Galdi, C., Persiano, G. (eds.) SCN 2002. LNCS, vol. 2576, pp. 268–289. Springer, Heidelberg (2003)
 ↑ ^{13.0} ^{13.1} Zhu, H.: New digital signature scheme attaining immunity to adaptive chosenmessage attack. Chinese Journal of Electronics 10(4), 484–486 (2001)
 ↑ ^{14.0} ^{14.1} ^{14.2} ^{14.3} ^{14.4} Hofheinz, D., Kiltz, E.: Programmable hash functions and their applications. In:Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 21–38. Springer, Heidelberg (2008)
 ↑ ^{15.0} ^{15.1} ^{15.2} ^{15.3} Gennaro, R., Halevi, S., Rabin, T.: Secure hashandsign signatures without the random oracle. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 123–139. Springer, Heidelberg (1999)
 ↑ Cachin, C., Micali, S., Stadler, M.: Computationally private information retrieval with polylogarithmic communication. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 402–414. Springer, Heidelberg (1999)
 ↑ ^{17.0} ^{17.1} Boneh, D., Freeman, D., Katz, J., Waters, B.: Signing a linear subspace: Signatureschemes for network coding. In: Jarecki, S., Tsudik, G. (eds.) PKC 2009. LNCS,vol. 5443, pp. 68–87. Springer, Heidelberg (2009)
 ↑ ^{18.0} ^{18.1} ^{18.2} ^{18.3} ^{18.4} ^{18.5} Gennaro, R., Katz, J., Krawczyk, H., Rabin, T.: Secure network coding over the integers. In: Nguyen, P.Q., Pointcheval, D. (eds.) PKC 2010. LNCS, vol. 6056, pp.142–160. Springer, Heidelberg (2010)
 ↑ H. Zhu. A formal proof of Zhu’s signature scheme. Cryptology ePrint Archive, Report 2003/155 (2003), http://eprint.iacr.org/
Присоединяйся к команде
ISSN:
Следуй за Полисом
Оставайся в курсе последних событий
License
Except as otherwise noted, the content of this page is licensed under the Creative Commons Creative Commons «AttributionNonCommercialNoDerivatives» 4.0 License, and code samples are licensed under the Apache 2.0 License. See Terms of Use for details.