some thoughts about Lipschitz

关于Lipschitz的思考

今天在看TFHE论文的过程中，看到了 $\kappa$-Lipschitz的概念

The notion of Lipschitz function always refers to the $\ell_{\infty}$-distance: a function $f: \mathbb{T}^m \rightarrow \mathbb{T}^n$ is said to be $\kappa$-Lipschitz if $|f(x)-f(y)|_{\infty} \leq \kappa |x-y|_{\infty}$ for all inputs $x, y$, where $|\cdot|_{\infty}$ is the $\ell_{\infty}$ norm.

一个新奇的想法：在学密码学过程中遇到的一些数学概念，或许我们应该去究其本质，看看它原本在数学领域和其他领域的应用，或者说提出的原因，这样更有利于我们理解他的概念

可能是笔者太久没学数学了，看到这样一个形式有点迷糊，甚至有一个奇怪的想法，$x$和$f(x)$量纲不同（考虑到量纲可能是因为选用的是$\infty$范数，现在倒是想不起来为什么会考虑到量纲了）的话，这么限制有什么意义呢？

之后去查阅了相关资料，发现Lipschitz多用于深度学习领域，并且该概念十分简单易懂。我们把RHS中的$|x-y|_{\infty}$除下来，其实就是斜率的概念

$$\frac{\|f(x)-f(y)\|_{\infty} }{|x-y\|_{\infty}}\leq \kappa$$

这不就是代表$f(x)$这个函数，在任意维度上，斜率最大也不超过$\kappa$​嘛。在TLWE提到这个概念，应该也只是想约束一下error对于明文带来的影响。

在TLWE中，我们是将Lipschitz套在phase function上使用的，phase的自变量$x$是ciphertext，因变量才是plaintext，因此笔者理解的是给ciphertext加error造成的影响，对于plaintext不大，所以才能正确解密。

我们可以这样看这个问题，假设密文是$(\pmb{a},b)$，对应的明文是$\mu$，则有$\varphi_s{(\pmb{a},b)}=b-\pmb{a}\pmb{s}=\mu$，我们引入噪声，可以参考TFHE中对于trivial encryption的概念，$(\pmb{0},e)$和$e$，则有$\varphi_s{(\pmb{0},e)}=e-\pmb{0}\pmb{s}=e$

因此，我们可以有

$$\frac{\|\varphi_s{(\pmb{a},b)}-\varphi_s{(\pmb{a},b-e)}\|_{\infty} }{|(\pmb{0},e)\|_{\infty}}\leq \kappa$$ $$\|\varphi_s{(\pmb{a},b)}-\varphi_s{(\pmb{a},b-e)}\|_{\infty} \leq \kappa{||(\pmb{0},e)\|_{\infty}}$$

因此，影响很小

参考资料：

[1] 详细解析深度学习中的 Lipschitz 条件

[2] Chillotti I, Gama N, Georgieva M, et al. TFHE: fast fully homomorphic encryption over the torus[J]. Journal of Cryptology, 2020, 33(1): 34-91.