An Observation on the Randomness Assumption over Lattices
An Observation on the Randomness Assumption over Lattices
复制标题
格上随机性假设的观察
DOI：
10.23919/isita.2018.8664341
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Tadanori Teruya
中科院分区：
文献类型：
--
作者：
Tadanori Teruya
Schnorr（STACS 2003）引入了格上的随机性假设（RA）来对采样算法（SA）的行为进行建模。SA用于随机采样缩减算法及其变体中，以有效地生成相对较短的向量。假设RA的有效性，Jakinase和Kashiwabara（JIP 2015，Vol.23，No.1）提出了由SA生成的格向量的平方长度的估计，以及有效地减少格基的策略。然而，最近，一些研究人员指出，RA可能不成立，没有提供任何数字证据。因此，在本文中，我们提供了一个简单的数值实验，通过SA的行为来研究RA的可信度。我们的实验结果表明，RA描述了SA的许多行为。我们注意到，根据Ludwig的观察（达姆施塔特工业大学博士论文2015），我们的结果捕获了RA不成立的地方。我们的结论是，虽然RA不能说是完全举行，它似乎是捕捉SA在实践中的行为在一定程度上。
The randomness assumption (RA) over lattices was introduced by Schnorr (STACS 2003) to model the behavior of sampling algorithms (SAs). SAs are used in random sampling reduction algorithms and their variants to efficiently generate relatively short vectors. Assuming the validity of RA, Fukase and Kashiwabara (JIP 2015, Vol.23, No.1) proposed an estimation of the squared length of lattice vectors generated by SA, and a strategy to reduce lattice bases efficiently. However, recently, several researchers pointed out that RA might not hold without providing any numerical evidence of their claim. Therefore, in this paper, we provide a simple numerical experiment to investigate the trustworthiness of RA through the behavior of SA. Our experimental result shows that RA describes many of the behaviors of SA. We note that ac-cording to the observation made by Ludwig (TU Darmstadt PhD Thesis 2015), our result captures where RA does not hold. We conclude that although RA cannot be said to completely hold, it seems to be capturing the behavior of SA in practice to some extent.