Improved Non-interactive Uncheatable Detecting Scheme Based on Bin-tree
Duan-Yang Liu · Jisuanji gongcheng · 2008
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.