What Happens When You Put Cramer-Shoup on Elliptic Curves?

Written by escholar | Published 2025/09/09
Tech Story Tags: lightweight-cryptography | post-quantum-cryptography | public-key-encryption | elliptic-curve-cryptography | isogeny-based-cryptography | internet-of-things-security | rsa-oaep-vulnerabilities | cramer-shoup-encryption

TLDRThis article explores how the Cramer-Shoup encryption scheme is adapted to elliptic curve cryptography (ECC) for enhanced public-key security. By leveraging the Elliptic Curve Discrete Logarithm Problem (ECDLP), this approach delivers shorter key lengths while maintaining high security levels, outperforming traditional integer factorization and DLP methods. It details key generation, public/private parameters, and standards like X.509 and ASN.1, showing why ECC-based Cramer-Shoup is a promising step toward supersingular isogeny cryptography.via the TL;DR App

Table of Links

Abstract and 1 Introduction

  1. Scenario and Requirements

  2. History and Related Work

  3. Concept of Cramer-Shoup with Elliptic Curve and 4.1 Prerequisite

    4.2 Public Key Generation by Receiver

    4.3 Encryption by Sender

    4.4 Decryption by Receiver

  4. Evaluation and 5.1 Proof of Correctness

    5.2 Preliminary Performance Comparison

  5. Proof: Secure against adaptive-chosen ciphertext attacks

    6.1 DDH Assumption and 6.2 CCA Assumption

    6.3 IND-CCA 1 - non-adaptive Security

    6.4 IND-CCA 2 - adaptive Security (Validity Checking Failure)

  6. Security discussion: Post-Quantum Cryptography

  7. Summary, References, and Authors

4 Concept of Cramer-Shoup with Elliptic Curve

This approach is premised on the general sender-receiver architecture, as shown in Figure 1. Our public-key encryption method is based on the approach of Cramer-Shoup (CS) [42,43]. Here, we adapt the cryptographic strong procedure of CS to the promising base of ECC as an intermediate step to supersingular isogeny EC. The main benefit is that the key length scales linear in relation to the security level [44]. The new security relies on the Elliptic Curve Discrete Logarithm Problem (ECDLP) [45,46]. This mathematical problem is more difficult to solve than the integer factorization problem or the classical DLP. Currently, no algorithm is known that solves the ECDLP in an efficient way. The known fastest approach is the parallelized Pollard-Rho Algorithms with approximately O( √p), where p is the largest prime factor of n [47]

4.1 Prerequisite

First of all, the following parameters are to be declared. The plain-text message to be secured, is described as the parameter m. Here it is a positive integer value, represented as binary.

4.2 Public Key Generation by Receiver

In summary, we obtain the following individual keys:

– Public-key - Points: C, D, H

– Private-key - Factors: x1, x2, y1, y2, z

In addition, we have in common the following parameters, which can also be public:

– Function Fp(X) with generator points G1, G2

– Function Hash

For the public format, recommended representation is ANSI X.509, X9.62, and X9.63 syntax following ASN.1 structure.

Author:

(1) Peter Hillmann, University of the Bundeswehr Munich, Department of Computer Science, Werner-Heisenberg-Weg 39, 85577 Neubiberg, Germany.


This paper is available on arxiv under ATTRIBUTION-NONCOMMERCIAL-SHAREALIKE 4.0 INTERNATIONAL license.


Written by escholar | We publish the best academic work (that's too often lost to peer reviews & the TA's desk) to the global tech community
Published by HackerNoon on 2025/09/09