Why there is no public key-based block cipher? It is known that the block ciphers are symmetric-key encryption. However, what is the motivation to not design a public key encryption that encrypts blocks of bits?


Let's make a list of reasons why public "block ciphers" are generally not used:

  1. asymmetric ciphers expand the ciphertext compared to the plaintext, rather than being a permutation of a block of bits;
  2. asymmetric ciphers require a lot more processing power;
  3. asymmetric ciphers require a lot more state;
  4. asymmetric ciphers are more vulnerable to side channel attacks (as they are based on big number arithmetic rather than binary operations on smaller words);
  5. asymmetric ciphers are more vulnerable against attacks using quantum computers;
  6. normal block cipher modes do generally not apply to asymmetric ciphers;
  7. because of 2 & 3, (full) hardware acceleration is generally less common for asymmetric ciphers.

I've left the word "generally" out of above reasons, but that may have to be inserted in each reason. There may be asymmetric ciphers that violate one or more of the rules displayed above.

Hybrid cryptography - where asymmetric / public cryptography is combined with symmetric / secret key cryptography - is rather easy to implement. So there is simply not much need for modes of encryption that use an asymmetric cipher for larger messages.

Modes such as ECIES or RSA-KEM are easy to describe and implement. Their main drawback is that the symmetric cipher mode of operation is generally not standardized.

  • 1
    $\begingroup$ Wiki answer, please edit me with additional reasons. $\endgroup$
    – Maarten Bodewes
    Apr 15 '20 at 21:26
  • $\begingroup$ We always hear that one of the objectives of doing program obfuscation can be (despite the impossibilities): gives us a way of doing the opposite - the use of a public-key cryptosystem in an asymmetric way. $\endgroup$ Apr 15 '20 at 22:08
  • 3
    $\begingroup$ @McFly Sorry? You simply use public key encryption instead of symmetric encryption in the hope that it isn't detected? I've heard of obfuscation techniques for symmetric ciphers, but I'm pretty sure that modular arithmetic over large numbers isn't that easy to hide. $\endgroup$
    – Maarten Bodewes
    Apr 15 '20 at 22:26
  • 1
    $\begingroup$ @Marteen, in fact, obfuscation of a symmetric cryptosystem to reach a public one iacr.org/archive/tcc2007/43920214/43920214.pdf The idea is: to obfuscate a program that executes a symmetric cryptosystem, with the secret key (obfuscated), and using that as an asymmetric scheme. $\endgroup$ Apr 16 '20 at 2:20
  • $\begingroup$ By 5, are you also saying that asymmetric schemes can not be unconditionally secure, wich can be possible with symmetric ones? $\endgroup$ Apr 24 '20 at 20:40

About the possibility: Yes, it is possible. As @Maarten-bodewes said, they can be easily described.

O. Goldereich in his book Foundation of Cryptography, vol. 2., p 416, give us the following construction:

Construction 5.3.16 (Randomized RSA - a public-key block-cipher scheme): this scheme employs collection fo trapdoor permutations [...] The following description is, however, self contained:

Key-generation: The key-generation algorithm consists of selecting at random two n-bit- primes, $P$ and $Q$, setting $N=PQ$, selecting at random a pair $(e,d)$ such that $ed \equiv 1 (\bmod (P-1)(Q-1))$, and outputting the pair $((N,e),(N,d))$, where $(N,e)$ is the encryption-key and $(N,d)$ is the decryption-key. That is, $((N,e),(N,d) \leftarrow G(1^n)$, where $N$, $e$, and $d$ are as specified here.

Encryption: To encrypt an n-bit string $\sigma$ (using the encryption-key $(N,e)$, the encryption algorithm randomly selects an element $r \in \{0,...,N-1\}$, and produces the ciphertext $(r^e \bmod N, \sigma \otimes LSB(r))$, where $LSB(r)$ denots the $n$ least-significant bits of $r$. That is, $E_{(N,e)}(\sigma) = (r^e \bmod N, \sigma \otimes LSB(r))$.

Decryption: To decrypt the ciphertext $(y,\varsigma) \in \{0,...,N-1\} \times \{0,1\}$ (using the decryption-key $(N,d)$, the decryption algorithm just computes $\varsigma \otimes LSB(y^d \bmod N)$ [...] That is $D_{(N,d)}(y,\varsigma)=\varsigma\otimes LSB(y^d \bmod N)$.

So, Goldreich continues on page 416,417:

[...] Furthermore, Randomized RSA is almost as efficient as "plain RSA" (or the RSA function itself).


Preposition 5.3.17: suppose that the large hard-core conjecture for RSA does hold. The construction 5.3.16 constitutes a secure public-key block-cipher (with block-length $l(n) = n$).

  • $\begingroup$ Sorry, but doesn't the scheme just describe how to encrypt the least significant bits of $\sigma$? $\sigma$ seems limited to the size of $r$ which is dependent on the size of $N$... $\endgroup$
    – Maarten Bodewes
    Apr 21 '20 at 0:41
  • $\begingroup$ Yes, @maarten. They also prove that this scheme is semantically secure and consequently secure for encrypting multiples messages with the same chosen keys. $\endgroup$ Apr 21 '20 at 15:37
  • $\begingroup$ Ah, OK, so you show that correctly implemented RSA can be used as (some kind of) block cipher by simply concatenating multiple messages together? That's actually a good answer. You'd still have "a bit of a problem" when it comes to the most significant bit if you want to see the block as a set of bits: the ciphertext must expand on the plaintext even with this scheme. $\endgroup$
    – Maarten Bodewes
    Apr 21 '20 at 19:13
  • $\begingroup$ Ok, @Maarten. I'm sure that the problem with my answer was that I grabbed it from a very theoretical (but undoubtedly an excellent one) book. Maybe that proposal is lacking something to reach correctness; but, anyway, could it be feasible? Surely not. So, you're right: this is not an answer to the question. $\endgroup$ Apr 21 '20 at 20:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.