数理解析研究所講究録 1222 巻 2001 年 64-73

64

Subgroup Membership Problem and Its Applications toInformation Security
Akihiro Yamamura (山村 明弘)*

Subgroup Membership Problem

1

It is well known that the subg $mup$ membership problem for afinitely presented groups is not decidable in general, whereas it is solvable for the class of finite groups or finitely generated abeliangroups, However, if we consider more practical computation, that is, the probabilistic polyn0mial time algorithms (or equivalently the class BPP), the membership problem is not trivial
even for the class of finite abelian groups. As amatter of fact, several algorithmic problems usedin cryptography are characterized as the subgroup membership problem under the assumptionthat the corresponding membership problem is not in BPP. For example, there exists no known
probabilistic polynomial time algorithm for the integer factorization or the discrete logarithm
problem for some class of finite cyclic groups. The quadratic residue (QR for short) problem andthe decision Diffie Hellman (DDH for short) problem hive numerous applications in cryptography, and hence, they have been studied in detail. Following [11], we generalize and formalize
them as the subgroup membership prvyblem and to show many other algorithmic problems, which
are used in public key cryptography, are characterized as the subgroup membership problem aswell. Such aunification of algorithmic problems used in cryptography has not been appeared
up to date as far as the authors are concerned. Widely used assumptions in cryptography are
divided into two groups: the algorithmic assumptions related to the integer factoring (and theand the algorithmic assumptions related to the discrete logarithm problem (and the DDH).
The first is originated ffom the RSA cryptosystem and the second from the Diffie Hellman key
exchange protocol. These two look different and are usually discussed separately. The unified
approach to the integer factoring problem and the discrete logarithm problem shed light on thefundamental properties of algorithms required to provide the security. Therefore, we can getbetter understanding of the algorithmic problems by unified treatment of subgroup membership$\mathrm{Q}\mathrm{R})$problems.

1..1

Subgroup Membership Assumption

Determining the membership of agiven element of acertain group in its subgroup is not always
easy. As amatter of fact, the membership problem of asubgroup in afinitely presented groupis not recursive in general. To apply the membership problem to cryptographic schemes such asasymmetric cryptosystems, we require the efficiency of computation for legal participants andthe existence of atrapdoor. In this section we consider the subgroup membership problem withatrapdoor, and show that several problems widely used in cryptography are characterized as
the subgroup membership problem.
’Comxhunications Research Laboratory, 4-2-1, Nukui-Kitamachi, Koganei, Tokyo, 184-8795Japan e-mail:aki@crLgo.jp

65
Let be agroup, and let $H$ be its subgroup. The membership problem is to decide whether
or not agiven element $g\in G$ belongs to $H$ . We suppose that every element in has abinary representation of size , where is the security parameter. The membership can bedecided within polynomial time in if acertain information, called atrapdoor, is provided.
The membership of an element $g\in G$ in $H$ can be decided provided the trapdoor, however,
the membership cannot be decided with aprobability suktantiAy larger than without the
trapdoor. We now formalize the subgroup membership problem.
Let be the security parameter. For the input , aprobabilstic polynomial time algorithm
outputs the description of agroup $G$ , the description of asubgroup $H\subset G$ and the trapdoor
that provides afast algorithm for the subgroup membership problem of $H$ in $G$ . The algorithm
is called the instance generator. Every element of is represented as abinary sequence oflength . Computation of the multiplication in $G$ is performed in polynomial time in .
The predicate for the membership of asubgroup is denoted by Mem, that is, Mem is defined
$G$

$G$

$k$

$k$

$k$

$\frac{1}{2}$$1^{k}$$k$$\mathrm{I}\mathcal{G}$$G$$\mathrm{I}\mathcal{G}$

$k$

$k$

as follows:Mem, $H,x$ ) $=\{$

1if $x\in H$
0if $x\in S$ ,outputs the pair $(G,H)$ for , is in $G$ , and $S=G\backslash H$ . The subgrv up membershipand obtain apair ofproblem is to compute Mem in polynomial time in when we inputs
groups $(G,H)$ and an element in $G$ , which is uniformly and randomly chosen from $H$ or $G$
according to the coin toss $barrow R\{0, 1\}$ . If there does not exist aprobabilstic polynomial timealgorithm that computes Mem with aprobability substantially larger than , then we say thatthe membership problem is intractable. We also assume that one can choose uniformly andrandomly an element from both $H$ and $G$ . This is significant to apply to cryptographic schemes.
The following is trivial, however, it is useful for the construction of an PIR system based on
the subgroup membership problem.

where$1^{k}$$\mathrm{I}\mathcal{G}$$x$$1^{k}$$k$$g$$\Sigma 1$

Proposition 1.1 Let $G$ be a group, and let $H$ be a subgroup of G. For any $g\in G$ and $h\in H$ ,0
we have $gh\in H$ if and only $\dot{l}fg\in H$ .
Subgroup Membership Assumption I
For every constant c, and every family
an integer K such that for aU k $>K$ we have$\{C_{k}|k\in \mathrm{N}\}$Probof circuits of polynomial size in k, there is$(C_{k}(G,H,g)= \mathrm{M}\mathrm{e}\mathrm{m}(G,H,g))<\frac{1}{2}+\frac{1}{k^{e}}$where the probability is taken over (G,b $=0$ .

$H)arrow \mathrm{I}\mathcal{G}(1^{k})$, b$\epsilon${0,1}, g,$\epsilon$(1.1)

H if b $=1$ , g$\epsilon$

S if

The assumption claims that there exists no polynomial size circuit family to compute thepredicate Mem. The following is equivalent to the assumption above.
Subgroup membership assumption II
For every constant c, and every family
an integer K such that for all k $>K$ we have$\{C_{k}|k\in \mathrm{N}\}$of circuits of polynomial size in k, there is$| \mathrm{P}_{H}-\mathrm{P}_{S}|<\frac{1}{k^{e}}$

,

(1.2)

66
where the probabilities$\mathrm{p}_{H}$and Ps are defined as follows;$\mathrm{p}_{H}=\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}_{(Gff)arrow \mathrm{I}\mathcal{G}(1^{\iota_{)jg}\mathrm{d}_{H}}}(C_{k}(G,H,g)=1)$

,

and
P.

1.2

$s=\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}_{(Gfl)arrow \mathrm{I}\mathcal{G}(1^{\mathrm{k}})jg}(g_{S}C_{k}(G,H,g)=1)$

ExamplesWe exhibit several subgroup membership problems: the DDH problem, the QR problem, theresidue (RR for short) problem studied by Kurosawa and Tsujii [6], the -subgroup(PSUB forshort) problem introduced by Okamoto and Uchiyama [8] and the decisional composite residuoeity (DCR for short) problem introduced by Pailler [9]. Recall that the assumption that
the QR problem is intractable (QR assumption) is employed to prove the semantic security ofGoldwasser-Mical cryptosystem [4], and the assumption that the DDH problem is intractable(DDH assumption) is employed to prove the semantic security of ElGamal cryptosystem. These
two have many other applications. The assumption that one of problems above is intractable isemployed to prove the semantic security of the corresponding cryptosystem [6], [8], [9], respectively. We also note that the security of the cryptosystem introduced by Naccache and Stern [7]depends on the PSUB assumption as well.
$r\mathrm{t}\mathrm{h}$$\triangleright$

Quadratic Residue Problem
Let $p,q$ be primes. Set $N=\Pi$ . The primes and are trapdoor information for the quadratic
residue problem, on the other hand, the number $N$ is public information. Let be the subgroupconsisting of the elements whose Jacobi symbol is 1, and let $H$ be the subgroup ofofforconsisting of quadratic residues of , that is, $H=$ {}.
$H$
The quadratic residue problem of in is to decide whether or not, a llvenv element $g\in G$ ,belongs to $H$ . We can effectively determine the membership of in $H$ provided that the
information and are available. No polynomial time algorithm is known for the membershipof arandomly chosen element of in $H$ without the information and . Hence, if we define
an instance generator for the QR problem as aprobabilistic algorithm that outputs two primes
and of size and aquadratic non-residue whose Jacobi symbol is 1for the input , thenthe QR problem is considered as asubgroup membership problem. Note that we can obtain aquadratic non-residue with Jacobi symbol 1by using $p,q$ , and that it is possible to uniformly
and randomly choose elements ffom $H$ without the trapdoor information provided is given.
$p$

$q$

$G$

$(\mathrm{Z}/(N))^{*}$

$G$

$G$

$x$ $\in G|x=y^{2}\mathrm{m}\mathrm{o}\mathrm{d} N$$y\in(\mathrm{Z}/(N))^{*}$

$G$

$g$

$g$

$p$

$q$

$G$

$p$

$p$

$1^{k}$

$h$

$k$

$q$

$q$

$h$

$h$

Problem
Decision
Let be acyclic group of prime order . The group may be amultiplication group of afinite
field or agroup of rational points of an elliptic curve. Let be agenerator of G. The decision
Diffie Hellman problem is to decide whether or not $h_{2}=ae$ for the given quadruple
is afor some $1\leq a\leq p-1$ . If so, we say thatof elements in withproblem.
trapdoorthedecision-Hellmanistheof
integerThe
quadruple.
Diffie-Hellman
Knowing the trapdoor , we can efficiently decide whether or not $h_{2}=ffl$ .
We show that the DDH problem can be characterized as asubgroup membership problem. Then the input to the DDH
for acertain group. We set to be the direct productproblem is $(x, y)$ where $x,y\in G$ , that is, $=(g_{1},h_{1})$ and $y=(g_{2},h_{2})$ . It is obvious that
is aDiffie-Hellman quadruple if and only if belongs to the subgroup
generated by . It follows that the DDH problem for the cyclic group is equivalent tothe subgroup membership problem of the group $H=<x>$ ’where $x=(g_{1},g_{1}^{a})$ , in the group$\mathrm{D}\mathrm{i}\mathrm{f}\mathrm{f}\mathrm{l}\triangleright \mathrm{H}\mathrm{e}\mathrm{U}\mathrm{m}\mathrm{a}\mathrm{n}$

$C$

$C$

$p$

$g$

$(g_{1},h_{1},g_{2}, h_{2})$$C$$(g_{1},h_{1},g_{2},h_{2})$$h_{1}=g_{1}^{t}$$\mathrm{D}\underline{\mathrm{i}\mathrm{f}\mathrm{f}\mathrm{i}}\mathrm{e}-$

$a$

$a$

$C\mathrm{x}C$

$G$

$x$

$(g_{1},h_{1},g_{2},h_{2})$$G$$<x>\mathrm{o}\mathrm{f}$

$y$

$C$

$x$

.

67
G $=C$ xC $=<g_{1}>\mathrm{x}<g_{1}>$ . N.ote that, when agenerator x of H is given, it is possible tochoose uniformly and randomly elements from H without the trapdoor information.
Rth Residue Problem
The RR problem is anatural extension of the QR problem defined as follows. Let $p,q$ beprimes, and let ,e2 be odd integers dividing $p-1$ and $q-1$ , respectively, such thatis
. The primes and are theprime to $q-1$ and e2 is prime to $p-1$ . Set $N=pq$ andtrapdoor information for the RR problem, on the other hand, the number $N$ and are the public, and let $H$ be the subgroup consisting of rth residues
information. Let be the groupfor $y\in G$ }. The RR problem of $H$ in $G$ is to decideof , that is, $H=$ {whether or not, agiven element $g\in G$, belongs to $H$ . Thus, the RR is asubgroup membershipproblem of $H$ in . We can effectively determine the membership of in $H$ provided that the
information and are available. No polynomial time algorithm is known for the membershipof arandomly chosen element of $G$ in $H$ without the information and . Note that we can.
$-1$ by using
for any $1\leq|$
obtain an element such thatthe trapdoor information, and that we can uniformly and randomly choose an element ffom $H$
provided is given.
$e_{1}$$e_{1}$$r$$=e_{1}e_{2}$

$p$

$q$

$r$

$G$

$G$

$(\mathrm{Z}/(N))^{*}$$x\in G|x=y^{r}\mathrm{m}\mathrm{o}\mathrm{d} N$

$g$

$G$

$p$

$g$

$q$

$p$

$h$

$q$

$\leq r$$h^{:}\not\in\{x^{r}\mathrm{m}\mathrm{o}\mathrm{d} N : x\in(\mathrm{Z}/(N))^{*}\}$$h$-Subgroup Problem
Let , be primes such that does not divide $q-1$ . Set $N=p^{2}q$ and let be arandom element inis . The primes and are trapdoor informationsuch that the order offor the PSUB problem, on the other hand, the number $N,g$ , are public information. Let $G$for
and $y\in(\mathrm{Z}/(N))^{*}$ }, and let
be agroup defined by $G=$ {$H$ be the subgroup defined by $H=$
for $y\in G$ }. The PSUB problem of $H${
in $G$ is to decide whether or not, agiven element $g\in G$ , belongs to $H$ . Thus, the PSUB is
the membership problem of $H$ in $G$ . We can efficiently determine the membership of in $H$
provided that the information and are available. No polynomial time algorithm is known
for the membership of arandomly chosen element of $G$ in $H$ without the information and .
Note that our description of PSUB is slightly diffrent ffom OkamotO-Uchiyama [8], where thePSUB is introduced as avariant of the coset indistinguishability problem which we will present
in Section 2.3. Naccache and Stern [7] implicitly used PSUB problem in their scheme. Pailier
introduces the decisional composite residuosity (DCR for short). This is ageneralization of [8]and also characterized as asubgroup membership problem.
$\mathrm{P}$

$p$

$p$

$q$

$g$

$g^{p-1}\mathrm{m}\mathrm{o}\mathrm{d} p^{2}$$(\mathbb{Z}/(N))^{*}$

$p$

$p$

$q$

$k$

$x|x=g^{m}y^{N}\mathrm{m}\mathrm{o}\mathrm{d} N$$m\in \mathrm{Z}/(p)$$x|x=y^{N}\mathrm{m}\mathrm{o}\mathrm{d} N$

$g$

$g$

$p$

$q$

$p$

$q$

For other plausible applications of the subgroup membership problem, the reader is also
referred to [10] in which the DDH assumption is applied to the cryptographic schemes which
only known method to construct is to base on the QR assumption.

1.3

Equivalent Problems

We examine several algorithmic problems equivalent to the subgroup membership problem.
outputs $(G,H)$ for
Suppose thatis an instance generator of afamily of groups, and thatthe input . We set $S=G\backslash H$ . Suppose that is an integer bounded above by apolynomial
position $(j\neq:)$ is occupied
in . Let K. be the direct product of $t-1H$ ’s and , where all$\mathrm{I}\mathcal{G}$$\mathrm{I}\mathcal{G}$$1^{k}$

$k$

$t$

$S$

$\cdot$$j\mathrm{t}\mathrm{h}$for every $:=1,2$ ,position, that is,by $H$ except for$L=K_{1}\cup
K_{2}\cup\cdots\cup
K_{t}$.
,, , that is,
Let be the union of ,$K_{}=H\mathrm{x}H\mathrm{x}\cdots\cross s^{}\mathrm{x}\cdots$$i\mathrm{t}\mathrm{h}$$L$$K_{1}$$K_{2}$$\cdots$$\mathrm{x}H$$\ldots$, .
$t$$K_{t}$

Pattern Indistinguishability Assumption
The pattern indistinguishability assumption is to assume the following holds: for every constantc, every familyof circuits of polynomial size in k and all :,j such that $1\leq:,j\leq n$$\{C_{k}|k\in \mathrm{N}\}$68
there is an integer $K$ such that for all $k>K$ we have
(1.3)$| \mathrm{p}_{:-}\mathrm{p}_{j}|<\frac{1}{k^{ae}}$

Here the probabilities$\mathrm{p}_{:}$

andare defined as follows;$\mathrm{P}_{j}$,$\mathrm{P}_{:}=\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}_{(G,H)\succ \mathrm{I}Q(1)j(g1,\ovalbox{\tt\small REJECT}\cdots ffl)}(\mathrm{r}\mathrm{g}_{K_{}}C_{k}(G,H,:, g_{1},g_{2}\ldots,g_{t})=1)$$\mathrm{P}_{j}=\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}_{(Gfl)\succ \mathrm{I}Q(1^{k})j(g1,\alpha\cdots\alpha)},(\mathrm{d}\kappa_{j}C_{k}(G,H,:, g_{1},g_{2}\ldots,g_{t})=1)$

General Pattern Indistinguishability Assumption
The general pattern indistinguishability assumption is to assume the following holds: for every, )of circuits of polynomial size in and all ( ,i2,constant , every family$K$, there is an integer such that for all $k>K$ we haveand$k$$\{C_{k}|k\in \mathrm{N}\}$$c$$:_{1}$$\ldots$$i_{u}$$(j_{1},j_{2}, \ldots,j_{u})$(1.4)$| \mathrm{P}_{(:_{1\prime^{12\prime\dot{\mathrm{w}}\mathrm{I}}}}\cdot,\ldots-\mathrm{P}_{(\mathrm{j}_{1}\mathrm{j}_{2\prime\cdots\dot{l}u})}|<\frac{1}{k^{e}}$Here the probabilities.and$\mathrm{P}_{\mathrm{t}:_{1,2,\ldots,\dot{\mathrm{h}})}}|$$\mathrm{P}_{(f_{1}\mathrm{j}_{2},\ldots \mathrm{j}_{u})}$are defined by$\mathrm{P}_{\mathrm{t}:_{1},_{2,\ldots,\dot{\mathrm{b}})}}=\mathrm{P}\mathrm{r}o\mathrm{b}(C_{k}(G,H,x_{1},x_{2} \ldots,x_{u})=1)$

where the probability is taken overand$(G,H)arrow \mathrm{I}\mathcal{G}(1^{k})$and$(x_{1},x_{2}\ldots,x_{u})\mathrm{d}$ $K_{_{1}}\mathrm{x}K_{\dot{1}2}\mathrm{x}\cdots \mathrm{x}K_{u}\dot{.}$$\mathrm{P}_{U\mathrm{j}_{2},\ldots \mathrm{j}.)}=\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}(1C_{k}(G,H,x_{1},x_{2}\ldots,x_{u})=1)$

where the probability is taken over$(G,H)arrow \mathrm{I}\mathcal{G}(1^{k})$

and

,

,

$(x_{1},x_{2}\ldots,x_{\tau\iota})L$$K_{j_{1}}\mathrm{x}K_{j_{2}}\mathrm{x}\cdots \mathrm{x}K_{j_{u}}$.

Assumption
Coset. assumption is to assume the following holds: for every constant
The coset, every familyof circuits of polynomial size in and every algorithm $F$ that on
input $(G,H)$ outputs apair of elements in , there is an integer $K$ such that for aU $k>K$ wehave$\mathrm{h}\mathrm{d}\mathrm{f}\mathrm{s}\mathrm{t}\mathrm{h}\mathrm{g}\mathrm{u}\mathrm{i}\mathrm{s}\mathrm{h}\mathrm{a}\mathrm{b}\mathrm{U}\ddagger \mathrm{t}\mathrm{y}$$\dot{|}nd\dot{u}$$t\cdot.ngu\dot{u}$ $hab\cdot.lu$$y$$k$$\{C_{k}|k \in \mathrm{N}\}$

$c$

$G$

Prob(

$C_{k}$

where the probability is taken over$g\iota H$( G,H, go, $g_{1},g)=b$)$(G,H)arrow \mathrm{I}\mathcal{G}(1^{k})$.

$< \frac{1}{2}+\frac{1}{k^{e}}$,, (go, ) $arrow F(G,H)$ , b

Theorem 1.2 The following are equivalent(1) The $\mathrm{r}p$ membership assumption .
(1) The $\mathrm{r}p$ membership assumption $II$.
(3) The pattern indistinguishability assumption.
(4) The general patternassumption.
(5) The coset indistinguishability assumption.

$g_{1}$(1.5)$\epsilon${0,1} and g A$I$$\dot{l}nd\dot{u}$$t\dot{1}ngu\dot{u}$$hab\cdot.l_{\dot{1}}ty$a69
2Private Information Retrieval
Chor, Goldreich, Kushilevitz and Sudan [2] introduced the private information retrieval scheme
for remote database access, in which the user can retrieve the data of user’s choice without
revealing it. Their scheme attains information theoretic security, however the database must
be replicated in several locations where the managers are not alowed to communicate eachother. The computational private information retrieval scheme was introduced by Chor andGilboa [3]. Their scheme attains more efficient communication than Chor, Goldreich, Kushilevitz
and Sudan’s model by sacrificing the information theoretic security, nevertheless, their scheme
enjoys computational security by assuming the existence of pseudorandom generators. However,their scheme stiu needs replication of the database. Kushilevitz and Ostrovsky [5] introduced
acomputational private information retrieval scheme in which only one database is needed.
Their scheme depends on the intractability of the quadratic residue problem. More efficiency,
polylogarithmic communication complexity, is attained by Cachin, Mical and Stadler [1]. They
assume anumber theoretic hypothesis, which they cffi the assumption, and sacrifice oneround communication and then obtain polylogarithmic communication complexity. However,assumption or its equivalence to awidely usedarigorous proof of the intractability of theassumption like the quadratic residue assumption or the integer factorization is not given in [1].
We briefly review the general scheme of aprivate information retrieval (PIR for short)scheme. Acomputational PIR scheme with asingle database is aprotocol for two players, auser and adatabase manager $VB$ . Both are able to perform only probabilstic polynomial
time computation. The database manager $DB$ maintains adatabase, which is abinary sequence
bit $x_{+1}$ of $X$. The goal of the protocol is to allow to obtain the
without leaking any information on :to $VB$ . The protocol runs as follows:$\Phi$$\Phi$$\mathcal{U}$$i\mathrm{t}\mathrm{h}$$\mathcal{U}$$X=\mathrm{X}\mathrm{O}\mathrm{X}1\mathrm{X}2\cdots x_{n-1}$$x$

Step 1computes a query Query(i) using his random tape (coin toss), which
Then he sends Query(i) to $DB$ .
$\mathcal{U}$$\mathcal{U}$keeps secret.

Step 2 $DB$ receives Query(i). He performs apolynomial-time computation for the input $X$ ,Query(i) and his random tape. The computation yields the answer Answer(Query(i)). He sends
Answer(Query(i)) back to .
$\mathcal{U}$receives Answer(Query(i)). He performs apolynomial-time computation using theanswer Answer(Query(i)) and his private information (his random tape). The computation
yields the
bit $X:+1$ of the database.
Step 3$\mathcal{U}$$i\mathrm{t}\mathrm{h}$Correctness
For any database sequence X and for any query Query(i) for ith bit of X,
end.

$\mathcal{U}$obtains X:at thePrivacy$DB$ cannot distinguish aquery for thebit for aU: and by a
bit and aquery for thepolynomial-time (probabilistic) computation with non-negligible probability. Formaly, for all
constants , for all database of length , for any two $1\leq:,j\leq n$ , and aU polynomial-size family$k>K$ we have
, there exists an integer $K$ such that forof circuits$i\mathrm{t}\mathrm{h}$

$n$

$c$

au

$C_{k}$

lProb(

where$k$$C_{k}$

Query(i $)=1$ ) -Prob($C_{k}$

is the security parameter of the protocol andComputation
Computations of both VB and$\mathcal{U}$$j$$j\mathrm{t}\mathrm{h}$(Query(j)) $=1$ )$\sigma=\frac{1}{({\rm Max}(k,n))^{e}}$$|<\sigma$

,

(2.1)

.

are bounded above by apolynomial in the size n of the database

70
and the security parmeter k.

3PIR Based on the Subgroup Membership Problem
Following [11], we show that the subgroup membership problem can be applied to aPIR schemeby modifying Kushilevitz and Ostrovsky’s scheme [5]. The proposed scheme has the samecommunication complexity as Kushilevitz and Ostrovsky’s scheme whose security depends on
the QR assumption. On the other hand, the security of the private information retrieval scheme
proposed in this paper is based on the subgroup membership assumption. Therefore, we canconstruct aprivate information retrieval scheme based on any algorithmic problems in Section
2.2, in particular, we can use groups of rational points on eliptic curves or multiplicative groupsof finite fields under the corresponding DDH assumption. We should remark that all the private
information retrieval schemes proposed so far depend on either the existence of pseudorandom
number generators or intractabilty assumption related to the integer factorization. No private
information retrieval scheme based on the DDH has been proposed, yet as far as the authors
are concerned. Modifying [5], we construct aPIR scheme based on the subgroup membershipproblem.

3.1

Basic Idea

First of all, we explain the basic idea of the scheme by asimple model. Suppose $VB$ has the,and thatwishes to know thebitchooses group
database,,,for $j\neq:-1$ and $g_{-1}\in S=G\backslash H$ .
so thatelements , , ,Then sends them aU to $DB$ . $DB$ computes the group element, $g-1$ ,,comes
and sends it badc to . $DB$ cannot get to know which of go, , ,ffom if the subgroup membership problem of $H$ in is intractable. Since possesses the
trapdoor, he can determine whether or not lies in $H$ . By Proposition 1, lies in $H$ if and only
if $x:-1=0$ . Therefore, can obtain the tth bit $x:-1$ . This simple model illustrates the idea ofusing the subgroup membership problem, but the communication complexity is still large. We
need the trick by [5] to reduce the communication complexity.
$X=\mathrm{X}\mathrm{O}\mathrm{X}1\mathrm{X}2\cdots$$g_{0}$$\mathrm{g}\mathrm{i}$$g_{2}$$\ldots$$g_{-1}$$\ldots$$x:-1\cdot \mathcal{U}$$\dot{|}\mathrm{t}\mathrm{h}$$\mathcal{U}$$x_{\iota-1}$$g_{\mathrm{j}}\in H$$g_{n-1}$$g=g_{0^{\mathrm{O}}}^{l}g_{1}^{x_{1}}g_{2^{2}}^{l}\cdots$ $g_{-1}^{x\dot{.}-1}.\cdot\cdots g_{1*-1}^{x_{n-1}}$$\mathcal{U}$$\mathcal{U}$$g_{1}$$g_{2}$$\ldots$$\ldots$$G$$S$$g_{l1-1}$$\mathcal{U}$

$g$

$g$

$\mathcal{U}$3.2

SchemeStep 0The user inputs
to the instance generator
and then gets apair $(G,H)$ ofgroups and the trapdoor for the subgroup membership problem of $H$ in $G$, where is the security
parameter and every element of $G$ is represented by abinary sequence of length . We assume
the subgroup membership assumption of $H$ in $G$ . The group $G$ is shared by both $DB$ and 2#.
On the other hand, keeps the trapdoor information for the subgroup membership problem
of $H$ secret. Computations of both $DB$ and are performed in the group $G$ . Let $X$ be the, where $x:\in\{0,1\}$ , and thatdatabase managed by $DB$ . We suppose that$n=d$ , where $t,l$ are positive integers.
$\mathcal{U}$$1^{k}$$\mathrm{I}\mathcal{G}$

$k$

$k$

$\mathcal{U}$$\mathcal{U}$$X=\mathrm{X}\mathrm{O}\mathrm{X}1\mathrm{X}2\cdots$$x_{\mathfrak{n}-1}$

Step 1 &computes query Query(t) for his desired bit x:-l, where $1\leq:\leq n$ , in the following. Then the t-ax3Xc expansion ofmanner. First, computes the t-Mc expansion of:. Let :$\mathcal{U}$$=\alpha_{0}$

71
i is

$\beta\iota\beta_{l-1}\ldots$$\hslash\beta_{1}$, where$\alpha 0=\alpha_{1}t+\$$0\leq\alpha \mathrm{p}\leq t^{l-1}-1$$\alpha_{1}=\alpha_{2}t+\alpha$$0\leq\alpha_{1}\leq t^{l-2}-1$$\alpha_{2}=\alpha_{3}t+\$$0\leq\alpha_{2}\leq t^{l-3}-1$$\alpha_{l-2}=\alpha_{l-1}t+\beta\iota-1$$0\leq\alpha\iota-2\leq t$, and $0\leq\beta_{1}\leq t-1$$\leq t-1$
, and
, and $0\leq h$ $\leq t-1$
$0\leq\hslash$-1, and$0\leq\alpha_{l-1}=\beta\iota\leq t-1$

(3.1)

$0\leq\beta_{l-1}\leq t-1$

and$\alpha_{l}=0$.

For each $u(1\leq u\leq l)$ ,chooses uniformly and randomly $t-1$ elements,,, $g(u,t-1)$ ffom $H$ . He also chooses uniformly and randomly$S=G\backslash H$ .
definesby$\mathcal{U}$$g_{(u,0)}$$g(u\beta_{\mathrm{u}}-1)’ g(u,\beta_{u}+1)$$\ldots$$\mathcal{U}$$g_{(u,1)}$$g_{(u,\beta_{u})}$

,

,
ffom
$\ldots$$\mathrm{Q}(\mathrm{t}\mathrm{i})$( $g_{(u,0)},g_{(u,1)},$ $\ldots,g_{(uflu^{-1)’ g(u,\beta_{u})’ g_{(ufl+1)},\ldots,g_{(u,t-1)})}}u$ ’(12)that is, $Q(u)$ is asequence of group elements of such that thecomponent is uniformly
and randomly chosen from $S=G\backslash H$ and the others are uniformly and randomly chosen ffom
$H$ . Then, $Q(1)$ , $Q(2)$ ,, $Q(l)$ comprise aquery (denoted by Query(i)) for the
bit $X:-1$ of$X$ , andsends Query(i) to $VB$ . Since each $Q(u)$ consists of group elements from $G$ , $Q(u)$ isrepresented bybits. Thus, Query(i) consists ofbits.
Step 2Receiving Query(i), DB constructs child databases recursively from the original
database X. We regard X as thext binary matrix$G$$\beta_{u}\mathrm{t}\mathrm{h}$$i\mathrm{t}\mathrm{h}$$\ldots$$\mathcal{U}$$t$$k\mathrm{x}t$$k\mathrm{x}t\mathrm{x}l$$t^{l-1}$$D(0,\lambda)=(\begin{array}{llll}x_{0} x_{1} x_{2} x_{t-1}x_{t} x_{t+1} x_{t+2} x_{2t-1}x_{t^{I}-t} x_{d-t+1} x_{t^{l}-1}\end{array})$,

where Adenotes the empty sequence in $\{0, 1, 2, \ldots, k-1\}^{*}$ . We note that the target bit $x:-1$ istheentry of( andare obtained in (3.1)). Denote it by Target(D(0, ).
We recursively define child databases $D(u, s)$ , where $1\leq u\leq l$ and $s\in\{0,1,2, \ldots,k-1\}^{u}$ .
Suppose that we have defined the databases $D(u, s)$ and their target bits Target(D(u, )) and$s\in\{0,1,2, \ldots, k-1\}^{u}$ for $0\leq u<l-1$ . Then we define the databases $D$ ( $u+1$ , sO), $D(u+1, s1)$,
. . . ’ $D(u+1, s(k-1))$ .
The database $D(u, s)$ is abinary sequence of length. We regard $D(u, s)$ as abinary matrix. Suppose that
$D(0, \lambda)$$(\alpha_{1},\beta_{1})$$\alpha_{1}$$\beta_{1}$$\lambda)$$s$$d^{-u}$$d^{-u-1}\mathrm{x}t$$D(u, s)=(\begin{array}{llll}y_{0} y_{1} w y_{t-1}y_{t} \Re+1 \Re+2 \Omega t-1y_{t^{l-u}-t} y_{t^{\mathrm{t}-\mathrm{u}}-t+1} y_{t^{l-u}-1}\end{array})$

We now constructchild databases, $D$ ( $u+1$ , sO), $D(u+1,50)$ ,,$D(u+1, s(k-1))$ .
Recall that $Q(u)$ consists of group elements $g(u,0)’ g(u,1)$ ’, $g_{(u.t-1)}$ in $G$ (defined in (3.2)).
$k$$\ldots$$t$$\cdots$

We define agroup element$g_{v}$

for each row $v=0,1,2$ ,$f_{(v,w)}=\{$$\ldots$, $d^{-u-1}-1$ as follows. We set

if $D(u,s)(v,w)=1$
1if $D(u,s)$ ( ,to) $=0$ ,$g_{(u,w)}$

$v$

(3.1)

72
where $D(u,s)(v,w)$ denotes the (v,.w) entry of $D(u,$ s). Then we set(3.4)$f_{D(u,s),v}= \prod_{\prime}f_{(v,w)}w=0,1,2,\ldots t-1$

, $d^{-u-1}-1$ . We note that the group element $f_{D(u,s),v}(0\leq v\leq$for each row $v=0,1,2$ ,$d^{-u-1}-1)$ is of size , and that $f_{D(u,s),v}\in H$ if and only if $D(u,s)(v,\beta_{u})=0$ by Proposition
1.1. The rth child database $D(u+1, sr)(0\leq r \leq k-1)$ is defined to be the sequence consisting
bit of the representation of $f_{D(u,s),v}$ .
,, $gd^{-u-1}-1(r)$ , where
denotes theofHence, we have the following matrix equation:$\ldots$$k$$\mathrm{g}\mathrm{v}(\mathrm{r})g_{1}(r)$$g_{v}(r)$$\ldots$$(\begin{array}{l}f_{D(\mathrm{u}_{\prime}\iota)_{\prime}0}f_{D(\mathrm{u}_{\prime}\ell)_{\prime}1}f_{D(u,\epsilon),t^{l-u-1}-1}\cdots\end{array})=$$r\mathrm{t}\mathrm{h}$$D(u+1, s(k-1)))$$(D(u+1,\mathrm{s})$(3.4)

where eachis arow vector and each $D(u+1, sr)$ is acolumn vector. Thus, $D(u+1, sr)$
is abinary sequence of length $d^{-u-1}$ . We regard it as a $d^{-u-2}\cross t$ binary matrix. Then the, $sr$))) is defined to be theentry oftarget bit for it (denoted by Target(D(u$D(u+1,sr)$ for every $\in\{0,1, \ldots, k-1\}$ (and
are obtained in (3.1)).
$f_{D(\tau_{4^{\ell),v}}}$

$+$

$r$

$(\alpha_{u+1},\beta_{u+1})$$1$$\alpha_{u+1}$$\beta_{u+1}$

databases $D(l-1, s)$
Step 3In the last stage of constructing child databases, $VB$ obtains$(s\in\{1,2, \ldots,k\}^{t-1})$ . Note that each $D(l-1, s)$ contains
bits. We regard $D(l-1, s)$ as a1
matrix. For each $D(l-1, s)$ , we define agroup element $A(s)$ as follows. First, we define$k^{t-1}$$t$$f_{(0,w)}=\{$$\mathrm{x}t$

if $D(l-1,\epsilon)(0,w)=1$
1if $D(l-1,s)(0,w)=0$ .

$g_{(u,w)}$,$\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{y}\mathrm{T}\mathrm{h}\mathrm{e}\mathrm{n},$$s \in\{0, 1,2\mathrm{v}\prime \mathrm{e}\mathrm{s}\mathrm{e}\mathrm{t}f_{D(l-1,\iota),0},\ldots,=\prod_{w=01,2..t-1}f_{(0,w)}=A(s).\mathrm{T}\mathrm{h}\mathrm{e}\mathrm{g}\mathrm{r}\mathrm{o}\mathrm{u}\mathrm{p}\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{m}\mathrm{e}\mathrm{n}\mathrm{t}A(s)\mathrm{i}\mathrm{s}\mathrm{o}\mathrm{f}\mathrm{s}\mathrm{i}\mathrm{z}\mathrm{e}k\mathrm{f}\mathrm{o}\mathrm{r}k-1\}^{t-\acute{1}}.\acute{\mathrm{T}}\mathrm{h}\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{g}\mathrm{r}\mathrm{o}\mathrm{u}\mathrm{p}\mathrm{e}1\mathrm{e}\mathrm{m}\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{s}A(s)(s\in\{0\mathrm{l},\ldots,k-1\}^{t-1})\mathrm{f}\mathrm{o}\mathrm{m}$the answer Answer(Query(i)) to the query Query(t), and $VB$ sends Answer(Query(i)) to .
Step 4
receives Answer(Query(i)) consisting of $A(s)$ , where $s\in\{0,1, \ldots,k-1\}^{t-1}$ .
in polynomial time in $k,n$ . In fact, the following
can retrieve the target bit
holds in general.
$\mathcal{U}$$\mathcal{U}$$\mathcal{U}$$x:=\mathrm{T}\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{e}\mathrm{t}(D(0,\lambda))$canTheorem 3.1 For every database $D(u,l)$ ’where $0\leq u\leq l-2$ and $\in\{1,2, \ldots,k\}^{u}$ ,,computein $\mu lynom.d$ time in $n,k|.f$ Thrget(D(u+l,\mbox{\boldmath $\omega$})), Target(D(u+l,sl)),$\mathcal{U}$$s$$\mathrm{I}\mathrm{b}\mathrm{g}\mathrm{e}\mathrm{t}(D_{(u,\ell)})$$\mathrm{I}\mathrm{h}\mathrm{r}\mathrm{g}\mathrm{e}\mathrm{t}(D_{(u+1,.(k-1))})$$\ldots$

are given.

$\square$

3.3 Privacy
In the proposed scheme, the query Query(i) consists of $Q(1)$ , $Q(2)$ ,consists of$\ldots$, $Q(l)$ , and each $Q(u)$$(g_{(u,0)}, g_{(u,1)}, \ldots, g_{(ufl\mathrm{u}^{-1)}}, g_{(u\phi_{u})}, g_{(u\beta_{*}+1)}, \ldots, g_{(u,t-1)})$,

where one of the components is chosen uniformly and randomly from $S=G\backslash H$ and the others
are chosen uniformly and randomly ffom $H$ . The privacy is assured by the inequality,(Query(i $)=1$ ) -Prob( (Query(j)) $=1$ )$|\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}(C_{k}$$C_{k}$$|<\sigma$

73
3.4

Communication Complexity, $Q(l))$ . Each $Q(u)$ consists of groupsends Query(i) $=(Q(1),Q(2)$ ,In the first step,elements in $G$ . Since every element in $G$ is represented by abinary sequence of length , the total
bits sent in this stage is xtxk. In the second step, $DB$ sends Answer(Query(i)) consisting of. Consequently,
group elements in $G$ . Therefore, the total bits sent in this stage is$ltk+k^{l}=ln^{1}\tau k+k^{l}$$l=O(*_{g}^{n})$ .
andthat
Suppose.
the communication complexity is$t$$\mathcal{U}$$\ldots$$k$$k^{l-1}$$l$$k^{l-1}\mathrm{x}k=k^{l}$$k=n^{\epsilon}$

Then we have$\mathit{1}=\sqrt{\frac{1\mathrm{o}\mathrm{g}n}{1\mathrm{o}\mathrm{g}k}}$, and$k^{l}=(2^{\log k})^{l}=2^{l\log k}=2^{\sqrt{\mathrm{o}\mathrm{g}n\log k}}=2^{\sqrt{\mathrm{o}\mathrm{g}n\epsilon\log n}}=n^{\sqrt{e}}$. On the. Itother hand, we have $ltk+k^{l}=k^{l}(lk +1)<k^{l}k^{l}=(k^{l})^{2}$ . Hence, we have $ltk+k^{l}=(n^{\sqrt{e}})^{2}$.
follows that the communication complexity is$O(n^{\mathrm{c}})$References[1] Cachin, C, Micali,S., Stadler,M.:Computationally Private Information Retrieval with Polylogarithmic Communication, Advances in Cryptology. Lecture Notes in Computer Science,Vol. 1592. Springer-Verlag, (1999) 402-414[2] Chor,B., Goldreich,O., Kushilevitz,E., Sudan,M.:Private Information Retrieval, IEEE
Symposium on Foundations of Computer Science. (1995) 41-50[3] Chor,B., Gilboa,N.: Computationally Private Information Retrieval ACM Symposium on
Theory of Computing. (1997) 304-313[4] Goldwasser,S., Micali,S.:Probabilstic Encryption, J. Computer and System Science 28(1984) 270-299

Single Database,Replication Is not Needed:[5] Kushilevitz,E., Ostrovsky,R.:
Foundations ofon
Symposium
Retrieval,
IEEE
Information
Computationally-private
Computer Science. (1997) 364-373[6] Kurosawa,K, Tsuj\"u,S.: AGeneral Method to Construct Public Key Residue Cryptosystems,
Transactions of the IEICE B73, (1990) 1068-1072[7] Naccache,D., Stem,J.:ANew Public-key Cryptosystem, Advances in Cryptology. Lecture
Notes in Computer Science, Vol. 1233. Springer-Verlag, (1997) 27-36[8] Okamoto,T., Uchiyama,S.:ANew Public-key Cryptosystem as Secure as Factoring, Advances in Cryptology. Lecture Notes in Computer Science, Vol. 1403. Springer-Verlag, (1998)

308-318[9] Pa.4h.er,P.:Public-key Cryptosystems Based on Composite Degree Residuosity Classes,
Advances in Cryptology. Lecture Notes in Computer Science, Vol. 1592. Springer-Verlag,(1999) $22\succ 238$

[10] Saito,T., Koshiba,T., Yammura,A.:The Decision Diffie Hellman assumption and the
Quadratic Residuosity Assumption, IEICE Transactions on Fundmentak of Electronics(1) E84-A, (2001) 165-171[11] Yamamura,A., Saito,T.:Private Information Retrieval Based on the Subgroup Membership
Problem, Information Security and Privacy, Lecture Notes in Computer Science, Sprin.gerVerlag, (2001) (to appear