AlexiaChen.github.io

AlexiaChen.github.io copied to clipboard

答案是：可以。 但是不能像RSA那样原生就支持，椭圆曲线原生不支持这样的加密原语，但是确实可以在其上构造出公钥加密，私钥解密的方案，而且很早就有了。如果了解[Elgamal公钥加密](http://en.wikipedia.org/wiki/ElGamal_encryption)体制就知道了，就是利用椭圆曲线上的有限循环群来做，这个方案叫EC-Elgamal。当然还有[ECIES方案](https://en.wikipedia.org/wiki/Integrated_Encryption_Scheme), 这个方案是一个混合方案，因为原理不是与RSA一样，其实是用public key用ECDH协商出了一个对称秘钥来加密的，然后用private key才可以拿到这个对称秘钥来进行解密，类似于封装了一层抽象层让使用方法保持一致体验。 如果想要更纯的公钥加密方案（类似于RSA那样)，就是Elgamal了，参考中的Sunuwar的论文。 ## 参考 - Rosy Sunuwar. [Elgamal Encryption using Elliptic Curve Cryptography](https://cse.unl.edu/~ssamal/crypto/EEECC.pdf) - [Can elliptic curve cryptography encrypt with public key and decrypt with private...

AlexiaChen

先说同构吧，一般数学上讨论这个会更多一点，一般提到同构你就要明白，是在讨论两个代数结构的关系，同构即保持相同的结构(元素数量和运算)。比如，所有二元群都是同构的。就是从代数上看，二者本质不变，其本质是一样的，群元素可以各种各样，但是同构。 再对同构进行一点更严谨的描述吧，上面说了，同构是两个代数结构的关系，那么这个关系是什么呢？这个关系其实就是一个映射f，这个映射f满足一些性质: - 两个集合之间双射或一一对应 - 保持代数结构的所有运算及一些特殊元素(单位元等) 举个例子，设f是群A到群B上的同构映射，那么群A和群B的集合之间双射，\*和o分别是群A，群B上的二元运算，任意a, b ∈ A 且该映射保持(没破坏)群的二元运算，即: f(a\*b) = f(a) o f(b)。 而同态更generalize，如果两个代数结构不同构，还是为了研究它们之间的关系，可以把条件不限制那么严格，就可以考虑它们之间保持(没破坏)运算的映射，也就是同构是同态的特例，同态限制少，那么会更好找。同态映射不是双射，也就是不是单射或不是满射。当映射不是满射的时候，就只用考虑映射的像(目标集合)，这个像是原来目标代数结构的子结构。例如，对于群同态的情况，同态的像集是一个子群。用子结构替换原来的代数结构，那么此时的同态映射就变成了满射。当同态映射不是单射时，不同的元素被映射到相同的元素。这时，可以把映射到同一个元素的不同元素看作是一样的(等价的)，这样我们就得到一个等价关系，叫商集合。在这个商集上诱导的同态映射就是一个单射了，这个同态映射从商集映射到原来的子结构上又变成了同构映射。也就是满足双射的同态就是同构，不然就是单同态或者满同态。 在密码学中，为了更方便的研究，所以放宽了一些限制，大部分用到的是同态，不强调同构。密码学上的同态也就是某个满足同态性质的函数(映射)，考虑两个椭圆曲线群(加法群)，上面的二元运算都是加法，那么就可以试图研究这两个群的关系，在它们之间找到一个同态函数H，H(x + y) = H(x) + H(y)。

AlexiaChen

## 前言 密码学很多问题都可以归结到计算困难问题，这些问题也是密码学安全的根基。这些根基就是论文里面安全证明的一些前提假设(assumption)。比如，RSA依赖大质因数分解，椭圆曲线生成公私钥对，通过公钥难以计算私钥这个问题一般是依赖离散对数难题( Discrete Logarithm)。 ## 正文 以下三个难题都是定义在群上的(半群也可以，但是群上会更有趣)，其中g是生成元: - 离散对数难题(DL): 对于等式g^x = y， 给定y，难以找到对应的x。但是给定x，求解y很容易。 - Computational Diffie-Hellman problem(CDH): 对于两个等式y1 = g^x1 , y2 = g^x2， 知道y1和y2, 不知道x1和x2，找到y = g^(x1*x2)很困难，即求解y很困难 -...

AlexiaChen

## 前言 之前写过[Schnorr单个签名的原理和算法](https://github.com/AlexiaChen/AlexiaChen.github.io/issues/123) ，现在写个多签方案，是由于毕竟BTC已经这样做了，为了加快验证签名的速度还有减小签名和公钥的占用Tx的空间。所以还是要讲解下已经落地的应用。当然，现在越来越多的链已经用BLS签名了，这个更好，等放到以后讲解吧。 BTC之前采用的ECDSA的多签方案，这种多签方案不能一次验证签名，需要对应的公钥一次一次的校验，这样签名越多，速度越慢，而且之前也提到过了，ECDSA的门限化比较黑科技，有技巧性，就是麻烦。Schnorr签名就不一样了，对于多签，相当方便做聚合，是由于其签名公式是线性的，这带来了优点。 ## 正文 假设x, x1, x2,... x_n为私钥，其对应的公钥为X, X1,X2, ... , X_n （X_i = x_i*G, G是生成元） m是被签名消息 H是密码学Hash函数，做随机预言机来生成challenge的。 首先回顾下Schnorr单签名算法: - Prover(签名者)生成签名(R, s) = (r\*G, r + H(X...

AlexiaChen

## 前言 我之前在PVSS的那个项目里面说到了那个多项式的承诺(commitment)不是pederseon承诺, 而是commit = g^r。承诺其实就是对某个信息m的绑定，以达到信息隐藏的目的，这样就可以不暴露出来，等到需要用的时候，在进行暴露。所以这时候你可以觉得Hash函数也可以用作承诺，但是相比pedersen commitment有更大的优势。我后面会说到。 ## Pedersen Commitment 先来解释下什么是pedersen commitment吧。 下文中的sender，prover，commiter是同一个对象。 receiver， verfier也是一个对象。从这里也可以看出来，pedersen commitment后面会大量用在零知识证明领域。 - 1. prover 知道一个秘密消息m - 2. prover随机生成一个随机秘密r - 3. prover生成pedersen承诺c = C(m, r)。 这个承诺函数C具体我们现在不用管，后面会告诉你算法...

AlexiaChen

这就是著名的Chaum-Pedersen零知识证明方案，在我的mpvss-rs里面用到了: https://github.com/AlexiaChen/mpvss-rs/blob/9861e7dc71296bffcf07c6001ff2315b96689221/src/dleq.rs#L66 里面设这个证明协议叫DLEQ。 下面来讲解下这个方案是怎么回事，首先这个知识证明把其看做是一个接受一个四元组的函数协议，该参数满足如下约束: ``` DLEQ(g, g^a, g^b, g^ab) => DLEQ(g1,h1, g2,h2) h1 = g1^a h2 = g2^a = (g^b)^a = g^(a*b) 只要以上关系约束能满足，Prover就可以向Verifier证明它知道a。不满足，则验证Proof就是错的。 这个a就是所谓的witness ``` g 一般来说是q素阶群上的生成元。然后Prover， Verifier这两个角色都知道以上这个参数约束可以证明一些东西。 好了，如果满足以上约束，那么就可以通过这个协议来做零知识的证明了，这个协议干了些什么呢？就是Prover想向Verifier证明我知道一个a, 并且a满足以上参数关系的约束，但是不需要把这个a公布出来，Verifier就能在DLEQ上验证Prover的秘密是否属实。协议的流程如下:...

AlexiaChen

## 正文 在很多密码学的论文里面都可以看到这个概念，特别是安全性相关的证明章节中，这是一个前提假设(assumption)。 打个比方: 随机预言机模型(ROM)被描述为以下模型: - 有个黑盒，盒子里面住着一个侏儒，还有一本书和一些骰子。 - 我们可以给任意二进制位序列作为黑盒的输入 - 给定一些侏儒事先没有见过的输入数据，然后侏儒使用它的骰子随机均匀地生成一个新的输出，然后侏儒再把这对的元组数据记录在它的书中 - 如果输入数据侏儒之前就见到过了（在它的书中找到了对应的输入数据），那么侏儒就从它书中记录的对应最后一次返回的输出，并将这个输出再次返回 再举个具体的例子 书中记录了以下元组: 现在又给了一个输入进去，假设是“123”， 那么侏儒在它书中找到了元组, 那么它将把的输出"ada"返回出去，因为这个元组记录是最后一次的返回输出记录。（相同输入，返回相同输出） 好了，这样就比较直观了，这么看来，随机预言机好像一个hash函数，只是这个hash函数对于相同的输入对应的是不同的输出。也就是我们根本不知道消息m对应的输出是什么，直到我们去尝试输入m。这就在密码学的安全证明中是个有用的工具，因为它可以用调用预言机的次数来表示攻击的努力程度。 随机预言机真正的问题在于，现实中很难构建一个真正的“随机”预言机。因为显然，在那个黑盒中没有证据表明存在这样一种在另外的神秘空间（黑盒）中扮演神秘的上帝公平视角的侏儒存在。 所以这个预言机的候选者只能是Hash函数了。一个安全的散列函数意味着对冲突、原像(preimage)和第二原像(second preimage)具有抵抗性，但这些属性并不意味着函数是随机预言机。随机预言机可能只有上帝世界才存在，比Hash函数限制更严格, 更困难。那只侏儒在现实中是不存在的，只存在于上帝的世界。这里的随机更像是统计学上的随机，而Hash中的随机更像是计算意义下的随机。 ## 总结 随机预言机模型中的证明很好，但是还不够完整，无法涵盖实际的实现：我们知道，我们使用的任何函数代替随机预言机都不会是真正的随机预言机；因此，安全性依赖于强烈的希望，即现实中实际的随机函数即使不是随机预言机的部分也不会影响安全性。不过，随机预言模型中的一个证明要比根本没有证明好得多。有总比没有好吧。所有这个模型也是在理论和现实中架起了一个安全证明的桥梁。 另外提到一个题外话就是我们的链的DPoS共识基于的PVSS方案就是在DDH和ROM模型下证明安全的，还有Cardano Ada的Ouroboros也用了PVSS方案。还有现在主流PoS DPoS共识(Algorand、DFINITY)基于的Verifiable Random...

AlexiaChen

## 定义 大概介绍下吧，其实就是定义三个素阶群G1，G2和Gt（素阶群就意味着是循环群了，这里设素数为q）。然后双线性配对就是从G1和G2中分别抽取一个群里的元素，然后把这两个群里的元素映射到群Gt里，这个映射关系就是双线性映射，有时候也叫双线性配对(bilinear pairings)。 定义双线性映射e: G1 * G2 -> Gt，并满足以下性质(一般来说，G1和G2为循环加法群，Gt是循环乘法群): - 双线性： e(g1^a, g2^b) = e(g1,g2)^(ab) 其中a, b ∈ Zq， g1 ∈ G1， g2 ∈ G2 - 非退化性： e(g1,g2) ≠...

AlexiaChen

计算机相关的顶级会议

3

# 计算机相关的顶级会议 ## 前言 大家都知道，自然科学类的一般发表的顶级期刊就是《Nature》《Science》《Cell》了，发表难度相当之大，是神级。但是一般来说上面不刊登计算机的论文，也有，但是太少了。而医学类，就是《柳叶刀》之流是顶级期刊了。而计算机呢，一般是顶级会议的论文，每个细分的子领域都有自己的顶级会议，因为听说大佬都不喜欢发表在期刊上，什么是顶会呢？顶级会议就是在业界（本领域本方向）收到广泛的承认，影响力较大的会议。一方面一般顶级专家、学者都倾向于将paper投到这些会议；另一方面这些会议的论文代表了该领域的目前很优秀、有重大意义的进展。“顶级会议”的投稿竞争压力一般都很大，属于在经典paper中选精英那种。所以大家读论文一般就是在这里找了，因为别人已经帮你筛选了，当然你也可以去读Arxiv之类的预印本，但是需要你有足够的学术训练来甄别好坏，因为预印本是没有同行评审的，它不是发表，只是在发表之前占个位，防止抄袭。 这里不会列出全部的会议，只是我在专业社区，论坛经常看到的缩写。 ## 顶级会议列表 ### 计算机网络 - A类：SIGCOMM(Special Interest Group on Data Communic), 难度很大很大，截止到sigcomm16，大陆好像仅有五人作为一作发了sogcomm，这类会议一般做的贡献影响很大，是更foundational的东西。 - B类：NSDI(Networked System Design and Implementation), 难度也很大，但是稍微比SIGCOMM差一些，NSDI2018录取了一篇国人做的区块链论文《Monoxide: Scale out Blockchains with Asynchronous...

AlexiaChen

深入解析fsync()

5

# 深入解析fsync() ## 前言 整理这篇文章最开始的起因是室友它想做一些性能方面的测试，需要把磁盘缓冲区清空了，为此我就摸索查了些相关资料。刚好在SO上找到了这个 https://stackoverflow.com/questions/9551838/how-to-purge-disk-i-o-caches-on-linux， 与室友的场景需求很一致。 可能大家看过数据库存储引擎相关源码的会对这个POSIX标准的API有了解(fsync fdatasync等)，因为需要它来配合实现数据本地事务的ACID中的D。调用它可以确保数据被写入物理硬盘，而这么一个简单的API描述背后，却有复杂的实现，与文件系统也相关，而且有些时候，并不保证落盘。 于此在业内发生了很多大事，就比如PostgreSQL的数据库团队错误使用fysnc有20年之久，hacker news上报道，标题为《PostgreSQL used fysnc incorrectly for 20 years》。连这些专家都会犯错，所以我们对这些看似简单的事物还是要保持敬畏和好奇的，正因为这样，这fsync()还是值得深究一番的，为此整理这个脉络。 ## 正文 首先来看，一些关于fsync()的变化。第一先看[POSIX标准](https://pubs.opengroup.org/onlinepubs/009695399/functions/fsync.html)： ```txt The fsync() function shall request that all data for...

AlexiaChen