What is probabilistic encryption?

Cryptography has been a vital area in the development of blockchain technology, but this would not be possible without the development of a basic concept for it: probabilistic encryption.

When we talk about probabilistic encryption we refer to an algorithm that is capable of applying randomness to an encryption mechanism. In this way, what the developer of this cryptographic function is looking for is something very simple: for each data input, obtain a different output for each interaction performed. Thus, probabilistic encryption algorithms seek to offer a higher level of security than that achieved by current deterministic techniques.

This idea serves to improve the systems of asymmetric cryptography that we know And from this point, we can understand its importance: probabilistic encryption is the fundamental building block for protect the privacy of our digital life, not only in blockchain, but also in the Internet and any other aspect related to this world now and in the near future.

The first probabilistic encryption system

The origin of the first probabilistic cipher system can be traced back to the development of Ralph Merkle with his work Secure Communications over Insecure Channels. This work was so far ahead of its time that at its initial presentation at the Association for Computing Machinery (ACM) in 1975, it was dismissed as an impossibility.

But by 1978, a year after the work of Whitfield diffie y Martin hellman and his asymmetric Diffie-Hellman cryptographic protocol, was finally considered as something possible making one thing clear: the birth of probabilistic encryption and public key systems were not just a possibility but the future of cryptography.

Thus, the proposals of Ralph Merkle, Whitfield Diffie and Martin Hellman became the first cryptographic proposals that used elements of probabilistic encryption for their operation. Its success lies in the fact that this new scheme was capable of securing any communication channel even in an insecure communication environment.

This advance was what led to the creation of one of the first asymmetric encryption systems with the most widely used probabilistic elements in the world: the RSA algorithm. RSA is still used today on the Internet and in many digital systems around the world. Of course, this whole scheme is also used in the rest of the asymmetric cryptographic systems, such as those known ECDSA, EdDSA, Schnorr, among others, which makes clear the level of importance of this advance.

Improving the system

Now, the use of probabilistic algorithms in RSA is actually quite small. Generally, it is used for a basic function: the producers of pseudo-random numbers or PRNG (Pseudo-random number generator). Let us remember that the PRNGs are in charge of helping us to obtain the numbers and entropy that we can consider safe and, therefore, they are the basis of the security of our current asymmetric encryption algorithms. These PRNGs are created using probabilistic algorithms, and hence, asymmetric encryption algorithms are considered probabilistic encryption algorithms, even though they do not fully apply that scheme.

While this is secure enough, even by our current standards, the security of these algorithms can be extended by extending the use of probabilistic properties to the rest of the encryption algorithm. That is, applying randomness not only to the number generator, but also to the entire encryption system, which would be a huge advance comparable to the very birth of asymmetric cryptography.

This was precisely the work that two great cryptographers brought to life, Shafi goldwasser y Silvio Micali (creator of Algorand). In 1982, Goldwasser and Micali introduced the well-known Goldwasser–Micali cryptographic protocol. Its biggest breakthrough is that this is the first fully probabilistic cryptographic system known worldwide.

Goldwasser and Micali's work creates a safe asymmetric system based on the quadratic residue problem described by Carl Friedrich Gauss in the year 1801. This mathematical problem is widely used in cryptography, the best example of its implementation being the algorithm PRNG BBS (BBS pseudorandom number generator), created in 1986 by Lenore Blum, Manuel Blum and Michael Shub.

It was based on this system that Goldwasser and Micali created an algorithm capable of generating a probabilistic cascade function in which each value generated by the factorization of randomly generated numbers serves to feed an entirely probabilistic encryption algorithm. Thus, a text can be taken and encrypted sequentially, in this way each sequence gives a totally different result, you will never see the same file with identical encryption no matter how many encryption iterations you perform. You can read an extended mathematical explanation of the system in this link.

Probabilistic Crypto System Security

Now, why reach this level? The answer to that is simple: improve our security. The probabilistic cipher system introduced by Goldwasser and Micali is perhaps one of the greatest cryptanalysis puzzles that can be created.

For example, a 500 character text would have more than 10^100000 different encryption combinations, which supposes a computationally unanalyzable level of result at present. That's even greater than the encryption capabilities that can be achieved with algorithms like AES, ECDSA, and EdDSA, combined.

The problem with probabilistic encryption systems is that their creation using deterministic machines always creates a gap or space in which we cannot fully verify its security. Put more simply, theoretically they are excellent, but formally at the algorithmic implementation level we cannot guarantee their total security. This in essence could be resolved with the next leap in the computing age: quantum computers, since by their nature, these are probabilistic and we could fully verify the security of these cryptographic systems.

In addition to creating efficient algorithms, since existing probabilistic encryption implementations are computationally inefficient and do not compensate for their security with respect to the computational power and performance they offer. That being said, there is still a lot to be researched in this area until we can finally develop complex algorithms that exploit the full potential of this new improvement in our encryption systems, but for now we will have to wait a little longer and improve the probabilistic bases that already protect our current ones. implementations.