One option is to use error correction codes as a cryptographic primitive.
The basics Error correction codes are digital codes used to reliably send data through an unreliable channel.
In a noisy channel, corruption of some of the bits would yield an invalid code word, so the error is detected.
If the space between code words is big enough, a reasonable guess can be made about which code word was probably corrupted and the error can be corrected.
Error values purposefully introduced in encryption schemes usually choose Hamming weights large enough to be secure and small enough to be corrected.
W = a. G. Generators are created by concatenating two arrays: I, which is a square matrix with ones in the diagonal and zeros everywhere else and P which has the error coding values.
In addition if s is non-zero and the error in w' is small enough you can use s to recover the error where w' = w + e, and thus the original w = w' + e. Unfortunately, in the general case, mapping s to e involves trying all possible errors and calculating their expected s values, storing them in a table, then looking up the error from the table using s. If you select H carefully you can create a function which gives you e from s directly.
Once you have the error, you can calculate the correct w, and then recover a. This means we can create a function Dg based on H, which will take a corrupted w' and give us the original a. Efficient mapping syndromes to errors Hamming codes There are several schemes which are used to build H in such a way that we can calculate the error from the syndrome efficiently.
These are called Hamming codes and they are popular because they are easy to implement for both encoding and error correction.
They are not the most efficient encoding scheme for correcting multibit errors with the minimum size code word, however.
Goppa codes Goppa codes were developed to give the most efficient mapping of maximum correctable error versus smallest size difference between w and a. The scheme involves picking several base values and functions and building up H from powers of those values multiplied by polynomials of these functions.
To find the error, the syndrome is turned into a polynomial, then that polynomial is processed into an oracle function.
The oracle function can be queried for each bit of the error to determine whether it is 1 or zero.
The idea is that because the density of 1s in the parity check matrix is small, the connections between the error bits and syndrome bits are small.
This fact can be used to create probabilistic algorithms for picking likely error bits by walking down each error bit and seeing how likely that error bit would be one or zero based on the connection this error bit has to the syndrome bits, and the value of the connected syndrome bits.
Calculate m= Dg(cPr-1)S-1 The arrays S and Pr hide the details of our original matrix G so the attacker doesn't know H and thus can't perform the Goppa algorithm to recover the error.
Other error correcting code schemes have been proposed to replace Goppa codes in the McEliece scheme.
Attempts at making a signature scheme based on error correcting codes have also been broken.
G is public and anyone can use G to recover the original message as long as the error bits are small enough.
The hamming weights of x, y, r1, r2, and e are chosen so that the error xr2-r1y+e is below the decoding threshold and m should be recovered.
This Cyber News was published on www.redhat.com. Publication date: Sat, 29 Jun 2024 09:13:06 +0000