On Some Papers (2)

中断了几天,接着看文章,希望能坚持下去,无论在哪里。

Square Root Algorithm in F(q) for q ≡ 2^s+ 1 (mod 2^(s+1))
平方根算法,之前在课本上看的那个应该是素域上的平方根算法吧,还真没仔细看是否适用于这种扩域上的情况。作者提出的这类平方根算法都很简单,复杂度也很低,只需要一个指数运算。s是满足如下条件的最大整数:2^s|q-1,因为算法有2^(s-1)个,所以暂时也只能解决s很小的情况,比如作者解决了s=2,3,4的情况,也就是q ≡ 5 (mod 8),q ≡ 9 (mod 16),q ≡ 17 (mod 32)这三种情况的平方根算法。

A new index calculus algorithm with complexity L(1/4 + o(1)) in small characteristic
又是离散对数问题的指数演算法,还是不太感兴趣,记住这个时间复杂度就好,貌似对于大特征上的DLP大家还没什么办法吧。

On the Complexity of Broadcast Setup
Byzantine broadcast,这篇文章考虑这样的问题,广播者希望广播一个消息m给n个用户,即使其中有t个用户被攻击者控制了,剩下的n-t个用户仍然能恢复出正确的消息m,而攻击者得不到这个消息m。很明显t不能比n/2大,文章提到一般是t<n/3时就需要一个叫做Broadcast Setup的东西;t>n/3时直接PKI解决吧。那么这篇文章提出的方案,可以处理t<n/2的情况,并且只需要广播一轮,广播比特数为O((logn)^3),进一步地,这个方案是无条件安全的,也就是信息论上的安全。那么这种协议可以用在多方安全计算中,就是在正式开始计算之前还有Setup的过程吧。最后继续送上一张图表示目前这方面的一些研究成果比较。1

打赏

发表评论

电子邮件地址不会被公开。 必填项已用*标注