Private feasible solution determination

Abstract

Abstract Applying secure multi‐party computation (SMC) to implement secure linear programming is an important problem of SMC. Private feasible solution determination means that one of the participants has a private value and the other participants have some constraints, and they want to cooperatively determine whether the private value satisfies the constraints without disclosing their private information. This problem has important theoretical and practical significance in both scientific research and practice. In this study, the authors propose a protocol based on elliptic curve cryptosystem for this problem and prove that the protocol is secure in the semi‐honest model. Furthermore, threshold decryption elliptic curve cryptosystem is used to privately determine a feasible solution with multiple constraints for two‐party and multi‐party scenarios. The efficiency analysis shows that the protocols developed in this study are simple and efficient. Finally, the authors also show how to use these protocols to solve other SMC problems.

Keywords

• cryptographic protocols
• cryptography
• data privacy
• linear programming
• protocols
• public key cryptography