Defining Symmetric vs Asymmetric cryptosystems

Question

I'm writing a project on the advantages and disadvantages of symmetric vs asymmetric cryptosystems. At the moment I am trying to define both systems using mathematical notation. Under the heading "Basic Cryptosystems" I have this:

We can define the cryptogram functionally as \begin{equation} \mathit{C=f(M,K)} \end{equation} It will also be helpful to think of the cryptogram as a family of transformations with one parameter like this \begin{equation} \mathit{C=T_{k}M} \end{equation} The transformation $T_{k}$ applied to the message $M$ produces cryptogram $C$. The operation of the transformation $T$ will depend on which cryptosystem is being used. The index $k$ corresponds to the particular key being used. Assume there are a finite number of keys, each with associated probability $P(T_{k})$. There will then be some discrete statistical process which chooses a transformation from the set $T_{1}, T_{2}, ..., T_{n}$. These transformations have associated probabilities $P(T_{1}), P(T_{2}), ..., P(T_{n})$ respectively. We should also assume a finite number of possible messages $M_{1}, M_{2}, ..., M_{m}$ with associated a priori probabilities $P(M_{1}), P(M_{2}), ..., P(M_{m})$. Once $C$ is received, it can be deciphered with $k$ in order to reveal $M$. This is achieved with a unique inverse transformation $T^{-1}_{k}$ such that $T_{k}T^{-1}_{k}=I$, the identity transformation. So \begin{equation} M=T^{-1}_{k}C \end{equation} The inverse transformation must be unique for every $C$ which can be deciphered with key $k$ to reveal $M$.

My question is: does this definition apply to both symmetric and asymmetric systems? If not, how can I change it to account for asymmetric systems?

thanks

Answer 1

Your definition only covers symmetric encryption since the same "index" $k$ is used in $T_k$ and $T^{-1}_k$ (i.e., encryption and decryption use the same key)

If you want to give a generic definition that covers both types of encryption, you could say that the transformations are $T_k$ and $T^{-1}_{k'}$ and that in the case of symmetric encryption $k'=k$.

Answer 2

I think it covers both symmetric and asymmetric systems. Given a transformation $T_k$, if computing $T^{-1}_k$ is easy then this is a symmetric cryptosystem. On the other hand, if this is difficult than it is an asymmetric one. Note that in this case, we are ''hard-coding'' the key $k$ inside the transformation. Thus we are just given the transformation $T_k$ and not $k$. In fact this is how Diffie and Hellman (and James Ellis) gave a "proof of existence" of public key encrypton

Answer 3

Preliminary on notation: in the question,

• it seems advisable to change $C=T_{k}M$  to $C=T_{k}(M)$ , and change $M=T^{-1}_{k}C$  to $M={T_k}^{-1}(C)$
• it is necessary to change $T_{k}T^{-1}_{k}=I$  to ${T_k}^{-1}\circ T_k=I$ , meaning that the function obtained by applying $T_k$ then its inverse ${T_k}^{-1}$ is identity, with $\forall M, {T_k}^{-1}(T_k(M))=M$.

The question separates the notion of key $K$ from the encryption transformation $T_k$ for this key ($k$ became lowercase and seemingly is now an index, perhaps from a space smaller than the space of all $K$). I would say that it could be extended to cover some forms of deterministic asymmetric encryption (like raw/textbook RSA); but that studying the asymmetry and security of such encryption would require additional considerations about the feasibility of computing $T_k$ for arbitrary input knowing $K$ (which would be the public key), when ${T_k}^{-1}$ would only be computable knowing $K'$, with $K'$ computationally impossible to derive from $K$.

As is, the definition only covers that kind of encryption where the output is a function of key and plaintext (only); when encryption often has an additional random input to the encryption function. That's the case in 3DES-CBC or AES-CTR using random IV, and any form of asymmetric encryption that is secure for small messages (like name of a particular students on a public call roll), including secure forms of RSA, and ElGamal encryption. As is, the notation in the question (modeling encryption for a given key as a function of plaintext only) can thus not cover any form of semantically secure asymmetric encryption; which is a huge gap.