# American Institute of Mathematical Sciences

doi: 10.3934/amc.2021004

## Classical reduction of gap SVP to LWE: A concrete security analysis

 Indian Statistical Institute, 203, BT Rd, Baranagar, Kolkata, West Bengal 700108, India

* Corresponding author: Palash Sarkar

Received  July 2020 Revised  December 2020 Published  March 2021

Regev (2005) introduced the learning with errors (LWE) problem and showed a quantum reduction from a worst case lattice problem to LWE. Building on the work of Peikert (2009), a classical reduction from the gap shortest vector problem to LWE was obtained by Brakerski et al. (2013). A concrete security analysis of Regev's reduction by Chatterjee et al. (2016) identified a huge tightness gap. The present work performs a concrete analysis of the tightness gap in the classical reduction of Brakerski et al. It turns out that the tightness gap in the Brakerski et al. classical reduction is even larger than the tightness gap in the quantum reduction of Regev. This casts doubts on the implication of the reduction to security assurance of practical cryptosystems.

Citation: Palash Sarkar, Subhadip Singha. Classical reduction of gap SVP to LWE: A concrete security analysis. Advances in Mathematics of Communications, doi: 10.3934/amc.2021004
##### References:

show all references

##### References:
 Algorithm 1 Reducing GapSVP$_{\zeta,\gamma}$ to LWE$_{q,\Psi_{\alpha}}$, where $\gamma=\gamma(n)\geq n/(\alpha\sqrt{\log n})$ and $q=q(n)\geq \zeta(n)\cdot \omega(\sqrt{\log n/n})$. 1: function ${\sf {solveGapSVP}}_{\zeta,\gamma}$ $\mathbf{B},d$ 2:        Let $\mathbf{D}$ be the reverse dual basis of $\mathbf{B}$; 3:        $d^{\prime} =d{\cdot}{\sqrt{n/(4\ln{n})}}$; $r = q\sqrt{2n} / (\gamma d)$; 4:        for $i\leftarrow 1$ to $N$ do 5:              $\mathbf{w} \xleftarrow{＄} {d^{\prime}}{\cdot}{\mathcal{B}}_n$; $\mathbf{x} = \mathbf{w} \bmod \mathbf{B}$; 6:              $\mathcal{L} \leftarrow \{\}$; 7:              for $j\leftarrow 1$ to $n^c$ do 8:                    $\mathcal{L}\leftarrow \mathcal{L}\cup {\sf {sample}}(D,r)$; 9:              end for 10:              $\mathbf{v} \leftarrow {\sf {solveCVP}}(\mathbf{B},\mathcal{L},\mathbf{x})$ 11:              if $\mathbf{v} \neq \mathbf{x} - \mathbf{w}$ then 12:                    return ${\sf {accept}}$; 13:              end if 14:        end for 15:        return ${\sf {reject}}$; 16: end function
 Algorithm 1 Reducing GapSVP$_{\zeta,\gamma}$ to LWE$_{q,\Psi_{\alpha}}$, where $\gamma=\gamma(n)\geq n/(\alpha\sqrt{\log n})$ and $q=q(n)\geq \zeta(n)\cdot \omega(\sqrt{\log n/n})$. 1: function ${\sf {solveGapSVP}}_{\zeta,\gamma}$ $\mathbf{B},d$ 2:        Let $\mathbf{D}$ be the reverse dual basis of $\mathbf{B}$; 3:        $d^{\prime} =d{\cdot}{\sqrt{n/(4\ln{n})}}$; $r = q\sqrt{2n} / (\gamma d)$; 4:        for $i\leftarrow 1$ to $N$ do 5:              $\mathbf{w} \xleftarrow{＄} {d^{\prime}}{\cdot}{\mathcal{B}}_n$; $\mathbf{x} = \mathbf{w} \bmod \mathbf{B}$; 6:              $\mathcal{L} \leftarrow \{\}$; 7:              for $j\leftarrow 1$ to $n^c$ do 8:                    $\mathcal{L}\leftarrow \mathcal{L}\cup {\sf {sample}}(D,r)$; 9:              end for 10:              $\mathbf{v} \leftarrow {\sf {solveCVP}}(\mathbf{B},\mathcal{L},\mathbf{x})$ 11:              if $\mathbf{v} \neq \mathbf{x} - \mathbf{w}$ then 12:                    return ${\sf {accept}}$; 13:              end if 14:        end for 15:        return ${\sf {reject}}$; 16: end function
 Algorithm 2: Construction of a distinguisher $\mathcal{B}$ for binLWE$_{n,m_1,q,\leq \alpha}$ using a distinguisher $\mathcal{A}$ for binLWE$_{n,m_2,q,\alpha}$. In the algorithm, $\theta$ is a known lower bound on the advantage of $\mathcal{A}$. 1: function $\mathcal{B}$($\mathcal{J}$) 2:        let $\mathcal{S}$ be a collection of $m_1$ samples drawn independently and uniformly from $\mathbb{Z}^n_p{\times}\mathbb{T}$; 3:        partition $\mathcal{S}$ as $\mathcal{S}=\cup_{i=1}^{\mathfrak{k}}\mathcal{S}_i$, such that $\#\mathcal{S}_i=m_2$, $i=1,\ldots,\mathfrak{k}$; 4:        let $\hat{p}_{＄} = (\mathcal{A}(\mathcal{S}_1)+\cdots+\mathcal{A}(\mathcal{S}_{\mathfrak{k}}))/\mathfrak{k}$; 5:        $m_3\leftarrow 6 (m_2/\theta)^{1/2}$; 6:        let $Z$ be the set of all integer multiples of $m_3^{-2}\alpha^2$ in the range $(0,\alpha^2]$; 7:        for $\gamma$ in $Z$ do 8:                $\mathcal{J}^{\prime} \leftarrow \emptyset$; 9:                for $(\mathbf{a},e) \in \mathcal{J}$ do 10:                   sample $\varepsilon$ from $\Psi_{\sqrt{\gamma}}$; 11:                    $\mathcal{J}^{\prime} \leftarrow \mathcal{J}^{\prime} \cup \{(\mathbf{a},e+\varepsilon)\}$; 12:                end for 13:                partition $\mathcal{J}^{\prime}$ as $\mathcal{J}^{\prime}=\cup_{i=1}^{k}\mathcal{J}_i$, such that $\#\mathcal{J}_i=m_2$, $i=1,\ldots,k$; 14:                let $p = (\mathcal{A}(\mathcal{J}_1)+\cdots+\mathcal{A}(\mathcal{J}_{\mathfrak{k}}))/\mathfrak{k}$; 15:                if $|p-\hat{p}_{＄}| > \theta/2$ then 16:                    return 1; 17:                end if 18:        end for 19:        return 0; 20: end function.
 Algorithm 2: Construction of a distinguisher $\mathcal{B}$ for binLWE$_{n,m_1,q,\leq \alpha}$ using a distinguisher $\mathcal{A}$ for binLWE$_{n,m_2,q,\alpha}$. In the algorithm, $\theta$ is a known lower bound on the advantage of $\mathcal{A}$. 1: function $\mathcal{B}$($\mathcal{J}$) 2:        let $\mathcal{S}$ be a collection of $m_1$ samples drawn independently and uniformly from $\mathbb{Z}^n_p{\times}\mathbb{T}$; 3:        partition $\mathcal{S}$ as $\mathcal{S}=\cup_{i=1}^{\mathfrak{k}}\mathcal{S}_i$, such that $\#\mathcal{S}_i=m_2$, $i=1,\ldots,\mathfrak{k}$; 4:        let $\hat{p}_{＄} = (\mathcal{A}(\mathcal{S}_1)+\cdots+\mathcal{A}(\mathcal{S}_{\mathfrak{k}}))/\mathfrak{k}$; 5:        $m_3\leftarrow 6 (m_2/\theta)^{1/2}$; 6:        let $Z$ be the set of all integer multiples of $m_3^{-2}\alpha^2$ in the range $(0,\alpha^2]$; 7:        for $\gamma$ in $Z$ do 8:                $\mathcal{J}^{\prime} \leftarrow \emptyset$; 9:                for $(\mathbf{a},e) \in \mathcal{J}$ do 10:                   sample $\varepsilon$ from $\Psi_{\sqrt{\gamma}}$; 11:                    $\mathcal{J}^{\prime} \leftarrow \mathcal{J}^{\prime} \cup \{(\mathbf{a},e+\varepsilon)\}$; 12:                end for 13:                partition $\mathcal{J}^{\prime}$ as $\mathcal{J}^{\prime}=\cup_{i=1}^{k}\mathcal{J}_i$, such that $\#\mathcal{J}_i=m_2$, $i=1,\ldots,k$; 14:                let $p = (\mathcal{A}(\mathcal{J}_1)+\cdots+\mathcal{A}(\mathcal{J}_{\mathfrak{k}}))/\mathfrak{k}$; 15:                if $|p-\hat{p}_{＄}| > \theta/2$ then 16:                    return 1; 17:                end if 18:        end for 19:        return 0; 20: end function.
 [1] Guiyang Zhu. Optimal pricing and ordering policy for defective items under temporary price reduction with inspection errors and price sensitive demand. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021060 [2] Mohsen Abdolhosseinzadeh, Mir Mohammad Alipour. Design of experiment for tuning parameters of an ant colony optimization method for the constrained shortest Hamiltonian path problem in the grid networks. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 321-332. doi: 10.3934/naco.2020028 [3] Dmitry Treschev. Travelling waves in FPU lattices. Discrete & Continuous Dynamical Systems, 2004, 11 (4) : 867-880. doi: 10.3934/dcds.2004.11.867 [4] Hailing Xuan, Xiaoliang Cheng. Numerical analysis and simulation of an adhesive contact problem with damage and long memory. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2781-2804. doi: 10.3934/dcdsb.2020205 [5] Hailing Xuan, Xiaoliang Cheng. Numerical analysis of a thermal frictional contact problem with long memory. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021031 [6] Palash Sarkar, Subhadip Singha. Verifying solutions to LWE with implications for concrete security. Advances in Mathematics of Communications, 2021, 15 (2) : 257-266. doi: 10.3934/amc.2020057 [7] Yves Dumont, Frederic Chiroleu. Vector control for the Chikungunya disease. Mathematical Biosciences & Engineering, 2010, 7 (2) : 313-345. doi: 10.3934/mbe.2010.7.313 [8] Vaibhav Mehandiratta, Mani Mehra, Günter Leugering. Existence results and stability analysis for a nonlinear fractional boundary value problem on a circular ring with an attached edge : A study of fractional calculus on metric graph. Networks & Heterogeneous Media, 2021, 16 (2) : 155-185. doi: 10.3934/nhm.2021003 [9] Ana Rita Nogueira, João Gama, Carlos Abreu Ferreira. Causal discovery in machine learning: Theories and applications. Journal of Dynamics & Games, 2021  doi: 10.3934/jdg.2021008 [10] Jérôme Ducoat, Frédérique Oggier. On skew polynomial codes and lattices from quotients of cyclic division algebras. Advances in Mathematics of Communications, 2016, 10 (1) : 79-94. doi: 10.3934/amc.2016.10.79 [11] Davi Obata. Symmetries of vector fields: The diffeomorphism centralizer. Discrete & Continuous Dynamical Systems, 2021  doi: 10.3934/dcds.2021063 [12] Flank D. M. Bezerra, Rodiak N. Figueroa-López, Marcelo J. D. Nascimento. Fractional oscillon equations; solvability and connection with classical oscillon equations. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021067 [13] Shan-Shan Lin. Due-window assignment scheduling with learning and deterioration effects. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021081 [14] Fatemeh Abtahi, Zeinab Kamali, Maryam Toutounchi. The BSE concepts for vector-valued Lipschitz algebras. Communications on Pure & Applied Analysis, 2021, 20 (3) : 1171-1186. doi: 10.3934/cpaa.2021011 [15] Javad Taheri, Abolfazl Mirzazadeh. Optimization of inventory system with defects, rework failure and two types of errors under crisp and fuzzy approach. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021068 [16] Huy Dinh, Harbir Antil, Yanlai Chen, Elena Cherkaev, Akil Narayan. Model reduction for fractional elliptic problems using Kato's formula. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021004 [17] Xiaofei Liu, Yong Wang. Weakening convergence conditions of a potential reduction method for tensor complementarity problems. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021080 [18] Ying Yang. Global classical solutions to two-dimensional chemotaxis-shallow water system. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2625-2643. doi: 10.3934/dcdsb.2020198 [19] Mehmet Duran Toksari, Emel Kizilkaya Aydogan, Berrin Atalay, Saziye Sari. Some scheduling problems with sum of logarithm processing times based learning effect and exponential past sequence dependent delivery times. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021044 [20] Hao Li, Honglin Chen, Matt Haberland, Andrea L. Bertozzi, P. Jeffrey Brantingham. PDEs on graphs for semi-supervised learning applied to first-person activity recognition in body-worn video. Discrete & Continuous Dynamical Systems, 2021  doi: 10.3934/dcds.2021039

2019 Impact Factor: 0.734

## Tools

Article outline

Figures and Tables