Lightweight Public Key Encryption in Post-Quantum Computing Era

Table of Links

Abstract and 1 Introduction

2. Scenario and Requirements

3. History and Related Work

4. 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

5. Evaluation and 5.1 Proof of Correctness

   5.2 Preliminary Performance Comparison

6. 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)

7. Security discussion: Post-Quantum Cryptography

8. Summary, References, and Authors

Abstract. Confidentiality in our digital world is based on the security of cryptographic algorithms. These are usually executed transparently in the background, with people often relying on them without further knowledge. In the course of technological progress with quantum computers, the protective function of common encryption algorithms is threatened. This particularly affects public-key methods such as RSA and DH based on discrete logarithms and prime factorization. Our concept describes the transformation of a classical asymmetric encryption method to a modern complexity class. Thereby the approach of CramerShoup is put on the new basis of elliptic curves. The system is provable cryptographically strong, especially against adaptive chosen-ciphertext attacks. In addition, the new method features small key lengths, making it suitable for Internet-of-Things. It represents an intermediate step towards an encryption scheme based on isogeny elliptic curves. This approach shows a way to a secure encryption scheme for the post-quantum computing era.

1 Introduction

More than 50 % of all internet traffic use the protocol combination of RSA with Optimal Asymmetric Encryption Padding (OAEP), i. e. in https. Also the financial market relies on RSA for online-banking, even if RSA is only cryptographic weak. Attacks on Secure Sockets Layer (SSL/TLS) following Public-Key Cryptography Standards (PKCS) #1 v1.5 show the weakness of the cryptosystem RSA. For example, the approaches of Bleichenbacher [1] could reveal the content of encrypted messages. In order to prevent such Adaptive Chosen Ciphertext Attacks (CCA2), it is necessary to use an encryption or encoding scheme that limits ciphertext malleability. To address this problem, RSA is combined with the coding scheme OAEP [2]. It is standardized in the updated PKCS#1 v2 (RFC 2437, RFC 8017). The security of OAEP has been proven secure in the random oracle model [3]. This model is typically used when the proof cannot be carried out using weaker assumptions compared to the Standard Model of Cryptography (SMC). The SMC uses only complexity assumptions for the verification. A growing body of evidence claims the insecurity of this approach [4]. Even the improved scheme OAEP+ is only proved secure against non-adaptive Chosen Ciphertext Attacks (CCA) in general. The security is still indistinguishability under CCA2 in the SMC [5,6]. Furthermore, vulnerabilities still exist with slight variations like Return Of Bleichenbacher’s Oracle Threat since 20 years [7]. The history shows that the current improvements have not solved the problem fundamentally by modified attacks [8,9].

However, the combination of RSA with OAEP was favored instead of using a different encryption system with inherent strength against such attacks. Nevertheless, the confidentiality of crypto systems is threatened by the rising quantum computing era. This also has a significant impact on the trustworthiness of all current blockchain applications [10] due to the public-key procedures used. More complex mathematical problems need to be identified for cryptography as large number factorization is developed. The algorithms of Shore and Grover allow fast factorization and search. This particularly affects public-key methods based on discrete logarithms and prime factorization such as RSA and DH. To address this problem fundamentally, we enhance a public-key encryption system for the post-quantum cryptographic (PQC) age. The direction of Elliptic Curve Cryptography (ECC) has yielded new algorithms, which provides increased security. Our base is the Cramer-Shoup crypto system, which is mathematical proven secure against CCA2 in SMC [11]. This security definition is currently the strongest confidentiality proof known for a public-key crypto system. This prevents such attacks like on RSA-OEAP from the beginning. Our contribution focuses on increasing security while keeping the keys small. In this paper, we highlight the requirements on modern crypto systems with focus on Internet of things (IoT). In our concept, we develop the Cramer-Shoup (CS) crypto system further to be resistant against quantum computing possibilities. Therefore, we adapt CS to the mathematical base of Elliptic Curves (EC). The main advantages are shorter keys, faster operations and increased security compared to the algorithms based on classical discrete logarithms. This is especially desired in lightweight cryptographic for mobile and wireless applications as in the IoT environments [12]. In addition, we provide an simple and detailed description for comprehensible implementation, also with regard to further research. Based on this approach, we will extend our solution to supersingular isogeny EC or graphs for higher protection class in a future step. This new mathematical construct is promising to be resistant to attacks via quantum computers in 21st century. Beside this, we give an overview about the development of public-key schemes and provide a performance comparison.

The structure of this paper is as follows: Section 2 describes a typical security scenario and lists the requirements for modern crypto systems. In Section 3, we provide an overview of the current state of the art with focus on EC. The main part in Section 4 describes our concept of a public-key crypto system. Then, we show the correctness of the our approach and evaluate the performance in comparison to other approaches in Section 5. Subsequently, we proof the fundamental security properties of the presented system in Section 6. A discussion on security in the post-quantum era is elaborated in Section 7. The last section summarizes our work and provides an outlook.

2 Scenario and Requirements

Our approach is based on the following common scenario for public-key encryption, see Figure 1. A sender wishes to send a confidential message to a particular recipient. For that purpose, the recipient has shared the public part of his asymmetric key on a free portal on the Internet (1). This is preferably included in a cryptographic certificate. The sender uses this public key (2) to encrypt the message (3). The encrypted message is then sent to the receiving party (4). The recipient can decrypt the message and process it based on knowledge of the corresponding private key (5). An omnipotent attacker can access both the public part of the key and the encrypted message. Therefore, the encryption method must provide cryptographically strong protection.

The following requirements are mandatory for modern crypto systems:

– Tiny keys for fast transmission – Forward secrecy and reusable keys

– Integrated message validation

– No Malleability [14]

– Provable strong security against adaptive CPA and CCA2, highest possible security

– Additionally in software engineering [15]:

• No data flow from secrets to array indices

• No data flow from secrets to branch conditions

• No padding oracles

• Centralizing randomness

• Avoiding unnecessary randomness with focus on audited deterministic functions