Definition of support in the context of an encryption scheme and usage of P = NP assumption in lemma 9.2 (Arora, Barak)

Question

EDIT: I've migrated the question by deleting the same question I asked on mathematics stackexchange.

2 questions: (1) I am confused about the definition of support used in the proof given in the textbook Computational Complexity: A Modern Approach lemma 9.2 by Arora and Barak (2) The usage of the assumption that $\boldsymbol{\mathbf{P}} = \boldsymbol{\mathbf{NP}}$

Lemma 9.2 states that

if $\boldsymbol{\mathbf{P}} = \boldsymbol{\mathbf{NP}}$, then given any polynomial-time computable encryption scheme $(E, D)$ with key length $n$ shorter than the message length $m$ and where $E$ and $D$ are each poly-time computable functions satisfying $D_k(E_k(x)) = x$ for plaintext $x$, we can construct a polynomial-time algorithm $A$ such that for every input length $m$ we can construct a pair of messages $x_0, x_1 \in \{0, 1\}^m$ satisfying that the algorithm $A$ distinguishes any given encryption of either $x_0$ or $x_1$ with probability greater than $\frac{3}{4}$.

(1) In the proof, they write:

Let $S \subseteq \{0, 1\}^*$ denote the support of $E_{U_n}(0^m)$

where $U_n$ is the uniform distribution on $\{0, 1\}^n$ and then they state:

Note that $y \in S$ if and only if $y = E_k(0^m)$; hence if $\boldsymbol{\mathbf{P}} = \boldsymbol{\mathbf{NP}}$ then membership in $S$ can be efficiently verified.

But the definition of a support as I have known is that the support of a function is the smallest closed set of inputs where the function does not vanish. But $y$ is the output of the encryption function so how can it be in defined to be in the support of the function in the definition I'm using? How is the support defined properly in this case?

(2) My second confusion is on the statement

Note that $y \in S$ if and only if $y = E_k(0^m)$; hence if $\boldsymbol{\mathbf{P}} = \boldsymbol{\mathbf{NP}}$ then membership in $S$ can be efficiently verified.

It seems that verification is efficient since in this case given a witness, a key $k$, one can encrypt $0^m$ with key $k$ and compare the output with $y$ and encryption is a poly-time computable function. Where does the assumption $\boldsymbol{\mathbf{P}} = \boldsymbol{\mathbf{NP}}$ come into play?

Answer 1

If you read the statements carefully, you see that $E_{U_n}(0^m)$ does not denote the encryption of $0^m$ with a specific key. It is function applied to a probability distribution - so $y$ is actually a probability distribution itself.

And this means, the word support fits to your understanding: It is the minimal set in the codomain (seeing $E$ as a function), where the probability is not 0 for any input from $U_n$ (side-note: the term closed doesn't really do anything for discrete or finite sets) - it is precisely the image of $E$ for this specific key length.

Another way to see this: The set $S$ is the image of the encryption function - for the specific parameters $m,n$.

Regarding this statement:

Note that $y \in S$ if and only if $y = E_k(0^m)$; hence if $\boldsymbol{\mathbf{P}} = \boldsymbol{\mathbf{NP}}$ then membership in $S$ can be efficiently verified.

This sentence might be missing something: It should state for claraification, that this is true for some key $k$ taken from $U_n$.

Regarding your 2nd question: For any $NP$ problem, verifying a witness if polynomial. But given some value in the codomain of $E$, you can't decide if it belongs to $S$ or not. However, if $P=NP$ you can find a witness in polynomial time. If for some potential witness exists, it is in $S$, and if no witness exists, it is not in $S$.