Adaptive Pseudo-Free Groups and Applications

From Bauman National Library
This page was last modified on 24 December 2015, at 14:30.

Adaptive Pseudo-free Groups and Applications
Authors Dario Catalano1,[@: 1],
Dario Fiore[@: 2],
Bogdan Warinschi[@: 3]
Published 2011 г.
Download оригинал


Abstract. In this paper we explore a powerful extension of the notion

of pseudo-free groups, proposed by Rivest at TCC 2004. We identify, motivate, and study pseudo-freeness in face of adaptive adversaries who may learn solutions to other non-trivial equations before having to solve a new non-trivial 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 pseudo-free. In particular, we demonstrate the generality of our framework for signatures by showing that most existing schemes are instantiations of our generic construction.


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 Dolev-Yao 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 pseudo-free 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 pseudo-free if it behaves as a free group as far as a computationally bounded adversary is concerned. More specifically, group is pseudo-free if an adversary who is given a description of the group cannot find solutions for non-trivial equations. Here, non-triviality 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 pseudo-freeness 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 pseudo-free 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 non-trivial equations before having to come up with his own new equation and solution. This is the case for example in RSA-based signature schemes where one can think of a signature as the solution to some non-trivial equation. A chosen-message attack allows the adversary access to an oracle that solves (non-trivial) 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 pseudo-freeness 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 pseudo-free, and exhibit several applications for adaptive pseudo-free groups. We detail our results next.

Adaptive pseudo-free groups. We first extend the notion of pseudo-freeness to adaptive adversaries. Informally, we consider an adversary that can see solutions for some equations and has as goal solving a new non-trivial 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 pseudo-freeness 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 non-trivial 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 pseudo-freeness 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 pseudo-freeness 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 RSA-based network coding homomorphic signature scheme secure in the standard model.

The RSA group is adaptive pseudo-free. Next, we turn to proving that the RSA group is adaptive pseudo-free. 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 pseudo-freeness 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 pseudo-free for a weaker version of adaptive adversaries who output their inputs to the distribution non-adaptively, but in this case the proof is for a larger class of distributions.

We do not attempt to prove adaptive pseudo-freeness 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 strong-RSA 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 Pseudo-free Groups As warm up, we recall the notion of pseudo-free 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 pseudo-free 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 non-trivial.

Static pseudo-free 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 pseudo-free 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 non-trivial equations may be easy. Therefore, the notion of pseudo-free 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 pseudo-free groups.

Definition 1 (Static Pseudo-Free Groups [9]).
A family of computational

groups is static pseudo-free if for any set A of polynomial size (where k is a security parameter), and PPT algorithm , the following holds. Let be a randomly chosen group index, and define by choosing uniformly at random in , for each . Then, the probability (over the selection of ) that on input adversary outputs an equation

and a solution for is negligible in k.

Adaptive Pseudo-free Groups

A rough definition. The notion described above requires an adversary to produce a solution for some non-trivial 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 non-trivial equation. A typical cryptographic game that captures this situation involves an adversary who works against a Challenger as follows.

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 of constants and gives

to the adversary.

Equations queries.
In this phase the adversary is allowed to see non-trivial equations together with their solutions.
At some point the adversary is supposed to output a new “nontrivial” equation (defined by ) together with a solution

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 pseudo-freeness.

The general definition of pseudo-freeness that we sketched above leaves open two important points: 1) How are the equations for which the adversary sees solutions produced? 2) What does “non-trivial 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 non-trivial 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 Pseudo-freeness”. 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 .

Non-trivial Equation w.r.t. Other Equations

Our definition of adaptive pseudo-freeness requires an adversary to find a solution to a non-trivial equation. In the original setting of Rivest, non-triviality of an equation simply meant that the equation has no solution in the free group. In our setting, non-triviality 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 non-triviality of both univariate and multi-variate 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.

Definition 2.
Let be a freely generated abelian group and let be

an arbitrary binary relation on . Let be the smallest congruence on that:


Then, and are trivially equal with respect to if

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.

Definition 3.
Equation is trivial with respect to if the equation

has a solution over .

We use the characterization of that we gave earlier to explicitly determine the class of trivial equations. Let

be an equation that has a solution over . Let be such a solution. From the explicit characterization of there exists in Q such that

Since equality is standard equality over F, the relation above translates (via symbol by symbol matching of exponents) into the following requirement. Equation has a solution if there exist in and such that:

(for all )

(for all )

The converse of the above statement is also true: if integers and rationals exist such that Equation holds then is a solution for Equation over .

Finally, we express these two conditions in a more compact matrix form which will be simpler to use in our proofs. Given the set of equations we define the following quantities:


These quantities are dependent on but we do not show the dependency explicitly

to avoid heavy notation.

Proposition 2 (Trivial equation w.r.t. a set of equations).
Equation is trivial w.r.t if and only if:

where .

The proposition follows by simply setting for all .

A Definition of Adaptive Pseudo-free Groups

The definition of adaptive pseudo-freeness 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.

{{Definition|Definition|Setup.| 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 .

Equations queries.
In this phase the adversary is allowed to adaptively query

the Challenger on equations and see their solutions. More precisely, controls the queried equations via the parametric distribution . Namely, foreach query it chooses a parameter and hands it to the Challenger. The Challenger runs , computes the solution for the equation

, which is and gives to .
Once the adversary has seen the solutions, then it is supposed to

output an equation (defined by )) together with a solution . We

say that A wins this game if is a non-trivial equation.

Definition 4 (Adaptive pseudo-free groups).
G is a family of adaptive

pseudo-free groups w.r.t. distribution , if for any set A of polynomial size, any

adversary wins in the game above with at most negligible probability.

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 all-powerful. As explained, by varying the distribution one obtains a large spectrum of potentially interesting instantiations, starting with static pseudo-freeness all the way to strong adaptive pseudo-freeness. Finally, we show that for some fixed distributions adaptive pseudo-freeness implies immediately secure signature schemes.

Applications of Adaptive Pseudo-free Groups

In this section we show that adaptive pseudo-free groups yield interesting cryptographic applications. Specifically, we prove that any group that is pseudo-free 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 Pseudo-free 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 pseudo-free w.r.t. . Let be a parametric distribution taken from the class and let G be a family of groups that is adaptive pseudo-free 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):

Theorem 1.
If G is a family of adaptive pseudo-free groups w.r.t. distribution

, then the signature scheme is strongly-unforgeable under chosenmessage


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.

Corollary 1.
If G is a family of adaptive pseudo-free groups w.r.t. distribution

, then the signature scheme is unforgeable under chosen-message attack.

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 Pseudo-free 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 RSA-based 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 n-dimensional 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 u-coordinates in (honestly-generated) 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 pseudo-free 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 m-dimensional 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.

Theorem 2.
If G is a family of adaptive pseudo-free groups w.r.t. distribution

, then the signature scheme described above is a secure (homomorphic)

network coding signature.

The RSA Group Is Adaptive Pseudo-free

In Section 3 we have defined the notion of adaptive pseudo-free 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 pseudo-free w.r.t. . At this stage, it is therefore interesting to find a computational group candidate to be proved adaptive pseudo-free. As proved by Micciancio in [9], the only group that we know to be pseudo-free 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 pseudo-freeness for the same group.

A parametric distribution . First of all we need to define the specific parametric distribution for which we will prove adaptive pseudo-freeness 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).

Theorem 3.
If the Strong-RSA Assumption holds, then is adaptive pseudofree w.r.t. .

As a corollary of the above theorem we can prove adaptive pseudo-freeness 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).

Corollary 2.
If the Strong-RSA Assumption holds, then is adaptive pseudofree w.r.t.

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 non-negligible 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.

Corollary 3.
If the Strong-RSA Assumption holds, and CH is a chameleon hash function, then is adaptive pseudo-free w.r.t.

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 pseudo-freeness of the RSA group. One may also consider a weaker notion of adaptive pseudo-freeness 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 pseudo-free group our results of section 4.1 lead to the construction of signature schemes that are weakly-secure.

A Framework for Strong RSA-Based 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 RSA-based 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.

Cramer-Shoup’s signatures [10]. While Cramer-Shoup’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.

Camenisch-Lysyanskaya’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 .

Hofheinz-Kiltz’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.

Gennaro-Halevi-Rabin’s signatures [15]. The scheme in [15] fits our framework for weakly-secure 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.


In this paper we have introduced a formal definition of adaptive pseudo-freeness. We have shown that under reasonable conditions the RSA group is adaptive pseudo-free for moduli that are products of safe primes, and exhibited the first direct cryptographic applications of adaptive pseudo-free groups: under some mild conditions, pseudo-free 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 pseudo-free. 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 multi-variate equations. The one-more RSA inversion problem has a strong flavor of adaptive pseudo-freeness 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 pseudo-freeness 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.


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 ICT-2007-216676 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
  1. Bellare, M., Rogaway, P.: Random oracles are practical: A paradigm for designing efficient protocols. In: ACM CCS 1993, Fairfax, Virginia, USA, November 3-5, pp.62–73. ACM Press, New York (1993)
  2. Canetti, R.: Universally composable security: A new paradigm for cryptographicprotocols. In: 42nd FOCS, Las Vegas, Nevada, USA, October 14-17, pp. 136–145.IEEE Computer Society Press, Los Alamitos (2001)
  3. Abadi, M., Rogaway, P.: Reconciling two views of cryptography (the computational soundness of formal encryption). Journal of Cryptology 20(3), 395 (2007)
  4. Backes, M., Pfitzmann, B., Waidner, M.: A composable cryptographic library with nested operations. In: ACM CCS 2003, Washington D.C., USA, October 27-30, pp. 220–230. ACM Press, New York (2003)
  5. 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)
  6. Dolev, D., Yao, A.C.: On the security of public key protocols. In: FOCS, pp. 350–357 (1981)
  7. Hohenberger, S.: The cryptographic impact of groups with infeasible inversion.Master’s thesis, Massachusetts Institute of Technology, EECS Dept. (2003)
  8. 8.0 8.1 8.2 8.3 8.4 8.5 Rivest, R.L.: On the notion of pseudo-free groups. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 505–521. Springer, Heidelberg (2004)
  9. 9.0 9.1 9.2 9.3 9.4 9.5 Micciancio, D.: The RSA group is pseudo-free. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 387–403. Springer, Heidelberg (2005)
  10. 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 1-4, pp. 46–51. ACM Press, New York (1999)
  11. 11.0 11.1 Fischlin, M.: The Cramer-Shoup strong-RSA signature scheme revisited. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 116–129. Springer, Heidelberg (2002)
  12. 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. 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. 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. 15.0 15.1 15.2 15.3 Gennaro, R., Halevi, S., Rabin, T.: Secure hash-and-sign signatures without the random oracle. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 123–139. Springer, Heidelberg (1999)
  16. 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. 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. 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)
  19. H. Zhu. A formal proof of Zhu’s signature scheme. Cryptology ePrint Archive, Report 2003/155 (2003),