1
$\begingroup$

I am currently reading about RS codes. I see that they are using a Galois Fields (Finite Fields) as vector spaces. Is there any other particular reason other than the fact that they simplify binary arithmetic and for example in $GF(2^8)$ each byte can be considered as a vector? Can they work in vector spaces that are defined on infinite fields like $\mathbb{Q}$. Thanks in advance for your time.

PS: Sorry in advance if this isn't the right place to post this question, but I saw that both Math and Crypto StachExchanges have coding-theory tag.

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ In crypto, we generally don't work in $\mathbb{Q}$; for boring practical reasons, we prefer messages that can be expressed in a bounded number of bits. $\endgroup$
    – poncho
    Commented Feb 22, 2022 at 20:28
  • 3
    $\begingroup$ We also like to be able to define a uniform probability distribution over a space! $\endgroup$
    – Mikero
    Commented Feb 22, 2022 at 21:24
  • 1
    $\begingroup$ What poncho and Mikero mention makes sense, and these are crucial reasons why we don't consider infinite algebraic structures in cryptography. However, just to satisfy your curiosity: Reed-Solomon codes can be easily applied over any field, no matter what size. In fact, they exist over any ring, no matter the size, as long as it contains a large enough "exceptional sequence" (e.g. crypto.stackexchange.com/a/96507/13843). $\endgroup$
    – Daniel
    Commented Feb 22, 2022 at 21:55
  • 1
    $\begingroup$ However, Reed-Solomon codes on their own simply take a message and add some redundancy for decoding errors. Their use in cryptography, for example in Shamir secret-sharing, requires sampling uniformly random elements over this structure, which as Mikero mentioned is not possible. $\endgroup$
    – Daniel
    Commented Feb 22, 2022 at 21:55

1 Answer 1

Reset to default
3
$\begingroup$

Yes they can work, and under some channel noise conditions be useful for error correction coding in a continuous channel. This idea was originally due to Prof. Welch (of Welch-Berlekamp algorithm and Welch bound fame) who had unpublished lecture notes about it in the 1980s, and from an engineering point of view $\mathbb{C}$ was the obvious field to use, where the issue of existence of primitive roots of unity of any desired order $n$ is trivial, just take $\omega=\exp\{2 \pi i/n\}.$

As the comments pointed out, this is not so useful for cryptography, since the existence of uniform distributions are crucial for certain protocols. Of course, Reed-Solomon codes in their field evaluation formulation are intimately linked to Shamir secret sharing, say with threshold $t,$ but in a finite field setting for enabling no leakage of information if less than $t$ shares are known.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.