Multiparty computation (MPC) is a cryptographic method that enables a set of parties to compute an arbitrary joint function of the private inputs of all parties and does not reveal any information other than the output. MPC based on a secret sharing scheme (SS-MPC) and garbled circuit (GC) is known as the most common MPC schemes. Another cryptographic method, homomorphic encryption (HE), computes an arbitrary function represented as a circuit by using ciphertexts without decrypting them. These technologies are in a trade-off relationship for the communication/round complexities, and the computation cost. The private decision tree evaluation (PDTE) is one of the key applications of these technologies. There exist several constant-round PDTE protocols based on GC, HE, or the hybrid schemes that are secure even if a malicious adversary who can deviate from protocol specifications corrupts some parties. There also exist other protocols based only on SS-MPC that are secure only if a semi-honest adversary who follows the protocol specification corrupts some parties. However, to the best of our knowledge, there are currently no constant-round PDTE protocols based only on SS-MPC that are secure against a malicious adversary. In this work, we propose a constant-round four-party PDTE protocol that achieves malicious security. Our protocol provides the PDTE securely and efficiently even when the communication environment has a large latency.

Multiparty computation (MPC) is the technology that computes an arbitrary function represented as a circuit without revealing input values. Typical MPC uses secret sharing (SS) schemes, garbled circuit (GC), and homomorphic encryption (HE). These cryptographic technologies have a trade-off relationship for the computation cost, communication cost, and type of computable circuit. Hence, the optimal choice depends on the computing resources, communication environment, and function related to applications. The private decision tree evaluation (PDTE) is one of the important applications of secure computation. There exist several PDTE protocols with constant communication rounds using GC, HE, and SS-MPC over the field. However, to the best of our knowledge, PDTE protocols with constant communication rounds using MPC based on SS over the ring (requiring only lower computation costs and communication complexity) are non-trivial and still missing. In this paper, we propose a PDTE protocol based on a three-party computation (3PC) protocol over the ring with one corruption. We also propose another three-party PDTE protocol over the field with one corruption that is more efficient than the naive construction.