Limitations of the decoding-to-LPN reduction via code smoothing

Das LPN-Problem (Learning Parity with Noise) ist eine grundlegende Herausforderung in der Kryptographie, die verschiedenen kryptographischen Primitiven wie symmetrischer Verschlüsselung, Public-Key-Kryptographie und kollisionssicherem Hashing zugrunde liegt. Dieser Artikel untersucht die Grenzen der Dekodierung zu LPN-Reduktion durch Codeglättung, eine Technik, die verwendet wurde, um für die Härte von LPN zu argumentieren, indem man es auf das Dekodierungsproblem linearer Codes reduzierte. Frühere Arbeiten stützten sich auf Codeglättung, um Reduktionen festzustellen, aber diese beschränkten sich auf Codesequenzen mit asymptotisch verschwindender Rate. Dieser Artikel hinterfragt die Durchführbarkeit solcher Reduktionen für Codes mit positiven Raten und präsentiert eine detaillierte Analyse der beteiligten Parameter und der in früheren Studien getroffenen Annahmen. Sie vertieft sich in das Konzept der Codeglättung und erklärt, wie sie verwendet wird, um einheitliche Verteilungen und ihre Rolle im Reduktionsprozess anzunähern. Der Artikel diskutiert auch die Auswirkungen seiner Ergebnisse auf die Härte des LPN und damit verbundene kryptographische Probleme und bietet eine nuancierte Perspektive auf die Rechenkomplexität dieser Herausforderungen. Durch die Untersuchung der Bedingungen, unter denen sinnvolle Verringerungen möglich oder unmöglich sind, bietet es wertvolle Einblicke in die Stärken und Grenzen der Decodierung zu LPN-Reduktion durch Codeglättung.