We consider the problem of securely computing the Greater Than (GT) predicate and its generalization - securely determining membership in a union of intervals. We approach these problems from the point of view of Q-Conditional Oblivious Transfer (Q-COT), introduced by Di Crescenzo, Ostrovsky and Rajagopalan. Q-COT is an oblivious transfer that occurs iff predicate Q evaluates to true on the parties' inputs. We are working in the semi-honest model with computationally unbounded receiver. In this paper, we propose: (ⅰ) a stronger, simple and intuitive definition of COT, which we call strong COT, or Q-SCOT. (ⅱ) A simpler and more efficient one-round protocol for securely computing GT and GT-SCOT. (ⅲ) A simple and efficient modular construction reducing SCOT based on membership in a union of intervals (UI-SCOT) to GT-SCOT, producing an efficient one-round UI-SCOT.
展开▼
