SESOS: A Verifiable Searchable Outsourcing Scheme for Ordered Structured Data in Cloud Computing



1 Sharif University of Technology, Tehran, Iran & Hong Kong University of Science and Technology, Hong Kong

2 Sharif University of Technology, Tehran, Iran

3 Associate Professor, Department of Computer Engineering, Sharif University of Technology, Tehran, IRAN.

4 Hong Kong University of Science and Technology, Hong Kong


While cloud computing is growing at a remarkable speed, privacy issues are far from being solved. One way to diminish privacy concerns is to store data on the cloud in encrypted form. However, encryption often hinders useful computation cloud services. A theoretical approach is to employ the so-called fully homomorphic encryption, yet the overhead is so high that it is not considered a viable solution for practical purposes. The next best thing is to craft special-purpose cryptosystems which support the set of operations required to be addressed by cloud services. In this paper, we put forward one such cryptosystem, which supports efficient search over structured data types, such as timestamps or network addresses, which are comprised of several segments with well-known values. The new cryptosystem, called SESOS, provides the ability to execute LIKE queries, along with the search for exact matches, as well as comparison.
In addition, the extended version, called XSESOS, allows for verifying the integrity of ciphertexts.
At its heart, SESOS combines any order-preserving encryption (OPE) scheme with a novel encryption scheme called Multi-map Perfectly Secure Cryptosystem(MuPS). We prove that MuPS is perfectly secure, and hence SESOS enjoys the same security properties of the underlying OPE scheme.
The overhead of executing equality and comparison operations is negligible. The performance of LIKE queries is significantly improved by up to 1370X and the performance of result decryption improved by 520X compared to existing solutions on a database with merely 100K records (the improvement is even more significant in larger databases).


[1] Raluca Ada Popa, Catherine Redfield, Nickolai Zeldovich, and Hari Balakrishnan. CryptDB: protecting confidentiality with encrypted query processing. In Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles, pages 85–100. ACM, 2011.

[2] Stephen Tu, M Frans Kaashoek, Samuel Madden, and Nickolai Zeldovich. Processing analytical queries over encrypted data. In Proceedings of the VLDB Endowment, Vol. 6, No. 5, pages 289–300, 2013.

[3] Zhian He, Wai Kit Wong, Ben Kao, David Wai Lok Cheung, Rongbin Li, Siu Ming Yiu, and Eric Lo. SDB: a secure query processing system with data interoperability. Proceedings of the VLDB Endowment, 8(12):1876–1879, 2015.

[4] Craig Gentry, Shai Halevi, and Nigel P Smart. Fully homomorphic encryption with polylog overhead. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 465–482. Springer, 2012.

[5] Xiaoqiang Sun, Jianping Yu, Ting Wang, Zhiwei Sun, and Peng Zhang. Efficient identitybased leveled fully homomorphic encryption from RLWE. Security and Communication Networks, 9(18):5155–5165, 2016.

[6] Craig Gentry et al. Fully homomorphic encryption using ideal lattices. In STOC, pages 169–178, 2009.

[7] Raluca Ada Popa, Catherine Redfield, Nickolai Zeldovich, and Hari Balakrishnan. CryptDB: processing queries on an encrypted database. Communications of the ACM, 55(9):103–111, 2012.

[8] Li Xiong, Slawomir Goryczka, and Vaidy Sunderam. Adaptive, secure, and scalable distributed data outsourcing: a vision paper. In Proceedings of the 2011 workshop on Dynamic distributed dataintensive applications, programming abstractions, and systems, pages 1–6. ACM, 2011.

[9] Jin Li, Zheli Liu, Xiaofeng Chen, Fatos Xhafa, Xiao Tan, and Duncan S Wong. L-EncDB: ISeCure January 2019, Volume 11, Number 1 (pp. 15–34) A lightweight framework for privacy-preserving data queries in cloud computing. KnowledgeBased Systems, 79:18–26, 2015.

[10] Ernesto Damiani, SDCD Vimercati, Sushil Jajodia, Stefano Paraboschi, and Pierangela Samarati. Balancing confidentiality and efficiency in untrusted relational DBMSs. In Proceedings of the 10th ACM conference on Computer and communications security, pages 93–102. ACM, 2003.

[11] Dongmei Li, Xiaolei Dong, and Zhenfu Cao. Secure and privacy-preserving pattern matching in outsourced computing. Security and Communication Networks, 9(16):3444–3451, 2016.

[12] Wei Song, Zhiyong Peng, Qian Wang, Fangquan Cheng, Xiaoxin Wu, and Yihui Cui. Efficient privacy-preserved data query over ciphertext in cloud computing. Security and Communication Networks, 7(6):1049–1065, 2014.

[13] Rakesh Agrawal, Jerry Kiernan, Ramakrishnan Srikant, and Yirong Xu. Order preserving encryption for numeric data. In Proceedings of the 2004 ACM SIGMOD international conference on Management of data, pages 563–574. ACM, 2004. [14] Hui Wang and Laks VS Lakshmanan. Efficient secure query evaluation over encrypted XML databases. In Proceedings of the 32nd international conference on Very large data bases, pages 127–138. VLDB Endowment, 2006.

[15] Divyakant Agrawal, Amr El Abbadi, Fatih Emekci, and Ahmed Metwally. Database management as a service: Challenges and opportunities. In Data Engineering, 2009. ICDE’09. IEEE 25th International Conference on, pages 1709–1716. IEEE, 2009.

[16] Mohammad Ali Hadavi, Morteza Noferesti, Rasool Jalili, and Ernesto Damiani. Database as a service: towards a unified solution for security requirements. In Computer Software and Applications Conference Workshops (COMPSACW), 2012 IEEE 36th Annual, pages 415–420. IEEE, 2012.

[17] Gagan Aggarwal, Mayank Bawa, Prasanna Ganesan, Hector Garcia-Molina, Krishnaram Kenthapadi, Rajeev Motwani, Utkarsh Srivastava, Dilys Thomas, and Ying Xu. Two can keep a secret: A distributed architecture for secure database services. CIDR 2005, 2005.

[18] Alexandra Boldyreva, Nathan Chenette, and Adam O’Neill. Order-preserving encryption revisited: Improved security analysis and alternative solutions. In CRYPTO, volume 6841, pages 578–595. Springer, 2011.

[19] Hasan Kadhem, Toshiyuki Amagasa, and Hiroyuki Kitagawa. A Secure and Efficient Order Preserving Encryption Scheme for Relational Databases. In KMIS, pages 25–35, 2010.

[20] George Weilun Ang, John Harold Woelfel, and Terrence Peter Woloszyn. System and method of sort-order preserving tokenization, May 2014. US Patent 8,739,265.

[21] Fahmida Y Rashid. Salesforce. com acquires SaaS encryption provider Navajo Systems. eWeek. com, 2011.

[22] Raluca Ada Popa, Frank H Li, and Nickolai Zeldovich. An ideal-security protocol for orderpreserving encoding. In Security and Privacy (SP), 2013 IEEE Symposium on, pages 463–477. IEEE, 2013.

[23] Yong Ho Hwang, Sungwook Kim, and Jae Woo Seo. Fast order-preserving encryption from uniform distribution sampling. In Proceedings of the 2015 ACM Workshop on Cloud Computing Security Workshop, pages 41–52. ACM, 2015. [24] Florian Kerschbaum. Frequency-hiding orderpreserving encryption. In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, pages 656–667. ACM, 2015.

[25] Dawn Xiaodong Song, David Wagner, and Adrian Perrig. Practical techniques for searches on encrypted data. In Security and Privacy, 2000. S&P 2000. Proceedings. 2000 IEEE Symposium on, pages 44–55. IEEE, 2000.

[26] Reza Curtmola, Juan Garay, Seny Kamara, and Rafail Ostrovsky. Searchable symmetric encryption: improved definitions and efficient constructions. In Proceedings of the 13th ACM conference on Computer and communications security, pages 79–88. ACM, 2006.

[27] Seny Kamara, Charalampos Papamanthou, and Tom Roeder. Dynamic searchable symmetric encryption. In Proceedings of the 2012 ACM conference on Computer and communications security, pages 965–976. ACM, 2012.

[28] Florian Hahn and Florian Kerschbaum. Searchable encryption with secure and efficient updates. In Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, pages 310–320. ACM, 2014.

[29] David Cash, Stanislaw Jarecki, Charanjit Jutla, Hugo Krawczyk, Marcel-C˘at˘alin Ro¸su, and Michael Steiner. Highly-scalable searchable symmetric encryption with support for boolean queries. In Advances in cryptology–CRYPTO 2013, pages 353–373. Springer, 2013.

[30] David Cash and Stefano Tessaro. The locality of searchable symmetric encryption. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 351– 368. Springer, 2014.

[31] Muhammad Naveed, Manoj Prabhakaran, and Carl A Gunter. Dynamic searchable encryption via blind storage. In Security and Privacy (SP), 2014 IEEE Symposium on, pages 639–654. IEEE, 2014.

[32] Ian Miers and Payman Mohassel. Io-dsse: Scaling dynamic searchable encryption to millions of indexes by improving locality. IACR Cryptology ePrint Archive, 2016:830, 2016.

[33] Rapha¨el Bost, Brice Minaud, and Olga Ohrimenko. Forward and backward private searchable encryption from constrained cryptographic primitives. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pages 1465–1482. ACM, 2017.

[34] Javad Ghareh Chamani, Dimitrios Papadopoulos, Charalampos Papamanthou, and Rasool Jalili. New constructions for forward and backward private symmetric searchable encryption. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pages 1038–1055. ACM, 2018.

[35] Alexandra Boldyreva, Nathan Chenette, Younho Lee, and Adam O’Neill. Order-preserving symmetric encryption. In EUROCRYPT, volume 5479, pages 224–241. Springer, 2009.

[36] Isamu Teranishi, Moti Yung, and Tal Malkin. Order-preserving encryption secure beyond onewayness. In ASIACRYPT, pages 42–61. Springer, 2014.

[37] Dan Boneh and Victor Shoup. A Graduate Course in Applied Cryptography. Draft of a book, version 0.3, December 2016. Available online from ~dabo/cryptobook/draft_0_3.pdf.

[38] The GNU Multiple Precision Arithmetic Library (GMP). Available from