Renyi散度:Renyi divergence
有关Renyi散度的基本介绍挺多博客已经写了。本文章主要介绍最基础的概念,以及近些年论文中为啥老喜欢引用这个概念。
一.基础概念
Renyi散度主要是描述两个分布之间的关系。对一个离散的概率分布X,其定义域记作,其实就是概率不为零的点的集合。形式化的定义如下:
Let ?denote the probability that event E occurs under distribution χ. We let?
对于两个离散的概率分布P和Q,假定(其实就是Q的取值更多),2阶Renyi散度定义如下:
二. 论文常用的Renyi散度结论
性质1:对分布进行确定的函数变换,只会降低Renyi散度。
对于两个离散的概率分布P和Q,假定,对任意给定的函数f,都有:
性质2:可忽略性质的传递(计算复杂性理论)
对于两个离散的概率分布P和Q,假定,从分布Q中取子事件,都有:
这个性质其实在密码学中很有用,为啥这么讲呢。如果可以证明的上界为多项式。那么当事件E在分布Q中发生的概率可忽略,就可以推出事件E在分布P中发生的概率也可忽略。
性质3:Renyi散度与离散的高斯分布(格密码中的概念)
接触过格密码(参考我之前介绍过格密码)的人可能见过一个符号,这个符号啥意思呢?D代表离散的高斯分布,代表该高斯分布的取值全为整数模q,代表离散高斯分布的标准差,m代表维度,也就是:
:关于原点对称的m维离散高斯分布
给一个不太大的数e,那么:
:中心点略微偏移原点的m维离散高斯分布。
好了,现在可以解释第三个性质了。
固定三个整数,有一个上限值,离散高斯分布的标准差满足。令,且满足,那么有:
这个性质看起来有点长,其实是想解释把离散高斯分布平移一点点后,该分布与原始的离散高斯分布的Renyi散度是有上界的。密码学非常关注多项式,指数,次指数等复杂度,利用该定理,比如令离散高斯分布的标准差时,可得。这其中的数学计算就暂时省掉了,密码学总是有许多的数学计算。。。。。
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!