SEDAN workshop
on
Searchable Encryption
Wednesday, October 7th, 2009
Horsttoren, room T 1300
University of Twente,
Enschede, The Netherlands
Program
No registration fee is required. Please, register before September 25, 2009 by sending an e-mail with your name and affiliation to n.timmer@utwente.nl.
| 8.30-9.00 | Welcome coffee |
| 9.00-9.45 | Invited talk:
"Robust Encryption and Its application to Searchable Encryption", Michel Abdala (ENS & CNRS, France) |
| 9.45-10.00 | Questions and discussion |
| 10.00-10.45 | Invited talk:
"Private-Key Hidden Vector Encryption with Key Confidentiality", Giuseppe Persiano (University of Salerno, Italy) |
| 10.45-11.00 | Questions and discussion |
| 11.00-11.45 | Invited talk:
"Zero-knowledge interval proofs and other cryptographic protocols involving intervals.", Berry Schoenmakers (TU/e, The Netherlands) |
| 11.45-12.00 | Questions and discussion |
| 12.00-13.30 | Lunch |
| 13.30-14.00 | "Mediated Ciphertext-Policy Attribute-Based
Encryption and its Application" Luan Ibraimi (University of Twente, The Netherlands) |
| 14.00-14.30 | "Public key encryption with prefix keyword search" Saeed Sedghi (Univesity of Twente, The Netherlands) |
| 14.30-15.00 | Coffee/Tea break |
| 15.00-15.30 | "Trapdoor-hiding in Searchable Encryption" Peter van Liesdonk (TU/e, The Netherlands) |
| 15.30-16.00 | "Blind and Anonymous Identity-Based Encryption and
Authorised Private Searches on Public Key Encrypted Data" Alfredo Rial (KU Leuven, Belgium) |
| 16.00-16.30 | Discussions and Closing Remarks |
Abstracts
"Robust Encryption and Its application to Searchable Encryption"
Michel Abdala (ENS & CNRS, France) (), 9:00-9:45
Motivated by applications to auctions, searchable encryption, and anonymous wireless communication, we provide a provable-security treatment of the notion of a ``robust'' encryption scheme, namely one where the decryption algorithm rejects when the ``wrong'' secret key is used. First, we provide formal definitions of robustness under chosen-plaintext and chosen-ciphertext attack. We find that contrary to what seems intuitive, robustness ---at least in combination with privacy and anonymity as required by applications--- is actually rarely, if ever, present and obvious ways to confer it fail.
We however provide general ways to efficiently confer robustness without sacrificing other security properties, for both public-key and identity-based encryption. Next, we examine the robustness of several well-known encryption schemes. Finally, we also show how to apply our results to searchable encryption schemes to obtain the first schemes with security against chosen-ciphertext attacks in the standard model. We believe these results are important to clarify and help fill gaps in the literature arising from the implicit use of a robustness property that until now lacked formal definitions.
This is joint work with Mihir Bellare and Gregory Neven.
"Private-Key Hidden Vector Encryption with Key Confidentiality"
Giuseppe Persiano (University of Salerno, Italy) (), 10:00-10:45
In this paper, we consider hidden vector encryption that is a special class of predicate encryptions. In a hidden vector encryption scheme, ciphertexts are associated with attribute vectors $\x$ of length $\ell$ over an alphabet $\Sigma$ and keys are associated with pattern vectors $\k$ of length $\ell$ over the alphabet $\Sigma\cup\{\star\}$. Constructions for hidden vector encryption have been given based on hardness assumptions in groups of composite order and based on hardness assumptions in groups of prime order.
Until now research has concentrated on guaranteeing the security of the ciphertext with respect to the cleartext and to the attribute vector and not much attention has been devoted to the security of the key. Specifically, one would like a key not to reveal the associated pattern. This is particularly important in some applications in which a user generates the key for a certain pattern and gives it to a third party to perform some operations. Knowledge of the pattern associated with the key might reveal some information about the operation being performed. Obviously, this is impossible to achieve in a public-key setting. Indeed an adversary $\A$ holding a key $\tilde K$ associated to a secret pattern $\k$ can simply produce a ciphertext $\tilde X$ with attribute $\x$ and then try to decrypt $\tilde X$ using $\tilde K$. If $\A$ succeeds in decrypting $\tilde K$ then $\A$ knows that $P(\x,\k)=1$. This attack does not hold in the private key setting as $\A$ cannot produce ciphertext $\tilde X$. Simply keeping the public key secret from the adversary does not seem to work for previous predicate encryption schemes (see, for example \cite{BoWa07,KaSaWa08}) and the problem seems to call for a new construction.
Joint work with Carlo Blundo and Vincenzo Iovino.
"Zero-knowledge interval proofs and other cryptographic protocols involving intervals."
Berry Schoenmakers (TU/e, The Netherlands) (), 11:00-11:45
By an interval we mean a set of consecutive integers. In this talk we consider several cryptographic protocols involving intervals. We present zero-knowledge interval proofs for committed integers, which are optimal when assuming DDH only, and other work such as efficient modulo reduction of (homomorphically) encrypted values.
"Mediated Ciphertext-Policy Attribute-Based Encryption and its Application"
Luan Ibraimi (University of Twente, The Netherlands), 13:30-14:00
In Ciphertext-Policy Attribute-Based Encryption (CP-ABE), a user secret key is associated with a set of attributes, and the ciphertext is associated with an access policy over attributes. The user can decrypt the ciphertext if and only if the attribute set of his secret key satisfies the access policy specified in the ciphertext. Several CP-ABE schemes have been proposed, however, some practical problems, such as attribute revocation, still needs to be addressed.
In this paper, we propose a mediated Ciphertext-Policy Attribute-Based Encryption (mCP-ABE) which extends CP-ABE with instantaneous attribute revocation. Furthermore, we demonstrate how to apply the proposed mCP-ABE scheme to securely manage Personal Health Records (PHRs).
"Public-Key Encryption with Prefix Keyword Search"
Saeed Sedghi (Univesity of Twente, The Netherlands), 14:00-14:30
Public key encryption with keyword search (PEKS) is a technique that allows a client to retrieve documents encrypted with his public key via a trapdoor built by his private key. Many PEKS schemes (including anonymous identity based encryption schemes) have been proposed.
In many practical cases the client wishes to retrieve a document if a queried keyword occurs in the prefix of (at least) one of the keywords of the encrypted document. However, existing PEKS schemes are proposed for the equality search, i,e, the server finds the encrypted documents that contain the exact queried keyword.
In this presentation a public key encryption with prefix keyword search scheme is presented. It addresses searching the prefix keywords in a more efficient and secure way than the trivially extended PEKS scheme. By more efficient we mean that the searching cost does not depend on the number of characters in the queried keyword. The scheme also does not reveal the number of characters in the encrypted keyword and the trapdoor.
"Trapdoor-hiding in Searchable Encryption"
Peter van Liesdonk (TU/e, The Netherlands), 15:00-15:30
In [BDOP04], Boneh et al. introduced the notion of public-key encryption with keyword search (PEKS), a construction that allows a client to outsource keyword searches to an untrusted server by constructing trapdoors. There has been a lot of research about these constructions and the security of their encryptions. However, there has been very little research about the security of the trapdoors. It seems inherent to the construction that trapdoors leak information.
In this talk we take a closer look at the information loss through these trapdoors and how this can be limited. We propose a solution based on proxy re-encryption.
"Blind and Anonymous Identity-Based Encryption and Authorised Private Searches on Public Key Encrypted Data"
Alfredo Rial (KU Leuven, Belgium), 15:30-16:00
Searchable encryption schemes provide an important mechanism to cryptographically protect data while keeping it available to be searched and accessed. In a common approach for their construction, the encrypting entity chooses one or several keywords that describe the content of each encrypted record of data. To perform a search, a user obtains a trapdoor for a keyword of her interest and uses this trapdoor to find all the data described by this keyword.
We present a searchable encryption scheme that allows users to privately search by keywords on encrypted data in a public key setting and decrypt the search results. To this end, we define and implement two primitives: public key encryption with oblivious keyword search (PEOKS) and committed blind anonymous identity-based encryption (IBE). PEOKS is an extension of public key encryption with keyword search (PEKS) in which users can obtain trapdoors from the secret key holder without revealing the keywords. Furthermore, we define committed blind trapdoor extraction, which facilitates the definition of authorisation policies to describe which trapdoor a particular user can request. We construct a PEOKS scheme by using our other primitive, which we believe to be the first blind and anonymous IBE scheme.
We apply our PEOKS scheme to build a public key encrypted database that permits authorised private searches, i.e., neither the keywords nor the search results are revealed.