Summary
The 2018 International Symposium on Information Theory and Its Applications　(ISITA2018)
2018
Session Number:Tu-AM-1-2
Session:
Number:Tu-AM-1-2.2
An Observation on the Randomness Assumption over Lattices
Tadanori Teruya,
pp.311-315
Publication Date:2018/10/18
Online ISSN:2188-5079
DOI:10.34385/proc.55.Tu-AM-1-2.2
PDF download
Summary:
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 according to the observation made by Ludwig (TU Darm- stadt 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.