Paper 2010/547

Symmetric-key Searchable keyword Concealment (SSC)

Yacov Yacobi

Abstract

We discuss what is commonly known as “searchable symmetric keywords encryption,” although we prefer to replace “encryption” with “concealment,” since many of these transformations are not (efficiently) reversible (they look more like one way hashing). The thrust of this paper is practical approaches to cryptographic solutions for cloud databases security and privacy. We limit the scope of this paper to symmetric key keyword concealment systems, and show the following: (i) for the attacker (with the DB admin as the attacker), any Symmetric-key Searchable keyword Concealment (SSC) with high probability behaves as far as the attacker is concerned like a deterministic cipher (therefore, we might as well use deterministic systems and rip their efficiencies). (ii) Range queries can be handled more securely and more efficiently than current proposals, such as OPE, at the cost of some extra bandwidth, but good compromises are easy to find; (iii) Conjunctions of keywords (and indeed any Boolean predicate) are easy to handle at the cost of some additional information leakage. We do not know of any real example where this extra leak matters.