Paper 2014/690

Efficient Interval Check in the Presence of Malicious Adversaries

Genqiang Wu, Yeping He, 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
private interval checksecure integer comparisonmalicious modelzero-knowledge proof$k$-ary tree indexlocation-based access control
Contact author(s)
genqiang80 @ gmail com
History
2014-09-04: received
Short URL
https://ia.cr/2014/690
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/690,
      author = {Genqiang Wu and Yeping He and Yi Lu and Liping Ding},
      title = {Efficient Interval Check in the Presence of Malicious Adversaries},
      howpublished = {Cryptology ePrint Archive, Paper 2014/690},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/690}},
      url = {https://eprint.iacr.org/2014/690}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.