Practical techniques for searchable encryption proposed by Song et al. [1] have a false positive rate of $l/2^m$ where $l$ is left half of encrypted bits and $m$ is right half and $l+m=n$ where $n$ is number of bits of the word being encrypted. For getting clarity on these bits please refer the figure 3 in page 6. (paper). enter image description here Especially when the input domain of words being encrypted is not so random say serial numbers, sequence ids etc. the false positives are simply high.

Is there any subsequent work done or techniques available for reducing the false positive rate ?

[1] – Song, Dawn Xiaoding, David Wagner, and Adrian Perrig. "Practical techniques for searches on encrypted data." Security and Privacy, 2000. S&P 2000. Proceedings. 2000 IEEE Symposium on. IEEE, 2000.

  • $\begingroup$ David Wagner is a member of this community... Hopefully he'll see this and give you an authoritative answer :) $\endgroup$
    – pg1989
    Sep 19, 2014 at 18:46
  • $\begingroup$ what is his id ? $\endgroup$
    – sashank
    Sep 23, 2014 at 13:55
  • $\begingroup$ D.W. is (i think) his handle here. $\endgroup$
    – pg1989
    Sep 23, 2014 at 21:55
  • $\begingroup$ @pg1989 Are you sure D.W. is who you think he is? I’m asking, because I am honestly having my doubts about that… David doesn’t tend to have D.W.’s (rather European) writing style, and the difference in wording doesn’t build a bridge either. $\endgroup$
    – Trina
    Sep 24, 2014 at 12:48
  • $\begingroup$ Actually I'm not sure, come to think of it. $\endgroup$
    – pg1989
    Sep 24, 2014 at 18:10

1 Answer 1


Additional Storage approach

A trivial way is with additional storage. by making the $l$ to be complete string instead of few $left$ bits shown in the figure above. so technically $|l|=|n|$ and $|m| = 0$.

This way the entire string is covered for search. Now rest of the scheme is same except that the stream cipher bits $S_i$ in the figure above are $\oplus$'ed with entire $l_i$ and store the encryption of $F_{ki}(S_i)$ separately for matching. Now there is an additional over head of storing $F_{ki}(S_i)$ bits. In reality, if we use AES for $F_{ki}(S_i)$ operation would result in 128 bits additionally which might be an over kill. If we use some length preserving encryption like FNR we could reduce the size of additional storage needed to size of word itself. Even in this case, we need double the storage of input text as premium for reducing false positives.

Not sure of any other approaches so far. I have made a quick proof-of-concept which could be found here. The test cases written for both that has false positives and also that will not have any but needs additional storage


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.