3
$\begingroup$

While talking about symmetric encryption schemes like AES we always have a goal of achieving confusion and diffusion. But when it comes to asymmetric encryption schemes like RSA, DH etc. we never talk about diffusion and confusion.

Is it known that modular arithmetic and prime arithmetic ensure confusion and diffusion?

Is there any literature that dives into the information theoretic analysis, in terms of confusion and diffusion, for RSA?

$\endgroup$
3
  • 1
    $\begingroup$ Maybe not exactly a dupe, however, there are some answers about this in Why is public-key encryption so much less efficient than secret-key encryption? (Samul Neves's answer..) $\endgroup$
    – kelalaka
    Nov 9, 2021 at 13:20
  • $\begingroup$ That answer explains the difference between RSA and symmetric encryption but doesn't really explain why confusion and diffusion is not needed for asymmetric crypto. Thank you for the reference, now i know why AES is much more efficient $\endgroup$ Nov 9, 2021 at 13:30
  • $\begingroup$ Because the lie in relies on the existence of trapdoor functions. Different design requires different anaylzes. $\endgroup$
    – kelalaka
    Nov 9, 2021 at 13:36

2 Answers 2

1
$\begingroup$

In asymmetric crypto, security of schemes typically relies on some underlying problem, which seems hard to solve (root extraction for RSA, discrete log for DH, short lattice vectors for lattice-based crypto, etc.).

In symmetric crypto, on the other hand, security is ad hoc and we have to rely on heuristics such as diffusion and confusion (which are though very vague concepts).

Note that asymmetric schemes often have some symmetries, such as the multiplicative property for RSA (let's ignore the padding for now). This seems to contradict confusion. But this is not a problem for the scheme, and relying on a nice hard problem is much better than relying on heuristics.

Also, we could even build symmetric crypto from asymmetric-style primitives and the diffusion/confusion might not be fully satisfied, but it would be secure. The core problem here is that asymmetric primitives are much slower compared to heuristic symmetric primitives. That's why we resort to diffusion/confusion and other heuristics in designing symmetric crypto.

$\endgroup$
2
$\begingroup$

The topic is a little dated, but similar concepts are discussed using slightly different language. People have questioned whether the computation of individual bits of discrete logarithms, or RSA decryptions is as hard as the overall problem. This particularly relevant in the design of PKC based random number generators such as Blum-Blum-Shub or Micauli-Schnorr. People define hard predicates for trapdoor functions to be Boolean functions (i.e. computation of a single bit) whose computation would enable the efficient inversion of the trapdoor problem. There are some nice proofs that certain bits of discrete logarithms and RSA ciphertexts are hard predicates for the underlying hard problems.

$\endgroup$
1
  • 1
    $\begingroup$ This answer missing answering the theoretical connection between the confusion&diffusion and hard predicates. Shannon 1941 page 708, In the method of diffusion the statistical structure of M which leads to its redundancy is “dissipated” into long-range statistics—i.e., into statistical structure involving long combinations of letters in the cryptogram. and later confusion... $\endgroup$
    – kelalaka
    Nov 9, 2021 at 20:15

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.