In this paper we consider a scenario where a user wants to outsource her documents to the cloud, so that she can later reliably delegate (to the cloud) pattern matching operations on these documents. We propose an efficient solution to this problem that relies on the homomorphic MAC for polynomials proposed by Catalano and Fiore (EuroCrypt 2013). Our main contribution are new methods to express pat- tern matching operations (both in their exact and approximate variants) as low degree polynomials, i.e. polynomials whose degree solely depends on the size of the pattern. To better assess the practicality of our schemes, we propose a concrete implementation that further optimizes the efficiency of the homomorphic MAC of Catalano and Fiore. Our implementation shows that the proposed protocols are extremely efficient for the client, while remaining feasible at server side.
Verifiable Pattern Matching on Outsourced Texts
Dario Catalano;Mario Di Raimondo;Simone Faro
2018-01-01
Abstract
In this paper we consider a scenario where a user wants to outsource her documents to the cloud, so that she can later reliably delegate (to the cloud) pattern matching operations on these documents. We propose an efficient solution to this problem that relies on the homomorphic MAC for polynomials proposed by Catalano and Fiore (EuroCrypt 2013). Our main contribution are new methods to express pat- tern matching operations (both in their exact and approximate variants) as low degree polynomials, i.e. polynomials whose degree solely depends on the size of the pattern. To better assess the practicality of our schemes, we propose a concrete implementation that further optimizes the efficiency of the homomorphic MAC of Catalano and Fiore. Our implementation shows that the proposed protocols are extremely efficient for the client, while remaining feasible at server side.File | Dimensione | Formato | |
---|---|---|---|
Verifiable pattern matching on outsourced texts.pdf
solo gestori archivio
Tipologia:
Versione Editoriale (PDF)
Dimensione
386.46 kB
Formato
Adobe PDF
|
386.46 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.