# 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] Jintai Ding, Joshua Deaton, Kurt Schmidt. Giophantus distinguishing attack is a low dimensional learning with errors problem. Advances in Mathematics of Communications, 2020, 14 (4) : 573-577. doi: 10.3934/amc.2020030 [2] Jintai Ding, Joshua Deaton, Kurt Schmidt. Giophantus distinguishing attack is a low dimensional learning with errors problem. Advances in Mathematics of Communications, 2020, 14 (1) : 171-175. doi: 10.3934/amc.2020014 [3] Ning Zhang, Qiang Wu. Online learning for supervised dimension reduction. Mathematical Foundations of Computing, 2019, 2 (2) : 95-106. doi: 10.3934/mfc.2019008 [4] Prashant Shekhar, Abani Patra. Hierarchical approximations for data reduction and learning at multiple scales. Foundations of Data Science, 2020, 2 (2) : 123-154. doi: 10.3934/fods.2020008 [5] Alexandre Caboussat, Roland Glowinski. Numerical solution of a variational problem arising in stress analysis: The vector case. Discrete & Continuous Dynamical Systems, 2010, 27 (4) : 1447-1472. doi: 10.3934/dcds.2010.27.1447 [6] Giuliano Lazzaroni, Mariapia Palombaro, Anja Schlömerkemper. Rigidity of three-dimensional lattices and dimension reduction in heterogeneous nanowires. Discrete & Continuous Dynamical Systems - S, 2017, 10 (1) : 119-139. doi: 10.3934/dcdss.2017007 [7] 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 [8] Toyohiko Aiki, Adrian Muntean. On uniqueness of a weak solution of one-dimensional concrete carbonation problem. Discrete & Continuous Dynamical Systems, 2011, 29 (4) : 1345-1365. doi: 10.3934/dcds.2011.29.1345 [9] 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 [10] Tomasz Kaczynski, Marian Mrozek, Thomas Wanner. Towards a formal tie between combinatorial and classical vector field dynamics. Journal of Computational Dynamics, 2016, 3 (1) : 17-50. doi: 10.3934/jcd.2016002 [11] Toyohiko Aiki, Adrian Muntean. Large time behavior of solutions to a moving-interface problem modeling concrete carbonation. Communications on Pure & Applied Analysis, 2010, 9 (5) : 1117-1129. doi: 10.3934/cpaa.2010.9.1117 [12] Costică Moroşanu. Stability and errors analysis of two iterative schemes of fractional steps type associated to a nonlinear reaction-diffusion equation. Discrete & Continuous Dynamical Systems - S, 2020, 13 (5) : 1567-1587. doi: 10.3934/dcdss.2020089 [13] Rentsen Enkhbat, Evgeniya A. Finkelstein, Anton S. Anikin, Alexandr Yu. Gornov. Global optimization reduction of generalized Malfatti's problem. Numerical Algebra, Control & Optimization, 2017, 7 (2) : 211-221. doi: 10.3934/naco.2017015 [14] Jiang Xie, Junfu Xu, Celine Nie, Qing Nie. Machine learning of swimming data via wisdom of crowd and regression analysis. Mathematical Biosciences & Engineering, 2017, 14 (2) : 511-527. doi: 10.3934/mbe.2017031 [15] Andreas Chirstmann, Qiang Wu, Ding-Xuan Zhou. Preface to the special issue on analysis in machine learning and data science. Communications on Pure & Applied Analysis, 2020, 19 (8) : i-iii. doi: 10.3934/cpaa.2020171 [16] G. Mastroeni, L. Pellegrini. On the image space analysis for vector variational inequalities. Journal of Industrial & Management Optimization, 2005, 1 (1) : 123-132. doi: 10.3934/jimo.2005.1.123 [17] Adrian Muntean, Toyohiko Aiki. Preface to The Mathematics of Concrete". Networks & Heterogeneous Media, 2014, 9 (4) : i-ii. doi: 10.3934/nhm.2014.9.4i [18] Dieudonné Nijimbere, Songzheng Zhao, Xunhao Gu, Moses Olabhele Esangbedo, Nyiribakwe Dominique. Tabu search guided by reinforcement learning for the max-mean dispersion problem. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020115 [19] Daniel Mckenzie, Steven Damelin. Power weighted shortest paths for clustering Euclidean data. Foundations of Data Science, 2019, 1 (3) : 307-327. doi: 10.3934/fods.2019014 [20] S. J. Li, Z. M. Fang. On the stability of a dual weak vector variational inequality problem. Journal of Industrial & Management Optimization, 2008, 4 (1) : 155-165. doi: 10.3934/jimo.2008.4.155

2019 Impact Factor: 0.734