research-article

Repeatable Oblivious Shuffling of Large Outsourced Data Blocks

Authors:

Ada Wai-Chee Fu,

Raymond Chi-Wing WongAuthors Info & Claims

SoCC '19: Proceedings of the ACM Symposium on Cloud Computing

Pages 287 - 298

https://doi.org/10.1145/3357223.3362732

Published: 20 November 2019 Publication History

Abstract

As data outsourcing becomes popular, oblivious algorithms have raised extensive attentions. Their control flow and data access pattern appear to be independent of the input data they compute on. Oblivious algorithms, therefore, are especially suitable for secure processing in outsourced environments. In this work, we focus on oblivious shuffling algorithms that aim to shuffle encrypted data blocks outsourced to a cloud server without disclosing the actual permutation of blocks to the server. Existing oblivious shuffling algorithms suffer from issues of heavy communication cost and client computation cost for shuffling large-sized blocks because all outsourced blocks must be downloaded to the client for shuffling or peeling off extra encryption layers. To help eliminate this void, we introduce the "repeatable oblivious shuffling" notation that avoids moving blocks to the client and thus restricts the communication and client computation costs to be independent of the block size. For the first time, we present a concrete construction of repeatable oblivious shuffling using additively homomorphic encryption. The comprehensive evaluation of our construction shows its effective usability in practice for shuffling large-sized blocks.

References

[1]

Abbas Acar, Hidayet Aksu, A Selcuk Uluagac, and Mauro Conti. 2018. A survey on homomorphic encryption schemes: theory and implementation. CSUR 51, 4 (2018), 79.

Digital Library

[2]

Ben Adida and Douglas Wikström. 2007. How to shuffle in public. In Proc. TCC'07. 555.

[3]

David W Archer, Dan Bogdanov, Yehuda Lindell, Liina Kamm, Kurt Nielsen, Jakob Illeborg Pagter, Nigel P Smart, and Rebecca N Wright. 2018. From Keys to Databases---Real-World Applications of Secure Multi-Party Computation. Comput. J. 61, 12 (2018), 1749--1771.

[4]

Sumeet Bajaj and Radu Sion. 2014. Trusteddb: A trusted hardware-based database with privacy and data confidentiality. TKDE 26, 3 (2014), 752--765.

Digital Library

[5]

Dan Bogdanov, Liina Kamm, Sven Laur, Pille Pruulmann-Vengerfeldt, Riivo Talviste, and Jan Willemson. 2014. Privacy-preserving statistical data analysis on federated databases. In Annual Privacy Forum. Springer, 30--55.

[6]

Li Cai and Yangyong Zhu. 2015. The challenges of data quality and data quality assessment in the big data era. Data Science Journal 14 (2015).

[7]

Ning Cao, Cong Wang, Ming Li, Kui Ren, and Wenjing Lou. 2014. Privacy-preserving multi-keyword ranked search over encrypted cloud data. TPDS 25, 1 (2014), 222--233.

Digital Library

[8]

Crypto++ community. 2019. Crypto++. https://www.cryptopp.com/.

[9]

Sabrina De Capitani di Vimercati, Sara Foresti, Stefano Paraboschi, Gerardo Pelosi, and Pierangela Samarati. 2011. Efficient and private access to outsourced data. In Proc. ICDCS'11. 710.

Digital Library

[10]

Srinivas Devadas, Marten van Dijk, Christopher W Fletcher, Ling Ren, Elaine Shi, and Daniel Wichs. 2016. Onion oram: A constant bandwidth blowup oblivious RAM. In Proc. TCC'16. 145.

[11]

David Steven Dummit and Richard M Foote. 2004. Abstract algebra. Vol. 3. Wiley Hoboken.

[12]

Michael T Goodrich. 2014. Zig-zag sort: A simple deterministic data-oblivious sorting algorithm running in O(nlogn) time. In Proc. STOC'14. 684.

Digital Library

[13]

Michael T Goodrich, Michael Mitzenmacher, Olga Ohrimenko, and Roberto Tamassia. 2012. Practical oblivious storage. In Proc. CODASPY'12. 13--24.

Digital Library

[14]

Paul Grubbs, Kevin Sekniqi, Vincent Bindschaedler, Muhammad Naveed, and Thomas Ristenpart. 2017. Leakage-abuse attacks against order-revealing encryption. In Proc. SP'17. 655.

[15]

Mohammad Saiful Islam, Mehmet Kuzu, and Murat Kantarcioglu. 2012. Access Pattern disclosure on searchable encryption: ramification, attack and mitigation. In Proc.NDSS'12. 12.

[16]

Seny Kamara, Payman Mohassel, and Mariana Raykova. 2011. Outsourcing Multi-Party Computation. IACR Cryptology ePrint Archive 2011 (2011), 272.

[17]

Georgios Kellaris, George Kollios, Kobbi Nissim, and Adam O'Neill. 2016. Generic Attacks on Secure Outsourced Databases. In Proc. CCS'16. 1329.

Digital Library

[18]

Sven Laur, Jan Willemson, and Bingsheng Zhang. 2011. Round-efficient oblivious database manipulation. In Proc. ISC'11. 262--277.

[19]

Ping Lin and K Selçuk Candan. 2004. Hiding traversal of tree structured data from untrusted data stores. In Proc. WOSIS'04. 314.

[20]

Paulo Martins, Leonel Sousa, and Artur Mariano. 2017. A survey on fully homomorphic encryption: An engineering perspective. CSUR 50, 6 (2017), 83.

Digital Library

[21]

Paulo Martins, Leonel Sousa, and Artur Mariano. 2018. A survey on fully homomorphic encryption: An engineering perspective. CSUR 50, 6 (2018), 83.

Digital Library

[22]

Xianrui Meng, Haohan Zhu, and George Kollios. 2018. Top-k query processing on encrypted databases with strong security guarantees. In Proc. ICDE'18. 353--364.

[23]

Oliver Müller, Iris Junglas, Jan vom Brocke, and Stefan Debortoli. 2016. Utilizing big data analytics for information systems research: challenges, promises and guidelines. European Journal of Information Systems 25, 4 (2016), 289--302.

[24]

Otto Mutzbauer. 1999. Normal forms of matrices with applications to almost completely decomposable groups. In Abelian Groups and Modules. Springer, 121--134.

[25]

Trygve Nagell. 1951. Introduction to number theory. New York (1951).

[26]

Muhammad Naveed, Seny Kamara, and Charles V Wright. 2015. Inference attacks on property-preserving encrypted databases. In Proc. CCS'15. 644.

Digital Library

[27]

Olga Ohrimenko, Michael T Goodrich, Roberto Tamassia, and Eli Upfal. 2014. The Melbourne shuffle: Improving oblivious storage in the cloud. In Proc. ICALP. 556.

[28]

Olga Ohrimenko, Felix Schuster, Cédric Fournet, Aastha Mehta, Sebastian Nowozin, Kapil Vaswani, and Manuel Costa. 2016. Oblivious Multi-Party Machine Learning on Trusted Processors. In Proc. USENIX Security'16. 619--636.

[29]

Pascal Paillier. 1999. Public-key cryptosystems based on composite degree residuosity classes. In Proc. EUROCRYPT'99. Springer, 223--238.

[30]

Sarvar Patel, Giuseppe Persiano, and Kevin Yeo. 2017. CacheShuffle: An Oblivious Shuffle Algorithm Using Caches. arXiv preprint arXiv:1705.07069 (2017).

[31]

Andreas Peter, Erik Tews, and Stefan Katzenbeisser. 2013. Efficiently outsourcing multiparty computation under multiple keys. TIFS 8, 12 (2013), 2046--2058.

[32]

Arnon Rosenthal, Peter Mork, Maya Hao Li, Jean Stanford, David Koester, and Patti Reynolds. 2010. Cloud computing: a new business paradigm for biomedical information sharing. Journal of biomedical informatics 43, 2 (2010), 342--353.

Digital Library

[33]

Tim Ruffing, Pedro Moreno-Sanchez, and Aniket Kate. 2014. Coinshuffle: Practical decentralized coin mixing for bitcoin. In Proc. ESORICS'14. Springer, 345--364.

[34]

Fahad Shaon, Murat Kantarcioglu, Zhiqiang Lin, and Latifur Khan. 2017. SGX-BigMatrix: A Practical Encrypted Data Analytic Framework With Trusted Processors. In Proc. CCS'17. ACM, 1211--1228.

Digital Library

[35]

Tomas Skripcak, Claus Belka, Walter Bosch, Carsten Brink, Thomas Brunner, Volker Budach, Daniel Büttner, Jürgen Debus, Andre Dekker, Cai Grau, et al. 2014. Creating a data exchange strategy for radiotherapy research: towards federated databases and anonymised public datasets. Radiotherapy and Oncology 113, 3 (2014), 303--309.

[36]

Jun Tang, Yong Cui, Qi Li, Kui Ren, Jiangchuan Liu, and Rajkumar Buyya. 2016. Ensuring security and privacy preservation for cloud data services. CSUR 49, 1 (2016), 13.

Digital Library

[37]

Marc Tiehuis. [n.d.]. libhcs. https://github.com/tiehuis/libhcs.

[38]

Dong Xie, Guanru Li, Bin Yao, Xuan Wei, Xiaokui Xiao, Yunjun Gao, and Minyi Guo. 2016. Practical private shortest path computation based on oblivious storage. In Proc. ICDE'16. 361--372.

[39]

Zhang Zhilin, Wang Ke, Lin Weipeng, Fu Ada Wai-Chee, and Wong Raymond Chi-Wing. 2019. Practical Access Pattern Privacy by Combining PIR and Oblivious Shuffle. In Proc. CIKM '19. ACM.

[40]

Jan Henrik Ziegeldorf, Roman Matzutt, Martin Henze, Fred Grossmann, and Klaus Wehrle. 2018. Secure and anonymous decentralized Bitcoin mixing. Future Generation Computer Systems 80 (2018), 448--466.

Digital Library

Cited By

Duan SLiu HGu L(2023)A searchable encryption scheme with hidden search pattern and access pattern on distributed cloud systemPeer-to-Peer Networking and Applications10.1007/s12083-023-01488-816:4(1716-1738)Online publication date: 25-May-2023
https://doi.org/10.1007/s12083-023-01488-8
Zhong RZhang QZhao Y(2022)Research on Enterprise Financial Accounting Information Security Model Based on Big DataWireless Communications & Mobile Computing10.1155/2022/79298462022Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1155/2022/7929846
Lin WWang KZhang ZFu AWong RLong CMiao C(2022)Towards Secure and Efficient Equality Conjunction Search Over Outsourced DatabasesIEEE Transactions on Cloud Computing10.1109/TCC.2020.297517510:2(1445-1461)Online publication date: 1-Apr-2022
https://doi.org/10.1109/TCC.2020.2975175
Show More Cited By

Index Terms

Repeatable Oblivious Shuffling of Large Outsourced Data Blocks
1. Security and privacy
  1. Database and storage security
    1. Management and querying of encrypted data
  2. Security services
    1. Privacy-preserving protocols

Recommendations

Verifiable Computation on Outsourced Encrypted Data
Computer Security - ESORICS 2014
Abstract
On one hand, homomorphic encryption allows a cloud server to perform computation on outsourced encrypted data but provides no verifiability that the computation is correct. On the other hand, homomorphic authenticator, such as homomorphic ...
New verifiable outsourced computation scheme for an arbitrary function

We study the construction of efficient verifiable outsourced computation for arbitrary functions. We improve previous verifiable outsourced computation schemes for arbitrary functions by using hybrid encryption based on fully homomorphic encryption and ...
An efficient and secure data sharing framework using homomorphic encryption in the cloud
Cloud-I '12: Proceedings of the 1st International Workshop on Cloud Intelligence

Due to cost-efficiency and less hands-on management, data owners are outsourcing their data to the cloud which can provide access to the data as a service. However, by outsourcing their data to the cloud, the data owners lose control over their data as ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SoCC '19: Proceedings of the ACM Symposium on Cloud Computing

November 2019

503 pages

ISBN:9781450369732

DOI:10.1145/3357223

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 November 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Conference

SoCC '19

Sponsor:

SoCC '19: ACM Symposium on Cloud Computing

November 20 - 23, 2019

CA, Santa Cruz, USA

Acceptance Rates

SoCC '19 Paper Acceptance Rate 39 of 157 submissions, 25%;

Overall Acceptance Rate 169 of 722 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
170
Total Downloads

Downloads (Last 12 months)16
Downloads (Last 6 weeks)7

Reflects downloads up to 23 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Duan SLiu HGu L(2023)A searchable encryption scheme with hidden search pattern and access pattern on distributed cloud systemPeer-to-Peer Networking and Applications10.1007/s12083-023-01488-816:4(1716-1738)Online publication date: 25-May-2023
https://doi.org/10.1007/s12083-023-01488-8
Zhong RZhang QZhao Y(2022)Research on Enterprise Financial Accounting Information Security Model Based on Big DataWireless Communications & Mobile Computing10.1155/2022/79298462022Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1155/2022/7929846
Lin WWang KZhang ZFu AWong RLong CMiao C(2022)Towards Secure and Efficient Equality Conjunction Search Over Outsourced DatabasesIEEE Transactions on Cloud Computing10.1109/TCC.2020.297517510:2(1445-1461)Online publication date: 1-Apr-2022
https://doi.org/10.1109/TCC.2020.2975175
Mardi DTanwar SHowlader J(2021)Multiparty protocol that usually shufflesSECURITY AND PRIVACY10.1002/spy2.1764:6Online publication date: 9-Jun-2021
https://doi.org/10.1002/spy2.176

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents