检索结果-内蒙古大学图书馆

JOURNAL OF THE ACM 2016年第1期63卷 3-3页

作者： Bilardi, Gianfranco Pietracaprina, Andrea Pucci, Geppino Scquizzato, Michele Silvestri, Francesco Univ Padua Dept Informat Engn I-35131 Padua Italy Univ Padua I-35131 Padua Italy

A framework is proposed for the design and analysis of network-oblivious algorithms, namely algorithms that can run unchanged, yet efficiently, on a variety of machines characterized by different degrees of parallelism and communication capabilities. The framework prescribes that a network-oblivious algorithm be specified on a parallel model of computation where the only parameter is the problem's input size, and then evaluated on a model with two parameters, capturing parallelism granularity and communication latency. It is shown that for a wide class of network-oblivious algorithms, optimality in the latter model implies optimality in the decomposable bulk synchronous parallel model, which is known to effectively describe a wide and significant class of parallel platforms. The proposed framework can be regarded as an attempt to port the notion of obliviousness, well established in the context of cache hierarchies, to the realm of parallel computation. Its effectiveness is illustrated by providing optimal network-oblivious algorithms for a number of key problems. Some limitations of the oblivious approach are also discussed.

关键词： algorithms Theory Communication models of computation network locality oblivious algorithms parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Waks-On/Waks-Off: Fast oblivious Offline/Online Shuffling and Sorting with Waksman Networks 23

Waks-On/Waks-Off: Fast Oblivious Offline/Online Shuffling an...

引用

30th ACM SIGSAC Conference on Computer and Communications Security (ACM CCS)

作者： Sasy, Sajin Johnson, Aaron Goldberg, Ian Univ Waterloo Waterloo ON Canada US Naval Res Lab Washington DC USA

ISBN: (纸本)9798400700507

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 need to be fully oblivious to circumvent leaking private information through memory or timing side channels. In this work, we present fast fully oblivious algorithms for shuffling and sorting data. oblivious shuffling and sorting are two fundamental primitives that are frequently used for permuting data in privacy-preserving solutions. We present novel oblivious shuffling and sorting algorithms in the offline/online model such that the bulk of the computation can be done in an offline phase that is independent of the data to be permuted. The resulting online phase provides performance improvements over state-of-the-art oblivious shuffling and sorting algorithms both asymptotically (O(beta n log n) vs. O(beta n log(2) n)) and concretely (> 5x and > 3x speedups), when permuting n items each of size beta. Our work revisits Waksman networks, and it uses the key observation that setting the control bits of a Waksman network for a uniformly random shuffle is independent of the data to be shuffled. However, setting the control bits of a Waksman network efficiently and fully obliviously poses a challenge, and we provide a novel algorithm to this end. The total costs (inclusive of offline computation) of our WAKSSHUFFLE shuffling algorithm and our WAKSSORT sorting algorithm are lower than all other fully oblivious shuffling and sorting algorithms when the items are at least moderately sized (i.e., beta > 1400 B), and the performance gap only widens as the item sizes increase. Furthermore, WAKSSHUFFLE improves the online cost of oblivious shuffling by > 5x for shuffling 2(20) items of any size;similarly WAKSSHUFFLE+QS, our other sorting algorithm, provides > 2.7x speedups in the online cost of oblivious sorting.

关键词： oblivious algorithms trusted execution environments SGX

来源：评论

学校读者我要写书评

暂无评论

Advanced Composition Theorems for Differential obliviousness 15

Advanced Composition Theorems for Differential Obliviousness

引用

15th Innovations in Theoretical Computer Science Conference (ITCS)

作者： Zhou, Mingxun Zhao, Mengshi Chan, T-H Hubert Shi, Elaine Carnegie Mellon Univ Pittsburgh PA 15213 USA Univ Hong Kong Hong Kong Peoples R China

ISBN: (纸本)9783959773096

Differential obliviousness (DO) is a privacy notion which mandates that the access patterns of a program satisfy differential privacy. Earlier works have shown that in numerous applications, differential obliviousness allows us to circumvent fundamental barriers pertaining to fully oblivious algorithms, resulting in asymptotical (and sometimes even polynomial) performance improvements. Although DO has been applied to various contexts, including the design of algorithms, data structures, and protocols, its compositional properties are not explored until the recent work of Zhou et al. (Eurocrypt'23). Specifically, Zhou et al. showed that the original DO notion is not composable. They then proposed a refinement of DO called neighbor-preserving differential obliviousness (NPDO), and proved a basic composition for NPDO. In Zhou et al.'s basic composition theorem for NPDO, the privacy loss is linear in k for k-fold composition. In comparison, for standard differential privacy, we can enjoy roughly root k loss for k-fold composition by applying the well-known advanced composition theorem given an appropriate parameter range. Therefore, a natural question left open by their work is whether we can also prove an analogous advanced composition for NPDO. In this paper, we answer this question affirmatively. As a key step in proving an advanced composition theorem for NPDO, we define a more operational notion called symmetric NPDO which we prove to be equivalent to NPDO. Using symmetric NPDO as a stepping stone, we also show how to generalize NPDO to more general notions of divergence, resulting in Renyi-NPDO, zero-concentrated-NPDO, Gassian-NPDO, and g-NPDO notions. We also prove composition theorems for these generalized notions of NPDO.

关键词： Differential Privacy oblivious algorithms

来源：评论

学校读者我要写书评

暂无评论

oblivious Stacking and MAX k-CUT for Circle Graphs 13th

Oblivious Stacking and MAX k-CUT for Circle Graphs

引用

13th International Conference on Computational Logistics (ICCL)

作者： Olsen, Martin Aarhus Univ Dept Business Dev & Technol Aarhus Denmark

ISBN: (纸本)9783031165795;9783031165788

Stacking is an important process within logistics. Some notable examples of items to be stacked are steel bars or steel plates in a steel yard or containers in a container terminal or on a ship. We say that two items are conflicting if their storage time intervals overlap in which case one of the items needs to be rehandled if the items are stored at the same LIFO storage location. We consider the problem of stacking items using k LIFO locations with a minimum number of conflicts between items sharing a location. We present an extremely simple online stacking algorithm that is oblivious to the storage time intervals and storage locations of all other items when it picks a storage location for an item. The risk of assigning the same storage location to two conflicting items is proved to be of the order 1/k(2) under mild assumptions on the distribution of the storage time intervals for the items. Intuitively, it seems natural to pick a storage location uniformly at random in the oblivious setting implying a risk of 1/k so the risk for our algorithm is surprisingly low. Our results can also be expressed within the context of the MAX k-CUT problem for circle graphs. The results indicate that circle graphs on average have relatively big k-cuts compared to the total number of edges.

关键词： oblivious algorithms MAX k-CUT Stacking Circle graphs

来源：评论

学校读者我要写书评

暂无评论

Efficient oblivious Permutation via the Waksman Network 22

Efficient Oblivious Permutation via the Waksman Network

引用

17th ACM ASIA Conference on Computer and Communications Security 2022 (ACM ASIACCS)

作者： Holland, William Ohrimenko, Olga Wirth, Anthony Univ Melbourne Sch Comp & Informat Syst Melbourne Vic Australia

ISBN: (纸本)9781450391405

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 n 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.6 n 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).

关键词： oblivious algorithms permutations access pattern

来源：评论

学校读者我要写书评

暂无评论

A Practical Approach to the Secure Computation of the Moore-Penrose Pseudoinverse over the Rationals 18th

A Practical Approach to the Secure Computation of the Moore-...

引用

18th International Conference on Applied Cryptography and Network Security (ACNS)

作者： Bouman, Niek J. de Vreede, Niels Roseman Labs Breda Netherlands Tech Univ Eindhoven Eindhoven Netherlands

ISBN: (纸本)9783030578084;9783030578077

Solving linear systems of equations is a universal problem. In the context of secure multiparty computation (MPC), a method to solve such systems, especially for the case in which the rank of the system is unknown and should remain private, is an important building block. We devise an efficient and data-oblivious algorithm (meaning that the algorithm's execution time and branching behavior are independent of all secrets) for solving a bounded integral linear system of unknown rank over the rational numbers via the Moore-Penrose pseudoinverse, using finite-field arithmetic. I.e., we compute the Moore-Penrose inverse over a finite field of sufficiently large order, so that we can recover the rational solution from the solution over the finite field. While we have designed the algorithm with an MPC context in mind, it could be valuable also in other contexts where data-obliviousness is required, like secure enclaves in CPUs. Previous work by Cramer, Kiltz and Padro (CRYPTO 2007) proposes a constant-rounds protocol for computing the Moore-Penrose pseudoinverse over a finite field. The asymptotic complexity (counted as the number of secure multiplications) of their solution is O(m(4) + n(2)m), where m and n, m <= n, are the dimensions of the linear system. To reduce the number of secure multiplications, we sacrifice the constant-rounds property and propose a protocol for computing the Moore-Penrose pseudoinverse over the rational numbers in a linear number of rounds, requiring only O(m(2)n) secure multiplications. To obtain the common denominator of the pseudoinverse, required for constructing an integer-representation of the pseudoinverse, we generalize a result by Ben-Israel for computing the squared volume of a matrix. Also, we show how to precondition a symmetric matrix to achieve generic rank profile while preserving symmetry and being able to remove the preconditioner after it has served its purpose. These results may be of independent interest.

关键词： Secure multiparty computation Secure linear algebra Moore-Penrose pseudoinverse oblivious algorithms

来源：评论

学校读者我要写书评

暂无评论

Private and oblivious set and multiset operations

引用

INTERNATIONAL JOURNAL OF INFORMATION SECURITY 2016年第5期15卷 493-518页

作者： Blanton, Marina Aguiar, Everaldo Univ Notre Dame Dept Comp Sci & Engn Notre Dame IN 46556 USA

Privacy-preserving set operations are a popular research topic. Despite a large body of literature, the great majority of the available solutions are two-party protocols and expect that each participant knows her input set in the clear. In this work, we put forward a new framework for secure multi-party set and multiset operations in which the inputs can be arbitrarily partitioned among the participants, knowledge of an input (multi)set is not required for any party, and the secure set operations can be composed and can also be securely outsourced to third-party computation providers. In this framework, we construct a comprehensive suite of secure protocols for set operations and their various extensions. Our protocols are secure in the information-theoretic sense and are designed to minimize the round complexity. We then also build support for multiset operations by providing (i) a generic conversion from a multiset to a set, which makes the protocols for set operations applicable to multisets and (ii) direct instantiations of multiset operations of improved performance. All of our protocols have communication and computation complexity of and logarithmic round complexity for sets or multisets of size m, which compares favorably with prior work. Practicality of our solutions is shown through experimental results, and novel optimizations based on set compaction allow us to improve performance of our protocols in practice. Our protocols are secure in both semi-honest and malicious security models.

关键词： Set and multiset operations oblivious algorithms Secure multi-party computation Secret sharing oblivious sorting

来源：评论

学校读者我要写书评

暂无评论

C2CU: a CUDA C program generator for bulk execution of a sequential algorithm

引用

CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE 2017年第17期29卷

作者： Takafuji, Daisuke Nakano, Koji Ito, Yasuaki Bordim, Jacir Hiroshima Univ Dept Informat Engn Kagamiyama 1-4-1 Higashihiroshima 7398527 Japan Univ Brasilia Dept Comp Sci Brasilia DF Brazil

Several important tasks, including matrix computation, signal processing, sorting, dynamic programming, encryption, and decryption, can be performed by oblivious sequential algorithms. A sequential algorithm is oblivious if an address accessed at each time does not depend on the input data. A bulk execution of a sequential algorithm is to execute it for many independent inputs in turn or in parallel. A number of works have been devoted to design and implement parallel algorithms for a single input. However, none of these works evaluated the bulk execution performance of these algorithms. The first contribution of this paper is to present a time-optimal implementation for bulk execution of an oblivious sequential algorithm. Our second contribution is to develop a tool, named C2CU, which automatically generates a CUDA C program for a bulk execution of an oblivious sequential algorithm. The C2CU has been used to generate CUDA C programs for the bulk execution of the bitonic sorting, Floyd-Warshall, and Montgomery modulo multiplication algorithms. Compared to a sequential implementation on a single CPU, the generated CUDA C programs for the above algorithms run, respectively, 199, 54, and 78 times faster.

关键词： bulk execution CUDA GPGPU oblivious algorithms

来源：评论

学校读者我要写书评

暂无评论

GraphSC: Parallel Secure Computation Made Easy 36

GraphSC: Parallel Secure Computation Made Easy

引用

IEEE Symposium on Security and Privacy SP

作者： Nayak, Kartik Wang, Xiao Shaun Ioannidis, Stratis Weinsberg, Udi Taft, Nina Shi, Elaine Univ Maryland College Pk MD 20742 USA Yahoo Sunnyvale CA USA Facebook New York NY USA Google New York NY USA Technicolor Los Altos CA USA

ISBN: (纸本)9781467369497

We propose introducing modern parallel programming paradigms to secure computation, enabling their secure execution on large datasets. To address this challenge, we present GraphSC, a framework that (i) provides a programming paradigm that allows non-cryptography experts to write secure code;(ii) brings parallelism to such secure implementations;and (iii) meets the needs for obliviousness, thereby not leaking any private information. Using GraphSC, developers can efficiently implement an oblivious version of graph-based algorithms (including sophisticated data mining and machine learning algorithms) that execute in parallel with minimal communication overhead. Importantly, our secure version of graph-based algorithms incurs a small logarithmic overhead in comparison with the non-secure parallel version. We build GraphSC and demonstrate, using several algorithms as examples, that secure computation can be brought into the realm of practicality for big data analysis. Our secure matrix factorization implementation can process 1 million ratings in 13 hours, which is a multiple order-of-magnitude improvement over the only other existing attempt, which requires 3 hours to process 16K ratings.

关键词： graph algorithms oblivious algorithms parallel algorithms secure computation

来源：评论

学校读者我要写书评

暂无评论

ObliVM: A Programming Framework for Secure Computation 36

ObliVM: A Programming Framework for Secure Computation

引用

IEEE Symposium on Security and Privacy SP

作者： Liu, Chang Wang, Xiao Shaun Nayak, Kartik Huang, Yan Shi, Elaine Univ Maryland College Pk MD 20742 USA Indiana Univ Bloomington IN 47405 USA

ISBN: (纸本)9781467369497

We design and develop ObliVM, a programming framework for secure computation. ObliVM offers a domain-specific language designed for compilation of programs into efficient oblivious representations suitable for secure computation. ObliVM offers a powerful, expressive programming language and user-friendly oblivious programming abstractions. We develop various showcase applications such as data mining, streaming algorithms, graph algorithms, genomic data analysis, and data structures, and demonstrate the scalability of ObliVM to bigger data sizes. We also show how ObliVM significantly reduces development effort while retaining competitive performance for a wide range of applications in comparison with hand-crafted solutions. We are in the process of open-sourcing ObliVM and our rich libraries to the community (***), offering a reusable framework to implement and distribute new cryptographic algorithms.

关键词： Compiler oblivious algorithms oblivious RAM Programming Language Secure Computation Type System

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：