改进的基于二叉树的无交互防欺骗检测方法

Improved Non-interactive Uncheatable Detecting Scheme Based on Bin-tree

针对一个已有的基于二叉树的无交互防欺骗检测方法进行改进。考虑用户实际诚实计算所花费的开销,把用户没有计算但猜中计算结果的概率计算在内,使进行欺骗的代价大于诚实计算所有任务的代价,用户从欺骗中得不到任何好处,从而达到防止欺骗的目的。改进后的方法比原方法需要更少的样本。

This paper extends an existed non-interactive sampling scheme based on bin-tree to suit the actual situation. It takes the cost of participant truthfully computing a subset of D into account, and also adds the probability that the participant can guess the correct result of f（x）, to make the cost of conducting the cheating more expensive than the cost of conducting all the required computations, therefore the cheating brings no benefit. The improved scheme needs fewer samples than the former scheme.