分布式OJ的数据加密(2)

上次解决了如何证明Peggy拥有Alice的x
现在把问题扩展,在OJ的题目中常有精度比较,转化问题即为证明Peggy拥有一个$x\in [a,b]$

第一个解决方法是trivial的,用上次的方法证明$x=a$或$x=a+1…x=b$即可,但这样是低效的

第二个解决方法借鉴于树状数组

对于区间[a,b],将其拆分为若干个长为$2^k$的区间,每个区间由二元组(l,t)表示,其中t的后l位为0,它代表区间[t,t+2^l)
使用树状数组的方法,可以将区间拆分为$O(\log^2 b)$个二元组,最后用这$O(\log^2 b)$个二元组作为对称加密的密钥将私钥锁住即可

UPD:线段树是$O(\log b)$的

发表回复

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