Léo Ducas 🇺🇦 ∀,≡,⊂<p>Ok, here is my very first serious math post. I'm going to do this at least once a week.</p><p><a href="https://mathstodon.xyz/tags/Math4Crypto" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>Math4Crypto</span></a> <a href="https://mathstodon.xyz/tags/Lattice" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>Lattice</span></a> <a href="https://mathstodon.xyz/tags/Torus" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>Torus</span></a> <a href="https://mathstodon.xyz/tags/LocalitySensitiveHashing" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>LocalitySensitiveHashing</span></a> <a href="https://mathstodon.xyz/tags/TrainOfMathematicalThought" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>TrainOfMathematicalThought</span></a>.<br>*Locality Sensitive Hashing over the Torus, or how I fooled myself twice.*</p><p>Locality Sensitive Hashing (LSH) over a metric space is the task of tiling the space such that two close points are likely to fall in the same tile. The tile need not be periodic, but they typically are for algorithmic convenience. One example application is the "Shazam app": quickly find a song from a noisy recording of it, maybe having preprocessed the database of songs. But if you know me, you can certainly imagine that I will use them to break cryptography.</p><p>It is somewhat similar to two other tasks: coding and quantizing. For coding we want the tiles to have a large inner radius: that is the amount of error tolerated (see my banner !). For quantization (aka: lossy compression from continuous to discrete data), we want minimize the average distance to the center of the tile.</p><p>For LSH, what we want is that if we add a small error to a random point in a tile, the probability that the error drags us outside the tile is low: that is the probability that you will miss out on detecting a pair of close points. For a small error of radius \(\epsilon\), a tile of volume \(V\) and surface \(S\), you can quickly convince yourself that the failure probability is roughly proportional to \(S \cdot \epsilon / V\). Minimizing \(S/V\) is a well known question: the isoperimetric inequality. The best shape for the tiles would be Eucilidean balls... if only they could tile Eucilidean spaces.</p><p>1/3</p>