Matrix-Based Secure Multi-Party Computation Homomorphic Encryption Scheme

Matrix-Based Secure Multi-Party Computation Homomorphic Encryption Scheme

Introduction

The rapid expansion of internet applications has brought significant challenges to data privacy and security. As personal data continues to accumulate online, ensuring the confidentiality and integrity of sensitive information in untrusted environments has become a critical issue. Homomorphic encryption (HE) technology, particularly matrix-based homomorphic encryption schemes, offers a promising solution by enabling computations on encrypted data without decryption. This capability allows data processors to perform operations on encrypted data while preserving privacy, even in scenarios where cloud servers may be compromised or pose internal threats.

Traditional homomorphic encryption schemes often suffer from inefficiencies, high noise growth rates, and large key sizes, which can compromise decryption accuracy and computational performance. To address these limitations, this paper introduces a novel lattice-based secure multi-party computation homomorphic encryption scheme (MFHE) that leverages integer matrices for improved efficiency and security.

Background and Related Work

Homomorphic encryption has evolved significantly since its inception. Early work by Aharonov and Regev introduced the Learning With Errors (LWE) problem, which forms the foundation for many modern encryption schemes. Subsequent developments, such as the Gentry-Sahai-Waters (GSW) scheme, improved efficiency by reducing key sizes and storage overhead.

Recent research has focused on enhancing multi-key homomorphic encryption, where multiple parties can jointly compute functions without fully decrypting their data. However, existing solutions often struggle with key management complexity, computational inefficiency, and rapid noise accumulation. For instance, some approaches require managing multiple keys, leading to increased overhead, while others suffer from high noise growth rates that degrade decryption accuracy.

To overcome these challenges, recent studies have explored techniques such as ciphertext packing, noise reduction, and optimized bootstrapping. These innovations aim to improve computational efficiency while maintaining security. However, many of these solutions still face limitations in handling large-scale data or require complex key management.

Proposed Scheme

The proposed MFHE scheme introduces several key innovations to enhance efficiency, security, and scalability in secure multi-party computation (MPC).

Key Contributions

1. Matrix-Based Plaintext Storage
   Unlike traditional bit or vector storage methods, the MFHE scheme employs matrices to store plaintext data. This approach significantly increases storage capacity and improves efficiency when processing large datasets. By organizing data in matrix form, the scheme reduces computational overhead and enables more efficient homomorphic operations.
2. Compact Key Sizes
   The scheme optimizes public and private key dimensions, reducing storage and transmission costs. Smaller key sizes contribute to faster encryption and decryption processes, making the solution more practical for real-world applications.
3. Noise Reduction Techniques
   One of the major challenges in homomorphic encryption is noise accumulation, which can lead to decryption errors. The MFHE scheme introduces proportional noise reduction techniques to mitigate noise growth during computations. This ensures decryption accuracy even after multiple homomorphic operations.
4. Ciphertext Packing and Bootstrapping
   The scheme employs ciphertext packing to bundle multiple plaintext messages into a single ciphertext, enabling complex homomorphic operations. Additionally, improvements to bootstrapping techniques help control noise growth, allowing for deeper computational circuits without compromising security.

Scheme Construction

The MFHE scheme consists of six core components:

1. Setup
   The setup phase generates system parameters based on security requirements and computational depth. These parameters include matrix dimensions, noise distributions, and modulus values.
2. Key Generation
   Public and private keys are derived from the setup parameters. The private key is structured as a matrix, while the public key is constructed to facilitate secure encryption and decryption.
3. Encryption
   Plaintext data is encrypted into ciphertext matrices using the public key. The encryption process incorporates noise to ensure security while maintaining homomorphic properties.
4. Decryption
   The decryption process recovers the original plaintext from ciphertext matrices using the private key. Noise reduction techniques ensure accurate decryption even after multiple operations.
5. Homomorphic Addition
   The scheme supports homomorphic addition, allowing two ciphertexts to be combined while preserving the underlying plaintext operations.
6. Homomorphic Multiplication
   Homomorphic multiplication is achieved through matrix operations, enabling more complex computations on encrypted data.

Secure Multi-Party Computation

To facilitate secure multi-party computation, the MFHE scheme incorporates ciphertext packing and optimized bootstrapping.

1. Ciphertext Packing
   • Permutation Key Generation: A permutation key is generated to enable efficient reordering of ciphertext elements. • Slot Switching: This technique allows multiple plaintext slots to be processed within a single ciphertext, improving computational efficiency.
2. Bootstrapping
   • Bootstrapping Key Generation: A specialized key is generated to refresh ciphertexts and reduce noise. • Bootstrapping Process: The scheme employs a novel bootstrapping method to maintain ciphertext integrity while minimizing noise growth.

Correctness and Security Analysis

Correctness

The correctness of the MFHE scheme is validated through rigorous theoretical analysis. The decryption process ensures that plaintext data can be accurately recovered from ciphertexts, even in the presence of noise. Key properties include:

• Noise Management: The scheme ensures that noise remains within acceptable bounds, preventing decryption errors.
• Homomorphic Operations: Both addition and multiplication operations preserve the underlying plaintext relationships.

Security

The security of the MFHE scheme is based on the hardness of the LWE problem, which is resistant to quantum attacks. The scheme is proven to be IND-CPA secure, meaning that ciphertexts are indistinguishable from random data under chosen-plaintext attacks.

A series of security games demonstrate that the scheme maintains confidentiality even when adversaries attempt to distinguish between encrypted messages. The use of random matrices and noise ensures that ciphertexts do not leak information about the plaintext.

Performance Evaluation

Theoretical Comparison

The MFHE scheme is compared with existing matrix-based homomorphic encryption solutions in terms of key sizes, ciphertext dimensions, and noise growth rates. Key findings include:

• Smaller Key Sizes: The MFHE scheme reduces public and private key dimensions, lowering storage and computational costs.
• Lower Noise Growth: The scheme’s noise expansion rate is significantly lower than competing solutions, ensuring reliable decryption.

Experimental Results

Experimental evaluations demonstrate the scheme’s efficiency in encryption, decryption, and homomorphic multiplication.

• Encryption and Decryption Speed: The MFHE scheme achieves at least 66.97% and 33.04% faster encryption and decryption times compared to existing solutions.
• Scalability: As plaintext matrix sizes increase, the scheme maintains superior performance in homomorphic operations.

Conclusion

The MFHE scheme represents a significant advancement in homomorphic encryption, addressing key challenges in efficiency, noise management, and scalability. By leveraging matrix-based storage, compact keys, and advanced noise reduction techniques, the scheme enables secure multi-party computation with improved performance.

Future research will focus on further optimizing performance, enhancing security, and expanding the scheme’s applicability to broader use cases. As homomorphic encryption continues to evolve, solutions like MFHE will play a crucial role in securing data privacy in cloud computing and distributed environments.

DOI: 10.19734/j.issn.1001-3695.2024.06.0267

Was this helpful?

YesNo

0 / 0