**Efficient Interval Check in the Presence of Malicious Adversaries**

*Genqiang Wu and Yeping He and Yi Lu and Liping Ding*

**Abstract: **We consider the following problem: Assuming that Alice and Bob have an integer interval $[a, e]$ and an integer $b$ respectively, for a commitment $c$ to $b$, Alice and Bob jointly check whether $b$ is within $[a, e]$ without revealing their inputs, where either party may behave maliciously. A special case of the problem is the secure integer comparison in the malicious model. This problem mainly arises from location-based access control systems where one party needs to assure to the other party that its location is within some definite area.

Our main result is a constant-round protocol that exhibit the square of $\log e$ communication and the square of $\log e$ exponentiations with simulation-based security. At the heart of the construction is perfect $k$-ary index and corresponding zero-knowledge proof techniques. We consider a more general case of the problem where the interval is substituted by a union of intervals.

**Category / Keywords: **cryptographic protocols / private interval check, secure integer comparison, malicious model, zero-knowledge proof, $k$-ary tree index, location-based access control

**Date: **received 3 Sep 2014

**Contact author: **genqiang80 at gmail com

**Available format(s): **PDF | BibTeX Citation

**Version: **20140904:061028 (All versions of this report)

**Short URL: **ia.cr/2014/690

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]