Secure Computation Schemes for Mahalanobis Distance Between Sample Vectors in Combating Malicious Deception

Xin Liu, Weitong Chen, Xinyuan Guo, Dan Luo, Liang Li, Baohua Zhang, Yu GuSymmetry 2025 · DOI

TL;DR

This paper introduces novel secure multi-party computation (MPC) schemes for calculating the Mahalanobis distance, a crucial metric for comparing data points. Their work addresses the challenge of performing these calculations while preserving data privacy and, importantly, defending against malicious participants who might try to cheat or tamper with the results.

What Problem Does This Paper Address?

In today's data-driven world, analyzing and comparing data samples is fundamental to fields like AI, medical diagnosis, and financial risk assessment. The Mahalanobis distance is a powerful tool for this, as it accounts for correlations between features in high-dimensional data. However, the sensitive nature of this data (e.g., patient records, financial information) means it cannot be shared openly. Secure Multi-Party Computation (MPC) offers a way to compute on private data without revealing it. While existing MPC solutions exist for distance calculations, they often fall short when dealing with potentially malicious actors who might deviate from the protocol. This paper tackles the critical need for MPC schemes that not only protect privacy but also actively resist and detect malicious behavior during the computation of Mahalanobis distance.

Methods

The authors propose three main schemes, building upon each other:

  1. Two-Party Protocol (Semi-Honest Model): This foundational scheme uses the fully homomorphic NTRU encryption algorithm and randomization techniques. It allows two parties to compute the Mahalanobis distance without revealing their individual data, assuming both parties follow the protocol honestly.
  2. Multi-Party Protocol (Semi-Honest Model): Extending the two-party approach, this scheme enables multiple participants to jointly compute the Mahalanobis distance. It breaks down the complex computation into five manageable steps, including multi-party encryption, inverse covariance matrix computation, and decryption.
  3. Multi-Party Protocol (Malicious-Secure): This is the most significant contribution. It enhances the multi-party protocol by integrating zero-knowledge proof techniques. This addition allows participants to verify the correctness of computations at critical stages, ensuring fairness and preventing malicious participants from submitting false results.

All schemes leverage the NTRU cryptosystem for its efficiency and quantum-resistance.

Datasets

Not discussed in the paper. The authors mention using simulated datasets for experiments.

Key Insights and Ideas

  • The Need for Malicious Security: The paper strongly emphasizes that simply protecting privacy isn't enough. Real-world scenarios demand defenses against participants who might actively try to cheat or disrupt the computation, a gap addressed by their third protocol.
  • Zero-Knowledge Proofs for Trust: Integrating zero-knowledge proofs is a key innovation. It allows participants to prove they've performed computations correctly without revealing their private data, building trust in a multi-party setting.
  • NTRU as a Foundation: The choice of the NTRU cryptosystem is strategic, offering a good balance of security, speed, and quantum resistance, making it suitable for practical applications.
  • Decomposition for Efficiency: Breaking down the complex Mahalanobis distance calculation into smaller, manageable steps (encryption, covariance, decryption) is crucial for making MPC feasible.

Key Results

The paper presents theoretical analyses and experimental simulations to validate their protocols.

  • Security and Correctness: The authors provide formal proofs demonstrating that their two-party and multi-party protocols securely compute the Mahalanobis distance under both semi-honest and malicious models.
  • Performance: Experimental results show that their algorithms achieve a favorable balance between security and performance.
  • Execution Time: Algorithm 1 (two-party, semi-honest) generally exhibits the lowest execution time, growing almost linearly with the number of samples and vector dimensions. Algorithm 3 (multi-party, malicious-secure) has the highest execution time due to the added verification steps, but still demonstrates good scalability for small to moderate datasets.
  • Communication Latency: Similar trends are observed for latency, with Algorithm 1 being the fastest and Algorithm 3 the slowest, reflecting the trade-off between security features and communication overhead.
  • Scalability: The proposed protocols are primarily suited for scenarios with a "small number of sample vectors" (hundreds) and "tens of dimensions." For these settings, execution times are typically in the seconds, with acceptable communication delays.

Limitations and Future Work

The authors acknowledge several limitations:

  • Scalability for Large Datasets: The current protocols are not designed for very large datasets (thousands of samples or high dimensions) due to the rapid increase in encryption/communication costs and the lack of distributed optimization.
  • Computational and Communication Overheads: Despite using NTRU, the inherent nature of MPC and homomorphic encryption still leads to significant overheads, especially for larger inputs.
  • Adversary Models: The current implementation is primarily based on semi-honest and partially malicious models, with a need for further improvement against more sophisticated, fully malicious adversaries.

Future work will focus on:

  • Developing more efficient encryption and parallel computation mechanisms to reduce system overhead.
  • Extending protocol security to fully malicious models.
  • Promoting practical deployment and optimization in real-world applications like healthcare and finance.

Summary updated

Abstract

In the context of rapid advancements in big data and artificial intelligence, similarity measurement methods between samples have been widely applied in data mining, pattern recognition, medical diagnosis, financial risk control, and other fields. The Mahalanobis distance, due to its effectiveness in capturing correlations within high-dimensional data, has become a crucial tool in many practical scenarios. However, sample data often contains sensitive privacy information, making it essential to achieve secure and privacy-preserving computation of Mahalanobis distance. This paper proposes a secure Mahalanobis distance calculation scheme tailored for sample vectors that effectively resists malicious cheating behaviors. The designed multi-party computation algorithms ensure privacy protection while maintaining computational efficiency and minimizing communication overhead. The experimental results compare three algorithms in terms of execution time and communication delay across varying sample sizes and vector dimensions. The results demonstrate that our proposed scheme achieves a favorable balance between security and performance. This research provides a practical and robust solution for similarity measurement under privacy constraints and lays a theoretical and practical foundation for secure data collaboration in multi-party computing environments, offering significant application potential.
BibTeX
@inproceedings{liu2025secure,
  author = {Xin Liu and Weitong Chen and Xinyuan Guo and Dan Luo and Liang Li and Baohua Zhang and Yu Gu},
  title = {{Secure Computation Schemes for Mahalanobis Distance Between Sample Vectors in Combating Malicious Deception}},
  booktitle = {Symmetry},
  year = {2025},
  doi = {10.3390/sym17091407},
}
Figure