Can Reed-Solomon codes work on infinite fields like $\mathbb{Q}$?

JAAAY

6/22/23, 8:10 PM

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.

0 + 0

coding-theory

poncho

6/22/23, 8:28 PM

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.

Mikero

6/22/23, 9:24 PM

We also like to be able to define a uniform probability distribution over a space!

Daniel

6/22/23, 9:55 PM

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. https://crypto.stackexchange.com/a/96507/13843).

Daniel

6/22/23, 9:55 PM

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.

Score:3

Crypto

kodlu

6/23/23, 7:18 AM

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.

0 + 0

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Can Reed-Solomon codes work on infinite fields like $\mathbb{Q}$?

TH: รหัส Reed-Solomon สามารถทำงานในฟิลด์ที่ไม่มีที่สิ้นสุดเช่น $\mathbb{Q}$ ได้หรือไม่

RO: Codurile Reed-Solomon pot funcționa pe câmpuri infinite precum $\mathbb{Q}$?

RU: Могут ли коды Рида-Соломона работать с бесконечными полями, такими как $\mathbb{Q}$?

VI: Mã Reed-Solomon có thể hoạt động trên các trường vô hạn như $\mathbb{Q}$ không?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.