记一节有关密码学承诺的课

666 0 0

作者:qs3c

80bit的安全强度意味着什么？

一般所说的80bit，160bit安全强度是对称密码学中的概念，它是说要去暴力破解或者说去穷举私钥，有(2^{80})次方种可能性。那么一个2048bit的公钥加密（比如RSA中n是一个1024bit的数）对应的对称密码中的安全强度时多少bit呢？大概是几十bit，大整数n的分解，大概要试(sqrt{n})次也就是(2^{1024})次，然而对于大整数分解问题，有更好的算法，所以实际大概需要试(2^{112})次，也就是112bit的安全强度。对于对称加密，一般密钥长度是多少bit，那么安全强度就是多少bit，而对于非对称加密，根据它基于的困难问题，是否存在一些相关的有效解决算法，一般安全强度没有密钥那么长。

离散对数才是困难问题：

对数能画出连续的函数曲线，怎么是困难问题呢？但是对数mod p 以后它的函数图像是离散的，东一榔头西一棒槌，变成了一个困难问题。并且对于这个p有要求，要足够大，才在计算上足够困难。

两类安全：

计算安全和信息论安全：信息论安全是指它从本质上就无懈可击，即使是计算力无限的计算机也不能破解它，也称为无条件安全。相对应的计算安全是目前大多公钥密码学原型能保证的，所使用的安全性假设在计算上是安全的，例如大整数因式分解、离散对数假设等等。

承诺的隐藏性concealing和绑定性binding：

这是一个简单的，剪刀石头布游戏中A对B的承诺：

使用的是哈希函数来完成承诺，这里利用哈希函数的“单向性”和“抗碰撞性”两大关键性质，来完成了承诺需要的两大性质。单向性保证了承诺的隐藏性，A先出但不让B知道以防B作弊。抗碰撞性保证了承诺的绑定性，使得A找不出其他的随机值(R_A^{'})来使得(H(R_A^{'}parallel stone)=H(R_Aparallel paper)) ，这样验证时A无法用其他值代替之前的承诺防止了A作弊。

三种承诺方案的安全性分析：

第一种(g^x)非常简单，利用了离散对数的计算困难性来做的一个承诺，它在隐藏性上是计算安全的，在绑定性上是信息论安全的。（素数阶循环群，每个元素都是独一无二的，不存在值一样指数不一样的元素。）
第三种(h^xg^a=g^{bx+a})是第一种的改进，第一种还是有可能泄露关于x的信息（因为是计算安全的）。这样只能泄露bx+a，隐藏并保护了x，它在隐藏性上是信息论安全的，在绑定性上是计算安全的，因为有可能可以找到((x^{'},a^{'}))使得(h^xg^a=h^{x^{'}}g^{a^{'}})，这里h很重要，它不能透露给任何人它是g的多少次方（保密b），也不能简单的选为g，因为如果选为g，承诺方案变为(g^{x+a})将完全失去绑定性，随意构造（x+1），（a-1）。
第二种((g^a,xh^a))是利用了CDH问题的计算困难性来做的一个加密承诺。（用的ElGamal的加密，但是你别考虑解密，因为承诺本来就是单向的，这里没有人知道b，但是在ElGamal中b是私钥，所以这里无法解密。）它的隐藏性是计算安全的，它的绑定性是信息论安全的。