# Complexity: Taylor series and security proofs [closed]

## 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.

1. 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?
2. 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?

• what do you mean by using it as a basis for complexity in security? Maybe you could do this point more clear which would increase your chances of getting an answer... :) Apr 24, 2017 at 14:57
• Ok... I'm just thinking that it is a little bit hard to say what is the basis for complexity theory... I mean, the basis are the computational models, how different types of functions grow, the fact that some types of functions are always "greater" than other if we take large enough inputs, the reductions among several problems... Apr 24, 2017 at 18:46
• @Vitor I added inequalities from LWE, and tried to keep my question clear...but I think I muddied the waters more than anything. I'm going to step away from this for a few minutes and try to think how I can make my question clearer. Apr 24, 2017 at 19:41
• What Wolfram means with that $O((x - \pi/4)^6)$ is that all the other infinite terms are somehow less then or equal to that $(x - \pi/4)^6$. And what the $\alpha$-BDD paper means is that if the real distance is $d$, then $d <= f(x) <= \sqrt{n / \log n} \cdot d$. In other words, it approximates the distance by a factor not bigger than this square root... Apr 24, 2017 at 20:07
• @Vitor: actually, in the first case, it means that the sum of all the other infinite terms are less than or equal to $C(x - \pi/4)^6$ for some constant $C$. This constant $C$ is an important part of what the $O$ notation is trying to convey. Apr 24, 2017 at 20:48