Join Log in
Score:3
Chirag Parmar avatar Crypto

Why is confusion and diffusion never talked about in asymmetric crypto?

cn flag
Chirag Parmar

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?

151
0 + 0
rsa
aes
kelalaka avatar
in flag
kelalaka
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?](https://crypto.stackexchange.com/q/586/18298) (Samul Neves's answer..)
1
Reply
Chirag Parmar avatar
cn flag
Chirag Parmar
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
0
Reply
kelalaka avatar
in flag
kelalaka
Because the lie in relies on the existence of trapdoor functions. Different design requires different anaylzes.
0
Reply
Score:2
Daniel S avatar Crypto
ru flag
Daniel S

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.

0 + 0
kelalaka avatar
in flag
kelalaka
This answer missing answering the theoretical connection between the confusion&diffusion and hard predicates. [Shannon 1941](http://pages.cs.wisc.edu/~rist/642-spring-2014/shannon-secrecy.pdf) 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...
1
Reply
Score:1
Fractalice avatar Crypto
in flag
Fractalice

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.

0 + 0
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.