• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Parallel and Distributed Systems >On Acceleration and Scalability of Number Theoretic Private Information Retrieval
【24h】

On Acceleration and Scalability of Number Theoretic Private Information Retrieval

机译：数论私人信息检索的加速和可扩展性

获取原文
获取原文并翻译 | 示例
       
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We present scalable and parallel versions of Lipmaa's computationally-private information retrieval (CPIR) scheme  , which provides log-squared communication complexity. In the proposed schemes, instead of binary decision diagrams utilized in the original CPIR, we employ an octal tree based approach, in which non-sink nodes have eight child nodes. Using octal trees offers two advantages: i) a serial implementation of the proposed scheme in software is faster than the original scheme and ii) its bandwidth usage becomes less than the original scheme when the number of items in the data set is moderately high (e.g., 4,096 for 80-bit security level using Damgård-Jurik cryptosystem). In addition, we present a highly-optimized parallel algorithm for shared-memory multi-core/processor architectures, which minimizes the number of synchronization points between the cores. We show that the parallel implementation is about 50 times faster than the serial implementation for a data set with 4,096 items on an eight-core machine. Finally, we propose a hybrid algorithm that scales the CPIR scheme to larger data sets with small overhead in bandwidth complexity. We demonstrate that the hybrid scheme based on octal trees can lead to more than two orders of magnitude faster parallel implementations than serial implementations based on binary trees. Comparison with the original as well as the other schemes in the literature reveals that our scheme is the best in terms of bandwidth requirement.
机译：我们提出了Lipmaa的计算专用信息检索（CPIR）方案的可扩展和并行版本，该方案可提供对数平方的通信复杂性。在提出的方案中，我们采用了基于八进制树的方法，而不是原始CPIR中使用的二进制决策图，其中非宿节点具有八个子节点。使用八进制树有两个优点：i）在软件中以串行方式实施所提出的方案要比原始方案快；并且ii）当数据集中的项目数适度较高时（例如，其带宽使用量小于原始方案） （使用Damgård-Jurik密码系统的80位安全级别为4,096）。此外，我们为共享内存多核/处理器体系结构提供了一种高度优化的并行算法，该算法可最大程度地减少内核之间的同步点数量。我们显示，对于八核计算机上具有4,096个项目的数据集，并行实现比串行实现快50倍。最后，我们提出了一种混合算法，该算法可将CPIR方案扩展到较大的数据集，而带宽复杂度较小。我们证明，基于八进制树的混合方案可以比基于二进制树的串行实现更快两个数量级的并行实现。与原始方案以及文献中的其他方案的比较表明，就带宽要求而言，我们的方案是最好的。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号