We previously discussed about how to use the keys and
how they affect the security applications of asymmetric cryptography.
For example, next to me is the diagram we use for digital signature.
Now let's shift gears and focus our attention to
the requirements of the cipher algorithms which corresponds to
the encryption and decryption functions and the public private key pair.
To be used for asymmetric cryptography,
the cipher and the key pair needs to fulfill the following requirements.
First, it should be computationally easy for any user I to generate a pair of
public key and private key so that
the decryption using one key reverses the encryption using the other key.
Generally, computationally easy is defined to mean a problem that
can be solved in polynomial time as a function of the input length.
Second, if holding the correct keys,
the encryption operation and the decryption processing are computationally easy.
In other words, Alice's computation for encryption and Bob's computation
for decryption should be computationally efficient.
Shifting our focus to the attacker's perspective,
the third requirement for the cipher is that it should be computationally
infeasible for an attacker knowing the public key to determine the private key.
Otherwise, the attacker will easily compromise
the private key after accessing the public key.
Fourth, it should be computationally infeasible for an attacker knowing
the public key K and a ciphertext C to recover the original plaintext P. In other words,
the attacker knowing the ciphertext from a public key cannot derive the plaintext.
An optional requirement for the cipher design is to support broader applications.
And the optional requirement is that the two keys can be applied in
either order so that for any plaintext PST input,
the decryption with the public key reverses the encryption with the private key.
And the decryption with the private key reverses the encryption with the public key.
These requirements can be challenging to meet and there are
only a few algorithms that are widely accepted for asymmetric cryptography such as RSA,
Elliptic Curve Crypro, Diffie-Hellman key exchange and DSS.
And this is even though it has been decades since
the concept of public key cryptography was proposed in the 1970s.
The cipher requirements boil down to the need for a trapdoor one-way function.
A one-way function is a function where the calculation of the function is computationally
easy while the calculation of the inverse is computationally infeasible.
That is, it is easy to compute in one direction from the input to the output,
but it is difficult to reverse that and determine the input from the output.
A trapdoor one-way function is a one-way function with more conditions.
A trapdoor one-way function is easy to calculate in one direction and infeasible
to calculate in the other direction unless certain additional information is known.
With the additional information,
the inverse can be calculated in polynomial time.
In other words, it's easy to compute with the additional information.
In other words, given that K is
the additional information or the key that makes the computation easy,
a trapdoor one-way function is a family of invertible functions F sub K such
that the computation for Y equals F sub K of X is easy if K and X are known.
The computation for X equals the inverse of F sub K of Y is easy if K and Y are known.
Third, the computation for X equals F sub K,
the inverse of F sub K of Y is infeasible if Y is known but K is not known.
Such trapdoor one-way function plays a significant role in asymmetric cryptography.
And the development of
a practical asymmetric cryptography scheme
depends on the discovery of a suitable trap door one-way function.