Practical backward-Secure Searchable Encryption from symmetric puncturable encryption

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

9 Citations (Scopus)

Abstract

Symmetric Searchable Encryption (SSE) has received wide attention due to its practical application in searching on encrypted data. Beyond search, data addition and deletion are also supported in dynamic SSE schemes. Unfortunately, these update operations leak some information of updated data. To address this issue, forward-secure SSE is actively explored to protect the relations of newly updated data and previously searched keywords. On the contrary, little work has been done in backward security, which enforces that search should not reveal information of deleted data. In this paper, we propose the first practical and non-interactive backward-secure SSE scheme. In particular, we introduce a new form of symmetric encryption, named symmetric puncturable encryption (SPE), and construct a generic primitive from simple cryptographic tools. Based on this primitive, we then present a backward-secure SSE scheme that can revoke a server’s searching ability on deleted data. We instantiate our scheme with a practical puncturable pseudorandom function and implement it on a large dataset. The experimental results demonstrate its efficiency and scalability. Compared to the state-of-the-art, our scheme achieves a speedup of almost 50× in search latency, and a saving of 62% in server storage consumption.

Original languageEnglish
Title of host publicationCCS’18 - Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security
Subtitle of host publicationOctober 15-19, 2018 Toronto, ON, Canada
EditorsMichael Backes, XiaoFeng Wang
Place of PublicationNew York NY USA
PublisherAssociation for Computing Machinery (ACM)
Pages763-780
Number of pages18
ISBN (Electronic)9781450356930
DOIs
Publication statusPublished - 2018
EventACM Conference on Computer and Communications Security 2018 - Beanfield Centre, Toronto, Canada
Duration: 15 Oct 201819 Oct 2018
Conference number: 25th
https://www.sigsac.org/ccs/CCS2018/ (Conference website)

Conference

ConferenceACM Conference on Computer and Communications Security 2018
Abbreviated titleCCS 2018
CountryCanada
CityToronto
Period15/10/1819/10/18
Internet address

Keywords

  • Backward Security
  • Puncturable Encryption
  • Symmetric Searchable Encryption

Cite this

Sun, S-F., Yuan, X., Liu, J. K., Steinfeld, R., Sakzad, A., Vo, V., & Nepal, S. (2018). Practical backward-Secure Searchable Encryption from symmetric puncturable encryption. In M. Backes, & X. Wang (Eds.), CCS’18 - Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security: October 15-19, 2018 Toronto, ON, Canada (pp. 763-780). New York NY USA: Association for Computing Machinery (ACM). https://doi.org/10.1145/3243734.3243782
Sun, Shi-Feng ; Yuan, Xingliang ; Liu, Joseph K. ; Steinfeld, Ron ; Sakzad, Amin ; Vo, Viet ; Nepal, Surya. / Practical backward-Secure Searchable Encryption from symmetric puncturable encryption. CCS’18 - Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security: October 15-19, 2018 Toronto, ON, Canada . editor / Michael Backes ; XiaoFeng Wang. New York NY USA : Association for Computing Machinery (ACM), 2018. pp. 763-780
@inproceedings{c6605cc477f449918996b9f271eb3124,
title = "Practical backward-Secure Searchable Encryption from symmetric puncturable encryption",
abstract = "Symmetric Searchable Encryption (SSE) has received wide attention due to its practical application in searching on encrypted data. Beyond search, data addition and deletion are also supported in dynamic SSE schemes. Unfortunately, these update operations leak some information of updated data. To address this issue, forward-secure SSE is actively explored to protect the relations of newly updated data and previously searched keywords. On the contrary, little work has been done in backward security, which enforces that search should not reveal information of deleted data. In this paper, we propose the first practical and non-interactive backward-secure SSE scheme. In particular, we introduce a new form of symmetric encryption, named symmetric puncturable encryption (SPE), and construct a generic primitive from simple cryptographic tools. Based on this primitive, we then present a backward-secure SSE scheme that can revoke a server’s searching ability on deleted data. We instantiate our scheme with a practical puncturable pseudorandom function and implement it on a large dataset. The experimental results demonstrate its efficiency and scalability. Compared to the state-of-the-art, our scheme achieves a speedup of almost 50× in search latency, and a saving of 62{\%} in server storage consumption.",
keywords = "Backward Security, Puncturable Encryption, Symmetric Searchable Encryption",
author = "Shi-Feng Sun and Xingliang Yuan and Liu, {Joseph K.} and Ron Steinfeld and Amin Sakzad and Viet Vo and Surya Nepal",
year = "2018",
doi = "10.1145/3243734.3243782",
language = "English",
pages = "763--780",
editor = "Backes, {Michael } and Wang, {XiaoFeng }",
booktitle = "CCS’18 - Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security",
publisher = "Association for Computing Machinery (ACM)",
address = "United States of America",

}

Sun, S-F, Yuan, X, Liu, JK, Steinfeld, R, Sakzad, A, Vo, V & Nepal, S 2018, Practical backward-Secure Searchable Encryption from symmetric puncturable encryption. in M Backes & X Wang (eds), CCS’18 - Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security: October 15-19, 2018 Toronto, ON, Canada . Association for Computing Machinery (ACM), New York NY USA, pp. 763-780, ACM Conference on Computer and Communications Security 2018, Toronto, Canada, 15/10/18. https://doi.org/10.1145/3243734.3243782

Practical backward-Secure Searchable Encryption from symmetric puncturable encryption. / Sun, Shi-Feng; Yuan, Xingliang; Liu, Joseph K.; Steinfeld, Ron; Sakzad, Amin; Vo, Viet; Nepal, Surya.

CCS’18 - Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security: October 15-19, 2018 Toronto, ON, Canada . ed. / Michael Backes; XiaoFeng Wang. New York NY USA : Association for Computing Machinery (ACM), 2018. p. 763-780.

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

TY - GEN

T1 - Practical backward-Secure Searchable Encryption from symmetric puncturable encryption

AU - Sun, Shi-Feng

AU - Yuan, Xingliang

AU - Liu, Joseph K.

AU - Steinfeld, Ron

AU - Sakzad, Amin

AU - Vo, Viet

AU - Nepal, Surya

PY - 2018

Y1 - 2018

N2 - Symmetric Searchable Encryption (SSE) has received wide attention due to its practical application in searching on encrypted data. Beyond search, data addition and deletion are also supported in dynamic SSE schemes. Unfortunately, these update operations leak some information of updated data. To address this issue, forward-secure SSE is actively explored to protect the relations of newly updated data and previously searched keywords. On the contrary, little work has been done in backward security, which enforces that search should not reveal information of deleted data. In this paper, we propose the first practical and non-interactive backward-secure SSE scheme. In particular, we introduce a new form of symmetric encryption, named symmetric puncturable encryption (SPE), and construct a generic primitive from simple cryptographic tools. Based on this primitive, we then present a backward-secure SSE scheme that can revoke a server’s searching ability on deleted data. We instantiate our scheme with a practical puncturable pseudorandom function and implement it on a large dataset. The experimental results demonstrate its efficiency and scalability. Compared to the state-of-the-art, our scheme achieves a speedup of almost 50× in search latency, and a saving of 62% in server storage consumption.

AB - Symmetric Searchable Encryption (SSE) has received wide attention due to its practical application in searching on encrypted data. Beyond search, data addition and deletion are also supported in dynamic SSE schemes. Unfortunately, these update operations leak some information of updated data. To address this issue, forward-secure SSE is actively explored to protect the relations of newly updated data and previously searched keywords. On the contrary, little work has been done in backward security, which enforces that search should not reveal information of deleted data. In this paper, we propose the first practical and non-interactive backward-secure SSE scheme. In particular, we introduce a new form of symmetric encryption, named symmetric puncturable encryption (SPE), and construct a generic primitive from simple cryptographic tools. Based on this primitive, we then present a backward-secure SSE scheme that can revoke a server’s searching ability on deleted data. We instantiate our scheme with a practical puncturable pseudorandom function and implement it on a large dataset. The experimental results demonstrate its efficiency and scalability. Compared to the state-of-the-art, our scheme achieves a speedup of almost 50× in search latency, and a saving of 62% in server storage consumption.

KW - Backward Security

KW - Puncturable Encryption

KW - Symmetric Searchable Encryption

UR - http://www.scopus.com/inward/record.url?scp=85056810408&partnerID=8YFLogxK

U2 - 10.1145/3243734.3243782

DO - 10.1145/3243734.3243782

M3 - Conference Paper

SP - 763

EP - 780

BT - CCS’18 - Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security

A2 - Backes, Michael

A2 - Wang, XiaoFeng

PB - Association for Computing Machinery (ACM)

CY - New York NY USA

ER -

Sun S-F, Yuan X, Liu JK, Steinfeld R, Sakzad A, Vo V et al. Practical backward-Secure Searchable Encryption from symmetric puncturable encryption. In Backes M, Wang X, editors, CCS’18 - Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security: October 15-19, 2018 Toronto, ON, Canada . New York NY USA: Association for Computing Machinery (ACM). 2018. p. 763-780 https://doi.org/10.1145/3243734.3243782