Thesis Abstract and Dissertation Abstracts
Poly Message Ciphers and Tanti Algebraic Encryption
Abstract Category: I.T.
Course / Degree: Bachelor of Science (Honours) in Information and Communication Technology
Institution / University: University of Malta, Malta
Published in: 2008
A poly message cipher is a cryptographic cipher where more than one distinct plaintexts are encrypted into one ciphertext using different keys for each plaintext, and each plaintext can be decrypted from the ciphertext using the corresponding key. Tanti Algebraic Encryption is an example of such a cipher.
In this article, only symmetric-key cryptography is considered, but the concept of poly message ciphers can be applied to public-key cryptography as well.
FORMAL DEFINITION
=================
Formally, such a cipher has to satisfy these 2 conditions:
Let c be the ciphertext, m the plaintext (or message), k the key, C be the ciphertext-set, e(m, k) the encryption algorithm and d(c, k) the decryption algorithm.
CONDITION 1
C = e(m, k)
{d(c, k) | c elemof C} = {m}
CONDITION 2
Given that the cipher supports up to n+1 distinct messages in the same ciphertext, where n > 0,
e(m_0, k_0) = C_0
e(m_1, k_1) = C_1
e(m_2, k_2) = C_2
...
e(m_n, k_n) = C_n
C_0 intersection C_1 intersection C_2 intersection ... C_n = {c}
d(c, k_0) = m_0
d(c, k_1) = m_1
d(c, k_2) = m_2
...
d(c, k_n) = m_n
where m_0, m_1, m_2, ..., m_n are any n+1 distinct messages and k_0, k_1, k_2, ..., k_n are any n+1 distinct keys.
Informally, condition 1 means that the encryption of a particular message-key pair will return a set of ciphertexts, called a ciphertext-set, where each ciphertext, if decrypted using the same key, will return the same plaintext (message).
Condition 2 means that, given a cipher which supports encrypting up to n different messages into the same ciphertext, for any n message-key pairs (where all keys and all messages are distinct) there exists a single common ciphertext in the returned ciphertext-set of each encryption. If this common ciphertext is decrypted using any key used during encryption, it will give the corresponding message.
USES
=================
Now such a cipher is useful because, given a brute force attack on the ciphertext, the attacker will encounter a number of messages which, if the author of the ciphertext used the cipher wisely, all messages will deceivingly look like the intended message to transmit and the attacker may never know which message is the intended message to transmit. Thus such a cipher is resistant to brute force attacks.
Another useful feature of such a cipher would be plausible deniability or steganography, given that an adversary does not know that a poly message cipher was used. The adversary would be given a deceiving key to decrypt, obtain a deceiving message and consider it the intended message.
IMPLEMENTATION EXAMPLE - Tanti Algebraic Encryption (TAE)
=================
A simple example of a poly message cipher is the Tanti Algebraic Encryption (TAE).
In this cipher, messages and keys are numerically represented. Algebraic equations are used to represent ciphertext-sets and points are used to represent ciphertexts. Given an n-dimensional space, n messages can be encrypted into a single ciphertext.
The following is the description of the algorithm to encrypt 2 messages into a single ciphertext.
Let m_0 and m_1 be the different messages to encrypt and k_0 and k_1 be the different keys.
e(m_0, k_0) = m_0 x + k_0
e(m_1, k_1) = m_1 x + k_1
Now we have 2 lines, each is the ciphertext-set of the corresponding message-key pair. Given this line, it is easy to determine both the message (gradient) and the key (y-intersect). Any point on the line can be used as a ciphertext, and since a single point is not enough information to reconstruct a line, there must be another point in order to find the gradient (message). That other point shall be the y-intersect (key).
Now by finding the point of intersection between the 2 lines, we have our common ciphertext which if decrypted using k_0 will give m_0 and if decrypted using k_1 will give m_1. The point or intersection, c, is found using the following encryption formula:
c = ( [k_1 - k_0]/[m_0 - m_1] , m_0*[[k_1 - k_0]/[m_0 - m_1]] + k_0 )
And that is our cipher text, c. Notice that it’s a point containing real numbers. Now in order to decrypt c using k_i to obtain m_i (where i is 0 or 1), we use the following decryption formula, where c = (x, y):
d( (x,y) , k_i ) = (y - k_i)/x = m_i
Notice the following:
The key space is infinite, and the key can be potentially any real number.
The message can be potentially any real number.
Brute force attack would require trying all the y values, which are real numbers.
The cipher only uses addition, subtraction, multiplication and division.
The ciphertext will normally be larger than the message.
If both messages are not distinct, a point of intersection will not exist.
If both keys are not distinct, the point of intersection will be the y-intersect, which means it will not be possible to decrypt (since the 2 points to reconstruct the line will be the same).
Line equations are well understood and it can easily be seen that no back door exists.
This algorithm can be used as a single message cipher by choosing an arbitrary point on the line (ciphertext-set).
More messages can be encrypted into one ciphertext by using higher-dimensional coordinate systems. However this would require more keys in order to be used as coefficients of the extra variables. For example for 3-dimensions:
e(m_0, k_0_0, k_0_1) = m_0 x + k_0_0 y + k_0_1
e(m_1, k_1_0, k_1_1) = m_1 x + k_1_0 y + k_1_1
e(m_2, k_2_0, k_2_1) = m_2 x + k_2_0 y + k_2_1
The point of intersection between these 3 planes will then be used as the ciphertext.
Any number of messages can be encrypted into one ciphertext in this way. However the ciphertext will be larger with every new dimension added (more values in a point) and more complex formulae will be required to encrypt and decrypt.
Although in this article the message is used as the gradient and the key as the y-intersect in the 2-message encryption, the message and key can be coefficients of any term in the algebraic equation. The encryption formula would just require substitution of variables (key for message and message for key) and the decryption formula would be different. In the case of 2-message encryption, using the key as the gradient and the message as the y-intersect, the message would be found using:
d( (x,y) , k_i ) = y - k_i x = m_i
As stated above, single message encryption is possible with 2-dimensional TAE (or any larger dimension). Let's consider 2-dimensional TAE. The ciphertext would be either a random point on the line or a single value in a point (x or y) where the other value (x or y) is constant. The only restriction is that the ciphertext and y-intersect must be distinct points.
Given that we can generate any ciphertext from any plaintext using a particular key, we can actually find the key which will encrypt a given message into the ciphertext we want, simply by placing the key as the subject of the formula in the linear equation. This would make possible a steganographic message where the covertext would be the ciphertext, given that the ciphertext is well chosen. For example if the message, m, is the y-intersect, the key, k, is the gradient and the ciphertext, c, is the x-insersect then k = -m/c Unfortunately this does not guarantee a small key and the message cannot be broken down into blocks to encrypt without having a key for each block. Notice that the same is achievable using xor encryption, however in xor encryption you need a key which is exactly equal in length to the message and ciphertext for this to work.
Report Keywords/Search Tags:
tae, cryptography, encryption, cipher
This Report Abstract may be cited as follows:
No user preference. Please use the standard reference methodology.
Submission Details: Report Abstract submitted by Marc Tanti from Malta on 09-Jul-2008 20:03.
Abstract has been viewed 3509 times (since 7 Mar 2010).
Marc Tanti Contact Details: Email: marctanti@gmail.com
Disclaimer
Great care has been taken to ensure that this information is correct, however ThesisAbstracts.com cannot accept responsibility for the contents of this Report abstract titled "Poly Message Ciphers and Tanti Algebraic Encryption". This abstract has been submitted by Marc Tanti on 09-Jul-2008 20:03. You may report a problem using the contact form.
© Copyright 2003 - 2024 of ThesisAbstracts.com and respective owners.