Searching Keywords with Wildcards on Encrypted Data

S. Sedghi, Peter van Liesdonk, S.I. Nikova, Pieter H. Hartel, Willem Jonker

Research output: Book/ReportReportProfessional

44 Citations (Scopus)
276 Downloads (Pure)

Abstract

A hidden vector encryption scheme (HVE) is a derivation of identity-based encryption, where the public key is actually a vector over a certain alphabet. The decryption key is also derived from such a vector, but this one is also allowed to have ``$\star$'' (or wildcard) entries. Decryption is possible as long as these tuples agree on every position except where a ``$\star$'' occurs. These schemes are useful for a variety of applications: they can be used as building block to construct attribute-based encryption schemes and sophisticated predicate encryption schemes (for e.g. range or subset queries). Another interesting application -- and our main motivation -- is to create searchable encryption schemes that support queries for keywords containing wildcards. Here we construct a new HVE scheme, based on bilinear groups of prime order, which supports vectors over any alphabet. The resulting ciphertext length is equally shorter than existing schemes, depending on a trade-off. The length of the decryption key and the computational complexity of decryption are both constant, unlike existing schemes where these are both dependent on the amount of non-wildcard symbols associated to the decryption key. Our construction hides both the plaintext and public key used for encryption. We prove security in a selective model, under the decision linear assumption.
Original languageUndefined
Place of PublicationEnschede
PublisherCentre for Telematics and Information Technology (CTIT)
Number of pages13
Publication statusPublished - 8 Apr 2010

Publication series

NameCTIT Technical Report Series
PublisherCentre for Telematics and Information Technology, University of Twente
No.TR-CTIT-10-14
ISSN (Print)1381-3625

Keywords

  • Pairing Based Cryptography
  • PEKS
  • SCS-Cybersecurity
  • METIS-270786
  • IR-70901
  • EWI-17789
  • Hidden Vector Encryption
  • Searchable Encryption

Cite this

Sedghi, S., van Liesdonk, P., Nikova, S. I., Hartel, P. H., & Jonker, W. (2010). Searching Keywords with Wildcards on Encrypted Data. (CTIT Technical Report Series; No. TR-CTIT-10-14). Enschede: Centre for Telematics and Information Technology (CTIT).
Sedghi, S. ; van Liesdonk, Peter ; Nikova, S.I. ; Hartel, Pieter H. ; Jonker, Willem. / Searching Keywords with Wildcards on Encrypted Data. Enschede : Centre for Telematics and Information Technology (CTIT), 2010. 13 p. (CTIT Technical Report Series; TR-CTIT-10-14).
@book{2f994d236f354c12915f58eee56ef65a,
title = "Searching Keywords with Wildcards on Encrypted Data",
abstract = "A hidden vector encryption scheme (HVE) is a derivation of identity-based encryption, where the public key is actually a vector over a certain alphabet. The decryption key is also derived from such a vector, but this one is also allowed to have ``$\star$'' (or wildcard) entries. Decryption is possible as long as these tuples agree on every position except where a ``$\star$'' occurs. These schemes are useful for a variety of applications: they can be used as building block to construct attribute-based encryption schemes and sophisticated predicate encryption schemes (for e.g. range or subset queries). Another interesting application -- and our main motivation -- is to create searchable encryption schemes that support queries for keywords containing wildcards. Here we construct a new HVE scheme, based on bilinear groups of prime order, which supports vectors over any alphabet. The resulting ciphertext length is equally shorter than existing schemes, depending on a trade-off. The length of the decryption key and the computational complexity of decryption are both constant, unlike existing schemes where these are both dependent on the amount of non-wildcard symbols associated to the decryption key. Our construction hides both the plaintext and public key used for encryption. We prove security in a selective model, under the decision linear assumption.",
keywords = "Pairing Based Cryptography, PEKS, SCS-Cybersecurity, METIS-270786, IR-70901, EWI-17789, Hidden Vector Encryption, Searchable Encryption",
author = "S. Sedghi and {van Liesdonk}, Peter and S.I. Nikova and Hartel, {Pieter H.} and Willem Jonker",
year = "2010",
month = "4",
day = "8",
language = "Undefined",
series = "CTIT Technical Report Series",
publisher = "Centre for Telematics and Information Technology (CTIT)",
number = "TR-CTIT-10-14",
address = "Netherlands",

}

Sedghi, S, van Liesdonk, P, Nikova, SI, Hartel, PH & Jonker, W 2010, Searching Keywords with Wildcards on Encrypted Data. CTIT Technical Report Series, no. TR-CTIT-10-14, Centre for Telematics and Information Technology (CTIT), Enschede.

Searching Keywords with Wildcards on Encrypted Data. / Sedghi, S.; van Liesdonk, Peter; Nikova, S.I.; Hartel, Pieter H.; Jonker, Willem.

Enschede : Centre for Telematics and Information Technology (CTIT), 2010. 13 p. (CTIT Technical Report Series; No. TR-CTIT-10-14).

Research output: Book/ReportReportProfessional

TY - BOOK

T1 - Searching Keywords with Wildcards on Encrypted Data

AU - Sedghi, S.

AU - van Liesdonk, Peter

AU - Nikova, S.I.

AU - Hartel, Pieter H.

AU - Jonker, Willem

PY - 2010/4/8

Y1 - 2010/4/8

N2 - A hidden vector encryption scheme (HVE) is a derivation of identity-based encryption, where the public key is actually a vector over a certain alphabet. The decryption key is also derived from such a vector, but this one is also allowed to have ``$\star$'' (or wildcard) entries. Decryption is possible as long as these tuples agree on every position except where a ``$\star$'' occurs. These schemes are useful for a variety of applications: they can be used as building block to construct attribute-based encryption schemes and sophisticated predicate encryption schemes (for e.g. range or subset queries). Another interesting application -- and our main motivation -- is to create searchable encryption schemes that support queries for keywords containing wildcards. Here we construct a new HVE scheme, based on bilinear groups of prime order, which supports vectors over any alphabet. The resulting ciphertext length is equally shorter than existing schemes, depending on a trade-off. The length of the decryption key and the computational complexity of decryption are both constant, unlike existing schemes where these are both dependent on the amount of non-wildcard symbols associated to the decryption key. Our construction hides both the plaintext and public key used for encryption. We prove security in a selective model, under the decision linear assumption.

AB - A hidden vector encryption scheme (HVE) is a derivation of identity-based encryption, where the public key is actually a vector over a certain alphabet. The decryption key is also derived from such a vector, but this one is also allowed to have ``$\star$'' (or wildcard) entries. Decryption is possible as long as these tuples agree on every position except where a ``$\star$'' occurs. These schemes are useful for a variety of applications: they can be used as building block to construct attribute-based encryption schemes and sophisticated predicate encryption schemes (for e.g. range or subset queries). Another interesting application -- and our main motivation -- is to create searchable encryption schemes that support queries for keywords containing wildcards. Here we construct a new HVE scheme, based on bilinear groups of prime order, which supports vectors over any alphabet. The resulting ciphertext length is equally shorter than existing schemes, depending on a trade-off. The length of the decryption key and the computational complexity of decryption are both constant, unlike existing schemes where these are both dependent on the amount of non-wildcard symbols associated to the decryption key. Our construction hides both the plaintext and public key used for encryption. We prove security in a selective model, under the decision linear assumption.

KW - Pairing Based Cryptography

KW - PEKS

KW - SCS-Cybersecurity

KW - METIS-270786

KW - IR-70901

KW - EWI-17789

KW - Hidden Vector Encryption

KW - Searchable Encryption

M3 - Report

T3 - CTIT Technical Report Series

BT - Searching Keywords with Wildcards on Encrypted Data

PB - Centre for Telematics and Information Technology (CTIT)

CY - Enschede

ER -

Sedghi S, van Liesdonk P, Nikova SI, Hartel PH, Jonker W. Searching Keywords with Wildcards on Encrypted Data. Enschede: Centre for Telematics and Information Technology (CTIT), 2010. 13 p. (CTIT Technical Report Series; TR-CTIT-10-14).