Improved Algorithms for the Approximate k -List Problem in Euclidean Norm
作者： Gottfried Herold , Elena Kirshanova
DOI: 10.1007/978-3-662-54365-8_2
关键词: Euclidean domain 、 Computer science 、 Hash function 、 Algorithm 、 Euclidean distance 、 Euclidean shortest path 、 Space (mathematics)
摘要: We present an algorithm for the approximate k-List problem Euclidean distance that improves upon Bai-Laarhoven-Stehle (BLS) from ANTS’16. The improvement stems observation almost all solutions to form a particular configuration in n-dimensional space. Due special properties of configurations, it is much easier verify whether k-tuple forms rather than checking gives solution problem. Thus, phrasing as finding such configurations immediately better algorithm. Furthermore, search can be sped up using techniques Locality-Sensitive Hashing (LSH). Stated terms configuration-search, our LSH-like offers broader picture on previous LSH algorithms.
springer.com
sci-hub.st 参考文章(44)
Vadim Lyubashevsky, On Random High Density Subset Sums Electronic Colloquium on Computational Complexity. ,(2005)
David Wagner, The Boomerang Attack fast software encryption. pp. 156- 170 ,(1999) , 10.1007/3-540-48519-8_12
Shan Chen, Rodolphe Lampe, Jooyoung Lee, Yannick Seurin, John Steinberger, Minimizing the Two-Round Even-Mansour Cipher Advances in Cryptology – CRYPTO 2014. ,vol. 2014, pp. 39- 56 ,(2014) , 10.1007/978-3-662-44371-2_3
Jacques Patarin, Pseudorandom permutations based on the D.E.S. scheme EUROCODE '90. pp. 193- 204 ,(1991) , 10.1007/3-540-54303-1_131
Alexander May, Ilya Ozerov, On Computing Nearest Neighbors with Applications to Decoding of Binary Linear Codes theory and application of cryptographic techniques. pp. 203- 228 ,(2015) , 10.1007/978-3-662-46800-5_9
Thijs Laarhoven, Sieving for Shortest Vectors in Lattices Using Angular Locality-Sensitive Hashing international cryptology conference. ,vol. 2014, pp. 3- 22 ,(2015) , 10.1007/978-3-662-47989-6_1
Shai Halevi, Invertible Universal Hashing and the TET Encryption Mode Advances in Cryptology - CRYPTO 2007. pp. 412- 429 ,(2007) , 10.1007/978-3-540-74143-5_23
Shai Halevi, Phillip Rogaway, A parallelizable enciphering mode the cryptographers’ track at the rsa conference. pp. 292- 304 ,(2004) , 10.1007/978-3-540-24660-2_23
David Wagner, A Generalized Birthday Problem Advances in Cryptology — CRYPTO 2002. pp. 288- 304 ,(2002) , 10.1007/3-540-45708-9_19
Vadim Lyubashevsky, The Parity Problem in the Presence of Noise, Decoding Random Linear Codes, and the Subset Sum Problem Lecture Notes in Computer Science. pp. 378- 389 ,(2005) , 10.1007/11538462_32