• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Applied cryptography and network security >Sampling from Arbitrary Centered Discrete Gaussians for Lattice-Based Cryptography
【24h】

Sampling from Arbitrary Centered Discrete Gaussians for Lattice-Based Cryptography

机译：从任意中心离散高斯样本进行基于格的加密的采样

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

摘要

Non-Centered Discrete Gaussian sampling is a fundamental building block in many lattice-based constructions in cryptography, such as signature and identity-based encryption schemes. On the one hand, the center-dependent approaches, e.g. cumulative distribution tables (CDT), Knuth-Yao, the alias method, discrete Zigurat and their variants, are the fastest known algorithms to sample from a discrete Gaussian distribution. However, they use a relatively large precomputed table for each possible real center in [0,1) making them impracticable for non-centered discrete Gaussian sampling. On the other hand, rejection sampling allows to sample from a discrete Gaussian distribution for all real centers without prohibitive precomputation cost but needs costly floating-point arithmetic and several trials per sample. In this work, we study how to reduce the number of centers for which we have to precompute tables and propose a non-centered CDT algorithm with practicable size of precomputed tables as fast as its centered variant. Finally, we provide some experimental results for our open-source C++ implementation indicating that our sampler increases the rate of Peikert's algorithm for sampling from arbitrary lattices (and cosets) by a factor 3 with precomputation storage up to 6.2 MB.
机译：非中心离散高斯采样是密码术中许多基于格的结构（例如，基于签名和基于身份的加密方案）中的基本构建块。一方面，依赖中心的方法例如累积分布表（CDT），Knuth-Yao，别名方法，离散Zigurat及其变体是从离散高斯分布中采样的最快已知算法。但是，它们在[0,1）中为每个可能的真实中心使用一个相对较大的预先计算的表，因此对于非中心离散高斯采样来说，它们是不可行的。另一方面，剔除采样允许从所有真实中心的离散高斯分布中采样，而不会产生过高的预计算成本，但需要昂贵的浮点算法和每个采样多次测试。在这项工作中，我们研究如何减少必须为其预先计算表的中心的数量，并提出一种非中心CDT算法，其可行的大小与中心变量一样快。最后，我们为开源C ++实现提供了一些实验结果，表明我们的采样器将Peikert算法从任意晶格（和共集）采样的速率提高了3倍，预计算存储高达6.2 MB。

著录项

  • 来源
  • 会议地点 Kanaxzawa(JP)
  • 作者

    Carlos Aguilar-Melchor; Martin R. Albrecht; Thomas Ricosset;

  • 作者单位

    INP ENSEEIHT, IRIT-CNRS, Universite de Toulouse, Toulouse, France;

    Information Security Group, Royal Holloway, University of London, London, UK;

    INP ENSEEIHT, IRIT-CNRS, Universite de Toulouse, Toulouse, France,Thales Communications Security, Gennevilhers, France;

  • 会议组织
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号