4 ms·

It's for performing any function on the data. A search is a function which takes the data as input and returns the search results as output.

by DavidSJ 15y ago

sp332 15y ago
All the homomorphic schemes I've seen do addition and/or multiplication. Is there one that does substring matching, or can you somehow use addition and multiplication to search?
- pnathan 15y ago
  I wonder if you could develop a parameterized algebra over a search string x that defined x as the identity for addition or multiplication.
narsil 15y ago
While that may be true, text search over documents has certain requirements that differ from the use cases being mentioned for homomorphic encryption over the past two years (since Craig Gentry's paper on fully homomorphic encryption). Although possible over structured data that you'd find in a database, I'm not sure if there's been a clear way to apply homomorphic encryption to search. If there has been progress made in this area, I'd love to know. In documents, keywords are scattered through the plain text and conjunctive keyword search should be possible without giving way to dictionary attacks: If I search for 'fire truck' I want a sentence 'the truck was firing up' to potentially return as a search result, but at the same time I don't want to encrypt each tokenized word ('fire', 'truck') and pattern-match the ciphertext. Encrypted search is an active research area. One of the more interesting/cited papers I've come across on the topic is Conjunctive, Subset, and Range Queries on Encrypted Data by Boneh and Waters [1] although there are several others. Boneh also authored an earlier paper on encrypted search involving public key encryption. [1] http://crypto.stanford.edu/~dabo/pubs/papers/search.pdf http://crypto.stanford.edu/~dabo/pubs/papers/search.pdf [2] http://www.cs.berkeley.edu/~dawnsong/papers/se.pdf http://www.cs.berkeley.edu/~dawnsong/papers/se.pdf

It's for performing any function on the data. A search is a function which takes the data as input and returns the search results as output.

by DavidSJ 15y ago

It's for performing any function on the data. A search is a function which takes the data as input and returns the search results as output.

sp332 15y ago

All the homomorphic schemes I've seen do addition and/or multiplication. Is there one that does substring matching, or can you somehow use addition and multiplication to search?

pnathan 15y ago
I wonder if you could develop a parameterized algebra over a search string x that defined x as the identity for addition or multiplication.

narsil 15y ago

While that may be true, text search over documents has certain requirements that differ from the use cases being mentioned for homomorphic encryption over the past two years (since Craig Gentry's paper on fully homomorphic encryption). Although possible over structured data that you'd find in a database, I'm not sure if there's been a clear way to apply homomorphic encryption to search. If there has been progress made in this area, I'd love to know. In documents, keywords are scattered through the plain text and conjunctive keyword search should be possible without giving way to dictionary attacks: If I search for 'fire truck' I want a sentence 'the truck was firing up' to potentially return as a search result, but at the same time I don't want to encrypt each tokenized word ('fire', 'truck') and pattern-match the ciphertext. Encrypted search is an active research area. One of the more interesting/cited papers I've come across on the topic is Conjunctive, Subset, and Range Queries on Encrypted Data by Boneh and Waters [1] although there are several others. Boneh also authored an earlier paper on encrypted search involving public key encryption. [1] http://crypto.stanford.edu/~dabo/pubs/papers/search.pdf http://crypto.stanford.edu/~dabo/pubs/papers/search.pdf [2] http://www.cs.berkeley.edu/~dawnsong/papers/se.pdf http://www.cs.berkeley.edu/~dawnsong/papers/se.pdf