In search of mathematical primitives for deriving universal projective hash families

IN SEARCH OF MATHEMATICAL PRIMITIVES FOR DERIVING UNIVERSAL PROJECTIVE HASH FAMILIES MAR´ IA ISABEL GONZ´ ALEZ VASCO AND JORGE L. VILLAR Abstract. We provide some guidelines for deriving new projective hash families of cryptographic interest. Our main building blocks are so called group action systems; we explore what properties of this mathematical primitives may lead to the construction of cryptographically useful projective hash families. We point out different directions towards new constructions, deviating from known proposals arising from Cramer and Shoup’s seminal work. 1. Introduction and Outline In [3], Cramer and Shoup presented a practical encryption scheme that could be proven IND-CCA secure in the standard model. Later, in [4, 5] the authors generalized that construction introducing a celebrated methodology for deriving IND-CCA schemes based on a new mathematical tool for cryptography: universal projective hash families. We start this contribution by recalling the basic notions and results related to this cryptographic primitive of increasing relevance (see Section 2). Also in [4, 5], so called group systems were introduced by Cramer and Shoup as atomic building blocks for projective hash families. Moreover, choosing the underlying group system wisely, one could actually prove the derived projective hash family to be cryptographically useful in a very strict sense. We introduce a generalization of Cramer and Shoup´s group systems, called group action systems and prove that, similarly, simple properties of this building blocks guarantee the desired cryptographic robustness of the derived projective hash families. Section 3 is devoted to the introduction of this new primitive, as well as to pointing out which properties of the underlying group action systems are suited for cryptographic applications. In search for specific constructions, in Section 4 we focus on a special type of group action systems, so called automorphism group systems, which Date: July 12, 2005. Key words and phrases. Projective Hash Families and Provable Security and Public Key Encryption. 1 2 MAR´ IA ISABEL GONZ´ ALEZ VASCO AND JORGE L. VILLAR are derived from the action of a certain subgroup of automorphisms on a given base group (these were recently defined in [14]). Section 5 roughly sketches some other types of action group systems of (potential) cryptographic relevance. Also, we note there that our work can actually be seen as a generalization of Cramer and Shoup´s original construction, for their celebrated abelian setting also yields concrete instances in our framework. 2. Some Preliminaries 2.1. Cryptographically Useful Hash Families. Families of hash functions have been widely used as essential building blocks of various cryptographic primitives. General hash functions are simply defined as mappings transforming n-bit strings into m-bit strings, which exist independently of any intractability assumption (See 3.5.1. of [7]). Together with one way permutations, general hash functions allow for the construction of pseudorandom generators. So called universal hash families were first defined in [6], as a tool for designing an algorithm for key storage and retrieval. The main feature of such families is, roughly speaking, a somehow strong collision resistance property. Later on, in 1989 [12], Naor and Yung introduced so called universal one way hash functions, which fulfill a kind of relaxed collision resistance property, which is referred to as hardness to form designated collisions or target collision resistance (see [8]). The existence of provable secure signature schemes can be derived from the existence of universal one way hash functions. Again, for a detailed discussion on the different definitions and application of these “classical” hash families, we refer the interested reader to [7, 8]. Whilst the above mentioned families are efficiently computable and essentially play the role of protecting the integrity of certain values, we will focus on a more recent type of hash families, which in addition have a special behaviour w.r.t. a certain subset of their domain. So called universal projective hash families were introduced by Cramer and Shoup [4, 5] as a valuable cryptographic primitive for deriving provable secure encryption schemes. We recall (informally) the basic definitions given in [5]: Let X, Π be finite non-empty sets, and Ksome finite index set. Consider a family H={Hk:X−→ Π}k∈Kof mappings from Xinto Π, and let α:K−→ Sbe a map from Kinto some finite non-empty set S(which may be seen as a projection). Definition 1. Let H, K, X, Π, S, and αbe as above. Then, for a given subset L⊂X, we refer to the tuple H= (H, K, X, L, Π, S, α), as projective hash family (PHF) for (X, L)if for all k∈Kthe restriction of Hkto MATH. PRIMITIVES FOR DERIVING UNIV. PROJ. HASH FAMILIES 3 Lis determined by α(k), i. e., for all x∈Land k1, k2∈Kthe equality α(k1) = α(k2)implies Hk1(x) = Hk2(x). Moreover, we say that His •ε-universal if for any x∈X\Land for k∈K(chosen uniformly at random), the probability of correctly guessing Hk(x)from xand α(k)is at most ε. •ε-universal2if for any x, x∗∈X\L, x 6=x∗,for k∈Kchosen uniformly at random, the probability of correctly guessing Hk(x) from α(k)and Hk(x∗)is at most ε. •ε-smooth if the probability distributions of (x, s, Hk(x)) and (x, s, π), where k,xand πare chosen uniformly at random in K,X\Land Π, respectively, and s=α(k), are ε-close.1 •strongly universal2if for k∈Kchosen uniformly at random, for any x, x∗∈X\L, x 6=x∗the random variables :-ξk:= Hk(x),conditioned to α(k) :-ηk,the variable ξkconditioned to both α(k)and Hk(x∗). are statistically close to the uniform distribution over Π.2 Note that the concepts above limit the amount of information about the behaviour of a map Hkon X\L, given by α(k). Clearly, for each case α(k) determines Hk|Lcompletely. However, α(k) hardly gives any information about Hk|X\Lif the family is universal. If His universal2, not even knowing, besides the projection given by α, some information about the behaviour of Hon a fixed (arbitrary) point of X\Lwill help on guessing its action on a new point x∈X\L. Smoothness is achieved if, on average (taken over k∈K,x∈X\L), guessing Hk(x) given αis no better than a random guess. Strongly universal2is roughly speaking worst-case smoothness, i.e., fixing any x∈X\L, Hk(x) is (close to) a uniform random variable on Π, whose distribution is induced by choosing kuniformly at random. Moreover, this still holds if the behaviour of Hon a given point of X\(L∪ {x}) is known. 2.2. Relations among Different Types of PHFs. Clearly, Definition 1 results on a kind of hierarchy, as it is easy to see that strongly universal2 PHSs are smooth, and similarly universal2PHFs are also universal. That is, roughly speaking, strongly universal2PHFs are the ones in which the projection gives less information about how {Hk}k∈Kacts on X\L, whereas given a PHF that can only be proven universal it may be the case that α leaks relevant information of what goes on outside L. However, there are 1A stronger notion of smoothness (which we will refer to as worst case smoothness) may be defined by imposing that, for any x∈X\Lthe distribution of Hk(x) conditioned to sis ε-close to the uniform distribution over Π.This is actually achieved in most cases. 2This definition first appeared in [11]. 4 MAR´ IA ISABEL GONZ´ ALEZ VASCO AND JORGE L. VILLAR efficient generic methods of ‘upgrading’ the weaker types of PHFs to achieve more robust constructions. More precisely: •Cramer and Shoup gave a construction for turning any ε-universal PHF into ε-universal2(see Lemma 2 of [4]); •applying the Leftover Hash Lemma [9], Cramer and Shoup also give a way to construct a smooth3PHF from a given ε-universal PHF, (Lemma 4 of [4]); •given a concrete universal PHF, it is often possible to find a more efficient dedicated upgrading method than the ones mentioned above (see, for instance Section 7.3 of [4]); •analogously as in Lemma 4 [4], ε-universal2PHFs can be transformed into strongly universal2PHFs, by a similar application of the Leftover Hash Lemma, since given x, x∗∈X\L, x 6=x∗, α(k) and Hk(x∗), the min-entropy of Hk(x) is at least log21 ε. 2.3. Cryptographic Applications of PHFs. Projective hash families are essential building blocks in some recent proposals of encryption schemes that can be proven IND-CCA secure in the standard model. Not only Cramer and Shoup’s generic design for such schemes has lead to the construction of practical instantiations [3, 4, 5], also recently Kurosawa and Desmedt [11] have proposed an efficient IND-CCA hybrid encryption scheme based on strongly universal2PHFs (see also [15]). Also, a theoretical construction using non abelian groups as a base and inspired by that of Cramer and Shoup, has been presented in [14]. Roughly speaking, in the encryption scheme proposed by Cramer and Shoup [4, 5] a message m∈Π is encrypted by using Hk(x) as a one time pad; while the value of kis kept secret, xand α(k) are made public. Those holding khave access to a private evaluation algorithm allowing them to evaluate Hkon any x∈X, whereas those holding only the public key can only access a public evaluation algorithm that computes Hk(x) only for x∈L. IND-CCA security is achieved by appending to the ciphertext a ‘proof of integrity’ obtained from a universal2HPS. In [11], Kurosawa and Desmedt design a hybrid encryption scheme where the image Hk(x) of a point x∈Lis used as input of a key derivation function supplying keys for both a symmetric encryption scheme and a message authentication code. Further applications of PHFs will surely appear in different areas of cryptography and some are actually already arising; for instance, recently Gennaro and Lindell [16] have proposed a general framework for password-based authenticated key exchange which makes use of 3Actually worst case smoothness is achieved. MATH. PRIMITIVES FOR DERIVING UNIV. PROJ. HASH FAMILIES 5 smooth projective hash functions. Also, using smooth projective hash families with some additional properties Kalai designed a 2-out-of-1 oblivious transfer protocol that has been presented at Eurocrypt 2005 [10]. 3. Group-Action Based PHF In search of suitable projective hash families that could be used for their above mentioned scheme, Cramer and Shoup designed a construction method that took as a starting point certain atomic abelian group theoretic tools, defined as group systems [4, 5]. We now generalize their definition in order to capture cases in which no underlying group structure on Xis assumed. 3.1. Group Action Systems. Let Xbe a finite set and consider a finite (not necessarily abelian) group Hleft-acting on X. Thus, each element φ∈Hcan be seen as an element of the symmetric group on X, and for all φ1, φ2∈Hand x∈X, (φ1φ2)x=φ1(φ2x). Take also Ssome finite group and χ:H−→ Sa group homomorphism. Note that for any φ∈H,χ(φ) gives some (limited) information about φ, and thus χprovides partial information about the action of Hon X. This partial information will eventually play the role of the information given by αin the PHFs we will be constructing. Definition 2. Let X,H,Sand χbe defined as above. Then the tuple (X, H, χ, S)is called a group action system. Let us consider the action of ker χin X, defined by the action of H. For any x∈X, let us denote by [x] the (ker χ)-orbit of x, i.e., [x] := {φx |φ∈ker χ}. Note that the action of Hon the set of points that remain fixed by ker χ is completely determined by χ. Let us thus define L:= {x∈X| |[x]|= 1}, that is L:= {x∈X|[x] = {x}}. Observe that ker χ⊆Stab(L) although they are not necessarily equal. Also, Hleaves Linvariant, as for any φ∈Hand x∈L, φx is fixed by all ψ∈ker χ, as there exists ρ∈ker χs.t. ψφ =φρ and thus ψφx =φρx =φx. As our aim is to construct cryptographically useful PHFs, the systems above will be useful for us if χgives little information about the action of Hon X\L; thus, we will be particularly interested in those systems for which the (ker χ)-orbits of elements in X\Lare large. Definition 3. Let p > 1be a positive integer. The group action system (X, H, χ, S)is p-diverse if |[x]| ≥ pfor all x∈X\L. 6 MAR´ IA ISABEL GONZ´ ALEZ VASCO AND JORGE L. VILLAR Lemma 1. Let (X, H, χ, S)be a group action system, and let pbe the smallest prime dividing |ker χ|. Then (X, H, χ, S)is p-diverse. Proof. Note that ker χacts on X, and thus |[x]|divides |ker χ|,so if x∈X\L (i.e., if |[x]| 6= 1) then |[x]|is at least p.ut 3.2. Group Action PHFs. As in [4, 5, 14], we outline the construction of a projective hash family from a group action system plus some additional elements: Let us consider a group action system (X, H, χ, S), and denote by ~: K→Ha bijection from a suitable index set K(which will later serve as the private key space). Noting that χ(~(k)) determines the action of ~(k) on Lcompletely, it is easy to see that the tuple (H, K, X, L, X, S, χ ◦~) is a projective hash family. Definition 4. Any PHF constructed from a group action system as described above is called group action projective hash family (AcPHF). Such a projective hash family is made explicit by the tuple (X, H, K, S, χ, ~). It is our aim to prove that, if the group action projective hash family has certain nice properties, the resulting AcPHF will be ε-universal for some ε > 0. We start by demonstrating that for any x∈X, choosing k∈K uniformly at random (that is, choosing uniformly at random a group element in H), given χ(~(k)),there are exactly |[x]|equally probable candidates for ~(k)x. Lemma 2. Let (X, H, χ, S)be a group action system and let x∈X. If φ∈His chosen uniformly at random, once s=χ(φ)is given then φis uniformly distributed on the coset χ−1(s)and φx is uniformly distributed on the set {ψx |ψ∈χ−1(s)}, that is, on a set of cardinality equal to |[x]|. Proof. Clearly, as φis chosen uniformly at random, once we fix s=χ(φ), the resulting distribution is uniform on χ−1(s). Moreover, for any x∈X, φx is uniformly distributed on {ψx |ψ∈χ−1(s)} provided that the sets Sy={ψ∈χ−1(s)|ψx =y} are of the same size for all y∈ {ψx, ψ ∈χ−1(s)}.But this is straightforward to see, as all Syare left cosets modulo ker χ∩Stab({x}). ut Proposition 1. Let H= (X, H, K, S, χ, ~)be a group action projective hash family. If the underlying group action system (X, H, χ, S)is p-diverse then His 1/p-universal. MATH. PRIMITIVES FOR DERIVING UNIV. PROJ. HASH FAMILIES 7 Proof. From Lemma 2, for any x∈X\L, the probability of guessing the right value of ~(k)xfor a random choice of k∈Kgiven χ(~(k)) is 1/|[x]|, that is at most 1/p.ut Once a universal projective hash family is constructed choosing the right elements according to the results above, the generic method of [5] may be used in order to transform it into a smooth projective hash family. Moreover, this transformation is sometimes superfluous: in some special cases, smoothness can even be guaranteed directly. Proposition 2. Let H= (X, H, K, S, χ, ~)be a group action projective hash family. If the whole set X\Lis a single orbit under the action of ker χ then His |L|/|X|-smooth. Proof. Let x∈X\L. From Lemma 2, ~(k)xis uniformly distributed on a set of size |[x]|=|X\L|. Then, the statistical distance between ~(k)xand the uniform distribution on Xis 1 2X x∈X\L ¯ ¯ ¯ ¯ 1 |X|−|L|−1 |X|¯ ¯ ¯ ¯ +1 2X x∈L 1 |X|=|L| |X|, thus the probability distribution of ~(k)xis |L|/|X|-close to the uniform distribution on Xut Thus, from a universal PHF one can derive a smooth PHF. Similarly, a simple extension of a universal PHF leads to the construction of a universal2 PHF. 3.3. Universal2Extended AcPHFs. In [5], the authors outline a generic transformation from any ε-universal projective hash family to an εuniversal2extended projective hash family. As done in [4, 5, 14] we give a more efficient extension for the case of AcPHFs. Let H= (X, H, K, S, χ, ~) be a group action projective hash family such that the underlying group action system (X, H, χ, S) is p-diverse. Let q be the smallest prime factor of |H|. Further on, denote by na positive integer and by Ea finite set. Let us define a new extended projective hash family ˆ Hby means of n+1 independent copies of Hand a “gluing” function gH γ:Hn+1 →Hdefined by: gH γ(φ0, . . . , φn) := φ0φγ1 1···φγn n where γ= (γ1, . . . , γn)∈Zn. Similarly, we define gS γ:Sn+1 →Sby gS γ(s0, . . . , sn) := χ(gH γ(φ0, . . . , φn)) = s0sγ1 1· · · sγn n, 8 MAR´ IA ISABEL GONZ´ ALEZ VASCO AND JORGE L. VILLAR where φj∈χ−1(sj) for all j= 0, . . . , n. At this point, ˆ K=Kn+1,ˆ S=Sn+1 and the natural extensions ˆχof χ and ˆ ~of ~are considered. The set Xis extended to ˆ X=X×E. Further on, given ˆ k, we define Φˆ k:X×E−→ Xby Φˆ k(x, e) := gH Γ(x,e)(ˆ ~(ˆ k))x, where Γ : (x, e)7→ (Γ1(x, e), . . . , Γn(x, e)) is an injective map from X×E into {0, . . . , q −1}n. Let us denote by ˆ Hthe set {Φˆ k|ˆ k∈ˆ K}. The soundness of our construction will rely on the commutativity of the following diagram: Hn+1 H ˆ SS - gH γ ? ˆχ ? χ - gS γ We will now proof that ˆ H= ( ˆ H, ˆ K, X ×E, L ×E, X, ˆ S, ˆχ◦ˆ ~) is a 1/p-universal2projective hash family. Recall that this actually means that for any x∈X\Land e∈Eif ˆ k∈ˆ Kis chosen uniformly at random and ˆχ(ˆ ~(ˆ k)), Φˆ k(x∗, e∗) are known (for some x∗∈X\(L∪{x}) and e∗∈E), the probability of guessing Φˆ k(x, e) correctly is at most 1/p. Let us start by obtaining an analogue of Lemma 2. Lemma 3. Let ˆ Hbe as above, x∈Xand e∈E. Then, if ˆ φ∈Hn+1 is chosen uniformly at random, once ˆs= ˆχ(ˆ φ)is fixed, then φ=gH Γ(x,e)(ˆ φ)is uniformly distributed on the coset χ−1(s), where s=gS Γ(x,e)(ˆs). Moreover, φx is uniformly distributed on the set {ψx |ψ∈χ−1(s)}, that is, on a set of cardinality equal to |[x]|. Proof. It is clear that in the conditional probability space, φis uniformly distributed on the set gH Γ(x,e)(ˆχ−1(ˆs)). Let us show that this set is just the coset χ−1(s). Clearly, gH Γ(x,e)(ˆχ−1(ˆs)) ⊆χ−1(s) since χ(gH Γ(x,e)(ˆχ−1(ˆs))) = gS Γ(x,e)(ˆχ−1(ˆχ(ˆs))) = s. Conversely, gH Γ(x,e)(ˆχ−1(ˆs)) contains a whole coset modulo ker χ. To see this, pick an element ψ∈gH Γ(x,e)(ˆχ−1(ˆs)). Then, there exists ˆ ψ=(ψ0, ψ1, . . . , ψn)∈ˆχ−1(ˆs) such that ψ=gH Γ(x,e)(ˆ ψ). For each η∈ker χ,ηψ =gH Γ(x,e)(ηψ0, ψ1, . . . , ψn) is also in ˆχ−1(ˆs). From this point, the proof proceeds exactly as in Lemma 2. ut MATH. PRIMITIVES FOR DERIVING UNIV. PROJ. HASH FAMILIES 9 Proposition 3. If (X, H, χ, S)is p-diverse then ˆ His a 1/p-universal projective hash family. Proof. From Lemma 3, for any x∈X\Land e∈E, the probability of guessing the right value of Φˆ k(x, e) = gH Γ(x,e)(ˆ ~(ˆ k))xfor a random choice of ˆ k∈ˆ Kgiven ˆχ(ˆ ~(ˆ k)) is 1/|[x]|, that is at most 1/p.ut Next, we show that ˆ His also universal2. Lemma 4. Let (X, H, χ, S)be a p-diverse AcPHF. For any e, e∗∈E, x∈X\Land x∗∈X\ {x},if ˆ φ∈Hn+1 is chosen uniformly at random, once ˆs= ˆχ(ˆ φ)is fixed, then the random variables φ=gH Γ(x,e)(ˆ φ)and φ∗= gH Γ(x∗,e∗)(ˆ φ)are independent. Proof. From Lemma 3, φand φ∗are uniformly distributed on χ−1(s) and χ−1(s∗),respectively, where s:= gS Γ(x,e)(ˆs) and s∗:= gS Γ(x∗,e∗)(ˆs). Now let ibe the smallest integer such that Γi(x, e)6= Γi(x∗, e∗), that surely exists since Γ is injective. Now, for any fixed values φj∈χ−1(sj) for j= 1, . . . , i −1, i + 1, . . . , n let us consider the map 4i:χ−1(s0)×χ−1(si)−→ χ−1(s)×χ−1(s∗) (φ0, φi)−→ (φ, φ∗), where, as above, φ=gH Γ(x,e)(ˆ φ) and φ∗=gH Γ(x∗,e∗)(ˆ φ).By defining ψL=φΓ1(x,e) 1· · · φΓi−1(x,e) i−1=φΓ1(x∗,e∗) 1· · · φΓi−1(x∗,e∗) i−1, ψR=φΓi+1(x,e) i+1 · · · φΓn(x,e) nand ψ∗ R=φΓi+1(x∗,e∗) i+1 · · · φΓn(x∗,e∗) n we can write 4i(φ0, φi) = (φ0ψLφΓi(x,e) iψR, φ0ψLφΓi(x∗,e∗) iψ∗ R). The map 4iis injective. Indeed, consider two pairs (φ0, φi) and (¯ φ0,¯ φi) in χ−1(s0)×χ−1(si) such that 4i(φ0, φi) = 4i(¯ φ0,¯ φi).Then, φ0ψLφΓi(x,e) i= ¯ φ0ψL¯ φΓi(x,e) iand φ0ψLφΓi(x∗,e∗) i=¯ φ0ψL¯ φΓi(x∗,e∗) i.Combining these two equalities, we obtain φΓi(x∗,e∗)−Γi(x,e) i=¯ φΓi(x∗,e∗)−Γi(x,e) i, that leads to φi=¯ φiand then to φ0=¯ φ0.4Thus, 4iis injective. Then, as χ−1(s0)×χ−1(si) and χ−1(s)×χ−1(s∗) have the same (finite) cardinality, 4iis a bijection. So, if (φ0, φi) is chosen uniformly at random in 4Note that, as |Γi(x∗, e∗)−Γi(x, e)|< q, we have gcd(Γi(x∗, e∗)−Γi(x, e),|H|) = 1. So there are a, b ∈ {0,...,|H| − 1}such that a(Γi(x∗, e∗)−Γi(x, e)) = 1 + b|H|,and, consequently, φa(Γi(x∗,e∗)−Γi(x,e)) i=φ1+b|H| i=φi.