Possibility of decryption speed-up by parallel processing in CCA secure hashed ElGamal.

Area of Science:

• Cryptography
• Number Theory
• Computer Science

Background:

• Proving ElGamal Chosen Ciphertext Attack (CCA) security requires the Interactive Computational Diffie Hellman (ICDH) assumption.
• Previously, only complex bilinear groups were known to support the ICDH assumption.
• Existing ICDH groups limit the practical application of CCA-secure ElGamal.

Purpose of the Study:

• To introduce a new group with a simple algebraic structure where the ICDH assumption holds.
• To propose a CCA-secure ElGamal variant based on this new group.
• To develop a faster, parallelizable version of the proposed ElGamal scheme.

Main Methods:

• Demonstrated that the ICDH assumption is valid in integer groups with composite moduli.
• Developed a hashed ElGamal encryption scheme that achieves CCA security.
• Designed a parallel processing variant to accelerate the decryption process.

Main Results:

• The ICDH assumption is proven to hold in integer groups with composite moduli.
• A new CCA-secure hashed ElGamal scheme is proposed.
• The parallel variant offers the fastest decryption among CCA-secure Public Key Encryption (PKE) schemes in integer groups.

Conclusions:

• The use of integer groups with composite moduli simplifies the algebraic structure required for ICDH.
• The proposed ElGamal variants enhance security and efficiency.
• This research paves the way for practical ElGamal implementations, especially with large moduli for quantum resistance.