<commit_before>% Copyright 2021 Google LLC
%
% Use of this source code is governed by an MIT-style
% license that can be found in the LICENSE file or at
% https://opensource.org/licenses/MIT.

%!BIB program = biber
%!TeX program = lualatex
%!TeX spellcheck = en-US

\documentclass[hctr2.tex]{subfiles}
\begin{document}
\subsection{Main lemma}\label{mainlemma}
In what follows, we take world X (the ``real world'') 
to be \(\HCTR[\Perm(n)]\),
ie HCTR with all calls to the block cipher
replaced with calls to a random permutation,
and world Y (the ``ideal world'') to be \(\pm\widetilde{\mathrm{rnd}}\),
which maps every query to a random response such that
all responses of the appropriate length are equally likely;
we then use the H-coefficient technique to bound
the distinguishing advantage between them
for a fixed adversary \(A \in \mathcal{A}(q, \sigma, t)\)
as defined in \autoref{definitions}.

We use superscripts to distinguish between queries;
where we refer to \(r\), \(s\), we assume that \(r < s\).
An encryption query \((T^s, P^s)\) yields ciphertext \(C^s\)
while a decryption query \((T^s, C^s)\)
yields plaintext \(P^s\).
We forbid ``pointless queries'':
encryption queries \((T^s, P^s)\)
such that \((T^r, P^r) = (T^s, P^s)\) for some \(r < s\), 
or decryption queries \((T^s, C^s)\)
such that \((T^r, C^r) = (T^s, C^s)\) for some \(r < s\),
whether query \(r\) was an encryption or decryption query.

For each query \(s\), 
let \(m^s \defeq \ceil{\abs{P^s}/n} = \ceil{\abs{C^s}/n}\)
be the number of blocks in the response,
and let \(d^s \defeq m^s + \ceil{\abs{T^s}/n}\)
be the number of blocks in the query.
Note that \(d^s\) is the degree of the hash
function polynomial used in query \(s\)
(since all but one block of the message is hashed),
and that \(\sum_s d^s \leq \sigma\).
We give the adversary some extra information
which is included in the transcript.
In world X, this information is:
\begin{itemize}
    \item the ``leftover block'' for each query:
    where a query has plaintext/ciphertext
    that is not a multiple of the block size,
    this is the extra output from the last
    block cipher call that is not used.
    For query \(s\), this is 
    \begin{displaymath}
        D^s = \XCTR_\pi(S^s)[\abs{P^s} - n; nm^s-\abs{P^s}]
    \end{displaymath}
    \item the hash key \(\hgen\), given after all queries are complete
    \item the mask \(L\), given after all queries are complete
\end{itemize}
In world Y, random output of the expected
length is substituted. Since the adversary can always ignore
this information, giving it to them cannot make their performance worse.

\subsubsection{Good and bad transcripts}
For \(j \in \{1 \ldots m^s-1\}\) we define \(S_j^s = S^s \xor \fromint(j)\),
the block cipher inputs used in XCTR, and \(Y_j^s\) the corresponding
outputs, so that in world X \(Y_j^s = \pi(S_j^s)\) and 
\(Y_1^s \Concat \cdots \Concat Y_{m^s-1}^s = \XCTR_\pi(S^s)[0;n(m^s -1)]\).

Given the full transcript, including \(\hgen\) and \(L\),
we can infer all block cipher plaintexts and ciphertexts.
For each query
(omitting the query superscript \(s\) for readability)
we know \(T\), \(P\), \(C\) and \(D\) and so can infer:
\begin{align*}
    M \Concat N &= P \\
    U \Concat V &= C \\
    \MM &= M \xor H_{\hgen}(T, N)\\
    \UU &= U \xor H_{\hgen}(T, V)\\
    S &= \MM \xor \UU \xor L\\ 
    S_j &= S \xor \fromint(j)\\
    Y_1 \Concat \cdots \Concat Y_{m-1} &= (N \xor V) \Concat D
\end{align*}
This gives us multisets \(\mathcal{D}\) and \(\mathcal{R}\)
of inferred block cipher plaintexts and ciphertexts:
\begin{align*}
    \mathcal{D} \defeq [\fromint(0), \fromint(1)] \uplus &
    \biguplus_s [\MM^s, S_1^s, \ldots, S_{m^s-1}^s]\\
    \mathcal{R} \defeq [\hgen, L] \uplus &
    \biguplus_s [\UU^s, Y_1^s, \ldots, Y_{m^s-1}^s]
\end{align*}
We therefore infer
\(\abs{\mathcal{D}} = \abs{\mathcal{R}} = \sigma_m \defeq 2 + \sum_s m^s\)
block cipher plaintexts/ciphertexts
from \(\sigma_m n\) bits of response
(including the extra information \(D^s\), \(\hgen\), \(L\)).
A transcript is ``bad'' (\(\tau \in \Tb\))
iff any entry in \(\mathcal{D}\) or \(\mathcal{R}\)
has multiplicity greater than one,
ie if any pair of inferred plaintexts are the same, or
if any pair of inferred ciphertexts are the same.

Since responses in world Y are coin flips,
the probability of a 
particular \(\tau \in \Tc\), good or bad,
in world Y is always simply \(2^{-\sigma_m n}\).
For a transcript \(\tau \in \Tg\),
the probability in world X
is the probability of all of those plaintext/ciphertext
pairs being part of a given random permutation.
This is 
\(\prod_{i=0}^{\sigma_m -1}1/(2^n - i)\).
Thus \(\prob{Y = \tau} \leq \prob{X = \tau}\)
for all \(\tau \in \Tg\) as required (\autoref{hco}).

\subsubsection{Case analysis of collisions}
Next we bound \(\prob{Y \in \Tb}\).
We consider a case by case analysis of possible collisions,
in either inferred plaintexts (\(\mathcal{D}\))
or inferred ciphertexts (\(\mathcal{R}\)),
and bound the probability in world Y each case.

Responses are random in world Y,
but some caution is required.
If we know the adversary's query \(s\), then conditioning on that,
we cannot treat the response to query \(r < s\) as uniformly random;
if the choice of later query depends on the earlier response,
knowing the later query is information about the earlier response.
However, conditioning on a query and all prior queries and responses,
we still have that \(\hgen\), \(L\), and the
query response are uniformly random and independent,
and so we can consider them in any order.

Consider for example the case \(S_i^r \qeq \MM^s\):
for a given \(r\), \(s\), \(i\),
we want to evaluate \(\prob{S_i^r = \MM^s}\).
From our inference rules, \(S_i^r = \MM^s\)
iff \(L = M^r \xor H_{\hgen}(T^r, N^r) \xor U^r \xor H_{\hgen}(T^r, V^r)
\xor \fromint(i) \xor M^s \xor H_{\hgen}(T^s, N^s)\).
\(\hgen\) and \(L\) are given at the end of the transcript
and so are independent of all other queries and responses.
If we knew the entire transcript except \(L\),
we would know the entire right hand side of this equation.
In world X, we would also know for example that \(L \neq \hgen\), but
in world Y, conditioning on the rest of the transcript,
all values of \(L\) are equally likely;
therefore this equation holds with probability exactly \(1/2^n\).

There are twenty-two cases to consider,
ten of which arise because we use the block cipher
to generate \(\hgen\) and \(L\).
In fourteen cases, the probability of a collision
between two specific blocks is \(1/2^n\):

\subfile{casetable.tex}
\begin{itemize}
    \item
    \(\hgen \qeq L\),
    \(L \qeq \UU^s\),
    \(L \qeq Y_j^s\),
    \(\fromint(0) \qeq S_j^s\),
    \(\fromint(1) \qeq S_j^s\),
    \(S_i^r \qeq \MM^s\),
    \(\MM^r \qeq S_j^s\),
    \(\MM^s \qeq S_j^s\):
    Given \(\hgen\) and all queries and responses,
    there is exactly one value of \(L\)
    which causes the equation to hold.
    \item
    \(\hgen \qeq Y_j^s\),
    \(\UU^r \qeq Y_j^s\),
    \(Y_i^r \qeq Y_j^s\),
    \(Y_i^s \qeq Y_j^s\) where \(i < j\): 
    If query \(s\) is an encryption query,
    then given \(\hgen\), \(L\), query \(s\), 
    all prior queries and responses, and
    \(C^s[0;jn]\), there is exactly one value of
    \(C^s[jn;n]\) that results in the equation holding.
    If \(s\) is a decryption query, the same reasoning holds
    with \(P^s\), \(C^s\) swapped.
    \item 
    \(\UU^s \qeq Y_j^s\):
    If query \(s\) is a decryption query,
    the exact argument above applies.
    If it is an encryption query,
    then given \(\hgen\), \(L\), \(T^s\), \(P^s\),<commit_msg>ebiggers@ fixes - unnecessary Ls<commit_after>% Copyright 2021 Google LLC
%
% Use of this source code is governed by an MIT-style
% license that can be found in the LICENSE file or at
% https://opensource.org/licenses/MIT.

%!BIB program = biber
%!TeX program = lualatex
%!TeX spellcheck = en-US

\documentclass[hctr2.tex]{subfiles}
\begin{document}
\subsection{Main lemma}\label{mainlemma}
In what follows, we take world X (the ``real world'') 
to be \(\HCTR[\Perm(n)]\),
ie HCTR with all calls to the block cipher
replaced with calls to a random permutation,
and world Y (the ``ideal world'') to be \(\pm\widetilde{\mathrm{rnd}}\),
which maps every query to a random response such that
all responses of the appropriate length are equally likely;
we then use the H-coefficient technique to bound
the distinguishing advantage between them
for a fixed adversary \(A \in \mathcal{A}(q, \sigma, t)\)
as defined in \autoref{definitions}.

We use superscripts to distinguish between queries;
where we refer to \(r\), \(s\), we assume that \(r < s\).
An encryption query \((T^s, P^s)\) yields ciphertext \(C^s\)
while a decryption query \((T^s, C^s)\)
yields plaintext \(P^s\).
We forbid ``pointless queries'':
encryption queries \((T^s, P^s)\)
such that \((T^r, P^r) = (T^s, P^s)\) for some \(r < s\), 
or decryption queries \((T^s, C^s)\)
such that \((T^r, C^r) = (T^s, C^s)\) for some \(r < s\),
whether query \(r\) was an encryption or decryption query.

For each query \(s\), 
let \(m^s \defeq \ceil{\abs{P^s}/n} = \ceil{\abs{C^s}/n}\)
be the number of blocks in the response,
and let \(d^s \defeq m^s + \ceil{\abs{T^s}/n}\)
be the number of blocks in the query.
Note that \(d^s\) is the degree of the hash
function polynomial used in query \(s\)
(since all but one block of the message is hashed),
and that \(\sum_s d^s \leq \sigma\).
We give the adversary some extra information
which is included in the transcript.
In world X, this information is:
\begin{itemize}
    \item the ``leftover block'' for each query:
    where a query has plaintext/ciphertext
    that is not a multiple of the block size,
    this is the extra output from the last
    block cipher call that is not used.
    For query \(s\), this is 
    \begin{displaymath}
        D^s = \XCTR_\pi(S^s)[\abs{P^s} - n; nm^s-\abs{P^s}]
    \end{displaymath}
    \item the hash key \(\hgen\), given after all queries are complete
    \item the mask \(L\), given after all queries are complete
\end{itemize}
In world Y, random output of the expected
length is substituted. Since the adversary can always ignore
this information, giving it to them cannot make their performance worse.

\subsubsection{Good and bad transcripts}
For \(j \in \{1 \ldots m^s-1\}\) we define \(S_j^s = S^s \xor \fromint(j)\),
the block cipher inputs used in XCTR, and \(Y_j^s\) the corresponding
outputs, so that in world X \(Y_j^s = \pi(S_j^s)\) and 
\(Y_1^s \Concat \cdots \Concat Y_{m^s-1}^s = \XCTR_\pi(S^s)[0;n(m^s -1)]\).

Given the full transcript, including \(\hgen\) and \(L\),
we can infer all block cipher plaintexts and ciphertexts.
For each query
(omitting the query superscript \(s\) for readability)
we know \(T\), \(P\), \(C\) and \(D\) and so can infer:
\begin{align*}
    M \Concat N &= P \\
    U \Concat V &= C \\
    \MM &= M \xor H_{\hgen}(T, N)\\
    \UU &= U \xor H_{\hgen}(T, V)\\
    S &= \MM \xor \UU \xor L\\ 
    S_j &= S \xor \fromint(j)\\
    Y_1 \Concat \cdots \Concat Y_{m-1} &= (N \xor V) \Concat D
\end{align*}
This gives us multisets \(\mathcal{D}\) and \(\mathcal{R}\)
of inferred block cipher plaintexts and ciphertexts:
\begin{align*}
    \mathcal{D} \defeq [\fromint(0), \fromint(1)] \uplus &
    \biguplus_s [\MM^s, S_1^s, \ldots, S_{m^s-1}^s]\\
    \mathcal{R} \defeq [\hgen, L] \uplus &
    \biguplus_s [\UU^s, Y_1^s, \ldots, Y_{m^s-1}^s]
\end{align*}
We therefore infer
\(\abs{\mathcal{D}} = \abs{\mathcal{R}} = \sigma_m \defeq 2 + \sum_s m^s\)
block cipher plaintexts/ciphertexts
from \(\sigma_m n\) bits of response
(including the extra information \(D^s\), \(\hgen\), \(L\)).
A transcript is ``bad'' (\(\tau \in \Tb\))
iff any entry in \(\mathcal{D}\) or \(\mathcal{R}\)
has multiplicity greater than one,
ie if any pair of inferred plaintexts are the same, or
if any pair of inferred ciphertexts are the same.

Since responses in world Y are coin flips,
the probability of a 
particular \(\tau \in \Tc\), good or bad,
in world Y is always simply \(2^{-\sigma_m n}\).
For a transcript \(\tau \in \Tg\),
the probability in world X
is the probability of all of those plaintext/ciphertext
pairs being part of a given random permutation.
This is 
\(\prod_{i=0}^{\sigma_m -1}1/(2^n - i)\).
Thus \(\prob{Y = \tau} \leq \prob{X = \tau}\)
for all \(\tau \in \Tg\) as required (\autoref{hco}).

\subsubsection{Case analysis of collisions}
Next we bound \(\prob{Y \in \Tb}\).
We consider a case by case analysis of possible collisions,
in either inferred plaintexts (\(\mathcal{D}\))
or inferred ciphertexts (\(\mathcal{R}\)),
and bound the probability in world Y each case.

Responses are random in world Y,
but some caution is required.
If we know the adversary's query \(s\), then conditioning on that,
we cannot treat the response to query \(r < s\) as uniformly random;
if the choice of later query depends on the earlier response,
knowing the later query is information about the earlier response.
However, conditioning on a query and all prior queries and responses,
we still have that \(\hgen\), \(L\), and the
query response are uniformly random and independent,
and so we can consider them in any order.

Consider for example the case \(S_i^r \qeq \MM^s\):
for a given \(r\), \(s\), \(i\),
we want to evaluate \(\prob{S_i^r = \MM^s}\).
From our inference rules, \(S_i^r = \MM^s\)
iff \(L = M^r \xor H_{\hgen}(T^r, N^r) \xor U^r \xor H_{\hgen}(T^r, V^r)
\xor \fromint(i) \xor M^s \xor H_{\hgen}(T^s, N^s)\).
\(\hgen\) and \(L\) are given at the end of the transcript
and so are independent of all other queries and responses.
If we knew the entire transcript except \(L\),
we would know the entire right hand side of this equation.
In world X, we would also know for example that \(L \neq \hgen\), but
in world Y, conditioning on the rest of the transcript,
all values of \(L\) are equally likely;
therefore this equation holds with probability exactly \(1/2^n\).

There are twenty-two cases to consider,
ten of which arise because we use the block cipher
to generate \(\hgen\) and \(L\).
In fourteen cases, the probability of a collision
between two specific blocks is \(1/2^n\):

\subfile{casetable.tex}
\begin{itemize}
    \item
    \(\hgen \qeq L\),
    \(L \qeq \UU^s\),
    \(L \qeq Y_j^s\),
    \(\fromint(0) \qeq S_j^s\),
    \(\fromint(1) \qeq S_j^s\),
    \(S_i^r \qeq \MM^s\),
    \(\MM^r \qeq S_j^s\),
    \(\MM^s \qeq S_j^s\):
    Given \(\hgen\) and all queries and responses,
    there is exactly one value of \(L\)
    which causes the equation to hold.
    \item
    \(\hgen \qeq Y_j^s\),
    \(\UU^r \qeq Y_j^s\),
    \(Y_i^r \qeq Y_j^s\),
    \(Y_i^s \qeq Y_j^s\) where \(i < j\): 
    If query \(s\) is an encryption query,
    then given \(\hgen\), query \(s\), 
    all prior queries and responses, and
    \(C^s[0;jn]\), there is exactly one value of
    \(C^s[jn;n]\) that results in the equation holding.
    If \(s\) is a decryption query, the same reasoning holds
    with \(P^s\), \(C^s\) swapped.
    \item 
    \(\UU^s \qeq Y_j^s\):
    If query \(s\) is a decryption query,
    the exact argument above applies.
    If it is an encryption query,
    then given \(\hgen\), \(T^s\), \(P^s\),
{'fraction_non_alphanumeric': 0.15663839021503256, 'fraction_numerical': 0.004208588150193989, 'mean_word_length': 3.121409214092141, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 3, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4771130', 'n_tokens_mistral': 5543, 'n_tokens_neox': 5312, 'n_words': 2200}