Score:6

Covering codes for digital signatures

ru flag

An encryption scheme should be injective in the sense that each ciphertext should only be associated with at most one message, in order that decryption is unambiguous. An efficient signature verification scheme should be surjective in the sense that each message (equivalently message hash) has an associated signature, so that all possible messages (resp. hashes) can be signed without rehashing.

In code-based cryptography then, error-correction codes are a logical choice for encryption where the set of uniquely-decodable-vectors/ciphertexts in the ambient vector space map to unique codewords/messages. For signatures, a more obvious thought is to use covering codes where all vectors/messages in the ambient vector space map to at least one covering-codeword/signature.

Is this an observation that has been considered before and are there covering code analogies to binary Goppa codes, that allow fast identification of a codeword that is close to a given covering codeword, but whose structure can hopefully be effectively concealed?

Score:2
gd flag

This makes perfect sense in principle. However you will need some extra properties from your covering code. My understanding is that no one ever came up with a family of covering codes having all three properties (except maybe WAVE but it is awkward as it rely on far codewords, not close ones...). In fact, I am not even aware of a family of codes achieving the first constraint. If you know one, that is a very good starting point toward a serious open problem.

  1. You need your covering code to come with an efficient algorithm for "quantization", that is for actually finding a close codeword to an arbitrary target. That quantization radius must be small enough to prevent generic algorithm such as Information Set Decoding to efficiently perform the same task.

  2. You need to prevent leakage of information from signature transcript. This has often been a downfall of proposed code-based signature schemes.

  3. You can scramble it efficiently to make a public key out of it. Applying an isometry might not be enough for binary codes, because of the Code Equivalence Problem is often quite easy.

Score:1
ng flag

Sort of --- but likely not in the way that you imagine. By this, I mean that what you want exists in the lattice-crypto world. I imagine it means it exists (or you could make it work) in the code-based crypto world as well, but I don't work in that world/can't comment on that as much.

In lattice-based crypto (or in the algorithmic theory of euclidean lattices more generally), there are "packing" and "covering" problems. By this I mean

  • Packing: Given a lattice point $\ell\in L$ ("codeword") perturbed by a small amount $e$ (less than the "packing radius" $\lambda_1(L)/2$), recover $\ell$ from $\ell + e$.

  • Covering: Given an arbitrary point $x \in \mathbb{R}^n\supseteq L$, find the nearest point $\ell\in L$, of distance at most the covering radius $\rho(L)$ of the lattice from $x$.

There are of course approximate versions of the above as well (where one replaces the bounds $\lambda_1(L)/2$ and $\rho(L)$ by $\gamma\lambda_1(L)/2$ and $\gamma\rho(L)$ for some $\gamma \geq 1$).

Anyway, some problems (exact CVP) can be used to solve both of the above lattice problems. If one doesn't have an exact CVP oracle though (and instead can only solve approximate CVP for some approximation factor), the situation bifurcates. Namely

  • Oracles for "CVP with a distance guaranteed" (or Bounded Distance Decoding). $\mathsf{SVP}_\gamma$ can often be solved with oracles of this type

  • Oracles for "Absolute Distance Decoding". $\mathsf{SIVP}_\gamma$ can often be solved with oracles of this type (or --- knowing a short dual basis often suffices for approximately solving "covering" problems)


One way of reading your question (in the lattice world, which is not the code world, but is often related) is whether one can get signatures from covering-type assumptions, for example from $\mathsf{SIVP}_\gamma$ instead of $\mathsf{SVP}_\gamma$ (LWE, via the worst-case to average-case reductions, relies on the worst-case hardness of $\mathsf{SVP}_\gamma$). The answer is easily "yes". In particular Lybushavesky's "Fiat Shamir with Aborts" construction fits this paradigm. Therefore, I would expect a similar coding-based construction to be able to be based on a covering-type problem. This paper (on page 2) makes it sound like such a construction is not known though, but progress in this area morally feels like it would be relevant to your question.

Note that other lattice-based signatures ("Hash-and-Sign") can similarly be seen from this perspective. One first hashes the message to an arbitrary point in $\mathbb{R}^n$, then uses a short basis to round this to the nearest point of the lattice, i.e. you solve the covering problem on that lattice.

Second, the closest analogue to code-based signatures (which you seem to be interested in) in the lattices context are "GGH signatures". These were proposed in the 90's, and are famously insecure (them, as well as NTRUSign, are two of the initial attempts at lattice-based signatures. These are notoriously tricky, to the point that we were able to construct FHE before signatures from standard lattice problems iirc).

Anyway, there is a recent attempt to redo GGH signatures in the context of lattice-based crypto. These are known as signatures from the Lattice Isomorphism Problem (see here for a sample construction). This led to the Hawk signature scheme. It has a "compressed variant" where you take a signature $(s_0, s_1)$, "drop" $s_0$, and then later reconstruct it as $s_0'\approx s_0$.

It seems highly likely to me that you can view this form of compression as applying a particular "lattice-based" covering code to $s_0$, so this is perhaps close to what you're interested in. You could plausibly post-process $(s_0, s_1)$ via some other (lattice-based) covering code instead, but I don't know if anyone has done this yet.

Daniel S avatar
ru flag
Many thanks, I'm familiar with much of the material for lattice signatures, but my interest is in code-based systems and in particular whether the existing literature on covering codes can be leveraged.
I sit in a Tesla and translated this thread with Ai:

mangohost

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.