Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
428601 | Information Processing Letters | 2011 | 4 Pages |
Order-preserving encryption (OPE) is a deterministic encryption scheme whose encryption function preserves numerical ordering of the plaintexts. The first provably-secure OPE scheme was constructed by Boldyreva, Chenette, Lee, and OʼNeill. The BCLO scheme is based on a sampling algorithm for the hypergeometric distribution and is known to call the sampling algorithm at most 5logM+12 times on average where M is the size of the plaintext-space. We show that the BCLO scheme actually calls the sampling algorithm less than logM+3 times on average.
► The first provably-secure order-preserving encryption scheme is the BCLO scheme. ► The upper bound for the computational cost of the BCLO scheme is 5logM+12. ► We present a new upper bound of logM+3.