...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of Cryptology >Efficient and Scalable Universal Circuits
【24h】

Efficient and Scalable Universal Circuits

机译：高效且可扩展的通用电路

获取原文
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Abstract A universal circuit (UC) can be programmed to simulate any circuit up to a given size n by specifying its program inputs. It provides elegant solutions in various application scenarios, e.g., for private function evaluation (PFE) and for improving the flexibility of attribute-based encryption schemes. The asymptotic lower bound for the size of a UC is Ω(nlogn)documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$Omega (nlog n)$$end{document}, and Valiant (STOC’76) provided two theoretical constructions, the so-called 2-way and 4-way UCs (i.e., recursive constructions with 2 and 4 substructures), with asymptotic sizes ∼5nlog2ndocumentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$${sim },5nlog _2n$$end{document} and ∼4.75nlog2ndocumentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$${sim },4.75nlog _2n$$end{document}, respectively. In this article, we present and extend our results published in (Kiss and Schneider EUROCRYPT’16) and (Günther et al. ASIACRYPT’17). We validate the practicality of Valiant’s UCs by realizing the 2-way and 4-way UCs in our modular open-source implementation. We also provide an example implementation for PFE using these size-optimized UCs. We propose a 2/4-hybrid approach that combines the 2-way and the 4-way UCs in order to minimize the size of the resulting UC. We realize that the bottleneck in universal circuit generation and programming becomes the memory consumption of the program since the whole structure of size O(nlogn)documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$${mathcal {O}}(nlog n)$$end{document} is handled by the algorithms in memory. In this work, we overcome this by designing novel scalable algorithms for the UC generation and programming. Both algorithms use only O(n)documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$${mathcal {O}}(n)$$end{document} memory at any point in time. We prove the practicality of our scalable design with a scalable proof-of-concept implementation for generating Valiant’s 4-way UC. We note that this can be extended to work with optimized building blocks analogously. Moreover, we substantially improve the size of our UCs by including and implementing the recent optimization of Zhao et al. (ASIACRYPT’19) that reduces the asymptotic size of the 4-way UC to ∼4.5nlog2ndocumentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$${sim },4.5nlog _2n$$end{document}. Furthermore, we include their optimization in the implementation of our 2/4-hybrid UC which yields the smallest UC construction known so far.
机译：摘要可以通过指定其程序输入来编程通用电路（UC）以模拟到给定大小N的任何电路。它在各种应用场景中提供优雅的解决方案，例如，用于私有函数评估（PFE），用于提高基于属性的加密方案的灵活性。 UC大小的渐近下限是ω（nlogn） documentClass [12pt] {minimal} usepackage {ammath} usepackage {isysym} usepackage {amsfonts} usepackage {amssys} usepackage {amsbsy} usepackage {mathrsfs} usepackage {supmeek} setLength { oddsidemargin} { - 69pt} begin {document} $$$ oomega（n log n）$$ end {document}，valiant（stoc'76）提供了两个理论结构，所谓的双向和4路UCS（即，具有2和4个子结构的递归结构），具有渐近大小~5nlog2n documentClass [12pt] {minimal} usepackage {ammath} usepackage {isysym} usepackage {amsfonts} usepackage {amssymb} usepackage {amsbsy} usepackage {mathrsfs} usepackage {supmeek} setLength { oddsideDemargin} { - 69pt} begin {document} $$ { sim} ，5n log _2n $$$ ~4.75nlog2n documentClass [12pt] {minimal} usepackage {ammath} usepackage {amsfonts} usepackage {amssys} usepackage {amsbsy} usepackage {mathrsfs } usepackage {supmeek} setLength { oddsideDemargin} { - - 69pt } begin {document} $$ { sim} ，4.75n log _2n $$ end {document}。在本文中，我们展示并扩展了（Kiss和Schneider Eurocrypt'16）发表的结果（Günther等人。亚洲秘密'17）。我们通过在模块化开源实现中实现双向和4路UC来验证Valiant的UCS的实用性。我们还提供了使用这些大小优化的UCS的PFE的示例实现。我们提出了一种2/4混合方法，将双向和4路UC组合起来以最小化所产生的UC的大小。我们意识到通用电路生成和编程中的瓶颈成为程序的内存消耗，因为大小O（nlogn） documentClass [12pt] {minimal} usepackage {ammath} usepackage {isysym} usepackage {amsfonts } usepackage {amssymb} usepackage {amsbsy} usepackage {mathrsfs} usepackage {supmeek} setLength { oddsideDemargin} { - 69pt} begin {document} $$ { mathcal {o}}（n log n ）$$ 结束{document}由内存中的算法处理。在这项工作中，我们通过为UC生成和编程设计新颖的可扩展算法来克服这一点。两个算法仅使用O（n） documentClass [12pt] {minimal} usepackage {ammath} usepackage {isysym} usepackage {amsfonts} usepackage {amssys} usepackage {mathrsfs} usepackage {mathrsfs} usepackage {supmeek } setLength { oddsidemargin} { - 69pt} begin {document} $$ { mathcal {o}}（n）$$ end {document}内存在任何时间点。我们通过可扩展的概念证明实现来证明我们可扩展设计的实用性，用于生成Valiant的4路UC。我们注意到，这可以扩展到类似于优化的构建块。此外，我们通过包括并实施最近的Zhao等人的优化，大大提高了UCS的大小。 （asiancrypt'19）将4路UC的渐近大小减少到〜4.5nlog2n documentClass [12pt] {minimal} usepackage {ammath} usepackage {isysym} usepackage {amsfonts} usepackage {amssymb} usepackage {amsbsy} usepackage {mathrsfs} usepackage {supmeek} setLength { oddsidemargin} {-69pt} begin {document} $$ { sim} ，4.5n log _2n $$ end {document}。此外，我们在执行我们的2/4混合UC的实施中的优化，从而产生到目前为止已知的最小UC建设。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号