BRICS RS-01-37 Cramer & Shoup: Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext … BRICS

Basic Research in Computer Science

Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption

Ronald Cramer Victor Shoup

BRICS Report Series RS-01-37 ISSN 0909-0878 October 2001 Copyright \begin{matrix}c \\ ◯ \end{matrix} 2001, Ronald Cramer & Victor Shoup.

BRICS, Department of Computer Science University of Aarhus. All rights reserved.

Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy.

See back inner page for a list of recent BRICS Report Series publications. Copies may be obtained by contacting:

BRICS Department of Computer Science University of Aarhus Ny Munkegade, building 540 DK–8000 Aarhus C Denmark

Telephone: +45 8942 3360
Telefax: +45 8942 3255
Internet: BRICS@brics.dk

BRICS publications are in general accessible through the World Wide Web and anonymous FTP through these URLs:

http://www.brics.dk
ftp://ftp.brics.dk

This document in subdirectory RS/01/37/

Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption

Ronald Cramer^{∗}  Victor Shoup^{†}

October 12, 2001

Abstract

We present several new and fairly practical public-key encryption schemes and prove them secure against adaptive chosen ciphertext attack. One scheme is based on Paillier’s Decision Composite Residuosity (DCR) assumption [7], while another is based in the classical Quadratic Residuosity (QR) assumption. The analysis is in the standard cryptographic model, i.e., the security of our schemes does not rely on the Random Oracle model.

We also introduce the notion of a universal hash proof system. Essentially, this is a special kind of non-interactive zero-knowledge proof system for an NP language. We do not show that universal hash proof systems exist for all NP languages, but we do show how to construct very efficient universal hash proof systems for a general class of group-theoretic language membership problems.

Given an efficient universal hash proof system for a language with certain natural cryptographic indistinguishability properties, we show how to construct an efficient public-key encryption schemes secure against adaptive chosen ciphertext attack in the standard model. Our construction only uses the universal hash proof system as a primitive: no other primitives are required, although even more efficient encryption schemes can be obtained by using hash functions with appropriate collision-resistance properties.

We show how to construct efficient universal hash proof systems for languages related to the DCR and QR assumptions. ¿From these we get corresponding public-key encryption schemes that are secure under these assumptions. We also show that the Cramer-Shoup encryption scheme (which up until now was the only practical encryption scheme that could be proved secure against adaptive chosen ciphertext attack under a reasonable assumption, namely, the Decision Diffie-Hellman assumption) is also a special case of our general theory.

1 Introduction

It is generally considered that the “right” notion of security for security for a general-purpose public-key encryption scheme is that of security against adaptive chosen ciphertext attack.

This notion was introduced by Rackoff and Simon [8]. While there are weaker notions of security, such as that defined by Naor and Yung [6], experience in the design and analysis of cryptographic protocols has shown that security against adaptive chosen ciphertext attack is both necessary and sufficient in many applications. Dolev, Dwork, and Naor [4] introduced the notion of non-malleable encryption, which turns out to be equivalent to the notion of security against adaptive chosen ciphertext attack (at least, when one considers the strongest possible type of adversary).

∗BRICS & Dept. of Computer Science, Aarhus University. Email: cramer@brics.dk †IBM Zurich Research Laboratory. Email: sho@zurich.ibm.com

Although Rackoff and Simon defined the notion of security against adaptive chosen ciphertext attack, they did not actually present a scheme that satisfied this property. Indeed, although they present an encryption scheme, it requires the involvement of a trusted third party that plays a special role. Dolev, Dwork, and Naor present a scheme that can be proven secure against adaptive chosen ciphertext attack under a reasonable intractability assumption. However, although their scheme is polynomial time, it is horrendously impractical, and so although their scheme is a valuable proof of concept, it appears that it has no practical significance.

Up until now, the only practical scheme that has been proposed that can be proven secure against adaptive chosen ciphertext attack under a reasonable intractability assumption is that of Cramer and Shoup [3]. This scheme is based on the Decision Diffie-Hellman (DDH) assumption, and is not much less efficient than traditional ElGamal encryption.

Other practical schemes have been proposed and heuristically proved secure against adaptive chosen ciphertext. More precisely, these schemes are proven secure under reasonable intractability assumptions in the Random Oracle model [1]. The Random Oracle model is an idealized model of computation in which a cryptographic hash function is modeled as a black box, access to which is allowed only through explicit oracle queries. While the Random Oracle model is a useful heuristic, it does not rule out all possible attacks: a scheme proven secure in this model might still be subject to an attack “in the real world,” even though the stated intractability assumption is true, and even if there are no particular weaknesses in the cryptographic hash function.

1.1 Our Contributions

We present several new and fairly practical public-key encryption schemes and prove them secure against adaptive chosen ciphertext attack. One scheme is based on Paillier’s Decision Composite Residuosity (DCR) assumption [7], while another is based in the classical Quadratic Residuosity (QR) assumption. The analysis is in the standard cryptographic model, i.e., the security of our schemes does not rely on the Random Oracle model.

We also introduce the notion of a universal hash proof system. Essentially, this is a special kind of non-interactive zero-knowledge proof system for an NP language. We do not show that universal hash proof systems exist for all NP languages, but we do show how to construct very efficient universal hash proof systems for a general class of group-theoretic language membership problems.

Given an efficient universal hash proof system for a language with certain natural cryptographic indistinguishability properties, we show how to construct an efficient public-key encryption schemes secure against adaptive chosen ciphertext attack in the standard model. Our construction only uses the universal hash proof system as a primitive: no other primitives are required, although even more efficient encryption schemes can be obtained by using hash functions with appropriate collision-resistance properties.

We show how to construct efficient universal hash proof systems for languages related to the DCR and QR assumptions. ¿From these we get corresponding public-key encryption schemes that are secure under these assumptions.

The DCR-based scheme is very practical. It uses an n-bit RSA modulus N (with, say, n = 1024). The public and private keys, as well as the ciphertexts, require storage for O(n) bits. Encryption and decryption require O(n) multiplications modulo N^{2}.

The QR-based scheme is somewhat less practical. It uses an n-bit RSA modulus N as above, as well as an auxiliary parameter t (with, say, t = 128). The public and private keys require O(nt) bits of storage, although ciphertexts require just O(n + t) bits of storage. Encryption and decryption require O(nt) multiplications modulo N.

We also show that the original Cramer-Shoup scheme follows from of our general construction, when applied to a universal hash proof system related to the DDH assumption.

1.1.1 Organization of the paper

The sections of this paper are organized as follows:

§2 recalls some basic terminology;

§3 recalls the classical notion of “universal hashing,” and introduces a generalization which we call “universal projective hashing.”

§4 formalizes the notion of a “subset membership problem”;

§5 introduces the notion of a “universal hash proof system,” which is based on “universal projective hashing,” and “subset membership problems”;

§6 presents a generic construction for building a secure public-key encryption scheme using a “universal hash proof system” for a “hard subset membership problem.”

§7 shows how to build practical “universal hash proof systems” for a general class of grouptheoretic “subset membership problems.”

§8 presents several new and fairly practical encryption schemes based on the preceding general constructions, including one based on the DCR assumption, and one based on the QR assumption, and also shows that the original Cramer-Shoup encryption scheme follows from these general constructions as well.

2 Some Preliminaries

We recall some basic cryptographic terminology.

A function f(k) mapping non-negative integers to non-negative reals if called negligible (in k) if for all c ≥ 1, there exists k_{0} > 0 such that f(k) ≤ 1/k^{c} for all k ≥ k_{0}.

Let X and Y be random variables taking values in a finite set S. The statistical difference between X and Y is defined to be

Dist(X, Y) = \frac{1}{2} · ∑_{s∈S} |Pr[X = s] − Pr[Y = s]| .

Equivalently,

Dist(X, Y) = max_{S′⊂S} |Pr[X ∈ S′] − Pr[Y ∈ S′]| .

Let X = {X_{k}}_{k≥0} and Y = {Y_{k}}_{k≥0} be sequences of random variables, where for each k ≥ 0, X_{k} and Y_{k} take values in a finite set S_{k}. Then we say that X and Y are statistically indistinguishable if Dist(X_{k}, Y_{k}) is a negligible function in k. For computational purposes, we will generally work in a setting where the sets S_{k} can be encoded as bit strings whose length is polynomial in k. For any probabilistic algorithm A that outputs 0 or 1, we define the distinguishing advantage for A (with respect to X and Y) as the function

Dist_{A}^{X,Y}(k) = |Pr[A(1^{k}, X_{k}) = 1] − Pr[A(1^{k}, Y_{k}) = 1]| .

Here, the notation 1^{k} denotes the unary encoding of k as a sequence of k copies of 1, and the probability distribution comprises the random coin tosses of the algorithm A and the distributions of X_{k} and Y_{k}. We say that X and Y are computationally indistinguishable if for all probabilistic, polynomial-time A, the function Dist_{A}^{X,Y}(k) is negligible in k.

3 Universal Projective Hashing

Before defining universal projective hash functions, we present various basic definitions of families of hash functions related to the general notion of “universal hashing” [2, 9].

3.1 Universal Hashing

Let H, X, Π be non-empty finite sets, and let F : H × X → Π be a function. We write F_{h}(x) for F applied to (h, x); moreover, it will often be natural to view h ∈ H as a function from X to Π, defined (in terms of F) as h(x) = F_{h}(x).^{1} Such a function h is called a hash function. With F implicitly understood, H = (H, X, Π) is called a family of hash functions, and each h ∈ H a hash function.

Definition 1 A family H = (H, X, Π) of hash functions is pair-wise independent if the following holds. Let h ∈ H be selected uniformly at random. Then, for all x, x^{∗} ∈ X with x ≠ x^{∗}, the values h(x) and h(x^{∗}) are uniformly and independently distributed in Π.

Let H = (H, X, Π) be a family of hash functions. Let h ∈ H be selected uniformly at random. For all x ∈ X and π ∈ Π, define p_{1}(x, π) as the probability that h(x) = π when h ∈ H is chosen

at random. Define p_{1}(H) as the maximum of p_{1}(x, π), taken over all x ∈ X and all π ∈ Π.

Similarly, for all x, x^{∗} ∈ X such that x ≠ x^{∗} and for all π, π^{∗} ∈ Π, define p_{2}(x, π|x^{∗}, π^{∗}) as the conditional probability that h(x) = π, given that h(x^{∗}) = π^{∗}. Finally, define p_{2}(H) as the maximum of p_{2}(x, π|x^{∗}, π^{∗}), taken over all x, x^{∗} ∈ X such that x ≠ x^{∗} and all π, π^{∗} ∈ Π.

Definition 2 Let ϵ ≥ 0 be a real number. A family H of hash functions is ϵ-universal if p_{1}(H) ≤ ϵ.

Definition 3 Let ϵ ≥ 0 be a real number. A family H of hash functions is ϵ-universal_{2} if p_{1}(H) ≤ ϵ and p_{2}(H) ≤ ϵ.

Note that by setting ϵ = 1/|Π|, Definition 1 is a special case of Definition 3.

The following lemma is an alternative characterization of Definition 2 that will be useful in the sequel.

Lemma 1 Let H = (H, X, Π) be a family of hash functions. For h ∈ H and for x ∈ X, define b(h, x) as the number of h′ ∈ H such that h′(x) = h(x). Then for ϵ ≥ 0, H is ϵ-universal if and only if for all x ∈ X and for all h ∈ H it holds that b(h, x) ≤ ϵ · |H|.

1Note that different elements of H may represent the same function.

3.2 Definition of Universal Projective Hashing

We now introduce the concept of universal projective hashing. Let (H, X, Π) be a family of hash functions. Let L be a non-empty, proper subset of X, and let X − L denote the set X with the exclusion of L. Let S be a finite, non-empty set, and let α : H → S be a function. Set H = (H, X, L, Π, S, α).

Definition 4 H = (H, X, L, Π, S, α), defined as above, is called a family of projective hash functions (for (X, L)) if for all h ∈ H, the action of h on L is determined by α(h).

In other words, for all h ∈ H, the element α(h) “encodes” the action of h on L (and possibly more than that), so that given α(h) and x ∈ L, the value h(x) is uniquely determined.

For all h ∈ H, let H_{h} denote as the collection of all h′ ∈ H with α(h′) = α(h). Note that, in particular, h ∈ H_{h}. We also define the family of hash functions H_{h} = (H_{h}, X − L, Π).

Definition 5 Let ϵ ≥ 0 be a real number. A family of projective hash functions H = (H, X, L, Π, S, α) is ϵ-universal (respectively, ϵ-universal_{2}) if for all h ∈ H, it holds that H_{h} = (H_{h}, X − L, Π) is a family of ϵ-universal (respectively, ϵ-universal_{2}) hash functions.

We will sometimes refer to the value of ϵ in the above definition as the “error” or “error rate” of H.

We now discuss the motivation for Definition 5. Let H be a family of ϵ-universal projective hash functions. Suppose h ∈ H is chosen uniformly at random. ¿From the projective property from Definition 4, if α(h) is given, the value h(x) is completely determined for all x ∈ L, yet the action of h on X − L is still unpredictable. More precisely, if h ∈ H is chosen at random, and if an adversary is given α(h), he cannot guess the value of h(x) for x ∈ X − L with probability better than ϵ. If H is a family of ϵ-universal_{2} projective hash functions, then it holds additionally that even given h(x^{∗}) for x^{∗} ∈ X of the adversary’s choice, he cannot guess the value of h(x) for x ∈ X − L with x ≠ x^{∗} with probability better than ϵ.

Note that Definition 5 does not rule out the possibility that α(h) decreases the uncertainty about the action of h on X − L: some information about this action may leak when α(h) is given, as long as the above conditional guessing probabilities for the action on X − L are at most ϵ.

Families satisfying Definition 5 are trivial to construct, at least from a combinatorial point of view. For instance, let H = (H, X, Π) be a universal family, and L be a subset of X, and let c ∈ Π be a constant. Then define S = {c}, and for all h ∈ H, define α(h) = c, and re-define h by setting h ≡ c on L. The resulting family \overline{H} = (H, X, Π, Π, α) of projective hash functions is 1/|Π|-universal. However, in our applications later on, we want these hash functions to be efficiently computable on all of X, even if L is hard to distinguish from X − L. Therefore, the trivial “solution” above is not useful in that scenario of interest.

We will need a variation of universal projective hashing, which we call smooth projective hashing.

Let H = (H, X, L, Π, S, α) be a family of projective hash functions. We define two distributions. Distribution U(H) is the distribution on triples (x, s, π) ∈ (X − L) × S × Π obtained by sampling x ∈ X − L at random, h ∈ H at random, and π ∈ Π at random, and setting s = α(h). Distribution V (H) is the distribution on triples (x, s, π) ∈ X × S × Π obtained by sampling x ∈ X − L at random, and h ∈ H at random, and setting s = α(h) and π = h(x).

Definition 6 Let ϵ ≥ 0 be a real number. A family H of projective hash functions is ϵ-smooth if the statistical difference between U(H) and V (H) is at most ϵ.

We point out a couple of obvious facts. Let H = (H, X, L, Π, S, α) be family of projective hash functions. First, if H is 1/|Π|-universal, then it is 0-smooth, i.e., “perfectly” smooth. Second, if L ⊂ X′ ⊂ X with |X′ − L|/|X − L| = 1 − δ, and (H, X′, L, Π, S, α) is ϵ-smooth, then H is (ϵ + δ)-smooth.

3.3 Some Elementary Reductions

We show some elementary reductions among the various notions introduced. Most of the reductions given here are primarily theoretically motivated. Later on, in a specialized context, we present reductions that are considerably more efficient.

3.3.1 Reducing the error rate

Let H = (H, X, L, Π, S, α) be a family of ϵ-universal (ϵ-universal_{2}) projective hash functions. The construction below reduces ϵ to ϵ^{t}, by simple t-fold “parallelization.”

Let t be a positive integer, and define \overline{H} = (H^{t}, X, L, Π^{t}, S^{t}, \overline{α}) as follows.

For h = (h_{1}, …, h_{t}) ∈ H^{t}, the action of h on X is defined as

h : X → Π^{t},
x ↦ (h_{1}(x), …, h_{t}(x)),

and

\overline{α}(h) = (α(h_{1}), …, α(h_{t})).

The proof of the following lemma is straightforward.

Lemma 2 Let H = (H, X, L, Π, S, α) be a family of ϵ-universal (ϵ-universal_{2}) projective hash functions, and let t be a positive integer. Then \overline{H} = (H^{t}, X, L, Π^{t}, S^{t}, \overline{α}), as defined above, is a family of ϵ^{t}-universal (ϵ^{t}-universal_{2}) projective hash functions.

3.3.2 From universal projective to universal_{2} projective

Let H = (H, X, L, Π, S, α) be a family of ϵ-universal projective hash functions. The next construction turns H into a family of ϵ-universal_{2} projective hash functions for (X, L).

Suppose that for positive integers n and m, each element x ∈ X has a unique encoding as an n-bit string, and that each element π ∈ Π has a unique encoding as an m-bit string. Hence, we may view X as a subset of \{0, 1\}^{n} and Π as a subset of \{0, 1\}^{m}. Then \overline{H} = (H^{2n}, X, L, \{0, 1\}^{m}, S^{2n}, \overline{α}) is defined as follows.

For h = ((h_{1,0}, h_{1,1}), …, (h_{n,0}, h_{n,1})) ∈ H^{2n}, the action of h on X is defined as

h : X → {0, 1}^{m},
x ↦ ⊕_{i=1}^{n}h_{i,x_{i}}(x),

where x = (x_{1}, …, x_{n}) ∈ {0, 1}^{n} is the bit representation of x ∈ X, and

\overline{α}(h) = (α(h_{1,0}), α(h_{1,1}), …, α(h_{n,0}), α(h_{n,1})).

Lemma 3 Let H = (H, X, L, Π, S, α) be a family of ϵ-universal projective hash functions. Suppose that elements of X are uniquely coded as n-bit strings and that elements of Π are uniquely coded as m-bit strings. Then \overline{H} = (H^{2n}, X, L, \{0, 1\}^{m}, S^{2n}, \overline{α}), as defined above, is a family of ϵ-universal_{2} projective hash functions.

Proof. It is immediate that Definition 4 is satisfied. As to Definition 5, let h ∈ H^{2n} be chosen uniformly random.

First, we have to show, for all x ∈ X − L, it holds that given \overline{α}(h), the value π = h(x) can be guessed with probability at most ϵ.

Let (x_{1}, …, x_{n}) be the bit representation of x. Suppose, for the sake of the argument, that in addition to \overline{α}(h), also h_{1,x_{1}}, …, h_{n−1,x_{n−1}} are given. In this setting, to guess h(x), it remains to guess h_{n,x_{n}}. Since all of the h_{i,x_{i}}’s are chosen uniformly random and independently from H, this task is equivalent to guessing h_{n,x_{n}}(x), given just α(h_{n,x_{n}}). Since H is ϵ-universal, this guessing probability is at most ϵ.

To finish the proof, it is sufficient to extend the setting above so that in addition (x^{∗}, π^{∗}) ∈ X ×{0, 1}^{m} such that h(x^{∗}) = π^{∗} is given, and to show that, for all x ∈ X −L with x ≠ x^{∗}, the value h(x) = π cannot be guessed with probability better than ϵ. But this follows by the same argument as above, when using the fact that H is ϵ-universal_{2}, and assuming without loss of generality that x and x^{∗} differ in the last bit, i.e., x_{n} ≠ x_{n}^{∗}.

△

The following construction is a variation on Lemma 3. It extends the sets X and L by taking the Cartesian product of these sets with a fixed finite set E. Such extensions will prove useful in the sequel.

Let E be a finite set, and suppose that X × E is identified with a subset of {0, 1}^{n} by some injective encoding function. Similarly, suppose that Π is identified with a subset of {0, 1}^{m}.

We set \overline{H} = (H^{2n}, X × E, L × E, \{0, 1\}^{m}, S^{2n}, \overline{α}). The action is defined as follows.

Let h = ((h_{1,0}, h_{1,1}), …, (h_{n,0}, h_{n,1})) ∈ H^{2n}. The action of h on X × E is defined as follows.

h : X × E → {0, 1}^{m},
(x, e) ↦ ⊕_{i=1}^{n}h_{i,y_{i}}(x),

where (x, e) = (y_{1}, …, y_{n}) ∈ \{0, 1\}^{n} is the bit representation of (x, e). The definition of \overline{α} is the same as in Lemma 3.

The proof of the following lemma is essentially the same as the proof of Lemma 3.

Lemma 4 Let H = (H, X, L, Π, S, α) be a family ϵ-universal projective hash functions. Let E be a finite set, and suppose that X × E is identified with a subset of {0, 1}^{n} by some injective encoding function. Similarly, suppose that Π is identified with a subset of {0, 1}^{m}. Then the family \overline{H} = (H^{2n}, X × E, L × E, \{0, 1\}^{m}, S^{2n}, \overline{α}) of projective hash functions, with the action as defined above, is ϵ-universal_{2}

3.3.3 From universal projective to smooth projective

Let H = (H, X, L, Π, S, α) be a family of ϵ-universal projective hash functions. The next construction turns H into a family \overline{H} of δ-smooth projective hash functions for (X, L), where the hash outputs are l-bit strings, provided ϵ and l are not too big, and δ is not too small.

The construction is a simple application of the Leftover Hash Lemma (a.k.a., Entropy Smoothing Lemma; see, e.g., [5, p. 86]).

Fix an integer l ≥ 1, and let F = (F, Π, {0, 1}^{l}) be a pair-wise independent family of hash functions. Such a family can easily be constructed using well-known and quite practical techniques based on arithmetic in finite fields. We do not discuss this any further here.

We define the family \overline{H} = (\overline{H}, X, L, \{0, 1\}^{l}, \overline{S}, \overline{α}) as follows. The collection \overline{H} of hash functions is F × H, where the value of (f, h) ∈ F × H on x ∈ X is defined to be f(h(x)). Also, \overline{S} = F × S. The map \overline{α} sends (f, h) ∈ F × H to (f, α(h)) ∈ F × S.

It is clear that \overline{H} satisfies the basic requirements of a family of projective hash functions.

Lemma 5 Let H be an ϵ-universal family of projective hash functions, and let \overline{H} be the corresponding family of projective hash functions as defined above, whose outputs are l-bit strings. For any integer e ≥ 0 such that l + 2e ≤ log_{2}(1/ϵ), \overline{H} is a 2^{−(e+1)}-smooth family of projective hash functions.

Proof. Let U(\overline{H}) and V (\overline{H}) be the distributions defined in the paragraph preceding Definition 6. Each of these is a distribution on triples (x, (f, s), z) ∈ X × (F × S) × {0, 1}^{l}. In both distributions, x is randomly sampled from X − L, h is randomly sampled from H, f is randomly sampled from F, and s = α(h). In the first distribution, z is a random bit string, while in the second, z = f(h(x)).

For fixed values x ∈ X − L and s ∈ S, consider the corresponding conditional distributions U(\overline{H} | x, s) and V (\overline{H} | x, s). Now, conditioning on a fixed x and s as above, by the definition of ϵ-universal projective hashing, the distribution of h(x) in this conditional probability space has min-entropy at least log_{2}(1/ϵ); further, f is still independently and uniformly distributed over F. The Leftover Hash Lemma then directly implies that the statistical difference between U(\overline{H} | x, s) and V (\overline{H} | x, s) is at most 2^{−(e+1)}. Since this bound holds uniformly for all x, s, it follows that the statistical difference between U(\overline{H}) and V (\overline{H}) is also at most 2^{−(e+1)}.

△

4 Subset Membership Problems

In this section we define a class of NP languages with some natural cryptographic indistinguishability properties. The definitions below capture the natural properties of well-known cryptographic problems such as the Quadratic Residuosity and Decision Diffie-Hellman problems, as well as others.

A subset membership problem L is a collection {L_{k}}_{k≥0} of distributions. For every value of a security parameter k ≥ 0, L_{k} is a probability distribution of instance descriptions.

An instance description Λ specifies the following:

• Finite sets X and L, such that L is a proper, non-empty subset of X.

• A finite, non-empty set W.

• A binary relation R ⊂ X × W such that for all x ∈ X, we have (x, w) ∈ R for some w ∈ W if and only if x ∈ L.

We write Λ[X, L, W, R] to indicate that the instance Λ specifies X, L, W and R as above. When x ∈ L and w ∈ W with (x, w) ∈ R, we say that w is a witness for x ∈ L. For all k ≥ 0, [L_{k}] denotes the instances that are assigned non-zero probability in the distribution L_{k}.

A subset membership problem also provides several algorithms. For this purpose, we require that instance descriptions, as well as elements of the sets X and W, can be uniquely encoded as bit strings of length polynomially bounded in k.

The following algorithms are provided:

• a probabilistic, polynomial time sampling algorithm that on input 1^{k} samples an instance Λ according to the distribution L_{k}.

Note that for technical reasons, we shall only require that the output distribution of the sampling algorithm on input 1^{k} be statistically indistinguishable from L_{k}; in particular, with negligible probability, the sampling algorithm may output something that is not even an element of [L_{k}].

• a deterministic, polynomial time algorithm that takes as input 1^{k} for k ≥ 0, an instance Λ[X, L, W, R] ∈ [L_{k}], and x ∈ {0, 1}^{∗}, and checks correctly whether x is a valid binary encoding of an element of X.

• a deterministic, polynomial time algorithm that takes as input 1^{k} for k ≥ 0, an instance Λ[X, L, W, R] ∈ [L_{k}] and x ∈ X and w ∈ W and correctly decides whether (x, w) ∈ R.

• a probabilistic, polynomial time sampling algorithm that takes as input 1^{k} for k ≥ 0 and an instance Λ[X, L, W, R] ∈ [L_{k}], and outputs a random x ∈ L, together with a witness w ∈ W for it.

We only require that the distribution of the value x output by the algorithm be statistically close to the uniform distribution on L.

This completes the definition of a subset membership problem.

We next define the notion of a hard subset membership problem. Intuitively, this means that it is computationally hard to distinguish random elements of L from random elements of X − L. We now formulate this notion more precisely.

Let L = {L_{k}}_{k≥0} be a subset membership problem. We define two sequences of distributions, {U_{k}^{L}}_{k≥0} and {V_{k}^{L}}_{k≥0}, as follows. Fix k ≥ 0. The distribution U_{k}^{L} is the distribution on pairs (Λ, x), where Λ[X, L, W, R] is sampled from from L_{k}, and x is sampled at random from L. The distribution V_{k}^{L} is the same distribution on pairs (Λ, x), except that x is sampled at random from X − L.

Definition 7 Let L be a subset membership problem. We say that L is hard if the two sequences of distributions {U_{k}^{L}}_{k≥0} and {V_{k}^{L}}_{k≥0} are computationally indistinguishable.

5 Universal Hashing Proof Systems

5.1 Hash proof systems

Let L = {L_{k}}_{k≥0} be a cryptographic subset membership problem as defined in §4.

Briefly, a hash proof system (HPS) H for L associates with each instance Λ[X, L, W, R] of L a family H_{Λ} = (H, X, L, Π, S, α) of projective hash functions for (X, L).

The system also provides efficient algorithms to carry out basic operations we have defined for the families of projective hash functions, such as sampling a random hash function h ∈ H and computing α(h) given h, as well as computing h(x) given h and x. We call this latter algorithm the private evaluation algorithm for H. Moreover, a crucial property is that the system provides an efficient algorithm to compute h(x), given α(h), x, and w, where x ∈ L and w is a corresponding witness. We call this algorithm the public evaluation algorithm for H.

To be more precise, for each k ≥ 0 and for each Λ = Λ[X, L, W, R] ∈ [L_{k}], a hash proof system H for L specifies a family H_{Λ} = (H, X, L, Π, S, α) of projective hash functions.

Furthermore, the system provides the algorithms briefly mentioned above, and which we now characterize in more detail.

These algorithms work with polynomially bounded bit strings to represent elements of H, Π and S. We also assume that these algorithms use the same encodings of the sets X, L and W as the algorithms from the subset membership problem L.

The following algorithms are provided:

• a probabilistic, polynomial time algorithm that takes as input 1^{k} and an instance Λ ∈ [L_{k}], and outputs a uniformly random hash function h ∈ H.

Actually, it is technically convenient to only require that the output of the sampling algorithm is statistically indistinguishable from the uniform distribution.

• a deterministic, polynomial time algorithm that takes as input 1^{k}, an instance Λ ∈ [L_{k}], h ∈ H, and outputs s ∈ S such that α(h) = s, where H_{Λ} = (H, X, L, Π, S, α).

• a deterministic, polynomial time algorithm that takes as input 1^{k}, an instance Λ ∈ [L_{k}], h ∈ H and x ∈ X, and outputs π ∈ Π such that h(x) = π, where H_{Λ} = (H, X, L, Π, S, α).

This is the private evaluation algorithm.

• a deterministic, polynomial time algorithm that takes as input 1^{k}, an instance Λ ∈ [L_{k}], s ∈ S such that α(h) = s for some h ∈ H, and x ∈ L together with a witness w ∈ W for it, and outputs π ∈ Π such that h(x) = π, where H_{Λ} = (H, X, L, Π, S, α).

This is the public evaluation algorithm.

• a deterministic, polynomial time algorithm that takes as input 1^{k}, an instance Λ ∈ [L_{k}], and π ∈ {0, 1}^{∗}, and determines if π is a valid encoding of an element of Π, where H_{Λ} = (H, X, L, Π, S, α).

5.2 Universal Hash Proof Systems

Definition 8 Let ϵ(k) be a function mapping non-negative integers to non-negative reals. We say that a given HPS H for L for is ϵ(k)-universal (respectively, ϵ(k)-universal_{2}, ϵ(k)-smooth) if for all k ≥ 0 and for all Λ ∈ [L_{k}], the associated family of projective hash functions H_{Λ} is ϵ(k)-universal (respectively, ϵ(k)-universal_{2}, ϵ(k)-smooth).

Moreover, if this is the case, and ϵ(k) is a negligible function, then we say that H is strongly universal (respectively, universal_{2}, smooth).

It is perhaps worth remarking that if a hash proof system is strongly universal, and the underlying subset membership problem is hard, then the problem of evaluating a random hash function h : X → Π on an arbitrary x ∈ X, given α(h) alone, must be hard.

We also need an extension of this notion. Let E = {E_{Λ} : k ≥ 0, Λ ∈ [L_{k}]} be a family of finite sets. Further, assume that elements of E_{Λ} can be encoded as bit strings of polynomial length and are easy to recognize.

The definition of an E-extended HPS for L is the same as that of ordinary HPS for L, except that for each k ≥ 0 and for each Λ = Λ[X, L, W, R] ∈ [L_{k}], an E-extended hash proof system H specifies a family H_{Λ} = (H, X × E_{Λ}, L × E_{Λ}, Π, S, α) of projective hash functions. Note that in this setting, to compute h(x, e) for x ∈ L and e ∈ E_{Λ}, the public evaluation takes as input α(h), x, e, and a witness w ∈ W for x ∈ L, and the private evaluation algorithm takes as input h, x, and e.

Definition 8 can be modified in the obvious way to define E-extended ϵ(k)-universal_{2} HPS’s (we do not need any of the other notions, nor are they particularly interesting).

5.2.1 Constructions

Note that based on the constructions in Lemmas 2, 3, 4, and 5, given an HPS that is (say) 1/2universal, we can construct a strongly universal HPS, a (possibly extended) strongly universal_{2} HPS, and a strongly smooth HPS. However, in many special cases of practical interest, there may well be much more efficient constructions.

6 Secure Public-Key Encryption Schemes

6.1 Adaptive Chosen Cipher-Text Security

Below we first recall the standard definition of security against adaptive chosen ciphertext attack for a public-key encryption scheme.

Consider the following game, played against an arbitrary, polynomial time, probabilistic adversary.

1. Key-Generation Phase. Let k be the security parameter. We run the key-generation algorithm of the public-key encryption scheme on input 1^{k}, and get a key-pair (pk, sk).

We equip an encryption oracle with the public-key pk, and a decryption oracle with the secret key sk.

The public-key pk is presented to the adversary.

2. Probing-Phase I. In this phase, the attacker gets to interact with the decryption oracle in an arbitrary, adaptive fashion. This phase goes on for a polynomial amount of time, specified by the adversary.

More precisely, in each round of this interaction, the adversary sends a query σ to the decryption oracle. A query is a string chosen by the adversary.

The decryption oracle in turn runs the decryption algorithm on input of the secret-key sk and the query σ, and responds to the query by returning the output to the adversary.

Note that a query is not required to represent an encryption (under pk) of some plaintext message; a query can indeed be any string designed to probe the behavior of the decryption oracle.

The interaction is adaptive in the sense that the next query may depend on the history so far, in some way deemed advantageous by the adversary.

3. Target-Selection Phase. The adversary selects two plaintexts m_{0} and m_{1} from the message space of the encryption scheme, and presents (m_{0}, m_{1}) to the encryption oracle.

The encryption oracle selects a random bit b, and runs the encryption algorithm on input of the public-key pk and the target plaintext m_{b}.

The resulting encryption σ^{∗}, the target ciphertext, is presented to the adversary.

4. Probing-Phase II. This phase is as Probing-Phase I, the only difference being that the decryption oracle only responds to queries σ that are different from the target ciphertext σ^{∗}.

5. Guessing-Phase. The adversary outputs a bit b̂.

The adversary is said to win the game if b̂ = b. We define the advantage (over random guessing) of the adversary as the absolute value of the difference of the probability that he wins and 1/2.

A public key encryption scheme is said to be secure against adaptive chosen ciphertext attack, if for all polynomial time, probabilistic adversaries, the advantage in this guessing game is negligible as a function of the security parameter.

6.2 The Scheme and its Analysis

The scheme makes use of a subset membership problem L = {L_{k}}_{k≥0}, as well as two HPS’s G and H for L.

In any context where k ≥ 0 and Λ[X, L, W, R] ∈ [L_{k}] are fixed, we write G_{Λ} = (G, X, L, K, T, β). We will require that G is a strongly smooth HPS (see Definition 8), and that for a given k and Λ, the associated set K of hash outputs forms an Abelian group which supports efficient computation. We will use multiplicative notation for the group operation of K. Also, we define E_{Λ} as E_{Λ} = K, and define the family E of finite sets as E = {E_{Λ} : k ≥ 0, Λ ∈ [L_{k}]}.

We require that H is an E-extended strongly universal_{2} HPS (see Definition 8 and the paragraphs following it), where E is as defined in the previous paragraph. In any context where k ≥ 0 and Λ[X, L, W, R] ∈ [L_{k}] are fixed, we write H_{Λ} = (H, X × K, L × K, Π, S, α), where K = E_{Λ}, as defined in the previous paragraph.

We remark that all we really need is is a 1/2-universal HPS, since we can convert this into appropriate strongly smooth and strongly universal_{2} HPS’s using the general constructions discussed in §5.2.1. Indeed, the Leftover Hash construction in Lemma 5 gives us a strongly smooth HPS whose hash outputs are bit strings of a given length l, and so we can take the group K in the above construction to be the the group of l-bit strings with “exclusive or” as the group operation.

We now describe the key generation, encryption, and decryption algorithms for the scheme, as they behave for a fixed value of the security parameter k.

Key Generation First, sample Λ[X, L, W, R] from L_{k}. Second, sample g at random from G and h at random from H. Third, compute t = β(g) and s = α(h).

Note that all of these operations can be efficiently performed using the algorithms provided by L, G, and H.

The public key is (Λ, t, s), and the secret key is (Λ, g, h).

The message space is K.

Encryption To encrypt a message m ∈ K under a public key as above, one does the following.

First, generate a random x ∈ L, together with a corresponding witness w ∈ W. This can be done using the algorithm provided by L.

Second, compute κ = g(x) ∈ K. This is done using the public evaluation algorithm for G on inputs t, x, and w.

Third, compute e = m · κ ∈ K.

Fourth, compute π = h(x, e) ∈ Π. This is done using the public evaluation algorithm for H on inputs s, x, e, and w.

The ciphertext is the triple (x, e, π).

Decryption To decrypt a ciphertext (x, e, π) ∈ X × K × Π under a secret key as above, one does the following.

First, compute \overline{π} = h(x, e) ∈ Π, using the private evaluation algorithm for H on inputs h, x, and e. Check whether π = \overline{π}; if not, then output a default error message and halt.

Third, compute κ = g(x) ∈ K, using the private evaluation algorithm for G on inputs g and x.

Fourth, compute m = e · κ^{−1} ∈ K, and output the message m.

Theorem 1 The above scheme is secure against adaptive chosen ciphertext attack, assuming L is a hard subset membership problem.

Proof. We show that the existence of an efficient adaptive chosen ciphertext attack with nonnegligible advantage implies the existence of an efficient distinguisher for L, thereby contradicting the hardness of L.

We define the following game between a simulator and an adversary that carries out an adaptive chosen ciphertext attack. Let k be fixed. The simulator takes as input Λ[X, L, W, R] sampled from L_{k}, along with x^{∗} ∈ X, where x^{∗} is either drawn from the uniform distribution on L or the uniform distribution on X − L.

The simulator provides a “simulated environment” for the adversary as follows. In the Key-Generation Phase, the simulator runs the key-generation as usual, except that the

given value of Λ is used.

In both Probing Phases I and II, the simulator runs the decryption algorithm, as usual, using the secret key generated in the Key-Generation Phase.

In the Target-Selection Phase, the attacker presents messages m_{0} and m_{1} of his choice to the simulator. The simulator flips a random coin b, and computes the target ciphertext (x^{∗}, e^{∗}, π^{∗}) in the following way. It first computes κ^{∗} = g(x^{∗}) using its input x^{∗}, and using the private evaluation algorithm for G on inputs g and x^{∗}. It then computes e^{∗} = m_{b} · κ^{∗}. Finally, it computes π^{∗} = h(x^{∗}, e^{∗}), using the private evaluation algorithm for H on inputs h, x^{∗}, and e^{∗}.

In the Guessing Phase, the adversary outputs a bit b̂. The simulator outputs 1 if b = b̂, and 0 otherwise, after which, the simulator halts.

We now analyze the advantage of the adversary in this game, making a distinction between the cases x^{∗} ∈ L and x^{∗} ∈ X − L.

Case x^{∗} ∈ L. In this case, the simulation is perfect, or at least, statistically close to perfect (since some of the sampling algorithms provided by L, G, and H may only be statistically close to perfect). Thus, if the adversary has a non-negligible advantage, the simulator outputs a 1 with probability bounded away from 1/2 by a non-negligible amount.

Case x^{∗} ∈ X − L. We call a ciphertext (x, e, π) a valid ciphertext if x ∈ L, and otherwise we call it invalid. Note that the output of the encryption oracle in this case is an invalid ciphertext.

Consider now a slightly modified simulator which simply rejects all invalid ciphertext submitted to the decryption oracle. Let F be the event that with this modified simulator, some invalid ciphertext (x, e, π) is rejected by the decryption oracle but h(x, e) = π. It is easily seen that the probability that F occurs is negligible. This follows from fact that H is an strongly universal_{2} HPS, and the fact that this modified simulator leaks no information to the adversary about h, other than α(h) and h(x^{∗}, e^{∗}).

Now, the adversary’s interaction with the original and modified simulators proceeds identically until the event F occurs. ¿From this, and the fact that F occurs with negligible probability, we conclude that the probability that b = b̂ with the modified simulator differs from the probability that b = b̂ with the original simulator by a negligible amount.

Let us modify the simulator yet again. This time, in the encryption oracle, instead of computing κ^{∗} as g(x^{∗}), the simulator generates κ^{∗} at random. ¿From the fact that G is a strongly smooth HPS, and the fact that the modified simulator leaks no information about g to the adversary, other than β(g), this transformation yields only a negligible change in the probability that b = b̂.

Note, however, in this modified game, the probability that b = b̂ is precisely 1/2, since the random value of κ^{∗} perfectly hides m_{b}. This implies that in the interaction between the original simulator and the adversary, the probability that b = b̂ is within a negligible distance from 1/2.

It follows that the above simulator, using an adversary with non-negligible advantage, provides an effective statistical test for distinguishing L from X − L. △

The security reduction for this scheme is quite tight. Suppose that H is ϵ(k)-universal_{2} and that G is δ(k)-smooth. Suppose that an adversary makes at most q_{D}(k) probing queries and has an advantage of γ(k). The running time of the statistical test implied in the above proof is roughly the same as that of the adversary. Let γ′(k) be the advantage that this statistical test has in distinguishing L from X − L. then we have

γ(k) ≤ γ′(k) + q_{D}(k) · ϵ(k) + δ(k) + ϵ′(k),

where the term ϵ′(k) absorbs the statistical differences from the uniform distributions for the sampling algorithms provided by L, G, and H.

7 Universal Projective Families: Constructions

We now construct universal projective hash functions using group-theory.

7.1 Diverse Group Systems

Let X, L and Π be finite Abelian groups, where L is a proper subgroup of X. We will use multiplicative notation for these groups.

Let Hom(X, Π) denote the group of all homomorphisms ϕ : X → Π. We will use additive notation for Hom(X, Π): for ϕ, ψ ∈ Hom(X, Π), x ∈ X, and a ∈ ZZ, we have (ϕ+ψ)(x) = ϕ(x)·ψ(x), (ϕ − ψ)(x) = ϕ(x) · ψ(x)^{−1}, and (a · ϕ)(x) = ϕ(x)^{a}. The zero (neutral) element υ sends all elements of X to 1 ∈ Π.

Let H be a subgroup of Hom(X, Π).

Fix a set of generating elements B = {g_{1}, …, g_{s}} for the group L. Define

α : H → Π^{s},
ϕ ↦ (ϕ(g_{1}), …, ϕ(g_{s})).

Note that for all ϕ ∈ H, the action of ϕ on L is determined by α(ϕ) (and vice-versa). Namely, given x ∈ L and integers r_{1}, …, r_{s} such that

x = ∏_{i=1}^{s} g_{i}^{r_{i}},

we have

ϕ(x) = ϕ(∏_{i=1}^{s} g_{i}^{r_{i}}) = ∏_{i=1}^{s} ϕ(g_{i})^{r_{i}}.

By abuse of notation, we will sometimes identify α(ϕ) with ϕ_{|L}, the functional restriction of ϕ to L.

Also note that with α as defined above, H_{ϕ} (as defined in the paragraph preceding Definition 5) consists of all ϕ′ ∈ H that are identical to ϕ on L, i.e., ϕ_{|L} ≡ ϕ′_{|L}. In particular, ϕ ∈ H_{ϕ}.

Definition 9 We call (H, X, L, Π, Π^{s}, α) as defined above a group system.

Clearly, any group system is a family of projective hash functions.

Our first goal is to investigate the conditions under which a group system constitutes a family of ϵ-universal projective hash functions for some ϵ < 1. By definition, (H_{ϕ}, X − L, Π) must be ϵ-universal, for all ϕ ∈ H. Therefore, it is a necessary condition on H_{ϕ}, that no x ∈ X − L is sent to the same π ∈ Π by all ψ ∈ H_{ϕ}. This is formally expressed in the following Definition.

Definition 10 Let H = (H, X, L, Π, Π^{s}, α) be a group system. We say that H is diverse if for all ϕ ∈ H and for all x ∈ X − L, there exists ϕ′ ∈ H_{ϕ} such that ϕ′(x) ≠ ϕ(x).

We will show below in Theorem 2 in §7.2 that a diverse group system forms a family ϵ-universal projective hash functions, where ϵ = 1/p, and p is the smallest prime dividing |X|/|L|.

7.2 An ϵ-Universal Projective Family

We start with a definition and two lemmas.

Definition 11 Let H = (H, X, L, Π, Π^{s}, α) be a group system. Let U be a subset of X. Then A_{U}^{H} = {ϕ ∈ H : ϕ(U) = 1}, i.e., the collection of all ϕ ∈ H that annihilate all of U.

Note that A_{U}^{H} is a sub-group of H (even though U may not be group). Also note that if U ⊂ V then A_{V}^{H} is a sub-group of A_{U}^{H}. In the following, we write A_{U,V}^{H} for A_{U∪V}^{H}.

Lemma 6 Let H = (H, X, L, Π, Π^{s}, α) be a group system. Then, for all ϕ ∈ H, it holds that H_{ϕ} is equal to the co-set ϕ + A_{L}^{H}, i.e., it consists of all element of the form ϕ + ξ, for some ξ ∈ A_{L}^{H}. In particular, |H_{ϕ}| = |A_{L}^{H}|.

Proof. We identify α(ϕ) with ϕ_{|L}. Consider the equation ψ_{|L} = ϕ_{|L}, in the unknown ψ ∈ H. If ψ_{0}, ψ_{1} are both solutions, then ψ_{0} − ψ_{1} ∈ A_{L}^{H}. Namely, for all x ∈ L, we have (ψ_{0} − ψ_{1})(x) = ψ_{0}(x)·ψ_{1}(x)^{−1} = ϕ(x)·ϕ(x)^{−1} = 1. On the other hand, if ξ ∈ A_{L}^{H}, then ϕ+ξ is a solution. Namely, for all x ∈ L, we have (ϕ + ξ)(x) = ϕ(x) · ξ(x) = ϕ(x) · 1 = ϕ(x). The cardinality claim follows trivially.

△

The following is a straightforward re-statement of Definition 10.

Lemma 7 A group system H = (H, X, L, Π, Π^{s}, α) is diverse if and only if A_{L,{x}}^{H} is a proper sub-group of A_{L}^{H}.

Proof. As remarked earlier, A_{L,{x}}^{H} is a sub-group of A_{L}^{H} in any case. Fix ϕ ∈ H and x ∈ X −L arbitrarily for the entire proof. Suppose that H is diverse. Let ϕ′ ∈ H be as guaranteed by Definition 10. Then (ϕ − ϕ′) ∈ A_{L}^{H} but (ϕ − ϕ′) ∉ A_{L,{x}}^{H}. Namely, (ϕ − ϕ′)(x) = ϕ(x) · ϕ′(x)^{−1} ≠ 1, since ϕ(x) ≠ ϕ′(x) by definition. Also, for all y ∈ L, we have (ϕ − ϕ′)(y) = ϕ(y) · ϕ′(y)^{−1} = ϕ(y) · ϕ(y)^{−1} = 1, since by definition ϕ_{|L} ≡ ϕ′_{|L}. In the other direction, let ψ ∈ A_{L}^{H} be such that ψ ∉ A_{L,x}^{H}. Then ϕ′ = ϕ − ψ is as required by Definition 10. Namely, ϕ′(x) = ϕ(x) · ψ(x)^{−1} ≠ ϕ(x), since ψ(x) ≠ 1 by definition. Finally, for all y ∈ L, ϕ′(y) = ϕ(y)·ψ(y)^{−1} = ϕ(y), since ψ annihilates L by definition. △

Theorem 2 Let H = (H, X, L, Π, Π^{s}, α) be a diverse group system. Recall that s is the size of a set of generators chosen for L, and that the action is application of a homomorphism. Let p denote the smallest prime divisor of |X|/|L|. Then H is 1/p-universal projective.

Proof. We have to show that, for all ϕ ∈ H, it holds that (H_{ϕ}, X − L, Π) is 1/p-universal. By Lemma 1, the latter is equivalent to showing that for all ψ ∈ H_{ϕ} and for all x ∈ X − L, the

collection of ψ′ ∈ H_{ϕ} with ψ′(x) = ψ(x) comprises at most a 1/p-fraction of H_{ϕ}.

Fix ϕ ∈ H, ψ ∈ H_{ϕ} and x ∈ X − L arbitrarily. Consider the equation

ψ′(x) = ψ(x),

in the unknown ψ′ ∈ H_{ϕ}. Using exactly the same style of reasoning as in the proof of Lemma 6, the set of solutions is the co-set

ψ + A_{L,{x}}^{H}.

Therefore, the number of ψ′ ∈ H_{ϕ} such that ψ′(x) = ψ(x), equals

|ψ + A_{L,{x}}^{H}| = |A_{L,{x}}^{H}|.

It remains to show that this is at most a 1/p-fraction of |H_{ϕ}|.

By Lemma 6, |H_{ϕ}| = |A_{L}^{H}|. Therefore we must show that

\frac{|A_{L,\{x\}}^{H}|}{|A_{L}^{H}|} ≤ 1/p.

By Lemma 7, A_{L,{x}}^{H} is a proper sub-group of A_{L}^{H}. Therefore, the fraction on the left-hand side is at most 1/q, where q is the smallest prime divisor of |A_{L}^{H}|.

We finally show that q divides the order |X|/|L| of the factor group X/L, so that we may conclude that 1/q ≤ 1/p.

Let ξ ∈ A_{L}^{H} be of order q. ^{2} Define m = |X|/|L|, and note that for all x ∈ X, we have that x^{m} ∈ L. For all x ∈ X, it holds that (m · ξ(x)) = ξ(x^{m}) = 1, since x^{m} ∈ L and ξ annihilates L. Therefore, q divides |X|/|L|, as desired.

△

7.3 Examples

Proposition 1 Let H = (H, X, L, Π, Π^{s}, α) be a group system such that X, L and Π are all isomorphic to vector-spaces over GF(q) for some prime q, and such that H is isomorphic the group of all linear maps from X to Π. Then H is diverse, and forms a 1/q-universal family of projective hash functions.

Proof. We show diversity of H using Lemma 7, so that the proposition follows from Theorem 2. Define K = GF(q). For the sake of the argument, define X = K^{a}, Π = K^{b}, and define H as

the collection of all a × b-matrices with entries in K. By definition, L is a proper sub-space of X.

Let x ∈ K^{a} − L. Fix a basis for L, and extend this basis to a basis for K^{a} that includes x. This is always possible.

Then define the linear map ϕ by sending all elements in the chosen basis of L to 0 ∈ K^{b}, while sending x to a non-zero element of K^{b}, and the remaining basis elements (if any) to arbitrary elements.

Thus the conditions of Lemma 7 are satisfied, and Theorem 2 applies.

△

The conditions of Proposition 1 can be weakened, but we choose the form above for its simplicity and for its usage in later examples.

Definition 12 The exponent of a finite Abelian group is the largest integer d such that there exists an element with order d in the group. Equivalently, it is the least common multiple of all integer d such that there exists an element with order d in the group.

Definition 13 A power-map is a homomorphism ϕ : X → Π such that there is an integer r with ϕ(x) = x^{r} for all x ∈ X. We call this the r-th power-map.

2It is a basic fact that in an Abelian group, for each prime that divides its order, there is an element of that order.

Note that the group of homomorphisms from X to X contains exactly e distinct power-maps, where e is the exponent of X. Namely x^{r} = x^{r′} for all x ∈ X if and only if r − r′ is a multiple of e.

Proposition 2 Let H = (H, X, L, Π, Π^{s}, α) be a group system such that for all x ∈ X − L the order of x does not divide the exponent e of the group L and H contains the e-th power-map (for example, H is the group of all power-maps). Then H is diverse, and forms a 1/p-universal family of projective hash functions, where p is the smallest prime divisor of |X|/|L|.

Proof. We show diversity of H using Lemma 7, so that the proposition follows from Theorem 2. We claim that for all x ∈ X − L, the e-th power-map satisfies the conditions of Lemma 7. Namely, for all x ∈ L, we have x^{e} = 1, since e is a multiple of the order of x. On the other

hand, for all x ∈ X − L, we have x^{e} ≠ 1, since for those x, e is not a multiple of the order of x. △

Corollary 1 Let H = (H, X, L, Π, Π^{s}, α) be a group system. Let e be the exponent of L. Suppose that H contains the e-th power-map (for example, H is the group of all power-maps), and that X is the direct internal product of L with a group G whose order is co-prime to that of L. Then H is diverse, and forms a 1/p-universal family of projective hash functions, where p is the smallest prime divisor of |X|/|L|.

7.4 Projective ϵ-Universal_{2} Family

It is important to note that no “interesting” group system is universal_{2} projective, even if it is diverse.

More precisely, let H = (H, X, L, Π, S, α) be a diverse group system. Assume that it is not degenerate, in the sense that there exists ϕ ∈ H such that ϕ does not annihilate all of L. ^{3} Let y ∈ L be such that ϕ(y) ≠ 1. In particular, y ≠ 1. Let x^{∗} ∈ X − L be arbitrary, and define x = x^{∗} · y. Clearly, x ≠ x^{∗}, and x ∈ X − L. These x^{∗} and x can trivially be used to show that (H_{ϕ}, X − L, Π) is not universal_{2}, thereby contradicting Definition 5. Namely, if ψ ∈ H_{ϕ} is chosen uniformly at random, and π^{∗} = ψ(x^{∗}) is given, then choose an arbitrary ψ′ ∈ H_{ϕ}, and simply compute π^{∗} · ψ′(y) = ψ(x^{∗}) · ψ(y) = ψ(x^{∗} · y) = ψ(x) = π.

7.4.1 Construction

Let H = (H, X, L, Π, Π^{s}, α) be a diverse group system, and let p be the smallest prime divisor of |X|/|L|.

Recall from Definition 9 that, for ϕ ∈ H, the value α(ϕ) is defined as the s-vector (ϕ(g_{1}), …, ϕ(g_{s})) ∈ Π^{s}, where s is the size of a set B of generators {g_{1}, …, g_{s}} chosen for L.

We now construct a 1/p-universal_{2} projective family \overline{H} for (X × E, L × E), where E is an arbitrary finite set. It is much like the group system H it is constructed from, except that we will work with a vector of homomorphisms, that acts in a specially tailored way on X.

Fix a positive integer τ ≤ p. Fix an injective encoding function

Γ : X × E → {0, …, τ − 1}^{n},

be given, where n is sufficiently large.

3In that case, at least half of ϕ ∈ H have this property.

We define how Φ = (ϕ_{0}, ϕ_{1}, …, ϕ_{n}) ∈ H^{n+1} acts as a function on an element (x, e) ∈ X × E. We first define ϕ_{x,e} ∈ H as

ϕ_{x,e} = ϕ_{0} + ∑_{i=1}^{n} y_{i} · ϕ_{i},

where (y_{1}, …, y_{n}) = Γ(x, e).

Then the action of Φ ∈ H^{n+1} on X × E is defined as

Φ(x, e) = ϕ_{x,e}(x) ∈ Π.

Define

\overline{α} : H^{n+1} → Π^{s(n+1)},
Φ ↦ ((ϕ_{0}(g_{1}), …, ϕ_{0}(g_{s})), …, ((ϕ_{n}(g_{1}), …, ϕ_{n}(g_{s}))) ,

where Φ = (ϕ_{0}, …, ϕ_{n}).

Equivalently, we have Φ(x, e) = ϕ_{0}(x) · ∏_{i=1}^{n} ϕ_{i}(x)^{y_{i}}, and \overline{α}(Φ) = (α(ϕ_{0}), …, α(ϕ_{n})).

Set \overline{H} = (H^{n+1}, X × E, L × E, Π, Π^{s(n+1)}, \overline{α}). In Theorem 3 we show that \overline{H} is a family of 1/p-universal_{2} projective hash functions, with the action defined as above.

In the construction above, the difference in efficiency compared to Lemma 4 is in the fact that roughly log_{p} n functions ϕ_{i} are required here, as opposed to log_{2} n in Lemma 4, where n is the number of bits needed to encode elements of X × E. The savings are considerable when p is very large.

Theorem 3 Let H = (H, X, L, Π, Π^{s}, α) be a diverse group system, let p denote the smallest prime divisor of |X|/|L|, and let 0 < τ ≤ p be an integer. Let s denotes the size of a set of generators chosen for L. Let E be an arbitrary finite set. Assume that X × E is identified with a subset of \{0, …, τ − 1\}^{n} for some integer n, via an injective encoding. Then \overline{H} = (H^{n+1}, X × E, L × E, Π, Π^{s(n+1)}, \overline{α}) is a family of 1/p-universal_{2} projective hash functions, with the action as defined above.

Proof. We have to show that ((H^{n+1})_{Φ}, (X − L) × E, Π) is 1/p-universal_{2}, for all Φ ∈ H^{n+1}. This follows quite straightforwardly by combining Theorem 2 and Proposition 3 (below), as we now show.

For the rest of the proof, fix an arbitrary

Φ = (ϕ_{0}, ϕ_{1}, …, ϕ_{n}) ∈ H^{n+1},

and fix arbitrary, distinct (x, e), (x^{∗}, e^{∗}) ∈ (X − L) × E. Write

(y_{1}, …, y_{n}) = Γ(x, e) , (y_{1}^{∗}, …, y_{n}^{∗}) = Γ(x^{∗}, e^{∗}).

Using the same kind of argument as in the proof of Theorem 2, and taking into account the definition of \overline{α}, it follows that (H^{n+1})_{Φ} consists of all

Ψ = (ϕ_{0} + ξ_{0}, ϕ_{1} + ξ_{1}, …, ϕ_{n} + ξ_{n}) ∈ H^{n+1}, with
ξ_{0}, ξ_{1}, …, ξ_{n} ∈ A_{L}^{H}.

Defining ϕ = ϕ_{x,e} and ϕ^{∗} = ϕ_{x^{∗},e^{∗}} (which are constants, since Φ is constant), we have

ψ_{x,e} = ϕ + (ξ_{0} + ∑_{i=1}^{n} y_{i} · ξ_{i}),

ψ_{x^{∗},e^{∗}} = ϕ^{∗} + (ξ_{0} + ∑_{i=1}^{n} y_{i}^{∗} · ξ_{i})

To select Ψ ∈ (H^{n+1})_{Φ} at random is the same as selecting ξ_{0}, ξ_{1}, …, ξ_{n} ∈ A_{L}^{H} uniformly at random and setting Ψ = (ϕ_{0} + ξ_{0}, ϕ_{1} + ξ_{1}, …, ϕ_{n} + ξ_{n}).

Using an argument from the proof of Theorem 2, all primes dividing |A_{L}^{H}| are greater than or equal to p. It follows by immediate application of Proposition 3 (applying the case t = 1 in that proposition) that ψ_{x,e} − ϕ and ψ_{x^{∗},e^{∗}} − ϕ^{∗} are uniformly and independently distributed in A_{L}^{H}.

As an immediate consequence, ψ_{x,e} and ψ_{x^{∗},e^{∗}} are uniformly and independently distributed in the respective co-sets ϕ + A_{L}^{H} = H_{ϕ} and ϕ^{∗} + A_{L}^{H} = H_{ϕ^{∗}}.

This immediately implies the theorem, as follows. H is diverse, so, by Theorem 2, it follows that H is 1/p-universal projective. In particular, (H_{ϕ}, X − L, Π) is 1/p-universal. Since ψ_{x,e} is uniformly distributed in H_{ϕ}, it follows that Ψ(x, e) = ψ_{x,e}(x) cannot be guessed with probability better than 1/p. We conclude that ((H^{n+1})_{Φ}, (X − L) × E, Π) is 1/p-universal.

Similarly, since ψ_{x,e} is also independently distributed from ψ_{x^{∗},e^{∗}}, it holds that when Ψ(x^{∗}, e^{∗}) = ψ_{x^{∗},e^{∗}}(x) is given, Ψ(x, e) = ψ_{x,e}(x) cannot be guessed with probability better than 1/p. Therefore, ((H^{n+1})_{Φ}, (X − L) × E, Π) is 1/p-universal_{2}, as desired.

We conclude that \overline{H} is 1/p-universal_{2} projective. △

If p is small, then Lemma 2 can be used to reduce the error to at most 1/p^{t} in a generic fashion. This comes at the cost of a multiplicative blow-up of a factor t in efficiency. In the family constructed above, this would lead to t(n + 1) homomorphisms ϕ_{ij} ∈ H, st(n + 1) elements ϕ_{ij}(g_{l}) ∈ Π to describe the action of these t(n + 1) homomorphisms on L, and finally, t values π_{i} in Π to describe the image of some pair (x, e).

We show a variant of the construction above that has error at most 1/p^{t}, but that requires n + 2t − 1 homomorphisms in H instead of t(n + 1), and s(n + 2t − 1) elements in Π to describe the actions on L, instead of st(n + 1).

The injective function Γ and the integer n are defined as before. We define how Φ = (ψ_{1}, …, ψ_{t}, ϕ_{1}, …, ϕ_{n+t−1}) ∈ H^{n+2t−1} acts as a function on an element (x, e) ∈ X × E.

For j = 1 … t, we define

Φ_{j} = (ψ_{j}, ϕ_{j}, …, ϕ_{n+j−1}),

Then Φ_{j}(x, e) is defined as in the construction above. The action of Φ is defined as

Φ(x, e) = (Φ_{1}(x, e), …, Φ_{t}(x, e)).

Finally, α̂(Φ) consists of all values ψ_{i}(g_{j}), ϕ_{l}(g_{j}) for i = 1 … t, j = 1 … s, l = 1 … n + t − 1.

Theorem 4 Let H = (H, X, L, Π, Π^{s}, α) be a diverse group system, let p denote the smallest prime divisor of |X|/|L|, and let 0 < τ ≤ p be an integer. Let s denotes the size of a set of generators chosen for L. Let E be an arbitrary finite set. Assume that X × E is identified with a subset of {0, …, τ − 1}^{n} for some integer n, via an injective encoding. Let t ≥ 1 be given. Then Ĥ = (H^{n+2t−1}, X × E, L × E, Π, Π^{s(n+2t−1)}, α̂) is a family of 1/p^{t}-universal_{2} projective hash functions, with the action as defined above.

Proof. The proof is essentially the same as the proof of Theorem 3, with the difference that the general case of Proposition 3 (see below) is applied. △

We review a well-known construction of a family of hash functions based on Toeplitz matrices, that is pair-wise independent according to Definition 1. The pair-wise independence property of this family is used in the proofs of Theorems 3 and 4, and proved in Proposition 3 below. However, we need to state a variant that is slightly more general than the usual one.

Let G be a finite Abelian group, and write its group operation as addition.

Definition 14 Let n, t be arbitrary positive integers, and let ξ ∈ G^{n+t−1}. Write ξ = (ξ_{1}, …, ξ_{n+t−1}). The Toeplitz matrix T_{ξ} is the t × n-matrix whose j-th row is the vector (ξ_{j}, …, ξ_{n+j−1}), j = 1 … t.

Let p be the smallest prime divisor of |G|. For

(ω, ξ) ∈ G^{t} × G^{n+t−1},

define

F_{ω,ξ} : {0, …, p − 1}^{n} → G^{t},
y ↦ ω + T_{ξ} · y,

where T_{ξ} · y is defined as standard multiplication of the matrix T_{ξ} by the column vector y. Multiplication of an integer and an element of an Abelian group is defined in the usual way. More precisely, if we set

ω = (ω_{1}, …, ω_{t}) ∈ G^{t} , ξ = (ξ_{1}, …, ξ_{n+t−1}) ∈ G^{n+t−1},
y = (y_{1}, …, y_{n}) ∈ {0, …, p − 1}^{n},

then F_{ω,ξ}(y) ∈ G^{t}, and its j-th coordinate (F_{ω,ξ}(y))_{j} satisfies

(F_{ω,ξ}(y))_{j} = ω_{j} + y_{1} · ξ_{j} + ⋯ + y_{n} · ξ_{n+j−1},

Proposition 3 Let G be a finite Abelian group, and let p be the smallest prime divisor of |G|. Let n, t be positive integers. Then the family T = (G^{t} × G^{n+t−1}, {0, …, p − 1}^{n}, G^{t}) of hash functions, with the action defined as above, is pair-wise independent. ^{4}

Proof. The proof is just basic linear algebra, with some small adjustments to deal with the more general scenario. We first prove the case t = 1. Fix arbitrary, distinct y, y^{∗} ∈ {0, …, p − 1}^{n}. Consider the equations

T_{ξ_{0},ξ}(y) = ψ , T_{ξ_{0},ξ}(y^{∗}) = ψ^{∗},

in the unknowns ξ_{0} ∈ G, ξ = (ξ_{1}, …, ξ_{n}) ∈ G^{n} and for some ψ, ψ^{∗} ∈ G. Equivalently,

ξ_{0} + y_{1} · ξ_{1} + ⋯ + y_{n} · ξ_{n} = ψ,
ξ_{0} + y_{1}^{∗} · ξ_{1} + ⋯ + y_{n}^{∗} · ξ_{n} = ψ^{∗}.

4As an aside, as can be easily seen from the proof, if G is a finite field, then {0, …, p − 1}^{n} can be replaced by G^{n}. The more usual form of this proposition corresponds to this setting.

To prove pair-wise independence of the family, it is sufficient to show that for each pair (ψ, ψ^{∗}), the system has a solution (ξ_{0}, ξ_{1}, …, ξ_{n}) and that the total number of solutions is the same in each case.

Clearly, if the system has a solution for some given pair (ψ, ψ^{∗}), then the complete set of solutions (ξ_{0}, ξ_{1}, …, ξ_{n}) is a co-set in the group G^{n+1}, where the size of the co-set does not depend on the choice of (ψ, ψ^{∗}).

By assumption, y ≠ y^{∗}. Without loss of generality, say y_{n} ≠ y_{n}^{∗}. By definition of the prime p, the integer y_{n} − y_{n}^{∗} is invertible modulo |G|. Let a be an integer such that a · (y_{n} − y_{n}^{∗}) ≡ 1 (mod |G|).

For 1 ≤ j ≤ n − 1, set ξ_{j} ∈ G to an arbitrary value, and define \overline{ψ} = ψ − y_{1} · ξ_{1} − ⋯ − y_{n−1} · ξ_{n−1}, and \overline{ψ}^{∗} = ψ^{∗} − y_{1}^{∗} · ξ_{1} − ⋯ − y_{n−1}^{∗} · ξ_{n−1}.

By Gaussian Elimination it follows that (ξ_{0}, ξ_{1}, …, ξ_{n−1}, ξ_{n}) is a solution, where

ξ_{0} = (1 − ay_{n}) · \overline{ψ} + (ay_{n}) · \overline{ψ}^{∗} , ξ_{n} = a · (\overline{ψ} − \overline{ψ}^{∗}).

This settles the case t = 1.

The case t > 1 is implied by the previous case, as argued below. Using the same approach to proving pair-wise independence as above, we now have, for j = 1 … t, the following equations:

ω_{j} + y_{1} · ξ_{j} + ⋯ + y_{n} · ξ_{n+j−1} = ψ_{j},
ω_{j} + y_{1}^{∗} · ξ_{j} + ⋯ + y_{n}^{∗} · ξ_{n+j−1} = ψ_{j}^{∗},

in the unknowns (ω_{1}, …, ω_{t}, ξ_{1}, …, ξ_{n+t−1}) ∈ G^{n+2t−1}, and for some choice of (ψ_{1}, ψ_{1}^{∗}, …, ψ_{t}, ψ_{t}^{∗}) ∈ G.

For essentially the same reason as above, for all choices such that the system has a solution, it has the same number of solutions. To show that for each choice there is a solution, we iterate with the case t = 1, as follows.

Suppose first that y_{n} ≠ y_{n}^{∗}, We start with the first pair of equations (j = 1), and apply case t = 1 to it. This gives us a solution where ω_{1} and ξ_{1}, …, ξ_{n} are set to some values.

In the next step (j = 2), the variables are ω_{2} and ξ_{2}, …, ξ_{n+1}. For ξ_{2}, …, ξ_{n} we use the settings from the previous step, and apply case t = 1. This gives us a value for ω_{2} and ξ_{n+1}. Thus, so far we have values for ω_{1}, ω_{2} and ξ_{1}, …, ξ_{n+1} that satisfy the first two pairs of equations. It is clear that this can be iterated until a solution to the complete system is defined.

If y_{n} = y_{n}^{∗}, let r be the smallest integer such that y_{r} = y_{r}^{∗}, …, y_{n} = y_{n}^{∗}. For j = 1 … t, we then define new variables

ω′_{j} = ω_{j} + y_{r} · ξ_{r+j−1} + ⋯ + y_{n} · ξ_{n+j−1}.

With this substitution, we get a smaller system of the same form, but now with y_{r−1} ≠ y_{r−1}^{∗}. Thus, it can be solved as above. This gives values for all ω′_{j} and for a subset of the ξ_{i}’s. Next, give arbitrary values to the ξ_{i}’s which haven’t been set. The ω_{j}’s are now determined, and we have a solution for the complete system.

△

8 Concrete Encryption Schemes

We present two new public-key encryption schemes secure against adaptive chosen ciphertext attack. All follow the general construction from §6.

The first scheme is based on Paillier’s Decision Composite Residuosity assumption. Ours is the first practical public-key encryption scheme secure against adaptive chosen ciphertext attack under this assumption.

The second is based on the classical Quadratic Residuosity assumption. Ours is the first publickey encryption schemes secure against adaptive chosen ciphertext attack under this assumption, that is quite practical, as opposed to theoretical constructions such as [4].

Before presenting the new schemes, we show how the public-key encryption scheme from [3] can be viewed as a special case of our general construction.

8.1 Schemes based on the DDH Assumption

Let G be a group of given large prime order q, and with a given generator g, such that the basic group operations can be performed efficiently. Let log_{g} : G → ZZ_{q} denote the usual discrete logarithm function in G to the basis g. The Decision Diffie-Hellman (DDH) assumption is the assumption that the following two distributions are hard to distinguish:

1. the uniform distribution on all triples (c, d, f) ∈ G^{3};

2. the uniform distribution on all triples (c, d, f) ∈ G^{3} such that log_{g} f = log_{g} c · log_{g} d.

To be completely formal, one should actually specify a sequence of distributions of groups, such that for each value of a security parameter k ≥ 0, a description of a group G, together with g and q, can be efficiently sampled from some distribution parameterized by k. We assume that 1/q is bounded by ϵ(k) for all groups associated with security parameter k, where ϵ(k) is a negligible function in k.

There are many possible realizations of suitable groups G. For instance, let p be a large random prime, and let q be a large prime factor of p − 1. Then G is the unique sub-group of order q in ZZ_{p}^{∗}.

With G, g, and q given, we now define an instance of a subset membership problem as follows. Set g_{0} = g and let g_{1} be a random element of G. Define X = G × G, and let L be the subgroup of X generated by μ = (g_{0}, g_{1}) ∈ G × G. A witness for x ∈ L is w ∈ ZZ_{q} such that x = μ^{w}. The description of the subset membership problem instance consists of descriptions of G, q, g_{0}, and g_{1}.

Obviously, one can efficiently sample a random element of L, together with a corresponding witness, by generating w ∈ ZZ_{q} at random, and computing x = μ^{w}.

It is clear that this defines a subset membership problem, and that the hardness of this subset membership problem is implied by the DDH assumption for G.

Now it remains to construct appropriate strongly smooth and strongly universal_{2} HPS’s for the construction in §6.2. To do this, we first construct a diverse group system (see Definition 10), from which we can then derive the required HPS’s. Let G = Hom(X, G). The elements of G can be identified with ZZ_{q}×ZZ_{q}, where each pair ϕ = (ϕ_{0}, ϕ_{1}) ∈ ZZ_{q}×ZZ_{q} determines the homomorphism from X to G that sends (h_{0}, h_{1}) ∈ X to h_{0}^{ϕ_{0}}h_{1}^{ϕ_{1}} ∈ G. So we have a group system G = (G, X, L, G, G, α), where α is the map that sends ϕ = (ϕ_{0}, ϕ_{1}) ∈ ZZ_{q} × ZZ_{q} to g_{0}^{ϕ_{0}}g_{1}^{ϕ_{1}}.

By Proposition 1, the group system G is diverse and forms a a 1/q-universal family of projective hash functions. By the observations in the paragraph following Definition 6, it follows that G is a 0-smooth family of projective hash functions. This immediately yields strongly smooth HPS Ĝ corresponding to G — one simply needs to verify that all the algorithms that must be provided by an HPS are available. This is rather straightforward. For example, the public evaluation function is given x ∈ L with a witness w ∈ ZZ_{q}, along with α(ϕ) ∈ G for some ϕ ∈ G, and can compute ϕ(x) = α(ϕ)^{w}.

So now we have a strongly smooth HPS Ĝ as needed for the construction in §6.2. Applying the construction in Theorem 3 to the group system G, we obtain a 1/q-universal_{2}

projective hash family H for (X × G, L × G), and from this, a corresponding strongly universal_{2} HPS Ĥ. Again, it is straightforward to verify that all the necessary algorithms required by an HPS are available.

8.1.1 The Encryption Scheme

We now present in detail the encryption algorithm obtained from the HPS’s Ĝ and Ĥ above.

We describe the scheme in terms of a fixed group of G of order q and with generator g = g_{0}. The message space for the scheme is the group G.

Let Γ : G × G × G → ZZ_{q}^{n} be an efficiently computable injective map for an appropriate n ≥ 1.

Key Generation First, generate g_{1} ∈ G at random. Second, choose z_{0}, z_{1} ∈ ZZ_{q} at random, and set h = g_{0}^{z_{0}}g_{1}^{z_{1}} ∈ G. Third, choose

y_{0,0}, y_{0,1}, …, y_{n,0}, y_{n,1} ∈ ZZ_{q}

at random, and set c_{i} = g_{0}^{y_{i,0}}g_{1}^{y_{i,1}} ∈ G for i = 0, …, n.

The public key is (g_{1}, h, c_{0}, …, c_{n}), and the private key is

(z_{0}, z_{1}, y_{0,0}, y_{0,1}, …, y_{n,0}, y_{n,1}).

Encryption To encrypt a message m ∈ G under a public key as above, one does the following.

First, choose r ∈ ZZ_{q} at random, and compute

u_{0} = g_{0}^{r} ∈ G, u_{1} = g_{1}^{r} ∈ G, e = m · h^{r} ∈ G.

Second, compute v = ∏_{i=0}^{n} c_{i}^{γ_{i}r} ∈ G, where γ_{0} = 1 and (γ_{1}, …, γ_{n}) = Γ(u_{0}, u_{1}, e) ∈ ZZ_{q}^{n}.

The ciphertext is (u_{1}, u_{2}, e, v).

Decryption To decrypt a ciphertext (u_{1}, u_{2}, e, v) ∈ G^{4} under a secret key as above, one does the following.

First, check that

v = u_{0}^{∑_{i=0}^{n} γ_{i}y_{i,0}}u_{1}^{∑_{i=0}^{n} γ_{i}y_{i,1}},

where γ_{0} = 1 and (γ_{1}, …, γ_{n}) = Γ(u_{0}, u_{1}, e) ∈ ZZ_{q}^{n}; if not, then output a default error message and halt.

Second, compute m = e/(u_{0}^{z_{0}}u_{1}^{z_{1}}) ∈ G, and output m.

Note that in the decryption algorithm, we are assuming that u_{1}, u_{2}, e, v are elements of G. This implicitly means that the decryption algorithm should test that this is the case, and otherwise reject the ciphertext. However, there is some room for optimization; that is, some of these tests may be omitted without affecting the functionality of the decryption algorithm.

This is precisely the scheme that our general construction in §6.2 yields, although we have changed the notation somewhat, and simplified a few expressions using trivial algebraic identities. Thus, the scheme is secure against adaptive chosen ciphertext attack, provided the DDH assumption holds.

This scheme is essentially the encryption scheme presented in §5.3 of [3], with just a few very minor differences.

To obtain a more efficient scheme, one could drop the requirement that Γ is injective. This would allow us to use a smaller value of n, possibly n = 1, thereby obtaining a much more compact and efficient scheme. It is straightforward to adapt our general theory to show that if Γ is collision resistant, then we still get a scheme that is secure against adaptive chosen ciphertext attack. With a somewhat more refined analysis, one can show that a universal one-way hash function suffices. When n = 1, the resulting encryption scheme is the main encryption scheme presented in [3], with just a few very minor differences.

8.2 Schemes based on the Decision Composite Residuosity Assumption

Let p, q, p′, q′ be distinct odd primes with p = 2p′ + 1 and q = 2q′ + 1, and where p′ and q′ are both λ bits in length. For convenience, we assume that p < q. Let N = pq and N′ = p′q′. Consider the group ZZ_{N^{2}}^{∗} and the subgroup P of ZZ_{N^{2}}^{∗} consisting of all N-th powers of elements in ZZ_{N^{2}}^{∗}.

Paillier’s Decision Composite Residuosity (DCR) assumption is that given only N, it is hard to distinguish random elements of ZZ_{N^{2}}^{∗} from random elements of P.

To be completely formal, one should specify specify a sequence of bit lengths λ(k), parameterized by a security parameter k, and to generate an instance of the problem for security parameter k, the primes p′ and q′ should be distinct, random primes of length λ = λ(k), such that p = 2p′ + 1 and q = 2q′ + 1 are also primes.

The primes p′ and q′ are called Sophie Germain primes by mathematicians, while p and q are called strong primes by cryptographers. It has never been proven that there are infinitely many Sophie Germain primes. Nevertheless, it is widely conjectured, and amply supported by empirical evidence, that the probability that a random λ-bit number is Sophie Germain prime is Ω(1/λ^{2}). We shall assume that this conjecture holds, so that we can assume that problem instances can be efficiently generated.

Note that Paillier did not make the restriction to strong primes in originally formulating the DCR assumption. As will become evident, we need to restrict ourselves to strong primes for technical reasons. However, it is easy to see that the DCR assumption without this restriction implies the DCR assumption with this restriction, assuming that strong primes are sufficiently dense, as we are here.

We can decompose ZZ_{N^{2}}^{∗} as an inner direct product

ZZ_{N^{2}}^{∗} = G_{p} · G_{q} · G_{p′} · G_{q′} · G_{2} · S,

where each group G_{τ} is a cyclic group of order τ, and S is the subgroup of ZZ_{N^{2}}^{∗} generated by (−1 mod N^{2}). Note that the element ξ = (1 + N^{2} mod N) ∈ ZZ_{N^{2}}^{∗} has order N, i.e., it generates G_{p}G_{q}, and that ξ^{m} = (1 + mN mod N) for 0 ≤ m < N.

Define the map

θ : ZZ_{N^{2}}^{∗} → {±1},
(a mod N^{2}) ↦ (a | N),

where (· | ·) is the Jacobi symbol. It is clear that θ is a group homomorphism.

Let X be the kernel of θ. It is easy to see that X = G_{p}G_{q}G_{p′}G_{q′}S, since |ZZ_{N^{2}}^{∗}/X| = 2 and S ⊂ X. In particular, X is a cyclic group. Let L be the subgroup of N-th powers of X. Then evidently, L = G_{p′}G_{q′}S. These groups X and L will define our subset membership problem.

Our instance description will contain N, along with a random generator g for L. It is easy to generate such a g: choose a random μ ∈ ZZ_{N^{2}}^{∗}, and set g = −μ^{2N}. With overwhelming probability, such a g will generate L, and so the output distribution of this sampling algorithm will be statistically close the uniform distribution over all generators.

Let us define the set of witnesses as W = {0, …, ⌊N/2⌋}. Clearly, x ∈ L if and only if x = g^{w} for some w ∈ W. To generate x ∈ L at random together with a corresponding witness, we simply generate w ∈ W at random, and compute x = g^{w}. The output distribution of this algorithm is not the uniform distribution over L, but one that is statistically close to it.

This completes the description of our subset membership problem. It is easy to see that it satisfies all the basic requirements specified in §4. The reason for using (X, L) instead of (ZZ_{N^{2}}^{∗}, P) is that ZZ_{N^{2}}^{∗} and P are not cyclic, which is inconvenient for a number of technical reasons.

Next, we argue that the DCR assumption implies that this subset membership problem is hard. Suppose we are given x sampled at random from ZZ_{N^{2}}^{∗} (respectively, P). If we choose b ∈ {0, 1} at random, then x^{2}(−1)^{b} is uniformly distributed over X (respectively, L). This implies that distinguishing X from L is at least as hard as distinguishing ZZ_{N^{2}}^{∗} from P, and so under the DCR assumption, it is hard to distinguish X from L. It is easy to see that this implies that it is hard to distinguish X − L from L as well.

Now it remains to construct appropriate strongly smooth and strongly universal_{2} HPS’s for the construction in §6.2. To do this, we first construct a diverse group system (see Definition 10), from which we can then derive the required HPS’s. Let G = Hom(X, X). The elements of G can be identified with ZZ_{2NN′}, where each ϕ ∈ ZZ_{2NN′} determines the homomorphism from X to X that sends h ∈ X to h^{ϕ}. So we have a group system G = (G, X, L, X, L, α), where the map α sends ϕ ∈ ZZ_{2NN′} to g^{ϕ}.

By Corollary 1, the group system G is diverse, and forms a 1/p-universal family of projective hash functions. This group system yields a corresponding ϵ(k)-universal HPS Ĝ, where ϵ(k) = 2^{−λ(k)}. To see this, we have to verify that we can effectively sample G and that we can effectively implement the public evaluation function. Although we cannot easily sample the uniform distribution of G, we can sample the uniform distribution on the power maps {0, …, ⌊N^{2}/2⌋}, which yields a distribution on G that is statistically close to the uniform distribution. To implement the public evaluation function, given x ∈ L and a corresponding witness w ∈ W, along with α(ϕ) ∈ L for ϕ ∈ G, we can compute ϕ(x) as α(ϕ)^{w}.

Now, we could easily convert Ĝ into a strongly smooth HPS by applying the Leftover Hash Lemma construction in Lemma 5 to the underlying family G of projective hash functions. However, this is not the most practical way to proceed. We get a more practical scheme by using the following observation.

Proposition 4 For any x ∈ X − L with order divisible by N, and any y ∈ L, the distribution of ϕ(x) for a random ϕ ∈ G subject to α(ϕ) = y is precisely the uniform distribution on a particular coset of G_{p}G_{q} in X (the exact coset depends on x and y). If the order of x is divisible by only p (respectively, q), then we get the uniform distribution over a coset of G_{p} (respectively, G_{q}) in X.

Proof. Any x ∈ X can be expressed uniquely as x = g^{a}ξ^{b} for a ∈ ZZ_{2N′} and b ∈ ZZ_{N}. Also, any ϕ ∈ G can be uniquely identified with a′ ∈ ZZ_{2N′} and b′ ∈ ZZ_{N}, where ϕ sends x = g^{a}ξ^{b} ∈ X as above to g^{aa′}ξ^{bb′}. If ϕ corresponds to (a′, b′) as above, then α(ϕ) = g^{a′}; thus, the distribution of b′ for a random ϕ ∈ G subject to α(ϕ) = g^{a′} is precisely the uniform distribution on ZZ_{N}. If x = g^{a}ξ^{b}, then conditioning on α(ϕ) = g^{a′}, we see that the distribution of ϕ(x) is the uniform distribution on the coset g^{aa′} ⟨ ξ^{b} ⟩, where ⟨ ξ^{b} ⟩ denotes the subgroup generated by ξ^{b}. One sees that ⟨ ξ^{b} ⟩ is either G_{p}G_{q} (respectively, G_{p}, G_{q}), according to whether the order of x is divisible by N (respectively, only p, only q).

△

Based on Proposition 4, we can construct a 2/p-smooth family G^{×} of projective hash functions as follows. Define the map

χ : ZZ_{N^{2}} → ZZ_{N},
(a + bN mod N^{2}) ↦ (b mod N) (0 ≤ a, b < N).

This map does not preserve any algebraic structure; however, it is easy to verify that the restriction of χ to any coset of G_{p}G_{q} in X is a one-to-one map from that coset onto ZZ_{N}. We define G^{×} = (G^{×}, X, L, ZZ_{N}, L, α^{×}), where G^{×} = {χ ∘ ϕ : ϕ ∈ G}, and α^{×} sends χ ∘ ϕ to α(ϕ). That is, G^{×} is the same as G, except that to hash a value, we pass the output of the hash function for G through the function χ. Since a random x ∈ X − L has order divisible by N with probability at least 1 − 2/p, Proposition 4 implies that G^{×} is a 2/p-smooth family of projective hash functions.

¿From G^{×} we get a corresponding (2ϵ(k))-smooth HPS Ĝ^{×}.

We can apply the construction in Theorem 3 to G, obtaining a 1/p-universal_{2} family H of projective hash functions for (X × ZZ_{N}, L × ZZ_{N}). This yields a corresponding extended ϵ(k)- universal_{2} HPS Ĥ. We could build our encryption scheme directly using Ĥ; however, we get more compact ciphertexts if we modify H by passing its hash outputs through χ, just as we did in building G^{×}, obtaining the analogous family H^{×} of projective hash functions for (X ×ZZ_{N}, L×ZZ_{N}). Combining the main observations from the proofs of Theorem 3 and Proposition 4, it is easy to see that the appropriate analog of Proposition 4 holds for H as well, and so we see that H^{×} is a 1/p-universal_{2} family of projective hash functions for (X × ZZ_{N}, L × ZZ_{N}). ¿From this, we get a corresponding extended ϵ(k)-universal_{2} HPS Ĥ^{×}.

8.2.1 The Encryption Scheme

We now present in detail the encryption scheme obtained from the HPS’s Ĝ^{×} and Ĥ^{×} above.

We describe the scheme for a fixed value of N that is the product of two (λ + 1)-bit strong primes. The message space for this scheme is ZZ_{N}.

Let X, L, θ, and χ be as defined above. Let R = {0, …, 2^{λ} − 1}, and let Γ : ZZ_{N^{2}} × ZZ_{N} → R^{n} be an efficiently computable injective map for an appropriate n ≥ 1. For sufficiently large λ, n = 7 suffices.

Key Generation Choose μ ∈ ZZ_{N^{2}}^{∗} at random and set g = −μ^{2N} ∈ L.

Choose

z, y_{0}, …, y_{n} ∈ {0, …, ⌊N^{2}/2⌋}

at random, and set h = g^{z} ∈ L and c_{i} = g^{y_{i}} ∈ L for i = 0, …, n.

The public key is (g, h, c_{0}, …, c_{n}), and the private key is (z, y_{0}, …, y_{n}).

Encryption To encrypt a message m ∈ ZZ_{N} under a public key as above, one does the following.

First, choose r ∈ {0, …, ⌊N/2⌋} at random, and compute

u = g^{r} ∈ L, e = m + χ(h^{r}) ∈ ZZ_{N}.

Second, compute v = χ(∏_{i=0}^{n} c_{i}^{γ_{i}r}) ∈ ZZ_{N}, where γ_{0} = 1 and (γ_{1}, …, γ_{n}) = Γ(u, e) ∈ R^{n}.

The ciphertext is (u, e, v).

Decryption To decrypt a ciphertext (u, e, v) ∈ X × ZZ_{N} × ZZ_{N} under a secret key as above, one does the following.

First, check that

v = χ(u^{∑_{i=0}^{n} γ_{i}y_{i}}),

where γ_{0} = 1 and (γ_{1}, …, γ_{n}) = Γ(u, e) ∈ R^{n}; if not, then output a default error message and halt.

Second, compute m = e − χ(u^{z}) ∈ ZZ_{N}, and output m.

Note that in the decryption algorithm, we are assuming that u ∈ X, which implicitly means that the decryption algorithm should check that u ∈ ZZ_{N^{2}}^{∗} and that θ(u) = 1, and reject the ciphertext if this does not hold.

This is precisely the scheme that our general construction in §6.2 yields, although we have changed the notation somewhat. Thus, the scheme is secure against adaptive chosen ciphertext attack, provided the DCR assumption holds.

As in §8.1.1, if we replace Γ by a collision resistant hash function we get an even more efficient scheme with a smaller value of n, possibly even n = 1. In fact, just a universal one-way hash function suffices.

Note that in this scheme, the factorization of N is not a part of the private key. This would allow, for example, many parties to work with the same modulus N, which may be convenient in some situations. Alternatively, if we allow the decryptor to know the factorization of N, a number of optimizations are possible. For example, Chinese Remaindering techniques can be used to speed up the computation in the decryption algorithm.

8.2.2 A Variation

We now present a variation of the above encryption scheme.

The key generation algorithm is exactly the same as in the above scheme, and the message space is {0, …, N − 1}. Let R = {0, …, 2^{λ} − 1}, and let Γ : ZZ_{N^{2}} × ZZ_{N^{2}} → R^{n} be an efficiently computable injective map for an appropriate n ≥ 1.

Recall that ξ = (1 + N mod N^{2}) ∈ ZZ_{N^{2}}^{∗} has order N, and that ξ^{m} = (1 + mN mod N^{2}) for m ∈ {0, …, N − 1}.

Encryption To encrypt a message m ∈ {0, …, N −1} under a public key as above, one does the following.

First, choose r ∈ {0, …, ⌊N/2⌋} at random, and compute

u = g^{r} ∈ L, e = ξ^{m} · h^{r} ∈ X.

Second, compute v = ∏_{i=0}^{n} c_{i}^{γ_{i}r} ∈ L, where γ_{0} = 1 and (γ_{1}, …, γ_{n}) = Γ(u, e) ∈ R^{n}.

The ciphertext is (u, e, v).

Decryption To decrypt a ciphertext (u, e, v) ∈ X × X × X under a secret key as above, one does the following.

First, check that

v = u^{∑_{i=0}^{n} γ_{i}y_{i}},

where γ_{0} = 1 and (γ_{1}, …, γ_{n}) = Γ(u, e) ∈ R^{n}; if not, then output a default error message and halt.

Second, compute e/u^{z} ∈ X; if this is of the form ξ^{m} for m ∈ {0, …, N − 1}, then output m; otherwise, a default error message.

Although this scheme does not follow directly from our general constructions, it is easy to see, based on Proposition 4, that it is also secure against adaptive chosen ciphertext attack under the DCR assumption. We leave the details of this as an exercise for the reader.

As usual, we get a more efficient scheme if we replace Γ by a collision resistant hash function (or universal one-way hash function), and use a smaller value of n, possibly even n = 1.

While the ciphertexts in this variation are less compact than in the previous scheme, they have more algebraic structure, and so we expect this scheme to be of use in protocols where a participant needs to prove that ciphertexts satisfy particular properties.

8.3 Schemes based on the Quadratic Residuosity Assumption

Let p, q, p′, q′ be distinct odd primes with p = 2p′ + 1 and q = 2q′ + 1, and where p′ and q′ are both λ bits in length. Let N = pq and let N′ = p′q′. Consider the group ZZ_{N}^{∗}, and let X be the subgroup of elements (a mod N) ∈ ZZ_{N}^{∗} with Jacobi symbol (a | N) = 1, and let L be the subgroup of squares (a.k.a., quadratic residues) of ZZ_{N}^{∗}. Note that L is a subgroup of X of index 2. These groups X and L will define our subset membership problem.

The Quadratic Residuosity (QR) assumption is that given only N, it is hard to distinguish random elements of X from random elements of L. This implies that it is hard to distinguish random elements of X − L from random elements of L.

To be completely formal, one should specify specify a sequence of bit lengths λ(k), parameterized by a security parameter k, and to generate an instance of the problem for security parameter k, the primes p′ and q′ should be distinct, random primes of length λ = λ(k), such that p = 2p′ + 1 and q = 2q′ + 1 are also primes.

As in §8.2, we shall assume that strong primes (such as p and q) are sufficiently dense. Note that the original QR assumption was not restricted to strong primes. However, the QR assumption without this restriction implies the QR assumption with this restriction, assuming that strong primes are sufficiently dense, as we are here.

We can decompose ZZ_{N}^{∗} as an inner direct product

ZZ_{N}^{∗} = G_{p′} · G_{q′} · G_{2} · S,

where each group G_{τ} is a cyclic group of order τ, and S is the subgroup of ZZ_{N}^{∗} generated by (−1 mod N).

It is easy to see that X = G_{p′}G_{q′}S, so it is a cyclic group, and that L = G_{p′}G_{q′}.

Our instance description will contain N, along with a random generator g for L. It is easy to generate such a g: choose a random μ ∈ ZZ_{N}^{∗}, and set g = μ^{2}. With overwhelming probability, such a g will generate L, and so the output distribution of this sampling algorithm will be statistically close the uniform distribution over all generators.

Let us define the set of witnesses as W = {0, …, ⌊N/4⌋}. Clearly, x ∈ L if and only if x = g^{w} for some w ∈ W. To generate x ∈ L at random together with a corresponding witness, we simply generate w ∈ W at random, and compute x = g^{w}. The output distribution of this algorithm is not the uniform distribution over L, but is statistically close to it.

This completes the description of our subset membership problem. It is easy to see that it satisfies all the basic requirements specified in §4. As already mentioned, the QR assumption implies that this is a hard subset membership problem.

Now it remains to construct appropriate strongly smooth and strongly universal_{2} HPS’s for the construction in §6.2. To do this, we first construct a diverse group system (see Definition 10), from which we can then derive the required HPS’s. Let G = Hom(X, X). The elements of G can be identified with ZZ_{2N′}, where each ϕ ∈ ZZ_{2N′} determines the homomorphism from X to X that sends h ∈ X to h^{ϕ}. So we have a group system G = (G, X, L, X, L, α), where the map α sends ϕ ∈ ZZ_{2N′} to g^{ϕ}.

By Corollary 1, this group system is diverse, and forms a 1/2-universal family of projective hash functions. This group system immediately yields a corresponding 1/2-universal HPS Ĝ. To see this, we have to verify that we can effectively sample G and that we can effectively implement the public evaluation function. Although we cannot easily sample the uniform distribution of G, we can sample the uniform distribution on the power maps {0, …, ⌊N/2⌋}, which yields a distribution on G that is statistically close to the uniform distribution. To implement the public evaluation function, given x ∈ L and a corresponding witness w ∈ W, along with α(ϕ) ∈ L for ϕ ∈ G, we can compute ϕ(x) as α(ϕ)^{w}.

We can apply the construction in Lemma 2 to get a 2^{−t}-universal family G_{∗} of projective hash functions, where t = t(k) is an auxiliary parameter, along with a corresponding 2^{−t(k)}-universal HPS Ĝ_{∗}.

Now, we could easily convert Ĝ_{∗} into a strongly smooth HPS by applying the Leftover Hash Lemma construction in Lemma 5 to the underlying family G_{∗} of projective hash families. However, this is not the most practical way to proceed. We get a more practical scheme by using the following observation.

Proposition 5 For any x ∈ X − L and any y ∈ L, the distribution of ϕ(x) for a random ϕ ∈ G subject to α(ϕ) = y is precisely the uniform distribution on {±z}, for some particular z ∈ X (the exact value of z depends on x and y).

Proof. Any x ∈ X can be expressed uniquely as x = g^{a}(−1)^{b} for a ∈ ZZ_{N′} and b ∈ ZZ_{2}. Also, any ϕ ∈ G can be uniquely identified with a′ ∈ ZZ_{N′} and b′ ∈ ZZ_{2}, where ϕ sends x = g^{a}(−1)^{b} ∈ X as above to g^{aa′}(−1)^{bb′}. If ϕ corresponds to (a′, b′) as above, then α(ϕ) = g^{a′}; thus, the distribution of b′ for a random ϕ ∈ G subject to α(ϕ) = g^{a′} is precisely the uniform distribution on ZZ_{2}. If x ∈ X − L, then x = g^{a}(−1)^{b} with b = 1, and so conditioning on α(ϕ) = g^{a′}, we see that the distribution of ϕ(x) is the uniform distribution {±g^{aa′}}.

△

Based on Proposition 5, we can construct a 0-smooth family G^{×} of projective hash functions as follows. Define the map χ : ZZ_{N} → ZZ_{2} as follows: for x = (a mod N) ∈ ZZ_{N}^{∗}, with 0 ≤ a < N, let χ(x) = 1 if a > N/2, and χ(x) = 0 otherwise. Then by Proposition 5, for any x ∈ X − L and any y ∈ L, the distribution of χ(ϕ(x)) for a random ϕ ∈ G subject to α(ϕ) = y is precisely the uniform distribution on ZZ_{2}. We define G^{×} = (G^{×}, X, L, ZZ_{2}, L, α), where G^{×} = {χ ∘ ϕ : ϕ ∈ G), and α^{×} sends χ ∘ ϕ to α(ϕ). That is, G^{×} is that same as G, except that we pass the output of a hash function for G through the function χ. It is clear from the above discussion that G^{×} is 0-smooth.

Now, we can apply the construction in Lemma 2 to G^{×} with the parameter t = t(k) to get a 0-smooth family G_{∗}^{×} of projective hash functions whose hash output space is ZZ_{2}^{t}. ¿From this, we get an corresponding 0-smooth HPS Ĝ_{∗}^{×}.

We can apply the construction in Theorem 4 to G, obtaining a 2^{−t′}-universal_{2} family H_{∗} of projective hash functions for (X × ZZ_{2}^{t}, L × ZZ_{2}^{t}). Here, t′ = t′(k) is an auxiliary parameter. The hash outputs for H_{∗} consist of t′-tuples of elements of X. This yields a corresponding extended 2^{−t′(k)}-universal_{2} HPS Ĥ_{∗}. We could build our encryption scheme directly using Ĥ_{∗}; however, we get more compact ciphertexts if we modify H_{∗} by passing each component of its hash output through χ, just as we did in building G^{×}, obtaining the analogous family H_{∗}^{×} of projective hash functions for (X ×ZZ_{2}^{t}, L×ZZ_{2}^{t}). Combining the main observations from the proofs of Theorem 4 and Proposition 5, it is easy to see that the appropriate analog of Proposition 5 holds for H_{∗} as well, and so we see that H_{∗}^{×} is a 2^{−t′}-universal_{2} family of projective hash functions for (X × ZZ_{2}^{t}, L × ZZ_{2}^{t}). ¿From this, we get a corresponding extended 2^{−t′(k)}-universal_{2} HPS Ĥ_{∗}^{×}.

8.3.1 The Encryption Scheme

We now present in detail the encryption obtained using the HPS’s Ĝ_{∗}^{×} and Ĥ_{∗}^{×} above.

We describe the scheme for a fixed value of N that is product of two (λ + 1)-bit strong primes. The message space for this scheme is ZZ_{2}^{t}, where t = t(k) is an auxiliary parameter. Note that t may be any size — it need not be particularly large. We also need an auxiliary parameter t′ = t′(k). The value of t′ should be large; more precisely, 2^{−t′(k)} should be a negligible function in k.

Let X, L, and χ be as defined above. Also, let Γ : ZZ_{N} × ZZ_{2}^{t} → {0, 1}^{n} be an efficiently computable injective map for an appropriate n ≥ 1.

Key Generation Choose μ ∈ ZZ_{N}^{∗} at random and set g = μ^{2} ∈ L. Randomly choose

z_{0}, …, z_{t−1}, x_{0}, …, x_{t′−1}, y_{0}, …, y_{n+t′−2} ∈ {0, …, ⌊N/2⌋}.

Then compute

\begin{aligned}h_{i} & = & g^{z_{i}} ∈ L & (i = 0, …, t − 1), \\ c_{i} & = & g^{x_{i}} ∈ L & (i = 0, …, t′ − 1), \\ d_{i} & = & g^{y_{i}} ∈ L & (i = 0, …, n + t′ − 2). \end{aligned}

The public key is (g; h_{0}, …, h_{t−1}; c_{0}, …, c_{t′−1}; d_{0}, …, d_{n+t′−2}). The private key is (z_{0}, …, z_{t−1}; x_{0}, …, x_{t′−1}; y_{0}, …, y_{n+t′−2}).

Encryption To encrypt a message m ∈ ZZ_{2}^{t} under a public key as above, one does the following. First, choose r ∈ {0, …, ⌊N/4⌋} at random, and compute u = g^{r} ∈ L as well as

h̃_{i} = h_{i}^{r} ∈ L (i = 0, …, t − 1).

Second, compute

e = m + (χ(h̃_{0}), …, χ(h̃_{t−1})) ∈ ZZ_{2}^{t}.

Third, compute

\begin{aligned}c̃_{i} & = & c_{i}^{r} ∈ L & (i = 0, …, t′ − 1), \\ d̃_{i} & = & d_{i}^{r} ∈ L & (i = 0, …, n + t′ − 2), \\ v_{i} & = & c̃_{i} ∏_{j=0}^{n−1}(d̃_{i+j})^{γ_{j}} ∈ L & (i = 0, …, t′), \end{aligned}

where (γ_{0}, …, γ_{n−1}) = Γ(u, e) ∈ {0, 1}^{n}. Fourth, compute

v = (χ(v_{0}), …, χ(v_{t′−1})) ∈ ZZ_{2}^{t′}.

The ciphertext is (u, e, v). Decryption

To decrypt a ciphertext (u, e, v) ∈ X × ZZ_{2}^{t} × ZZ_{2}^{t′} under a private key as above, one does the following. First, compute

v̂_{i} = u^{x_{i}+∑_{j=0}^{n−1} γ_{j}y_{i+j}} ∈ X (i = 0, …, t′ − 1),

where (γ_{0}, …, γ_{n−1}) = Γ(u, e) ∈ {0, 1}^{n}. Second, check that

v = (χ(v̂_{0}), …, χ(v̂_{t′−1}));

if not, then output a default error message and halt.

Third, compute

ĥ_{i} = u^{z_{i}} ∈ X (i = 0, …, t − 1).

Fourth, compute

m = e − (χ(ĥ_{0}), …, χ(ĥ_{t−1})) ∈ ZZ_{2}^{t}

and output m.

Note that in the decryption algorithm, we are assuming that u ∈ X, which implicitly means that the decryption algorithm should check that u = (a mod N) with Jacobi symbol (a | N) = 1.

This is precisely the scheme that our general construction in §6.2 yields, although we have changed the notation somewhat. Thus, the scheme is secure against adaptive chosen ciphertext attack, provided the QR assumption holds.

As in §8.1.1, if we replace Γ by a collision resistant hash function we get an even more efficient scheme with a smaller value of n. In fact, just a universal one-way hash function suffices.

Note that in this scheme, the factorization of N is not a part of the private key. This would allow, for example, many parties to work with the same modulus N, which may be convenient in some situations. Alternatively, if we allow the decryptor to know the factorization of N, a number of optimizations are possible. For example, Chinese Remaindering techniques can be used to speed up the computation in the decryption algorithm.

While this scheme is not nearly as efficient as our schemes based on the DDH and DCR assumptions, it is based on an assumption that is perhaps qualitatively weaker than either of these assumptions. Moreover, the scheme may just be practical enough for some applications. Let us consider some concrete security parameters. We might choose N to be a 1024-bit number. If we use this scheme just to encrypt a symmetric encryption key, then t = 128 is a reasonable value. Setting t′ = 128 is also reasonable. If we implement Γ using a hash function like SHA-1, then we can take n = 160.

With these choices of parameters, the size of a public or private key will be less than 70KB. Ciphertexts are quite compact, requiring 160 bytes. An encryption takes less than 600 1024-bit exponentiations modulo N; this will take about 10 seconds or so on typical a 1GHz PC. A decryption will require about half as many exponentiations modulo N, and so without any optimizations, this would take roughly half as much time as encryption; however, if we use the Chinese Remaindering optimizations mentioned above, this should cut the running time further by a factor of between 3 and 4; also, if we exploit the fact that all exponentiations in the decryption algorithm are to the same basis, further significant optimizations are possible, bringing the time for a decryption down to around one second or less.

So clearly, this scheme is not suitable for, say, implementation on a smart card. However, it is not astronomically impractical, either.

Acknowledgments

Thanks to Ivan Damgaard for noting an improvement in the 1/p-bound stated in Theorem 2, and thanks to Amit Sahai and Yehuda Lindell for useful discussions.

References

[1] M. Bellare and P. Rogaway. Random oracles are practical: a paradigm for designing efficient protocols. In: Proc. ACM Computer and Communication Security ’93, ACM Press, 1993.

[2] J. Carter and M. Wegman. Universal classes of hash functions. In: Journal of Computer and System Sciences, vol. 18, pp. 143–154, 1979.

[3] R. Cramer and V. Shoup. A practical public key cryptosystem secure against adaptive chosen cipher text attacks. In: Proc. CRYPTO ’98, Springer Verlag LNCS, 1998.

[4] D. Dolev and C. Dwork and M. Naor. Non-malleable cryptography. In: Proc. STOC ’91, ACM Press, 1991.

[5] M. Luby. Pseudorandomness and Cryptographic Applications. Princeton University Press, 1996.

[6] M. Naor and M. Yung. Public-key cryptosystems provably secure against chosen ciphertext attacks. In: Proc. STOC ’90, ACM Press, 1990.

[7] P. Paillier. Public-key cryptosystems based on composite degree residue classes. In: Proc. EUROCRYPT ’99, Springer Verlag LNCS, 1999.

[8] C. Rackoff and D. Simon. Non-interactive zero knowledge proof of knowledge and chosen ciphertext attacks. In: Proc. CRYPTO ’91, Springer Verlag LNCS, 1991.

[9] M. Wegman and J. Carter. New hash functions and their use in authentication and set equality. In: Journal of Computer and System Sciences, vol. 22, pp. 265–279, 1981.

Recent BRICS Report Series Publications

RS-01-37 Ronald Cramer and Victor Shoup. Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption. October 2001. 34 pp.

RS-01-36 Gerth Stølting Brodal, Rolf Fagerberg, and Riko Jacob. Cache Oblivious Search Trees via Binary Trees of Small Height. October 2001.

RS-01-35 Mayer Goldberg. A General Schema for Constructing One-Point Bases in the Lambda Calculus. September 2001. 6 pp.

RS-01-34 Flemming Friche Rodler and Rasmus Pagh. Fast Random Access to Wavelet Compressed Volumetric Data Using Hashing. August 2001. 31 pp.

RS-01-33 Rasmus Pagh and Flemming Friche Rodler. Lossy Dictionaries. August 2001. 14 pp. Short version appears in Meyer auf der Heide, editor, 9th Annual European Symposiumon on Algorithms, ESA ’01 Proceedings, LNCS 2161, 2001, pages 300– 311.

RS-01-32 Rasmus Pagh and Flemming Friche Rodler. Cuckoo Hashing. August 2001. 21 pp. Short version appears in Meyer auf der Heide, editor, 9th Annual European Symposiumon on Algorithms, ESA ’01 Proceedings, LNCS 2161, 2001, pages 121– 133.

RS-01-31 Olivier Danvy and Lasse R. Nielsen. Syntactic Theories in Practice. July 2001. 37 pp. Extended version of an article to appear in the informal proceedings of the Second International Workshop on Rule-Based Programming, RULE 2001 (Firenze, Italy, September 4, 2001).

RS-01-30 Lasse R. Nielsen. A Selective CPS Transformation. July 2001. 24 pp. To appear in Brookes and Mislove, editors, 27th Annual Conference on the Mathematical Foundations of Programming Semantics, MFPS ’01 Proceedings, ENTCS 45, 2000. A preliminary version appeared in Brookes and Mislove, editors, Preliminary Proceedings of the 17th Annual Conference on Mathematical Foundations of Programming Semantics, MFPS ’01, (Aarhus, Denmark, May 24–27, 2001), BRICS Notes Series NS-01-2, 2001, pages 201–222.