3
$\begingroup$

In the cryptography course, the professor said that:

these days for symmetric key encryption, instead of sending out the key, Alice sends the seed to Bob, and then based on that Bob can get the key.

I didn't actually understand the role of the seed, besides, if Bob can generate the key based on the seed so Eve can do the same, right?

$\endgroup$
2
  • 4
    $\begingroup$ Some surrounding context for this quote would be very helpful. $\endgroup$ Nov 2, 2021 at 2:35
  • 1
    $\begingroup$ Which course? Where? Online or "real" university? Link? $\endgroup$
    – ilkkachu
    Nov 2, 2021 at 11:21

3 Answers 3

5
$\begingroup$

Seed is a term used in random number generators, for symmetric-key encryption, we talk about keys.

If your professor meant:

Instead of sending the full one time pad, we send a seed for it.

Then he's talking about stream ciphers where a key is exchanged to be used in encryption.

Another possibility is that he's trying to simplify the concept of "key exchange" for you. Key exchange is a way to establish a common secret key between 2 (or more) parties over a public insecure channel. Diffie-Hellman is a archetypal example of key exchange algorithm.

$\endgroup$
2
$\begingroup$

Your professor is talking about the following relatively common optimization

Let $\mathcal{K}$ be a set, and let $\mathsf{Sample} : \{0,1\}^r\to\mathcal{K}$ be an algorithm that, on input $r$ uniformly random bits, outputs an element $k\in \mathcal{K}$.

If $\mathsf{PRG} : \{0,1\}^s\to\{0,1\}^r$ is a PRG, then for $s\leftarrow\{0,1\}^s, r\leftarrow\{0,1\}^r$, the distributions of $$\mathsf{Sample}(\mathsf{PRG}(s))\approx_c \mathsf{Sample}(r)$$ are computationally indistinguishable.

The proof of this is roughly trivial. By the security of the PRG, $\mathsf{PRG}(s) \approx_c r$. Applying the (efficient) algorithm $\mathsf{Sample}$ maintains computational indistinguishability (as otherwise $\mathsf{Sample}$ would be an efficient adversary against the PRG).

Essentially, if your final construction needs an $s$-bit key, it can often suffice to have the key be a $r$-bit PRG seed, and then stretch this to $s$ bits with the PRG.

There are a number of specific details to point out in the above:

  1. The final key generated from $\mathsf{Sample}(r)$ need not itself be uniformly random (although this is the most common case by far).

  2. One can weaken the assumptions on the above result further --- by appealing to randomness extractors, the input $r$ itself need not be uniform, but instead requires "enough min entropy" in a way that can be made precise.

  3. You still need key exchange. The security game of PRGs require that the seed of the PRG be kept secret for security to hold, so you still need to ensure that Eve does not gain access to the seed (as you mention).

All this optimization is saying is that the "payload" of the key exchange can be made to be smaller using a PRG (in particular, it can be $r$ bits rather than $s$ bits).


There is a related optimization (that is different in a subtle way) that it may be worth discussing as well. Often in cryptography (in particular, in lattice and coding-based cryptography) one has to transmit a large, uniformly random element. In particular, the Learning with Errors assumption is about LWE "samples":

$$ (A, As+e)$$

I won't bother define everything in this sample, and instead say that $A$ is typically a uniformly random matrix, of size $\approx 1-10kb$, depending on the particular scheme.

You might be tempted to replace this uniformly random object with a PRG seed $s$, which one can then deterministically expand to the random value $A$ later. As PRG seeds are on the order of $\approx 128$ bits, this is a significant (potential) gain.

This is not a valid optimization though, because of the 3rd point above --- you can't use a PRG to "compress" a uniformly random value to a short seed in this way if your scheme later makes this uniformly random value public. Or you can, but for particular PRGs this may totally break security.

There are still similar things you can do with things called extendible output functions (for whatever reason, the acronym is XOF). These are hashing-based primitives that (roughly) are meant to be used when one wants PRG-like properties, but with a public seed.

Anyway, using an XOF to compress a large uniformly random value is an incredibly common optimization. I am pretty sure that both of the LPR-based NIST PQC finalists (Saber/Kyber) use this optimization, although any particular implementation could mildly deviate from the specification and include/fail to include the optimization.

$\endgroup$
0
$\begingroup$

The main thing about this question was that I thought that seed is sending in cleartext.
But in the reality, for example, for AES or DES seeds are sent encrypted by DH or RSA cryptosystems, and then the seed will be used to generate the keys in key schedule in order to generate different round keys.

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