A new security model for secure thresholding

The goal of secure computation is for distrusted parties on a network to collaborate with each other without disclosing private information. In this paper, we focus on secure thresholding, or comparing two secret numbers, which is a key step in pattern recognition. Existing cryptographic protocols are too complex to be used in real-time signal processing. We propose a new security model based on noninvertible functions called Quasi-Information-Theoretic Security. Using this model, we develop a novel secure thresholding protocol that is both secure and computationally efficient. The proposed protocol hides information in a carefully-designed random polynomial and in a lower-rank subspace based on Chebyshev's polynomials.