Databases Reference
In-Depth Information
•
k
p
: Denotes the private-key of the user.
k
p
∈{
0
,
1
}
s
which is kept a secret
by the user.
s
and is
•
k
c
: Denotes a key called the
collection key
of the user.
k
c
∈{
0
,
1
}
publicly known
s
n
−
m
m
,isa
•
Pseudo-Random Function:
F
:
{
0
,
1
}
×{
0
,
1
}
→{
0
,
1
}
pseudo-random function that takes a
n
m
bit string, a
s
-bit key and
maps it to a random
m
-bit string.
F
is publicly known.
−
•
Trapdoor function
:Let
T
denote a
trapdoor
function which takes as
input, a private-key
k
p
and a word
w
and outputs the trapdoor for the
word
w
, i.e.,
T
(
k
p
,w
)=
E
k
p
(
w
) where
E
is a deterministic encryption
function. For a given document, we denote the trapdoor for the
i
th
word
by
t
i
.
•
BuildIndex
(
D
,
k
p
,
k
c
): This function is used to build the index for doc-
ument
D
. It uses a pseudo-random generator
G
which outputs random
string of size
s
. The pseudo-code of the function is given below.
Algorithm 1
:
BuildIndex
1: Input:
D, k
p
,k
c
;
2: Output:
I
D
/* The index for the document*/
3:
4:
I
D
=
φ
;
5:
for
all
w
i
∈ D
do
6: Generate a pseudo-random string
s
i
using
G
;
7: Compute trapdoor
T
(
w
i
)=
E
k
p
(
w
i
);
8: Compute ciphertext
c
i
=
T
(
w
i
)
⊕s
i
,F
k
c
(
s
i
)
;
9:
I
D
=
I
D
∪ c
i
;
10:
end for
11: Return
I
D
;
•
SearchIndex
(
I
D
,
T
(
w
)): Given the document index and the trapdoor
for the word
w
being searched, the
SearchIndex
functionality returns the
document
D
if the word
w
is present in it. The pseudo-code is given below.
Algorithm 2
:
SearchIndex
1: Input:
I
D
,T
(
w
);
2: Output:
D
or
φ
3:
4:
for
all
c
i
∈ I
D
do
5:
if
c
i
⊕ T
(
w
) is of the form
s, F
k
c
(
s
)
then
6: Return
D
;
7:
end if
8:
end for
9: Return
φ
;
