Secure Compressed Suffix Arrays

Let $T$ be a string of length $n$ on alphabet $𝒜$ of size $\sigma$. The $j$-th character of $T$ is denoted by $T[j]$ ($j=0,1,\mathrm{\dots },n-1$) and it belongs to $𝒜$. We assume that a unique terminator $, which is smaller than any character in $𝒜$, is appended to $T$. That is, $T[n]=\$$. A substring $T[i]T[i+1]\mathrm{\cdots }T[j]$ of $T$ is denoted by $T[i,j]$. The substring $T[j,n]$ is called the $j$-th suffix of $T$ and denoted by $T_j$.

The suffix array [8] of the string $T$ is an integer array $\mathrm{SA}[0,n]$ defined as $\mathrm{SA}[i]=j$ ($i=0,1,\mathrm{\dots },n$) if $T_j$ is the lexicographically the $i$-th suffix of $T$. It always holds that $\mathrm{SA}[0]=n$, which corresponds to the shortest suffix consisting of only the terminator.

If we have $T$ and $\mathrm{SA}$, we can support the following queries:

• $\mathrm{■}$

  $\mathrm{Count}(P,T)$: returns the number of occurrences of $P$ in $T$ in $\mathrm{O}(|P|\log n)$ time

• $\mathrm{■}$

  $\mathrm{Locate}(P,T)$: returns the positions of occurrences of $P$ in $T$ in $\mathrm{O}(|P|\log n+\mathrm{𝑜𝑐𝑐})$ time where $\mathrm{𝑜𝑐𝑐}=\mathrm{Count}(P,T)$

To support these queries, we use the following query:

• $\mathrm{■}$

  $\mathrm{Range}(P,T)$: returns the maximal range $[s,e]\subset [0,n]$ so that for any $i\in [s,e]$ the substring $T[SA[i],SA[i]+|P|-1]$ is equal to $P$.

Let $[s,e]=\mathrm{Range}(P,T)$. Then it holds $\mathrm{Count}(P,T)=e-s+1$ and $\mathrm{Locate}(P,T)=\{\mathrm{SA}[s],\mathrm{SA}[s+1],\mathrm{\dots },\mathrm{SA}[e]\}$.

The size of the suffix array $\mathrm{SA}$ is $n\log n$ bits. We also need to store the string $T$ itself, which occupies $n\log \sigma$ bits. The suffix array requires a huge space compared with the string itself, especially for strings on small alphabets, such as DNA strings. For human DNA, $\sigma =4$, whereas $n>2^{31}$. Then $\log n$ is more than $15$ times larger than $\log \sigma$.

Succinct data structures are data structures storing objects in minimum number of bits. More precisely, consider storing an element $x$ of a set $S$. Then the information-theoretic lower bound of the number of bits to represent $x$ is defined as $\lceil {\log }_{2}x\rceil$. Hereafter we omit the base $2$ of logarithm. Let $Z$ denote this value. Then a data structure for storing $x$ is called succinct if it uses $Z+\mathrm{o}(Z)$ bits, and compact if it uses $\mathrm{O}(Z)$ bits.

The most fundamental succinct data structure is a bit-vector supporting rank and select queries. A bit-vector is a string $B[1,n]$ on the binary alphabet $\{0,1\}$ and rank and select are defined as follows.

• $\mathrm{■}$

  ${\mathrm{rank}}_c(B,i)$ returns the number of $c$’s in $B[0,i]$. We define ${\mathrm{rank}}_c(B,0)=0$ and ${\mathrm{rank}}_c(B,i)={\mathrm{rank}}_c(B,n)$ if $i>n$.

• $\mathrm{■}$

  ${\mathrm{select}}_c(B,j)$ returns the position of the $j$-th $c$ in $B$. We define ${\mathrm{select}}_c(B,0)=0$ and ${\mathrm{select}}_c(B,j)=n+1$ if $j>{\mathrm{rank}}_c(B,n)$.

For a bit-vector of length $n$, rankand selectare computed in constant time using the bit-vector itself and an $\mathrm{O}(n\log \log n/\log n)$ bit auxiliary data structure [11].

We briefly review the rank data structure. The bit-vector $B$ is partitioned into super-blocks of length $L_1$ each, and each super-block is further partitioned into blocks of length $L_2$ each. We store rank values for all super-block boundaries in array $R_1$ using $\mathrm{O}((n\log n)/L_1)$ bits, and rank values for all block boundaries in array $R_2$ using $\mathrm{O}((n\log L_1)/L_2)$ bits. Inside a block, we count the number of $c$’s using table lookups for every $1/2\log n$ bits. The size of the table is $\mathrm{O}(\sqrt{n}\log n\log \log n)=\mathrm{o}(n)$ and the time complexity is $\mathrm{O}(L_2/\log n)$. If we set $L_1=\mathrm{\Theta }({\log }^{2}n)$ and $L_2=\frac{1}{2}\log n$, we obtain the desired bound.

If we forget about time efficiency, any computation can be done on encrypted data if we can support additions and multiplications on two encrypted integers. There exist two such schemes.

• $\mathrm{■}$

  Secret Sharing [13]. Data are distributed into two or more servers and for each server the stored data look like random values and no information is leaked. Additions can be done locally in each server, whereas for multiplications the servers must comminicate each other.

• $\mathrm{■}$

  Fully Homomorphic Encryption (FHE) [3, 1]. Any number of additions and multiplications on encrypted numbers can be done.

Both schemes have a drawback that the computation is much slower than plain (unencrypted) data. In Secret Sharing schemes the servers communicate each other for computing multiplications. This takes much more time than the computation on plain data in a single server. In FHE schemes, there are no communication because there is only one server. However multiplications are extremely slow. Therefore it is important to develop efficient secure algorithms.

In this paper, we assume that in both schemes, integer addition, multiplication, division, less-than comparison are done efficiently in unit time. Then our algorithm runs in both schemes.

Oblivious RAMs [7, 15, 10], or ORAMs for short, are data structures supporting oblivious read and write to an array. Without loss of generality we can assume the array stores a binary string $S$ of length $n$. $S$ can be regarded as an array of length $n/w$ storing $w$-bit integers. An ORAM has a parameter $b$ called the block size. $S$ is partitioned into blocks of length $b$ each, and a block is accessed as a unit. To achieve oblivious access, more than one blocks are accessed to obtain one block. The ratio is called bandwidth blowup.

Obliviousness is defined as follows. Let $\overrightarrow{y}=(({\mathrm{op}}_1,a_1,d_1),({\mathrm{op}}_1,a_1,d_1),\mathrm{\dots },({\mathrm{op}}_M,a_M,d_M))$ be a sequence of accesses to an ORAM where ${\mathrm{op}}_i$ is either read or write, $a_i$ is the address of the $i$-th access, and $d_i$ is the content to be written in the $a_i$-th block when ${\mathrm{op}}_i$ is write. Let $A(\overrightarrow{y})$ be denote the sequence of accesses to the server given $\overrightarrow{y}$. Then the ORAM is said to be oblivious if two any access sequences $\overrightarrow{y}$ and $\overrightarrow{z}$ of the same length, $A(\overrightarrow{y})$ and $A(\overrightarrow{z})$ are computationally indistinguishable by anyone but the client, and if the failure probability is negligible [15].

Table 1 shows existing oblivious RAM data structures. Onodera and Shibuya [10] give a succinct oblivious RAM, that is, the server space is $n+\mathrm{o}(n)$ bits. The other two data structures are compact, that is, the server space is $\mathrm{O}(n)$ bits.

Grossi and Vitter [5, 4] have proposed compressed suffix arrays, which are a compressed version of suffix arrays. Let $\mathrm{SA}$ be the suffix array of string $T$ of length $n$ on alphabet $𝒜$ of size $\sigma$. The compressed suffix array is a data structure which efficiently supports the following operation:

• $\mathrm{■}$

  $\mathrm{Lookup}(i)$: returns $\mathrm{SA}[i]$.

• $\mathrm{■}$

  $\mathrm{Inverse}(j)$: returns $i$ such that $j=\mathrm{SA}[i]$ (the inverse suffix array).

The core component of the compressed suffix arrays is the $\mathrm{\Psi }$ function, defined as follows.

if $i>0$, and $\mathrm{\Psi }[0]={\mathrm{SA}}^{-1}[1]$. The $\mathrm{\Psi }$ function has a good property that it is piecewise monotone. Precisely, let $[s_c,e_c]$ be the range of the suffix array such that $T[SA[i]]=c$ for any $i\in [s_c,e_c]$ where $c\in 𝒜$. Then if $i,j\in [s_c,e_c]$ and , it holds . Then the following function is strictly increasing.

We can compress ${\mathrm{\Psi }}^{\prime }$ in $n(2+\log \sigma )+\mathrm{o}(n)$ bits so that any ${\mathrm{\Psi }}^{\prime }[i]$ is computed in constant time. From ${\mathrm{\Psi }}^{\prime }[i]$, we can obtain $T[\mathrm{SA}[i]]$ and $\mathrm{\Psi }[i]$ easily in constant time.

The encoding of ${\mathrm{\Psi }}^{\prime }$ is as follows. each entry of ${\mathrm{\Psi }}^{\prime }$ is a $(\log \sigma +\log n)$-bit integer. We partition it into higher part and lower part. The higher part has $\log n$ bits and the lower part has the rest ($\log \sigma$ bits). The lower parts for all entries are stored in an integer array $L[0,n]$ in $n\log \sigma$ bits. The upper parts for all entries are represented by a bit-vector $H[0,2n]$ as follows. Let $d_i=({\mathrm{\Psi }}^{\prime }[i]÷\sigma )-({\mathrm{\Psi }}^{\prime }[i-1]÷\sigma )$ for $i=0,1,\mathrm{\dots },n$ (we assume ${\mathrm{\Psi }}^{\prime }[-1]=0$). Because ${\mathrm{\Psi }}^{\prime }$ is increasing, $d_i\ge 0$ for any $i$. We encode $d_i$’s by unary codes. That is, we write $d_i$ many zeros followed by a one, to $H$. Then, $H[i]$ can be computed in constant time as

From the definition of $\mathrm{\Psi }$, if $\mathrm{SA}[i]=j$, it holds $\mathrm{SA}[\mathrm{\Psi }[i]]=j+1$. That is, if we know the lexicographic order $i$ of a suffix $T_j$, we can obtain that of the next suffix $T_{j+1}$ by computing $\mathrm{\Psi }[i]$. We sample the values of the suffix array for every $L_3$ entries and stores them in an array $A$. We also store a bit-vector $F[0,n]$ such that $F[i]=1$ iff $SA[i]$ is sampled. Then $\mathrm{Lookup}(i)$ is computed as follows.

The array $A$ uses $\mathrm{O}((n\log n)/L_3)$ bits and $F$ uses $n+\mathrm{o}(n)$ bits. If we set $L_3=\mathrm{\Theta }(\log n)$, the space for $A$ is $\mathrm{O}(n)$ bits and $\mathrm{Lookup}(i)$ is computed in $\mathrm{O}(\log n)$ time. See Figure 1 for an example of

The original compressed suffix array is a compressed representation of the suffix array and used together with the string itself. We can change it to a self-index, that is, a data structure for string matching which does not use the string. It is enough to add $n+\mathrm{o}(n)+\mathrm{O}(\sigma \log n)$ bits. We use a bit-vector $D[0,n]$ showing that if $D[i]=1$ then $i=0$ or $T[SA[i]]\ne T[SA[i-1]]$. That is, $D[i]=1$ iff lexicographically the $i$-th suffix has a different head character from the $(i-1)$-st suffix. We use an array $C$ of length $\sigma$ such that $C[{\mathrm{rank}}_1(D,i)]=T[SA[i]]$. We define $\mathrm{Head}(i)=C[{\mathrm{rank}}_1(D,i)]$. The array uses $\sigma \log \sigma =\mathrm{O}(\sigma \log n)$ bits (we assume $\sigma \le n$). We use another array $C^{-1}[1,\sigma ]$ storing in $C[c]$ the range $[s_c,e_c]\subset [0,n]$ such that for any $i\in [s_c,e_c]$ it holds $T[SA[i]]=c$. This array uses $\mathrm{O}(\sigma \log n)$ bits.

Using $C$, we can recover a substring of $T$. Assume the lexicographic order $i$ of a suffix $T_j$ is known ($\mathrm{SA}[i]=j$). Then the character $T[j+k]$ is equal to $\mathrm{Head}({\mathrm{\Psi }}^k[i])$. The substring $T[j,j+\mathrm{\ell }-1]$ is computed in $\mathrm{O}(\mathrm{\ell })$ time by iteratively computing $i:=\mathrm{\Psi }[i]$. Computing the lexicographic order $i$ of $T_j$ is equivalent to computing $\mathrm{Inverse}(j)$, and it is done similarly to computing an entry of the suffix array using $\mathrm{\Psi }$ and the sampled suffix array [12].

To support $\mathrm{Range}(P,T)$, we use what we call backward search. Let $m$ be the length of $P$. First we obtain the range for the shortest suffix $P[m,m]$ by $[s,e]:=C^{-1}[P[m]]$. Then, given the range $[s,e]$ for a suffix $P[j+1,m]$, we compute the range $[s^{\prime },e^{\prime }]$ for the suffix $P[j,m]$. This is done as follows.

By a simple binary search, the new range is obtained in $\mathrm{O}(\log n)$ time, and therefore $\mathrm{Range}(P,T)$ is done in $\mathrm{O}(|P|\log n)$ time, which is the same as the suffix array [12].

We can simplify the algorithm as follows.

Now we do not need the array $C^{-1}$. This has another merit that it is easier to make it oblivious, which will be shown in the next section.

As shown in Section 3.2, $\mathrm{Range}(P,T)$ is done by $|P|$ many binary searches on ${\mathrm{\Psi }}^{\prime }$. Given the range $[s,e]$ for $P[j+1,m]$, we compute the range $[s^{\prime },e^{\prime }]$ for $P[j,m]$. To do so, we first compute $P[j]\cdot (n+1)+s$ and $P[j]\cdot (n+1)+e$, which can be done obliviously. Then using a binary search on ${\mathrm{\Psi }}^{\prime }$ we compute $s^{\prime }$. The initial range is $[0,n]$, and in each step we update the range based on the result of a less-than comparison. Using ${\mathrm{\Psi }}^{\prime }$ is easier than using $\mathrm{\Psi }$ because we do not need the array $C^{-1}$ that must support oblivious accesses. We can compute $\mathrm{Range}(P,T)$ using $\mathrm{O}(|P|\log n)$ many oblivious accesses to ${\mathrm{\Psi }}^{\prime }$.

$\mathrm{Lookup}(i)$ can be done using the sampled array $A$, the bit-vector $F$, and $\mathrm{\Psi }$. The original algorithm repeats computing $i:=\mathrm{\Psi }[i]$ until $F[i]=1$. This is not oblivious because the number $k$ of iteration depends on $i$. Precisely, it holds $\mathrm{Lookup}(i)=A[{\mathrm{rank}}_1(F,{\mathrm{\Psi }}^k[i])]-k$ where $k\ge 0$ is the smallest number such that $F[{\mathrm{\Psi }}^k[i]]=1$.

To change the algorithm oblivious, we fix the number of iterations to $L_3$. Because the suffix array entries are sampled every $L_3$ entries in text order, for exactly one entry it holds $F[{\mathrm{\Psi }}^k[i]]=1$ among those for $k=0,1,\mathrm{\dots },L_3-1$. Therefore we change the algorithm as follows.

1. 1.

   $x:=0$

2. 2.

   for $k=0,1,\mathrm{\dots },L_3-1$

3. 3.

   $x:=x+F[i]\cdot (A[{\mathrm{rank}}_1(F,i)]-k)$

4. 4.

   $i:=\mathrm{\Psi }[i]$

5. 5.

   return $x$

Here we need oblivious accesses to $F$ and $A$, and oblivious computation of ${\mathrm{rank}}_1(F,i)$.

For $A$, we use the Path ORAM [15] with block size $b={\log }^{2}n$. Then the space usage is $\mathrm{O}(n)$ bits and an entry of $A$ is obtained in $\mathrm{O}({\log }^{2}n)$ many accesses to blocks, which can be done in $\mathrm{O}({\log }^{3}n)$ time.

For $F$, we use the succinct ORAM [10] with block size $b={\log }^{2}n$. Then a block of $F$ is obtained in in $\mathrm{O}({\log }^{2}n)$ many accesses to blocks, which can be also done in $\mathrm{O}({\log }^{3}n)$ time. For computing a rank on $F$, we use the array $R_1$ defined in Section 2.2. This is stored using the Path ORAM. The space usage is $\mathrm{O}(n/\log n)$ bits. The rank inside a block is computed by logical operations in $\mathrm{O}(\log n)$ time. Therefore a rank value is computed in $\mathrm{O}({\log }^{3}n)$ time.

The computation of $\mathrm{Inverse}(j)$ is similar.

Finally, we show how to compute $\mathrm{\Psi }[i]$. As shown in Section 3.1, ${\mathrm{\Psi }}^{\prime }$ is represented by a bit-vector $H[0,2n]$ and an array $L[0,n]$ of $\log \sigma$-bit integers. The array $L$ is stored using the succinct ORAMs. The bit-vector $H$ is stored similarly to $F$, but here we also need to store the auxiliary data structure for ${\mathrm{select}}_1$. This can be stored using the Path ORAM.

To sum up, $\mathrm{\Psi }[i]$ is computed in $\mathrm{O}({\log }^{3}n)$ time and the space usage is $n(2+\log \sigma )+\mathrm{o}(n)\log \sigma$ bits.

$\mathrm{\Psi }[i]$ takes $\mathrm{O}({\log }^{3}n)$ time. A step of a backward search is a binary search on ${\mathrm{\Psi }}^{\prime }$, and therefore it is done in $\mathrm{O}({\log }^{4}n)$ time. Then $\mathrm{Range}(P,T)$ takes $\mathrm{O}(|P|{\log }^{4}n)$ time. For $\mathrm{Lookup}(i)$, we set $L_3=\mathrm{O}(\log n)$. Then it takes $\mathrm{O}({\log }^{4}n)$ time. The space usage is $(n+\mathrm{o}(n))\log \sigma +\mathrm{O}(n)$ bits in total.