## 2 Materials and Methods
### Hardness of Decoding Payload in Absence of Disambiguation Information
: _A payload that is generated for an input \(n\)-bits long \(\mathcal{A}\) with the proposed NPF scheme has more than \(2^{\alpha\cdot(2^{d-1}-2)}\) distinct decodings for \(\alpha=\lfloor\frac{n}{d\cdot 2^{d}}\rfloor\), where only one of them, which is specified with the disambiguation information, is the original input \(\mathcal{A}\). When \(d\) is chosen to be \(n=d\cdot 2^{d}\), \(\Omega(2^{(2^{d-1}-2)})\) different payload generations are possible._  
Proof. : We will analyze the input \(\mathcal{A}\) in blocks of \(2^{d}\)\(d\)-bits long symbols. Each symbol in a block is mapped to a variable-length non-prefix-free code-word according to the \(\Sigma\to W\), and when the code-word boundaries are unknown on that code-stream, then many different decoding possibilities appear. We aim to first count how many different decoding would be possible for a block, and then use this information to determine possibilities for the whole code-word stream. In a block of \(2^{d}\) symbols, the number of \(\ell\)-bits long code-words is \(2^{\ell}\) for \(\ell\in\{1,2,\ldots,d-1\}\), and \(2\) for \(\ell=d\) according to Proposition 1. Therefore, the number of possible permutations of those items is more than \(2^{(2^{d-1}-2)}\) as shown below. \[\frac{2^{d}!}{2!\cdot 2!\cdot 4!\cdot\ldots\cdot 2^{d-1}!} =\frac{1\cdot 2}{1\cdot 2}\cdot\frac{3\cdot 4}{1\cdot 2} \cdot\frac{5\cdot 6\cdot 7\cdot 8}{1\cdot 2\cdot 3\cdot 4}\cdot\ldots\cdot \frac{(2^{d-2}+2)\cdot\ldots 2^{d-1}+1}{1\cdot\ldots\cdot 2^{d-2}}\cdot\frac{2^{d-1}!}{2^{d-1 }!} \tag{14}\] \[>1\cdot 2^{2}\cdot 2^{4}\cdot 2^{8}\cdot\ldots\cdot 2^{2^{d-2} }\cdot 1=2^{(2^{d-1}-2)} \tag{15}\]  
Let \(\alpha=\lfloor\frac{n}{d\cdot 2^{d}}\rfloor\) be the number of blocks in an input \(n\)-bits long data stream. Since there are more than \(2^{(2^{d-1}-2)}\) different decodings per each block, then \(\alpha\) blocks in total will have _more than \(2^{\alpha\cdot(2^{d-1}-2)}\)_ distinct decoding possibilities. Given a payload and the used code-word mapping \(\Sigma\to W\), the number of distinct original data decodings is shown in Table 3. Notice that only one of them is the correct \(\mathcal{A}\), and actually generating these possibilities is computationally not feasible. Therefore, decoding the NPF stream without the code-word boundary information is computationally hard for sufficiently large \(d\) values, where as a minimum \(d=8\) in practice brings a complexity of \(2^{125})\) for possibilities. Thus, encrypting only the code-word boundary information, and transmitting the code-word stream in plain can provide privacy of the whole data in practice. The interesting point here is that the disambiguation information occupies much less space when compared to the total size of the originl data as previously analyzed in Lemma 2, which can provide a significant reduction in the encryption volume required for the data security. \begin{table}
\begin{tabular}{l l l l l l} \hline \hline  & \(n=d\cdot 2^{d}\) & **Payload Size** & **Minimum Number of** & **Dis. Info. Size** & **Percentage of Dis.Info** \\
**d** & **in Bits** & \(n\cdot(1-\frac{2}{d}+\frac{2(d+1)}{d\cdot 2^{d}})\) & **Distinct Parse \(\Omega(2^{(2^{d-1}-2)})\)** & \(n\cdot(\frac{2}{d}-\frac{2(d+1)}{2^{d}})\)** & **100 - \(\frac{Dis.Info.Size}{n}\)** \\ \hline
8 & 2048 & 1554 & \(2^{126}\) & 508 & \% 24.80 \\ \hline
12 & 48 K & 40,986 & \(2^{2046}\) & 8188 & \% 16.65 \\ \hline
16 & 1 M & 917,538 & \(2^{327,766}\) & 131,068 & \% 12.49 \\ \hline
20 & 20 M & 18,874,410 & \(2^{524,286}\) & 2,097,148 & \% 9.99 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: When \(n=d\cdot 2^{d}\), the payload size, the disambiguation information size, and the corresponding number of possible decodings are shown. Last column depicts the percentage of the volume to be encrypted to provide privacy with the specified level of ambiguity, i.e., when \(d=8\), encrypting only around 25% of the input volume (2048 bits) introduces an ambiguity of around \(2^{126}\).