Understanding Functions That Are Onto But Not One-to-One in the Context of Encryption

When discussing functions in mathematics and their applications in cryptography, it is essential to understand different types of functions, particularly those which are onto but not one-to-one. This article will explore the definitions and implications of these functions, provide examples of possible cryptographic applications, and discuss the importance of bijective functions in symmetric encryption schemes.

Defining One-to-One and Onto Functions

To begin, let's define some key terms:

One-to-One Injective Function

A function f: A to B is injective (or one-to-one) if every element of A maps to a unique element of B. In other words, no two different elements of A map to the same element in B. This property ensures that each input has a unique output, crucial for ensuring unambiguous decryption in symmetric encryption schemes.

Onto Surjective Function

A function f: A to B is surjective (or onto) if every element of B is the image of at least one element of A. In other words, for every element in the codomain B, there exists at least one element in the domain A that maps to it. Ensuring that a function is surjective in the context of encryption means that every possible ciphertext can be produced by some plaintext, maximizing the use of the ciphertext space and complicating certain types of cryptanalytic attacks.

For a function to be both one-to-one and onto, it must be bijective. Bijective functions guarantee that each plaintext maps to a unique ciphertext and every ciphertext corresponds to a plaintext, which is ideal for encryption schemes.

Theoretical and Practical Implications

Theoretically, it is possible to have cryptographic functions that are injective but not surjective. Such functions can arise in specific constrained scenarios, often where the ciphertext space is larger than the plaintext space. Let's explore a few examples:

Simple Substitution Cipher with Redundant Ciphertext Alphabet

Imagine a substitution cipher that maps the 26 letters of the English alphabet to 30 unique symbols, with 4 symbols never used. In this scenario, the function is injective because each plaintext letter maps to a unique ciphertext symbol, but it is not surjective because not all ciphertext symbols are used.

Padding-Based Encryption Schemes

In some encryption schemes, plaintext is padded to a fixed block size before encryption, resulting in a larger ciphertext space. For example, if plaintexts are 8-bit values but padded to 16-bit values, some 16-bit ciphertexts may not be used, depending on the padding scheme. This creates an injective but not surjective scenario.

Simplified Theoretical Models

Consider a toy encryption system where plaintexts are 2-bit values and ciphertexts are 3-bit values. If the encryption function maps each 2-bit value to a unique 3-bit value, but not all 3-bit values are used, this function is injective but not surjective. An example might be where 00 maps to 001, 01 maps to 010, 10 maps to 011, and 11 maps to 100, with 101, 110, and 111 unused.

In practical cryptography, it is generally desirable for encryption functions to be both injective and surjective, ensuring all possible ciphertexts are valid and each plaintext maps to a unique ciphertext. However, understanding injective but not surjective mappings can be useful for theoretical discussions or specific constrained applications.

Conclusion

In summary, while the theoretical understanding of functions that are onto but not one-to-one is valuable for certain applications and theoretical discussions in cryptography, practical cryptographic systems typically require bijective functions for optimal security and decryption efficiency.