Analogy between Learning With Error Problem and Ill-Posed Inverse Problems
2025
Read Analogy between Learning With Error Problem and Ill-Posed Inverse Problems (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-21653.txt.
Introduction
A famous hard problem in coding theory may share its shape with a classic problem in applied math. Gaurav Mittal draws that link in a 2025 paper on the Learning With Errors problem. That problem rests on lattices and noisy equations, and it underpins several modern ciphers. Ill-posed inverse problems, by contrast, ask for causes from blurred effects and are known to be unstable.
Mittal shows the coding problem can be seen as a structured inverse problem. He then builds a secret-key cipher from ill-posed problems and reviews its security in depth. A public-key scheme follows, built from the secret-key one plus a standard key exchange method. The paper argues the analogy runs both ways and may seed new cipher designs.
Catalog record
| YEAR | 2025 |
|---|---|
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 19 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-21653
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Analogy between Learning With Error Problem and Ill-Posed Inverse Problems Abstract . In this work, we unveil an analogy between well-known lattice based learning with error problem and ill-posed inverse problems. We show that LWE problem is a structured inverse problem. Further, we propose a symmetric encryption scheme based on ill-posed problems and thoroughly discuss its security. Finally, we propose a public key encryption scheme based on our symmetric encryption scheme and CRYSTALS-Kyber KEM (key encapsulation mechanism) and discuss its security. Gaurav Mittal Defence Research and Development Organization, Near Metcalfe House, New Delhi, 110054, India email: [email protected], [email protected] 2010 MSC: Primary: 94A60, 65J22 Keywords: Learning With Error Problem, Cryptography, Inverse Problems 1. Introduction and Analogy 1.1. Learning with Error Problem The LWE (Learning With Error) problem is a well-known hard problem in cryptography [ 2 ] . Having been the subject of intense scrutiny for nearly a decade, the crypto-primitives CRYSTALS Kyber [ 3 ] and CRYSTALS Dilithium [ 4 ] , whose security inherently rely on LWE problem, have been standardized by NIST. The LWE problem was put forward by Regev in his seminal work [ 6 ] . Formally, one may define LWE problem as follows: Definition 1 . For a prime q , let \mathcal{D} be an error distribution over the modular ring \mathbb{Z}_{q} . For a given m (also known as dimension parameter), let s\leftarrow\mathbb{Z}_{q}^{m} be chosen uniformly at random and it is kept as a secret. For 1\leq j\leq n , where n is some polynomial in m , consider the samples (a_{j},b_{j}=\langle a_{j},s\rangle+e_{j})\in\mathbb{Z}_{q}^{m}\times\mathbb{Z}_{q}, where a_{j}\leftarrow\mathbb{Z}_{q}^{n} is picked uniformly at random. Further, e_{j}\leftarrow\mathbb{Z}_{q} is picked following distribution \mathcal{D} and typically, this is a short element (in terms of norm). The LWE problem is to derive s from the knowledge of (a_{j},b_{j})_{1\leq j\leq n} . The LWE problem can also be formulated in terms of matrix form as follows: Given \mathbf{A}=\begin{bmatrix}(a_{1})\\ (a_{2})\\ \vdots\\ (a_{n})\end{bmatrix}_{m\times n},\quad\mathbf{e}=\begin{bmatrix}e_{1}\\ e_{2}\\ \vdots\\ e_{n}\end{bmatrix}\in\mathbb{Z}_{q}^{n},\quad\mathbf{b}=\mathbf{A}\mathbf{s}+\mathbf{e}=\begin{bmatrix}(a_{1})\\ (a_{2})\\ \vdots\\ (a_{n})\end{bmatrix}\times\mathbf{s}+\begin{bmatrix}e_{1}\\ e_{2}\\ \vdots\\ e_{n}\end{bmatrix}\in\mathbb{Z}_{q}^{n}, we need to find \mathbf{s}\in\mathbb{Z}_{q}^{m} from the knowledge of \mathbf{A},\mathbf{b} . It is well-known that LWE problem is very hard and solving it, on an average, is equivalent to solve certain lattice problems in the worst-case using quantum computers [ 6 ] . This makes LWE a very strong candidate for post-quantum cryptography and the worst-case advantage (discussed above) is not associated with any other post-quantum candidates [ 2 ] . Further, to explore the roots of computational hardness of LWE problem, we switch into the subject of inverse problems. We refer to [ 5 ] for more preliminary details on this subject. 1.2. Well-Posed and Ill-Posed Problems We consider the operator equations of the form T:D(T)\subset U\to V\ \ \ \text{defined as}\ \ \ \ T(u)=v, (1.1) where U and V denote Banach spaces and D(T) denotes the domain of T . Given u , deducing v=T(u) is the direct problem. The corresponding inverse problem is deducing u from the value of v . As per Hadamard criteria, a problem of the form ( 1.1 ) is well-posed if the following three conditions are met. (i) For a given v\in V , ( 1.1 ) has a solution. (ii) The solution is unique. (iii) Continuous dependency must be there, i.e., if v^{\prime} is given in place of v and it is close to v , then the corresponding solutions u^{\prime} and u should be near to each other (in terms of norm). Further, if any one of the above three conditions is not satisfied, then the problem ( 1.1 ) is ill-posed. It is worth to note that the conditions (i)-(ii) are straight-forward to understand. The condition (iii) is less clear. Before going further, we discuss an example of an ill-posed problem, which is ill-posed since it does not fulfill condition (iii). Example of an ill-posed Problem . Let L^{2}[0,1] be the space of real-valued Lebesgue integrable functions g defined on [0,1] such that \int_{0}^{1}g^{2}(y)\,dy<\infty . We consider an operator \mathcal{S}:L^{2}[0,1]\to L^{2}[0,1] defined as (\mathcal{S}(\Psi))(y)=\int_{0}^{1}e^{-|y-s|}\Psi(s)\,ds. (1.2) This operator is also known as Hilbert-Schmidt operator (HSO). For the integral equation ( 1.2 ), the kernel \mathcal{K}(y,s)=e^{-|y-s|} is square-integrable as well as continuous. Therefore, HSO is a compact operator. Further, we know that any compact operator possess a singular value decomposition (see [ 5 ] ). Consequently, we may write \mathcal{S}(\Psi)=\sum_{k=1}^{\infty}s_{k}\langle\Psi,\beta_{k}\rangle\alpha_{k}, where \{s_{k}\} are singular values of \mathcal{S} satisfying s_{k}\to 0 as k\to\infty and \{\alpha_{k}\},\{\beta_{k}\} are orthonormal systems. For the operator \mathcal{S} , the inverse operator can be written as \Psi=\mathcal{S}^{-1}(\Phi)=\sum_{k=1}^{\infty}\frac{1}{s_{k}}\langle\Phi,\alpha_{k}\rangle\beta_{k}. (1.3) We assume the availability of perturbed data since exact data is not available in practice. So, we may write \Phi=\mathcal{S}(\Psi)+\mathcal{E}. Here \mathcal{E} represents the small error. Applying \mathcal{S}^{-1} on this \Phi using ( 1.3 ) to derive that \mathcal{S}^{-1}(\Phi)=\Psi+\mathcal{S}^{-1}(\mathcal{E})=\Psi+\sum_{k=1}^{\infty}\frac{1}{s_{k}}\langle\mathcal{E},\alpha_{k}\rangle\beta_{k}. (1.4) Since the operator \mathcal{S} is compact, we note that s_{k}\to 0\ \ \ \text{as}\ \ \ \ k\to\infty\implies\frac{1}{s_{k}}\to\infty\ \ \ \text{as}\ \ \ \ k\to\infty. This and ( 1.4 ) derive that \|\mathcal{S}^{-1}(\Phi)-\Psi\|_{L^{2}[0,1]}>C for any positive constant C>0 . Therefore, there is no continuous dependence between the data and the solution. Hence, the operator \mathcal{S} is ill-posed in the sense of Hadamard due to violation of condition (iii). 1.3. Degree of Ill-posedness In this subsection, we discuss about the operator equations of the form ( 1.1 ) with the additional constraint that T is a compact operator between Hilbert spaces. The singular value decomposition (SVD) theorem implies that T has singular values s_{1}\geq s_{2}\geq s_{3}\geq\cdots\geq s_{k}>0. We note that ( 1.1 ) is ill-posed if s_{k}\to\ 0\ \ \text{as}\ \ k\to\infty. This is also evident from ( 1.4 ) as decaying values of s_{k} leads to instability of A^{-1} . Further, the degree of ill-posedness can be described by looking at rate at which singular value decays. Accordingly, we have the following two categories of ill-posed problems. (i) Mildly ill-posed: If the decay is of the form s_{k}\sim k^{-t},\quad t>0, i.e., s_{k} decays polynomially (or algebraic decay), then ( 1.1 ) is mildly ill-posed. (ii) Severely ill-posed: If the decay is of the form s_{k}\sim e^{-rk},\quad r>0, i.e., s_{k} decays exponentially, then ( 1.1 ) is severely ill-posed. We note that faster the rate at which s_{k}^{\prime} s decay, more the degree of ill-posedness of ( 1.1 ). 1.4. Structural Analogy In this subsection, we discuss the analogy between LWE problem and ill-posed inverse problems. This is discussed in the following Table 1 . Parameters LWE Problem Inverse Problem for HSO Dimension Finite: modular matrix multiplication Infinite: Operator \mathcal{S}:L^{2}[0,1]\to L^{2}[0,1] Data \mathbf{b}=\mathbf{A}\mathbf{s}+\mathbf{e} with noise \mathbf{e} in finite \Phi=\mathcal{S}(\Psi)+\mathcal{E} with noise \mathcal{E} in infinite dimensional space dimensional space Solution Deduce \mathbf{s} from noisy samples \mathbf{b} but Deduce \Psi from noisy data \Phi . Noise it is computationally hard due to presence makes it highly unstable and presence of noise \mathbf{e} therefore regularization techniques are needed to reconstruct the exact solution Noise Discrete in nature and makes deduction Analytic and continuous in nature and, of secret \mathbf{s} computationally infeasible in practice, noisy data is available. Here, noise is added deliberately in place of exact data Table 1. Analogy between LWE problem and Inverse problems We note the following: • Both LWE problem and Inverse problem for HSO demand to invert a linear operator,