精华内容
下载资源
问答
  • 差分

    千次阅读 多人点赞 2018-11-04 20:06:48
    差分攻击通过分析特定明文差分对相对应密文差分的影响来提取密钥。差分分析现在被广泛应用于各种分组密码的攻击。 分组加密的轮数对差分分析的影响比较大。如果DES只是使用8轮的话,则在个人计算机上只需要几分钟就...

    一.差分攻击的背景
    差分攻击是由Biham和Shamir于1991年提出的选择明文攻击方法,它的提出时间甚至比DES的设计要早十年。它是针对分组密码攻击最有效的方法之一。差分攻击通过分析特定明文差分对相对应密文差分的影响来提取密钥。差分分析现在被广泛应用于各种分组密码的攻击。
    分组加密的轮数对差分分析的影响比较大。如果DES只是使用8轮的话,则在个人计算机上只需要几分钟就可以破译。但要是在完全的16轮情况下,差分分析仅比穷尽密钥搜索稍微有效。然而如果增加到17或者18轮,则差分分析和穷尽密钥搜索攻击花费同样的时间。如果再把轮数增加到19轮的话,则用穷尽搜索攻击比差分分析更容易了。差分攻击是针对对称分组加密算法提出的攻击方法,看起来是最有效的攻击DES的方法(之所以说看起来,是因为差分攻击需要很大的空间复杂度,实际上可能不如野蛮攻击具有可操作性)。2000年以前,差分攻击就被证明对MD5的一次循环是有效的,但对全部4次循环似乎难以奏效。但是随着对MD5研究的进展,情况有了变化。

    二.差分攻击的描述
    (1)简单的例子
    一个简单的异或加密算法:
    在这里插入图片描述
    其中,c是密文,m是明文,k是密钥。可以通过密文差分来算出一对明文的差分:
    在这里插入图片描述
    通过这种方式,我们可以从一对密文中直接得到一对明文的异或,经过一次异或运算消除了密钥。这体现了差分攻击的思想,我们可以不从单个明文和密文中考虑信息的获取,而是从一对密文和一对明文的差分入手,进行破解。实际上的密码并没有那么简单,但是依然延续了这种思想。

    (2)ChiperOne
    加密过程图解:
    在这里插入图片描述
    加密过程及中间状态:
    在这里插入图片描述
    此时
    在这里插入图片描述
    而由于S盒是公开的,我们可以求得S盒的逆。
    在这里插入图片描述
    此时我们可以知道:
    在这里插入图片描述
    我们可以通过猜测的值来计算出:
    在这里插入图片描述
    举例:
    在这里插入图片描述
    在这里插入图片描述

    (3)ChiperTwo
    加密流程图解:
    在这里插入图片描述
    加密过程及中间状态:
    在这里插入图片描述
    此时我们运用破解ChiperOne的方法,发现不太可行了,因为我们可以通过猜测的值算出其对应的的值,但是此时我们不能得到的值。我们可以通过
    在这里插入图片描述
    求出
    在这里插入图片描述
    的值。
    同ChiperOne,我们可以得出:
    在这里插入图片描述
    但实际上:
    在这里插入图片描述
    S盒是非线性的,我们完全套用ChiperOne的方法是不可行的。
    但这个S盒存在一定的输入输出差分统计规律:当输入i,j的差分为f时,结果如下表所示:
    在这里插入图片描述
    从上表可以看出,10/16的输出都是d。
    所以我们可以取
    在这里插入图片描述
    此时正确的应当使
    在这里插入图片描述
    的概率为10/16,错误的会使其概率为1/16。

    (4)ChiperThree
    加密过程图解
    在这里插入图片描述
    S盒的差分分布表:
    在这里插入图片描述
    此时可以引入一个多轮的差分特征值概念,根据差分分布表,可知
    在这里插入图片描述
    的概率为10/16,
    在这里插入图片描述
    的概率为6/16。所以两轮差分特征值
    在这里插入图片描述
    的概率为10/16*6/16=15/64。此时我们可以通过和ChiperTwo类似的方法求得的值。

    (5)ChiperFour
    r轮,分组长度为16bit的ChiperFour加密过程:
    在这里插入图片描述
    五轮ChiperFour加密的图解:
    在这里插入图片描述
    如果可以找到一个高概率的差分特征值,理论上我们可以得到轮密钥。如果将四个S盒的输入差分都取为0,可以得到差分特征值的最高概率为16/16=1。但这对于差分分析没有意义,于是我们把其中的三个输入差分取为0,另一个输入差分取为f。
    此时有
    在这里插入图片描述
    其概率为10/16。
    在这里插入图片描述
    两轮差分特征的概率为(10/16)(6/16)^3=135/4096。但由于第二轮中有三个S盒的输入差分不为0(活跃S盒),此时得到的不是最高概率的差分特征值。
    我们可以找到更好的差分特征值:
    在这里插入图片描述
    概率为6/16,两轮的概率为(6/16)^2>135/4096
    我们可以重复四轮这个过程。得到概率为(6/16)^4<1/16,需要改进。
    此时可以发现以下几组差分轨迹都可以满足该条件:
    在这里插入图片描述 此时概率为4
    (6/16)^4=81/1024>1/16。

    三、差分分析的步骤

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述
    (2)差分分析的关键步骤
    由r-轮迭代密码差分分析的基本过程可以发现,差分分析首先需要寻找一条高概率的差分特征,这里的高概率是指远远大于穷搜概率。
    自从AES的设计者提出宽轨迹策略以来,所有新发表的分组密码在证明其关于差分分析的安全性时都用到了一个相似的原理,那就是:密码的设计者通过连续r轮加密活跃S盒个数的下界,给出了关于最优差分路径的一个非常小的上界。因此,如何找到活跃S盒个数的下界,是差分分析的关键。

    四、自动化差分分析
    现有文献中,混合整数线性规划(MILP)方法是求解最少活跃S盒个数最自动化的方法,通过建立模型、编写程序生成关于差分传播模式的MILP实例,即可实现最少活跃S盒个数的自动化求解。与其它方法相比,该方法需要更少的工作量。
    4.1 MILP问题
    MILP问题是指一类从线性规划发展来的优化问题,旨在找出一个线性的目标函数在某些线性限制下的最优解。尽管MILP问题和许多离散优化问题有密切的联系,诸如集合覆盖问题,0-1背包问题和推销员旅行问题,但是它直到近几年才被应用于密码学的研究上。
    MILP问题可描述如下:
    在这里插入图片描述
    4.2 Mouha等人提出的框架及其扩展
    4.2.1 Mouha等人基于字级(word-oriented)分组密码提出的框架
    Mouha等人通过建立MILP模型,自动确定字级分组密码算法中活跃S盒个数的下界。下面给出该方法的简要描述。
    在这里插入图片描述
    Mouha等人提出的框架中,用0-1变量表示字级差分在密码算法中的扩散,变量取值为1表示非零差分,取值为0表示零差分,这些0-1变量满足上述三种运算所对应的限制条件。
    1.异或运算的约束表达式
    在这里插入图片描述
    2.线性变换的约束表达式
    在这里插入图片描述
    3.MILP模型目标函数的表示
    在这里插入图片描述
    4.2.2 Mouha等人提出的框架在比特级分组密码上的扩展
    比特级的SPN结构的分组密码算法,主要包括异或运算、S盒代换层及P置换扩散层三种运算。其中,扩散层不产生新的约束条件,只是将上一层约束条件中的变量进行了置换。因此,我们只需总结出两类约束表达式:一类是异或运算应满足的约束条件,另一类则是S盒代换应满足的约束条件。此外,为使最少活跃S盒个数不为0,需增加一些新的约束。
    1.异或运算的约束表达式
    将前面所描述的字级约束表达式转化到比特级后,异或操作的约束表达式是一致的,见表达式(4-3)。
    2.S盒代换的约束表达式
    在这里插入图片描述
    在这里插入图片描述
    3.其他约束
    在这里插入图片描述
    4.0-1约束
    目前为止,所有引入的变量都是0-1变量,因此前面提到的MILP模型实际上是一种纯整数线性规划问题。但在实际应用中,为节省求解时间,我们只要求表示明文差分的变量及所有的哑变量为0-1变量,其他变量的取值为实数,这就成了一般的MILP问题,在很大程度上节省了问题的求解时间。
    5.MILP模型目标函数的表示
    将前面所描述的字级约束表达式转化到比特级后,目标函数的表达式是一致的,见表达式(4-5)。

    研究步骤:
    1.建立寻找PRESENT算法高概率差分特征的MILP模型
    Step 1. 建立MILP模型的变量:利用若干0-1变量表示PRESENT算法加密过程中每一个比特级的差分,当该处有差分时变量取值为1,反之为0。依据的原则是使得引入变量的个数最少。
    Step 2. 建立MILP模型的约束:将差分比特经过异或、S盒代换层(非线性层)和P置换层产生的约束分别用线性不等式表示出,即为变量应满足的约束。
    Step 3. 对约束不等式进行自动化筛选,筛选的目标是:能够剔除的不可能差分对最多的那n个不等式
    Step 4. 建立MILP模型的目标函数:将加密过程中涉及到的S盒用0-1变量Aj表示,当S盒活跃时,Aj取值为1;反之,取值为零。目标函数为:
    在这里插入图片描述
    ,即使得活跃S盒个数最少。

    2.对PRESENT算法进行自动化差分分析
    根据1中的步骤,建立PRESENT算法低轮加密的MILP模型,通过Python编程生成Gurobi求解软件可识别的文件,并对该文件进行求解,得到PRESENT的一条高概率差分特征;逐渐增加轮数,分别求得相应轮数的一条高概率差分特征。
    分别计算各差分特征的概率并与穷搜结果进行对比,给出对PRESENT算法进行自动化差分分析的结论。 以PRESENT算法举例PRESENT加密过程图解:
    在这里插入图片描述
    PRESENT的轮函数
    在这里插入图片描述
    表4-1 PRESENT算法S盒的差分分布表

    在这里插入图片描述
    表格的第i行第j列表示当S盒的输入差分为时输出差分为的频数,频数除以16即为相应差分的概率。从表格中可看出,当输入差分不为0时,输出差分的最大频数为4,即输出差分的概率不超过1/4,这是PRESENT算法S盒的一个重要的性质。

    表4-2 PRESENT-80单密钥差分分析结果
    在这里插入图片描述
    在这里插入图片描述
    从表4-2可看出,PRESENT-80单密钥模型的全轮MILP实例包含1056个0-1变量,1984个连续变量,7937个约束。这个实例可以在222秒内求解,解得的最少活跃S盒个数为62。由于PRESENT算法S盒差分的最大概率为1/4,因此,全轮PRESENT-80的单密钥差分特征的最大概率不超过2-2*62,其小于穷搜概率2^-80,因此我们认为PRESENT-80在抵抗单密钥差分分析时是安全的.

    展开全文
  • 差分——(2)二维差分

    千次阅读 多人点赞 2020-02-25 23:28:30
    下面我们扩展一下,来介绍二维差分。 什么是二维差分 我们有一个矩阵,如下图所示。 根据二维前缀和表示的是右上角矩形的和,由于差分只涉及前面相邻的数(由一维可以推出),并且由前面范围的数相加得到这个...

    前面部分我们介绍了一维差分,https://blog.csdn.net/justidle/article/details/103761632。下面我们扩展一下,来介绍二维差分。

    什么是二维差分

    我们有一个矩阵,如下图所示。

    根据二维前缀和表示的是右上角矩形的和,由于差分只涉及前面相邻的数(由一维可以推出),并且由前面范围的数相加得到这个位置的数。那么类比二维前缀和和一维差分,可以简单推测出二维差分的公式

    p[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]

    如何从差分矩阵得到原矩阵呢?可以参考下面公式

    p[i][j]=p[i][j]+p[i-1][j]+p[i][j-1]-p[i-1][j-1]; a[i][j]=p[i][j];

    P.S. 道歉,前面这个公式写错了,感谢 @繁星-落眼 的纠正。再次道歉。

    举例

    比如,我们有一个矩阵 a,如下所示:

    1 2 4 3
    5 1 2 4
    6 3 5 9

    那么对应的二维差分矩阵 p 如下:

    1  1  2 -1
    4 -5 -1  3
    1  1  1  2

    应用

     如果我们要在左上角是 (x1,y1),右下角是 (x2,y2) 的矩形区间每个值都 +a,如下图所示

    在我们要的区间开始位置(x1,y1)处 +c,根据前缀和的性质,那么它影响的就是整个黄色部分,多影响了两个蓝色部分,所以在两个蓝色部分 -c 消除 +c 的影响,而两个蓝色部分重叠的绿色部分多了个 -c 的影响,所以绿色部分 +c 消除影响。所以对应的计算方法如下:

    diff[x1][y1] += c;
    diff[x1][y2+1] -=c;
    diff[x2+1][y1] -=c;
    diff[x2+1][y2+1] += c;
    

    模板题

    链接

    我的OJ,http://47.110.135.197/problem.php?id=5227

    题目描述

    输入一个 n 行 m 列的整数矩阵,再输入 q 个操作,每个操作包含五个整数 x1,y1,x2,y2,c,其中 (x1, y1) 和 (x2, y2) 表示一个子矩阵的左上角坐标和右下角坐标。
    每个操作都要将选中的子矩阵中的每个元素的值加上 c。
    请你将进行完所有操作后的矩阵输出。

    输入

    第一行包含整数 n,m,q。
    接下来 n 行,每行包含 m 个整数,表示整数矩阵。
    接下来 q 行,每行包含 5 个整数 x1,y1,x2,y2,c,表示一个操作。

    输出

    共 n 行,每行 m 个整数,表示所有操作进行完毕后的最终矩阵。

    样例输入

    3 4 3
    1 2 2 1
    3 2 2 1
    1 1 1 1
    1 1 2 2 1
    1 3 2 3 2
    3 1 3 4 1

    样例输出

    2 3 4 1
    4 3 4 1
    2 2 2 2

    数据范围

    1 ≤ n, m ≤ 1000,
    1 ≤ q ≤ 100000,
    1 ≤ x1 ≤ x2 ≤ n,
    1 ≤ y1 ≤ y2 ≤ m,
    −1000 ≤ c ≤ 1000,
    −1000 ≤ 矩阵内元素的值 ≤ 1000

    分析

    这是一个二维差分的模板题。

    数据分析

    下面我们根据样例输入来分析一下,样例输出是如何得到的。

    初始状态的差分数组 diff 为

     1  1 0 -1
     2 -2 0  0
    -2  1 0  1

    第一次操作为 1 1 2 2 1,得到差分数组 diff 变为

     2  1 -1 -1
     2 -2  0  0
    -3  1  1  1

    第二次操作为 1 3 2 3 2,得到差分数组 diff 变为

     2  1  1 -3
     2 -2  0  0
    -3  1 -1  3

    第二次操作为 1 3 2 3 2,得到差分数组 diff 变为

     2  1  1 -3
     2 -2  0  0
    -2  1 -1  3

    最终,我们可以根据差分数组 diff 求出对应的数组。

    数据范围

    从题目中知道,n 的最大值为 1000,因此我们定义数组为 1004。

    数组的每个数范围为 [-1000, 1000],c 的范围为 [-1000, 1000],操作数 q 最大值为 100000。因此我们可以计算出,经过 q 次操作后,最大的数据为 1000+1000*100000 = 10^8+1000,在 int 的表示范围内。同理最小的数据将是 -1000+(-1000*100000)=-10^8-1000,也在 int 的表示范围内。

    AC 代码

    #include <bits/stdc++.h>
    using namespace std;
    
    const int MAXN = 1e3+6;
    const int MAXM = 1e3+6;
    int a[MAXN][MAXM] = {};
    int diff[MAXN][MAXM] = {};
    
    int main() {
        int n,m,q;
        scanf("%d%d%d", &n, &m, &q);
    
        int i, j;
        for (i=1; i<=n; i++) {
            for (j=1; j<=m; j++) {
                scanf("%d", &a[i][j]);
                diff[i][j] = a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1];
            }
        }
    
        for (i=0; i<q; i++) {
            int x1, y1, x2, y2, c;
            scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
            diff[x1][y1] += c;
            diff[x1][y2+1] -=c;
            diff[x2+1][y1] -=c;
            diff[x2+1][y2+1] += c;
        }
    
        for (i=1; i<=n; i++) {
            for (j=1; j<=m; j++) {
                diff[i][j] += diff[i-1][j]+diff[i][j-1]-diff[i-1][j-1];
                printf("%d ", diff[i][j]);
            }
            printf("\n");
        }
    
        return 0;
    }

    展开全文
  • 有限差分法 有限差分方法(FDM)是计算机数值模拟最早采用的方法,至今仍被广泛运用。 该方法将求解域划分为差分网格,用有限个网格节点代替连续的求解域。有限差分法以Taylor级数展开等方法,把控制方程中的导数用...

    有限差分法
    有限差分方法(FDM)是计算机数值模拟最早采用的方法,至今仍被广泛运用。
    该方法将求解域划分为差分网格,用有限个网格节点代替连续的求解域。有限差分法以Taylor级数展开等方法,把控制方程中的导数用网格节点上的函数值的差商代替进行离散,从而建立以网格节点上的值为未知数的代数方程组。该方法是一种直接将微分问题变为代数问题的近似数值解法,数学概念直观,表达简单,是发展较早且比较成熟的数值方法。

    分类
    对于有限差分格式,从格式的精度来划分,有一阶格式、二阶格式和高阶格式。从差分的空间形式来考虑,可分为中心格式和逆风格式。考虑时间因子的影响,差分格式还可以分为显格式、隐格式、显隐交替格式等。目前常见的差分格式,主要是上述几种形式的组合,不同的组合构成不同的差分格式。差分方法主要适用于有结构网格,网格的步长一般根据实际情况和条件来决定。

    构造差分的方法
    构造差分的方法有多种形式,目前主要采用的是泰勒级数展开方法。其基本的差分表达式主要有三种形式:一阶向前差分、一阶向后差分、一阶中心差分和二阶中心差分等,其中前两种格式为一阶计算精度,后两种格式为二阶计算精度。通过对时间和空间这几种不同差分格式的组合,可以组合成不同的差分计算格式。

    泰勒级数
    在这里插入图片描述
    在这里插入图片描述

    Python中调用sympy模块求解差分

    from sympy import diff
    from sympy import symbols
    import sympy
    def func(t):
        return 2000 * sympy.log(14*10000/(14*10000-2100*t))-9.8*t  #函数
    t = symbols("t")
    print(func(16))
    print(diff(func(t),t))  #对函数进行求导
    print(diff(func(t),t).subs(t,16))
    

    运行上述程序结果:

    392.073691403521
    588000000000*(1 - 3*t/200)/(140000 - 2100*t)**2 - 9.8
    29.6736842105263
    

    【注意】:
    函数的写法不能调用sympy以外的模块的函数
    比如这样写就不对:

    from sympy import diff
    from sympy import symbols
    import math
    def func(t):
        return 2000 * math.log(14*10000/(14*10000-2100*t))-9.8*t
    t = symbols("t")
    print(func(16))
    print(diff(func(t),t))
    print(diff(func(t),t).subs(t,16))
    

    结果:

    392.07369140352074
    print(diff(func(t),t))
    return 2000 * math.log(14*10000/(14*10000-2100*t))-9.8*t
    raise TypeError("can't convert expression to float")
    TypeError: can't convert expression to float
    

    错误点在于:sympy的模块的函数不能调用math模块的函数

    一阶向前差分

    在这里插入图片描述
    Python代码:

    import sympy
    from sympy import diff
    from sympy import symbols
    
    #差分的对象
    x = 16
    k = 2  #步长
    x1 = x + k  #向前
    x2 = x - k  #向后
    
    #方程式
    def func(t):
        return 2000 * sympy.log(14*10000/(14*10000-2100*t))-9.8*t
    
    #一阶向前差分
    def for_difference():
        a_for_diff = (func(x1) - func(x))/k
        for_error = abs(a_for_diff - a_true)/a_true
        print(f'{x}的一阶向前差分值:{a_for_diff}')
        print(f'{x}的一阶向前差分的误差:{for_error*100}%')
    
    if __name__ == '__main__':
        t = symbols("t")
        a_true = diff(func(t), t).subs(t, x)  # 真值
        for_difference()
    

    结果:

    16的一阶向前差分值:30.4738991379398
    16的一阶向前差分的误差:2.69671578943888%
    

    一阶向后差分

    在这里插入图片描述
    Python代码:

    import sympy
    from sympy import diff
    from sympy import symbols
    
    #差分的对象
    x = 16
    k = 2  #步长
    x1 = x + k  #向前
    x2 = x - k  #向后
    
    #方程式
    def func(t):
        return 2000 * sympy.log(14*10000/(14*10000-2100*t))-9.8*t
    
    #一阶向后差分
    def beh_difference():
        a_beh_diff = (func(x) - func(x2))/k
        beh_error = abs(a_beh_diff - a_true)/a_true
        print(f'{x}的一阶向后差分值:{a_beh_diff}')
        print(f'{x}的一阶向后差分的误差:{beh_error*100}%')
    
    if __name__ == '__main__':
        t = symbols("t")
        a_true = diff(func(t), t).subs(t, x)  # 真值
        beh_difference()
    

    运行结果:

    16的一阶向后差分值:28.9145121806904
    16的一阶向后差分的误差:2.55840166138381%
    

    一阶中心差分

    在这里插入图片描述
    Python代码:

    import sympy
    from sympy import diff
    from sympy import symbols
    
    #差分的对象
    x = 16
    k = 2  #步长
    x1 = x + k  #向前
    x2 = x - k  #向后
    
    #方程式
    def func(t):
        return 2000 * sympy.log(14*10000/(14*10000-2100*t))-9.8*t
    
    #一阶中心差分
    def cen_difference():
        a_cen_diff = (func(x1)-func(x2))/(k*2)
        cen_error = abs(a_cen_diff - a_true)/a_true
        print(f'{x}的二阶中心差分值:{a_cen_diff}')
        print(f'{x}的二阶中心差分的误差:{cen_error*100}%')
    
    if __name__ == '__main__':
        t = symbols("t")
        a_true = diff(func(t), t).subs(t, x)  # 真值
        cen_difference()
    

    代码运行结果:

    16的二阶中心差分值:29.6942056593151
    16的二阶中心差分的误差:0.0691570640275347%
    

    二阶中心差分

    在这里插入图片描述
    Python代码:

    import sympy
    from sympy import diff
    from sympy import symbols
    
    #差分的对象
    x = 16
    k = 2  #步长
    x1 = x + k  #向前
    x2 = x - k  #向后
    
    #方程式
    def func(t):
        return 2000 * sympy.log(14*10000/(14*10000-2100*t))-9.8*t
    
    #二阶中心差分
    def two_cen_difference():
        a_cen_diff = (func(x1)+func(x2)-2*func(x))/(k**2)
        cen_error = abs(a_cen_diff - a_true)/a_true
        print(f'{x}的二阶中心差分值:{a_cen_diff}')
        print(f'{x}的二阶中心差分的误差:{cen_error*100}%')
    
    if __name__ == '__main__':
        t = symbols("t")
        a_true = diff(func(t), t , 2).subs(t, x)  # 求2阶导真值
        two_cen_difference()
    

    程序运行结果:

    16的二阶中心差分值:0.779693478624694
    16的二阶中心差分的误差:0.0779896119162236%
    

    迭代直到精确要求——以一阶向前差分为例

    要求初始步长为2,经过多次迭代,一阶向前差分的误差能小于1%
    Python代码如下:

    import sympy
    from sympy import diff
    from sympy import symbols
    
    #方程式
    def func(t):
        return 2000 * sympy.log(14*10000/(14*10000-2100*t))-9.8*t
    
    #一阶向前差分
    def for_difference(x1,x,a_true,k):
        a_for_diff = (func(x1) - func(x))/k
        for_error = abs(a_for_diff - a_true)/a_true
        print(f'{x}的一阶向前差分值:{a_for_diff}')
        print(f'{x}的一阶向前差分的误差:{for_error*100}%')
        return for_error
    
    def Judge_precision(x):
        D = True
        k = 2  # 初始步长
        n = 0
        while D:
            n += 1
            x1 = x + k  # 向前
            t = symbols("t")
            a_true = diff(func(t), t).subs(t, x)
            error = for_difference(x1,x,a_true,k)
            if error <= 0.01:
                D = False
                print(f'迭代第{n}次后,{x}的一阶向前差分的误差为{error}')
            else:
                k = k/2
    
    if __name__ == '__main__':
        x = 16  #差分对象
        Judge_precision(x)
    

    运行结果:

    16的一阶向前差分值:30.4738991379398
    16的一阶向前差分的误差:2.69671578943888%
    16的一阶向前差分值:30.0684298016344
    16的一阶向前差分的误差:1.33028844112341%
    16的一阶向前差分值:29.8697466293837
    16的一阶向前差分的误差:0.660728265039121%
    迭代第3次后,16的一阶向前差分的误差为0.00660728265039121
    
    展开全文
  • 随着大数据时代的到来,人们在便利和隐私之间的矛盾在不断放大。本文介绍了差分隐私的基本概念,让大家能理解差分隐私的思想,并且带大家理解如何使用拉普拉斯分布来实现差分隐私。

    差分隐私

    差分隐私通过在统计结果中加入了适量噪音以确保修改数据集中一条个体记录不会对统计结果造成显著影响,从而满足了隐私保护的要求。即便攻击者掌握了除一条数据外的全部其他的数据记录,差分隐私仍然能够防止攻击者分析出他不掌握的那条数据信息,有效避免了数据发布导致隐私泄露的问题。
    差分隐私是有严格的、可量化的隐私保护模型。假设D和D’为相邻数据集,S为在随机函数A所有可能的输出,Pr为A(D1)获得某个值的概率。那么只要算法满足下面的公式则可以说此算法满足ε -差分隐私的标准。
    dp

    图1 DP标准

    为更好的理解差分隐私,下面对相关名词进行说明

    相邻数据集

    两个数据集只相差一条记录。

    灵敏度

    差分隐私保护可以通过在查询函数的返回值中加入噪声来实现,但是噪声的大小同样会影响数据的安全性和可用性。通常使用敏感性作为噪声量大小的参数,表示删除数据集中某一记录对查询结果造成的影响。敏感度分为全局敏感度和局部敏感度,通常情况下采用全局敏感度会加入过大的噪音,使数据失真,但若使用局部敏感度,在一定程度上就会泄露数据分布信息,这个时候就有了平滑敏感度

    对于一个查询函数:,d为正整数,D为一个数据集的集合,代表的函数的灵敏度由下面公式定义:
    D,D’是相邻数据集,敏感度是查询函数作用在相邻数据集中差值最大的那一个,当数据集针对全局时,Δf就是全局敏感度。当数据针对部分数据集时,Δf就是局部敏感度。
    为了更好的理解差分隐私的作用,下面用一个例子来说明

    例子

    假设我们有一个医疗记录数据库 D1 在那里每条记录是一对 (名字, x), 其中 X 是一个布尔值表示一个人是否患有心脏病。例如:

    姓名有心脏病
    Rose
    Eric
    Joey
    Phoebe
    Chandler
    图2 医疗记录

    假设一个恶意用户 (通常被称为攻击者) 想知道Chandler是否有心脏病。假设他知道Chandler在数据库的哪一行。攻击者只能使用特定形式的查询Qi返回数据库中前i行中第一列 X 的部分总和。攻击者为了获取Chandler是否有心脏病的信息。只需要执行两个查询 Q5(D1)和Q4(D1),分别计算前五行和前四行的总和,然后计算两个查询的差别。在本例中Q5(D1)=3,Q4(D1)=2,差是1。攻击者在知道Chandler在第5行的情况下,就会知道他的心脏病状况是1(有心脏病)。这个例子显示了即使在没有明确查询特定个人信息的情况下, 个人信息如何被泄露。
    如果我们用(Chandler,0)代替(Chandler,1)构造D2,那么这个恶意攻击者将能够通过计算每个数据集的Q5-Q4来区分D2和D1。 如果攻击者被要求通过ε -差分隐私算法接收Qi值,对于足够小的ε,则他将不能区分这两个数据集。
    在上面医学数据库的例子中,如果我们认为f是函数Qi,那么,因为任意两个相邻数据集的差值是0或者1,所以函数的灵敏度就是1。

    差分隐私拉普拉斯实现

    Laplace 分布

    Laplace分布是统计学中的概念,是一种连续的概率分布。如果随机变量的概率密度函数分布为:

    那么它就是拉普拉斯分布。其中, μ 是位置参数, b 是尺度参数。画出来就是长这样:
    Laplace

    图 3 拉普拉斯分布

    我们之前提到过,保护数据隐私的方法就是将原有的单一查询结果概率化。Laplace噪声就给我们提供了一个很好的概率化的方法。继续上面的例子,假如查询为“查询数据集中患有心脏病的人数”,并且查询结果为“2”:在传统模式下,输出就是2;在差分隐私模式下,会以比较大概率输出2左右的结果,也会以比较小的概率输出和2差别比较大的结果。但是,我们需要保证输出的期望为2(保证数据有效性)。

    拉普拉斯实现DP

    那么这个概率怎么用Laplace分布来实现呢?我们可以直接在输出结果2上加均值为0的噪声。直观上来说,我们通过Laplace将查询结果概率化了。然后拉普拉斯噪声就正好能满足差分隐私的要求。那么Laplace噪声是如何产生符合差分隐私的噪声的呢?我们想一下差分隐私的设计目标:当相邻数据集求结果时,两者的结果不会相差太大。那么相邻数据集在真实情况下会相差多少呢?研究这个问题是因为我们不限定用户对数据集做出什么样的查询,直观上来说,如果查询的是人数,那么相邻数据集相差不大(只会相差1),只需要加一个小一点的噪声即可造成两个结果的混淆;那如果我们查询的是人的工资呢,加一个很小的噪声显然是无法满足应用需求的(因为数据相差太大,稍微对数据的改变依然可以看出数据差别很大)。由此可见,如何设计DP机制是和查询紧密相关的。所以我们需要对查询有一个简单的了解:
    因此,我们用到了上面提到的敏感度这一个概念。由于数据集中少一条记录就会对数据查询f的结果结果造成一定的影响,我们自然想知道,这个影响最大是多少呢?也就是上述定义中给出的敏感度的值Δf了。
    有了 Δf 之后,我们自然想: Δf 越大,噪声应该越大, Δf 越小,噪声应该越小。这就给我们设计接下来的机制给了一定的启发。
    拉普拉斯机制:给定查询函数 ,拉普拉斯机制可以表示为:
    查询机制

    图 4 拉普拉斯查询机制

    其中, Yi是独立同分布的变量,为 Lap(Δf /ε)
    接下来我们将说明,上面的Laplace机制就能满足ε-DP。证明过程如下:
    令b=Δf /ε
    假设px表示ML(x,f,ε)的pdf(probability density function),py表示ML(x,f,ε)的pdf,则对于某个输出z,我们有:
    推导

    图 5 拉普拉斯符合DP推导

    推导过程中进行了二次缩放,第一次缩放用到了绝对值不等式进行缩放,第二个缩放用到了上面我们的定义,由此我们就可以证明拉普拉斯分布可以用来实现差分隐私。
    然后我们要求拉普拉斯的概率累计函数,因为期望等于μ,而差分隐私要求期望等于0,所以直接令μ=0进行就算。
    求得概率累计函数在x<μ时等于1/2exp(x/b),当x>=μ时,等于1-1/2exp(-x/b)。然后可以通过每次随机数的大小算出x的值。
    当p<0.5时候,x=log(2); 当x>=0.5时,-blog(2-2p)(以此为例子,前一个同理可得);
    噪声大小

    图 6 拉普拉斯噪音大小

    有了上面的公式,代码的实现就简单了。
    噪音大小和累加和的值大小无关,只和敏感度与ε有关,因为我们只需要假如一定的噪音,让攻击者无法识别出相邻集的差值究竟是多少就行了。
    假设一个医院的心脏病患者相邻集的数值分别是5000和5001,然后外界接口进行查询时,我们加入拉普拉斯噪音在返回,在分别调用接口1000次返回数据集如下。当攻击者获得某次数据的值根本不可能推导出相邻集的数据差值,也就保护了相邻集的那一条数据的隐私。
    数据集可视化

    图 7 拉普拉斯算法返回数据集

    一些缺点

    当攻击者能够查询足够次数接口时,攻击者能够根据查询出来的接口的频次大概反推出原始数据的值大小,因为噪声的返回是符合拉普拉斯分布的,此时攻击者也能够拿到相邻集的差值。这应该算拉普拉斯实现的一点缺点吧,但我们可以限制查询次数,或者通过加入多组ε-差分隐私来进行对抗。
    差分隐私的拉普拉斯实现只能对数值型的数据发布起到保护作用,对于非数值型数据的话,拉普拉斯机制就不好处理了,此时就需要其他的实现机制来保护了,比如指数机制等。

    结语

    在大数据的时代中,各公司都在利用数据提供更好的服务的同时,用户隐私的保护问题也日益凸显。对用户隐私的保护既是法律的要求,也是安全行业的追求。我们相信隐私保护技术会越来越受到重视,并从学术理论迅速投入工业界实战应用。

    展开全文
  • GPS差分定位

    千次阅读 2020-09-02 21:24:20
    1 差分定位 差分GPS系统包含着一个或多个安装在已知坐标位置点上的GPS接收机作为基准站接收机,通过基准站接收机对GPS卫星信号的测量而计算出差分校正量,然后将差分校正量播发给位于差分服务范围内的用户(又称流动站...
  • 差分——(1)一维差分

    千次阅读 2020-02-09 21:38:12
    差分,是一种和前缀和相对的策略。 差分概念 对于一个数列 ,我们需要维护的数据是“相邻两个数之差”。这种策略是,令,即相邻两数的差。我们称数列 为数列 的差分数列。 应用 它可以维护多次对序列的一个区间...
  • 差分隐私

    千次阅读 2019-02-08 21:51:09
    上一篇介绍了数据脱敏的三种基本方法,这里介绍另一种方法——差分隐私。差分隐私的优点在于其不需要特殊的攻击假设,不关心攻击者拥有的背景知识,量化分析隐私泄露风险。 核心研究问题:在满足差分隐私的前提下...
  • 差分约束系统

    万次阅读 多人点赞 2016-12-22 21:42:43
    差分约束系统 一、何为差分约束系统: 差分约束系统(system of difference constraints),是求解关于一组变数的特殊不等式组之方法。如果一个系统由n个变量和m个约束条件组成,其中每个约束条件形如xj-xi 通俗...
  • 树上差分之边差分

    千次阅读 2020-09-24 20:09:48
    学会了点差分,边差分就很简单了。 给定一棵树,给出若干次修改操作以及少次查询操作 修改操作:给定两个点u,vu,vu,v,将u,vu,vu,v路径上所有的边权值+k+k+k 查询操作:询问点xxx到其父亲结点的边权值 思路:树上边...
  • 差分、二维差分、树上差分

    千次阅读 2019-04-19 20:53:49
    一维差分: 给你一个数组a[1] ~ a[n],有Q个操作,每一操作给定 l , r , x 表示 [l, r] 区间所有的数都加上 x, 让你求最后a[1] ~ a[n] 最后各自是多少,要求用 O(n) 复杂度 完成。 设定一个差分数组C[] , 对于每一...
  • 二阶差分

    万次阅读 2019-07-27 22:26:00
    定义X(k),则Y(k)=X(k+1)-X(k)就是此函数的一阶差分Y(k)的一阶差分Z(k)=Y(k+1)-Y(k)=X(k+2)-2*X(k+1)+X(k)为此函数的二阶差分.二阶差分法在工程,电学等方面应用还是比较广泛的,具体可以搜索一下 ...
  • 差分

    千次阅读 2020-05-10 22:49:45
    差分 差分就是将数列中的每一项分别与前一项数做差,例如: 一个序列[1 7 6 5 2 4],差分后得到[1 6 -1 -1 -3 -2 -4] 差分序列第一个数和原序列第一个数相同(相当于第一个数减去0) 差分序列最后比原序列多一个数...
  • 差分方程前向,后向差分

    万次阅读 2019-08-05 10:33:04
    z变换求差分方程
  • 差分电路

    万次阅读 多人点赞 2019-09-30 14:33:03
    差分信号和差分电路讲解: 1、什么是差分信号?为什么要用差分信号? 两个芯片要通信,我们把它们用一根导线连接起来,一个传输1,另一个接受1,一个传输0,另一个接受0,不是很好吗?为什么还要搞其他的花花...
  • 理解单端、全差分和伪差分

    千次阅读 2018-10-19 01:42:07
      单端信号: 单端信号(single-end)是相对于差分信号而言的,单端输入指信号有一个参考端和一个信号端构成,参考...差分(Differential)是将单端信号进行差分变换,输出两个信号,一个和原信号同相,一个和原信号...
  • 差分运算

    万次阅读 2017-06-26 08:43:31
    差分运算差分运算的实质拿到观察值序列之后,无论是采用确定性时序分析方法还是随机时序分析方法,分析的第一步都是要通过有效的手段提取序列中蕴涵的确定性信息。
  • 时间差分法(帧间差分法)opencv和vc代码实现,已经测试过,可以实现!
  • 差分隐私(Differential privacy)浅析

    万次阅读 多人点赞 2019-09-05 08:56:23
    通过几天对差分隐私的左思右想,总算是摸到了点门道,顺着学习思路,就一些比较关键性概念说一下自己的看法: 一、关键性概念 1、查询 对数据集的各种映射函数被定义为查询(Query),用 ={, , ......}来表示一...
  • 双重差分模型DID学习笔记

    万次阅读 多人点赞 2020-06-22 20:17:50
    双重差分模型 (Difference-Differences, DID)是政策评估的非实验方法中最为常用的一种方法,其中交互项是DID的灵魂。 交互项形式拥有各种形式,包括(1)传统DID;(2)经典DID;(3)异时DID;(4)广义DID;以及...
  • 有限差分

    万次阅读 多人点赞 2018-07-09 18:26:47
    总的思想就是把微分方程变成差分方程(离散化),用精度换取计算的可进行性。 几种差分方法及其误差: (来源:https://wenku.baidu.com/view/aa580fd619e8b8f67d1cb919.html) MATLAB实现 以一个对...
  • 自建基站希望通过RTK差分共享猫转发的朋友,需要加装蓝牙模块,或准备串口转otg转接线,将数据通过基站串口或电台数据口传出,通过蓝牙模块或otg(手机充电口)与手机进行通信,预计成本不会超过100元,已有朋友测试...
  • 理解单端,全差分、伪差分

    千次阅读 2017-12-18 20:55:20
    单端信号(single-end)是相对于差分信号而言的,单端输入指信号有一个参考端和一个信号端构成,参考端一般为地端。   ADC单端输入 比如说UART232串口中,发送端TXD,接收端RXD,参考端是地,GND,是典型的...
  • 什么是差分信号?怎样差分走线?

    千次阅读 2020-10-23 16:09:10
    1、什么是差分信号? 差分信号是用一个数值来表示两个物理量之间的差异。差分信号又称差模信号,是相对共模信号而言的。 我们用一个方法对差分信号做一下比喻,差分信号就好比是跷跷板上的两个人,当一个人被跷...
  • 双重差分模型了解一下?

    万次阅读 2019-08-31 09:55:43
    总第163篇/张俊红今天给大家介绍一种比较常用分析方法。叫做双重差分法。啥叫个双重差分法呢?我们先不管这个什么法,我们直接来看例子。假如现在市场同学做了一场促销活动,然后...
  • 差分隐私 走过的坑

    千次阅读 多人点赞 2019-03-11 12:59:02
    差分隐私 小记:学了隐私保护相关匿名模型后,初看差分隐私感觉真不是一个层次,好难理解,像是个大坑。书上的内容就给一对兄弟数据表,一个ε-差分隐私公式,然后两个实现机制。真的很难结合起来看懂,到底如何...
  • 差分序列

    千次阅读 2018-07-04 06:37:49
    设{an}是r阶差分数列,dk是k阶差分首项(1&lt;=k&lt;=r),则 an=a1+(n-1)d1+(n-1)(n-2)d2/2!+……+(n-1)(n-2)……(n-k)dk/k!+……+(n-1)(n-2)……(n-r)dr/r!。设{an}是r阶差分数列,dk是k阶差分首项(1&lt;=...
  •   这道题就是一个引子,可能其他专业同学,对这种问题不甚了解。不过没有关系,丝毫不影响我们今天进行内容的分析。   ...题目二:(微分方程边值问题)梁挠度方程数值求解...要求:(1)分别用向前差分、向后差...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 653,187
精华内容 261,274
关键字:

差分