8
$\begingroup$

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?

$\endgroup$
0

3 Answers 3

11
$\begingroup$

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.
$\endgroup$
15
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\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.