research-article

Efficient Oblivious Permutation via the Waksman Network

Authors:

William Holland,

Olga Ohrimenko,

Anthony WirthAuthors Info & Claims

ASIA CCS '22: Proceedings of the 2022 ACM on Asia Conference on Computer and Communications Security

Pages 771 - 783

https://doi.org/10.1145/3488932.3497761

Published: 30 May 2022 Publication History

Abstract

Memory accesses to data stored on an untrusted server are known to leak information, even if the data is encrypted. The oblivious permutation (OP) is a key primitive for algorithms and protocols that are designed to hide these client accesses to the server. An OP algorithm permutes outsourced data blocks according to a given permutation without revealing the permutation to the server.

Existing solutions strive to use only O (B) bits of client memory when permuting n blocks each of B bits. State-of-the-art O (B) bit solutions, require an optimal O (n log n) I/Os to complete. However, the hidden constant factor is at least $19600$. In this work, we depart from this memory constraint and, in pursuit of an I/O efficient algorithm, consider the context of cloud storage where a client can have a larger amount of private memory.

We propose an algorithm, WaksmanOP, that uses 2n + o(n) + 2B bits of client storage and permutes data in at most 4n log n - 3.6n I/Os. WaksmanOP is based on the Waksman network and involves a novel routing algorithm that carefully configures network switch settings using small client space. We implement WaksmanOP and compare it with existing solutions. Compared to practical methods based on sorting, WaksmanOP reduces the number of I/Os by a log n factor and uses significantly less client space than methods based on shuffling for large values of B. (e.g., 41MB vs. 6.4GB of private memory to permute 16TB of data).

References

[1]

Miklós Ajtai, János Komlós, and Endre Szemerédi. 1983. An O(n log n) sorting network. In ACM Symposium on Theory of Computing (STOC). 1--9.

Digital Library

[2]

Joshua Allen, Bolin Ding, Janardhan Kulkarni, Harsha Nori, Olga Ohrimenko, and Sergey Yekhanin. 2019. An algorithmic framework for differentially private data analysis on trusted processors. Advances in Neural Information Processing Systems (NIPS), Vol. 32 (2019), 13657--13668.

[3]

Amazon. 2021. Using Amazon S3 storage classes. https://docs.aws.amazon.com/AmazonS3/latest/userguide/storage-class-intro.html. [Online; accessed 24-Jul-2021].

[4]

Ittai Anati, Shay Gueron, Simon Johnson, and Vincent Scarlata. 2013. Innovative Technology for CPU Based Attestation and Sealing. In Workshop on Hardware and Architectural Support for Security and Privacy (HASP), Vol. 13. 7.

[5]

Gilad Asharov, TH Hubert Chan, Kartik Nayak, Rafael Pass, Ling Ren, and Elaine Shi. 2020 a. Bucket Oblivious Sort: An Extremely Simple Oblivious Sort. In Symposium on Simplicity in Algorithms. 8--14.

[6]

Gilad Asharov, Ilan Komargodski, Wei-Kai Lin, Kartik Nayak, Enoch Peserico, and Elaine Shi. 2020 b. OptORAMa: Optimal Oblivious RAM. In Annual International Conference on the Theory and Applications of Cryptographic Techniques (EuroCrypt). 403--432.

[7]

Kenneth E Batcher. 1968. Sorting networks and their applications. In Spring Joint Computer Conf. 307--314.

Digital Library

[8]

Bruno Beauquier and E Darrot. 2002. On arbitrary size Waksman networks and their vulnerability. Parallel Processing Letters, Vol. 12 (2002), 287--296.

[9]

Mihir Bellare and Phillip Rogaway. 2005. Introduction to modern cryptography. Ucsd Cse, Vol. 207 (2005), 207.

[10]

Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, and Eran Tromer. 2013. Fast Reductions from RAMs to Delegatable Succinct Constraint Satisfaction Problems: Extended Abstract. In Conference on Innovations in Theoretical Computer Science (ITCS). 401--414.

Digital Library

[11]

Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer, and Madars Virza. 2014. Succinct non-interactive zero knowledge for a von Neumann architecture. In USENIX Security Symposium. 781--796.

Digital Library

[12]

Vincent Bindschaedler, Muhammad Naveed, Xiaorui Pan, XiaoFeng Wang, and Yan Huang. 2015. Practicing oblivious access on cloud storage: the gap, the fallacy, and the new way forward. In ACM SIGSAC Conference on Computer and Communications Security (CCS). 837--849.

Digital Library

[13]

Andrea Bittau, Úlfar Erlingsson, Petros Maniatis, Ilya Mironov, Ananth Raghunathan, David Lie, Mitch Rudominer, Ushasree Kode, Julien Tinnes, and Bernhard Seefeld. 2017. Prochlo: Strong privacy for analytics in the crowd. In Symposium on Operating Systems Principles (SOSP). 441--459.

Digital Library

[14]

Ferdinand Brasser, Urs Müller, Alexandra Dmitrienko, Kari Kostiainen, Srdjan Capkun, and Ahmad-Reza Sadeghi. 2017. Software Grand Exposure: SGX Cache Attacks Are Practical. In USENIX Workshop on Offensive Technologies (WOOT).

Digital Library

[15]

Victor Costan, Ilia Lebedev, and Srinivas Devadas. 2016. Sanctum: Minimal hardware extensions for strong software isolation. In USENIX Security Symposium. 857--874.

[16]

Artur Czumaj. 2015. Random permutations using switching networks. In ACM Symposium on Theory of Computing (STOC). 703--712.

Digital Library

[17]

Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Abhradeep Thakurta. 2019. Amplification by shuffling: From local to central differential privacy via anonymity. In ACM-SIAM Symposium on Discrete Algorithms (SODA). 2468--2479.

[18]

Badih Ghazi, Noah Golowich, Ravi Kumar, Rasmus Pagh, and Ameya Velingker. 2021. On the Power of Multiple Anonymous Messages: Frequency Estimation and Selection in the Shuffle Model of Differential Privacy. In Annual International Conference on the Theory and Applications of Cryptographic Techniques (EuroCrypt). 463--488.

[19]

Oded Goldreich and Rafail Ostrovsky. 1996. Software protection and simulation on oblivious RAMs. Journal of the ACM (JACM), Vol. 43, 3 (1996), 431--473.

Digital Library

[20]

Michael T Goodrich. 2014. Zig-zag sort: A simple deterministic data-oblivious sorting algorithm running in O (n log n) time. In ACM Symposium on Theory of Computing (STOC). 684--693.

Digital Library

[21]

Michael T Goodrich and Michael Mitzenmacher. 2011. Privacy-preserving access of outsourced data via oblivious RAM simulation. In International Colloquium on Automata, Languages, and Programming (ICALP). Springer, 576--587.

[22]

Michael T. Goodrich, Michael Mitzenmacher, Olga Ohrimenko, and Roberto Tamassia. 2012a. Practical Oblivious Storage. In ACM Conference on Data and Application Security and Privacy (CODASPY). 13--24.

[23]

Michael T. Goodrich, Michael Mitzenmacher, Olga Ohrimenko, and Roberto Tamassia. 2012b. Privacy-Preserving Group Data Access via Stateless Oblivious RAM Simulation. In ACM-SIAM Symposium on Discrete Algorithms (SODA). 157--167.

[24]

Intel. [n.d.]. Intel Xeon Processor Scalable Family Technical Overview. https://software.intel.com/content/www/us/en/develop/articles/intel-xeon-processor-scalable-family-technical-overview.html. [Online; accessed 24-Jul-2021].

[25]

Mohammad Saiful Islam, Mehmet Kuzu, and Murat Kantarcioglu. 2012. Access pattern disclosure on searchable encryption: ramification, attack and mitigation. In The Network and Distributed System Security Symposium (NDSS), Vol. 20.

[26]

Pratheek Karnati. 2018. Data-in-use protection on IBM Cloud using Intel SGX . https://www.ibm.com/cloud/blog/data-use-protection-ibm-cloud-using-intel-sgx.

[27]

Eyal Kushilevitz, Steve Lu, and Rafail Ostrovsky. 2012. On the (in)Security of Hash-based Oblivious RAM and a New Balancing Scheme. In ACM-SIAM Symposium on Discrete Algorithms (SODA). 143--156.

[28]

Wei-Kai Lin, Elaine Shi, and Tiancheng Xie. 2019. Can we overcome the $n łog n$ barrier for oblivious sorting?. In ACM-SIAM Symposium on Discrete Algorithms (SODA). 2419--2438.

[29]

Fangfei Liu, Yuval Yarom, Qian Ge, Gernot Heiser, and Ruby B Lee. 2015. Last-level cache side-channel attacks are practical. In IEEE Symposium on Security and Privacy (S&P). 605--622.

Digital Library

[30]

Microsoft. [n.d.]. Azure confidential computing. https://azure.microsoft.com/en-au/solutions/confidential-compute. [Online; accessed 24-Jul-2021].

[31]

Ahmad Moghimi, Gorka Irazoqui, and Thomas Eisenbarth. 2017. CacheZoom: How SGX Amplifies the Power of Cache Attacks. In International Conference on Cryptographic Hardware and Embedded Systems (CHES). 69--90.

[32]

David Nassimi and Sartaj Sahni. 1979. Bitonic sort on a mesh-connected parallel computer. IEEE Trans. Comput. 1 (1979), 2--7.

Digital Library

[33]

Olga Ohrimenko, Michael T Goodrich, Roberto Tamassia, and Eli Upfal. 2014. The Melbourne shuffle: Improving oblivious storage in the cloud. In International Colloquium on Automata, Languages and Programming (ICALP). 556--567.

[34]

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 USENIX Security Symposium . 619--636.

[35]

Sarvar Patel, Giuseppe Persiano, Mariana Raykova, and Kevin Yeo. 2018b. PanORAMa: Oblivious RAM with logarithmic overhead. In IEEE Symposium on Foundations of Computer Science (FOCS). IEEE, 871--882.

[36]

Sarvar Patel, Giuseppe Persiano, and Kevin Yeo. 2018a. CacheShuffle: A Family of Oblivious Shuffles. In International Colloquium on Automata, Languages and Programming (ICALP).

[37]

SCIPR Lab project.[n.d.]. libsnark: a Clibrary for zkSNARK proofs. https://github.com/scipr-lab/libsnark. [Online; accessed 24-Jul-2021].

[38]

Ling Ren, Christopher Fletcher, Albert Kwon, Emil Stefanov, Elaine Shi, Marten Van Dijk, and Srinivas Devadas. 2015. Constants Count: Practical Improvements to Oblivious RAM. In USENIX Security Symposium. 415--430.

Digital Library

[39]

Sajin Sasy, Sergey Gorbunov, and Christopher W. Fletcher. 2018. ZeroTrace: Oblivious Memory Primitives from Intel SGX. In The Network and Distributed System Security Symposium (NDSS).

[40]

Elaine Shi. 2020. Path oblivious heap: Optimal and practical oblivious priority queue. In IEEE Symposium on Security and Privacy (S&P). 842--858.

[41]

Emil Stefanov, Elaine Shi, and Dawn Song. 2011. Towards practical oblivious RAM. In The Network and Distributed System Security Symposium (NDSS).

[42]

Emil Stefanov, Marten Van Dijk, Elaine Shi, Christopher Fletcher, Ling Ren, Xiangyao Yu, and Srinivas Devadas. 2013. Path ORAM: an extremely simple oblivious RAM protocol. In ACM SIGSAC conference on Computer & communications security (CCS). 299--310.

Digital Library

[43]

Abraham Waksman. 1968. A permutation network. Journal of the ACM (JACM), Vol. 15, 1 (1968), 159--163.

Digital Library

[44]

Yuanzhong Xu, Weidong Cui, and Marcus Peinado. 2015. Controlled-Channel Attacks: Deterministic Side Channels for Untrusted Operating Systems. In IEEE Symposium on Security and Privacy (S&P). 640--656.

[45]

Samee Zahur, Xiao Wang, Mariana Raykova, Adrià Gascón, Jack Doerner, David Evans, and Jonathan Katz. 2016. Revisiting square-root ORAM: efficient random access in multi-party computation. In IEEE Symposium on Security and Privacy (S&P). 218--234.

Cited By

Sasy SJohnson AGoldberg IMeng WJensen CCremers CKirda E(2023)Waks-On/Waks-Off: Fast Oblivious Offline/Online Shuffling and Sorting with Waksman NetworksProceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security10.1145/3576915.3623133(3328-3342)Online publication date: 15-Nov-2023
https://dl.acm.org/doi/10.1145/3576915.3623133

Index Terms

Efficient Oblivious Permutation via the Waksman Network
1. Security and privacy
  1. Database and storage security
    1. Management and querying of encrypted data

Recommendations

Waks-On/Waks-Off: Fast Oblivious Offline/Online Shuffling and Sorting with Waksman Networks
CCS '23: Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security

As more privacy-preserving solutions leverage trusted execution environments (TEEs) like Intel SGX, it becomes pertinent that these solutions can by design thwart TEE side-channel attacks that research has brought to light. In particular, such solutions ...
Tighter upper bound for sorting permutations with prefix transpositions

Permutations are sequences where each symbol in the given alphabet Σ appears exactly once. A transposition is an operation that exchanges two adjacent sublists in a permutation; if one of these sublists is restricted to be a prefix then one obtains a ...
Improved upper bound for sorting permutations by prefix transpositions
Abstract
Modelling of chromosomes with permutations has triggered the research of sorting permutations using global rearrangement operations in computational molecular biology. One such rearrangement is transposition which swaps two adjacent ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ASIA CCS '22: Proceedings of the 2022 ACM on Asia Conference on Computer and Communications Security

May 2022

1291 pages

ISBN:9781450391405

DOI:10.1145/3488932

General Chairs:
Yuji Suga
Internet Initiative Japan Inc., Japan
,
Kouichi Sakurai
Kyushu University, Japan
,
Program Chairs:
Xuhua Ding
Singapore Management University, Singapore
,
Kazue Sako
Waseda University, Japan

Copyright © 2022 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 ACM 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

SIGSAC: ACM Special Interest Group on Security, Audit, and Control

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 May 2022

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Australian Research Council

Conference

ASIA CCS '22

Sponsor:

SIGSAC

ASIA CCS '22: ACM Asia Conference on Computer and Communications Security

May 30 - June 3, 2022

Nagasaki, Japan

Acceptance Rates

Overall Acceptance Rate 418 of 2,322 submissions, 18%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
269
Total Downloads

Downloads (Last 12 months)74
Downloads (Last 6 weeks)10

Reflects downloads up to 16 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Sasy SJohnson AGoldberg IMeng WJensen CCremers CKirda E(2023)Waks-On/Waks-Off: Fast Oblivious Offline/Online Shuffling and Sorting with Waksman NetworksProceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security10.1145/3576915.3623133(3328-3342)Online publication date: 15-Nov-2023
https://dl.acm.org/doi/10.1145/3576915.3623133

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