Score:8

What does puncturing in cryptography mean

tl flag

While I was reading the documentation for the cryptocode $\LaTeX$ package I stumbled across the "primitive" called puncturing in subsection 2.12. This was the first time I read about this "primitive". Additionally, I am no native speaker, which is why I have no intuition about what it could mean. Can someone explain it to me on a basic level?

Score:15
ng flag

Other than kodlu's answer, there exists another meaning of the term - potentially more specific to Cryptography rather than coding theory: That of a 'punctured' PRF. This describes a PRF $F : K \times X \rightarrow Y$, with two keys $k, k_\hat{x} \in K$. The main key $k$ allows evaluating the PRF at any point $x \in X$, while $k_\hat{x}$ allows to evaluate it at all points except a specific $\hat{x} \in X$.

There also exists generalizations of this, called 'constrained' PRFs. In a constrained PRF we are able to generate secondary keys with more generic constraints about which points of the PRF they can evaluate.

Similarly, the term 'puncturing' is then also used to refer to e.g. KEMs or encryption schemes with the same property of certain 'points' being unable to be processed with certain keys.

For some more details, check out e.g. the introductory section of this paper by Boneh, Kim and Montgomery.

Score:11
tr flag

Similarly to the meaning of everyday life, puncturing denotes the act of poking a hole into something, making that part somewhat irrelevant. In the cryptographic context, puncturable schemes usually seem to characterize schemes with an additional algorithm that removes some specified capability, for instance, decryption or a function evaluation. Some examples to add to others:

  1. Puncturable Encryption: Green and Miers use puncturable encryption in the linked paper to achieve forward-secret encryption. The idea is that ciphertext is associated with a list of tags. And there's a puncture algorithm that modifies the secret key in a way that removes decryption capability only for a specified tag.
  2. Puncturable Key Wrapping: proposed to provide better forward secrecy guarantees for symmetric key hierarchies (for instance, using a Key Encryption Key to protect a Data Encryption Key). Additional use cases are forward security of TLS1.3 with 0-RTT and outsourced file storage.
  3. The Puncturable Key Wrapping scheme above is instantiated by an AEAD scheme and a Puncturable PRF (described in this answer).
  4. Besides primitive constructions, there are other examples in proofs as well. In the book of Boneh and Shoup, an identity-based encryption scheme (construction 2) is presented that has the advantage of not requiring hashing identities into curves. The proof is (amongst) others a reduction to the Decision bilinear Diffie-Hellman problem and uses a punctured secret key.
Score:4
sa flag

There are these fantastic coding theory notes online by Jon Hall at MSU. Here is the link to Chapter 6 on modifying codes.

For a linear code $k$ is the rate (number of data bits, if binary) and $n$ is the codeword length. This means $r=n-k$ is the redundancy (number of parity check bits, if binary)

In puncturing a code you delete one coordinate but leave $k$ unchanged. This means that you still have the same number of data bits but decrease the number of parity checks. This may or may not reduce the minimum distance of the code.

See also Wikipedia which describes it in the communications context.

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.