关于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\)-infinity norm.

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

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

之后去查阅了相关资料，发现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}} \]

因此，影响很小