Taylor Series
For some functions entered into Wolfram, a Taylor series expansion is represented in Big-O notation. E.g. $\sin x, x = \frac \pi4$ produces:
$\frac {1} {\sqrt[]{2}} +\frac{x-\frac{\pi}{4}}{\sqrt[]{2}}+\frac{(x-\frac{\pi}{4})^2}{2{\sqrt[]{2}}}+\frac{(x-\frac{\pi}{4})^3}{6{\sqrt[]{2}}}+\frac{(x-\frac{\pi}{4})^4}{24{\sqrt[]{2}}}+\frac{(x-\frac{\pi}{4})^5}{120{\sqrt[]{2}}}+O(({x}-{\frac{\pi}{4})^6})$
Taylor series represent an approximation of a function, and also give a quantitative estimate on the error introduced by the approximation of the function. $O\left(({x}-{\frac{\pi}{4})^6}\right)$ symbolizes the asymptotic behavior associated with the error introduced by this series at the point $x=\frac{\pi}{4}$ for the function $\sin x$. Taylor series apply to real and complex variables, and lattice schemes use both real and complex functions in their construction.
$\alpha$-BDD
$\alpha$-BDD, or alpha bounded distance decoding, is a formulation of the LWE problem, such that given a lattice $\frak L$ and vector $y$, find a lattice point $x\in\frak L$ within distance $\alpha \cdot \lambda _1(\frak L)$. The paper on $\alpha$-BDD states:
"... a function $f(x)$ which approximates the distance of a target point $x$ from a lattice within a factor of $O\left(\sqrt{\frac{n}{\log n}}\right)$."
One Way Functions
Drawing from Micciancio speaking at the PQCrypto '14 Summer School, you can represent the noise of a lattice vector by looking at a specific point in that lattice. Drawing from what Micciancio said about the one-way function, there is a method of studying lattice cryptography using analytic geometry.
Micciancio covers the different forms of functions associated with the CVP:
- Injective
- Surjective
The following mathematical expressions are taken from the video lecture of Miccancio:
Let $\beta \gg \mu:g_{\frak L}(\overrightarrow{x}) $ be nearly uniform. The vector $\overrightarrow{x} \in \beta$ denotes error for an arbitrary hard lattice $\frak L$, with input $\overrightarrow{x}$, and $\| \overrightarrow{x} \| \leq \beta$.
Then:
$\beta < \frac{\lambda_1}{2}:f(\frak L)$ is injective.
$\beta > \frac{\lambda_1}{2}:f(\frak L)$ is not injective.
$\beta \geq{\mu}:g_\frak L$ is surjective.
All three of these functions can be associated with how error is mapped to a specific point in the lattice.
For example, Micciancio shows in the video that the three inequalities are a OWF relying on the CVP. The error is what creates the "noise," which in turn makes the CVP computationally difficult. The inequalities are the bounds associated with the error, or another way of defining an $\alpha$ bound as discussed.
The Taylor series also evaluates an approximate function at a specific point. So in the function from the Taylor series example, for argument's sake, assume that $\sin x$ is the Gaussian distribution with basis vectors $b_1 \dots b_n \in \beta$ for a lattice $\frak L$ generated by the Taylor series.
Question
My question assumes that 1 is true, while 2 may or may not be true.
- My understanding is that the approximate functions used to calculate the error in lattice cryptography helps established the security in that proof. So we can compare this to the boundary conditions to determine if $\sin x$ is injective or surjective, correct?
- Can't we just drop most of the terms from the Taylor series to derive $O(({x}-{\frac{\pi}{4})^6})$? This would become $O(({n}-{\frac{k}{4})^6})$ for some $n$ and constant $k$, right?
If both Big-O terms from the Taylor series and $\alpha$-BDD examples are error associated with their approximate functions, is it possible to use a Taylor series as a way to evaluate error associated with a point to determine if the scheme is an instance of LWE or SIVP?
