# Analysis of Multivariate Scoring Functions for Automatic Unbiased Learning
to Rank

Tao Yang<EMAIL_ADDRESS>University of Utah50 Central Campus Dr. Salt
Lake CityUtah84112 ,  Shikai Fang<EMAIL_ADDRESS>University of Utah50
Central Campus Dr. Salt Lake CityUtah84112 ,  Shibo Li<EMAIL_ADDRESS>University of Utah50 Central Campus Dr. Salt Lake CityUtah84112 ,  Yulan Wang
<EMAIL_ADDRESS>University of Utah50 Central Campus Dr. Salt Lake
CityUtah84112 and  Qingyao Ai<EMAIL_ADDRESS>University of Utah50 Central
Campus Dr. Salt Lake CityUtah84112

(2020)

###### Abstract.

Leveraging biased click data for optimizing learning to rank systems has been
a popular approach in information retrieval. Because click data is often noisy
and biased, a variety of methods have been proposed to construct unbiased
learning to rank (ULTR) algorithms for the learning of unbiased ranking
models. Among them, automatic unbiased learning to rank (AutoULTR) algorithms
that jointly learn user bias models (i.e., propensity models) with unbiased
rankers have received a lot of attention due to their superior performance and
low deployment cost in practice. Despite their differences in theories and
algorithm design, existing studies on ULTR usually use uni-variate ranking
functions to score each document or result independently. On the other hand,
recent advances in context-aware learning-to-rank models have shown that
multivariate scoring functions, which read multiple documents together and
predict their ranking scores jointly, are more powerful than uni-variate
ranking functions in ranking tasks with human-annotated relevance labels.
Whether such superior performance would hold in ULTR with noisy data, however,
is mostly unknown. In this paper, we investigate existing multivariate scoring
functions and AutoULTR algorithms in theory and prove that permutation
invariance is a crucial factor that determines whether a context-aware
learning-to-rank model could be applied to existing AutoULTR framework. Our
experiments with synthetic clicks on two large-scale benchmark datasets show
that AutoULTR models with permutation-invariant multivariate scoring functions
significantly outperform those with uni-variate scoring functions and
permutation-variant multivariate scoring functions.

Unbiased learning to rank; Multivariate Scoring Function

††journalyear: 2020††copyright: acmcopyright††conference: Proceedings of the
29th ACMInternational Conference on Information and Knowledge Management;
October19–23, 2020; Virtual Event, Ireland††booktitle: Proceedings of the 29th
ACM International Conference on Informationand Knowledge Management (CIKM
’20), October 19–23, 2020, Virtual Event, Ireland††price: 15.00††doi:
10.1145/3340531.3412128††isbn: 978-1-4503-6859-9/20/10††ccs: Information
systems Learning to rank

##  1\. Introduction

The study of learning to rank with implicit user feedback such as click data
has been extensively studied in both academia and industry. Usually, learning
to rank directly with implicit user feedback would suffer from the intrinsic
noise and propensity in user interaction(e.g., position bias). In recent
years, many algorithms have been proposed to find the best model that ranks
query-document pairs according to their intrinsic relevance. Among them,
unbiased learning to rank (ULTR) algorithms that automatically estimate click
bias and construct unbiased ranking models, namely the AutoULTR algorithms,
have drawn a lot of attention (Ai et al., 2018b; Wang et al., 2018). Because
they do not need to conduct separate user studies or online experiments to
estimate user bias (i.e., the propensity models), most AutoULTR algorithms can
easily be deployed on existing IR systems without hurting user experiences.

Despite their differences in background theories and algorithm design,
previous studies on ULTR usually use uni-variate learning-to-rank models,
which score each document independently, for experiments and theoretical
analysis. Recently, multivariate scoring functions, which take multiple
documents as input and jointly predict their ranking scores, have been proved
to be more effective than uni-variate scoring function in many learning-to-
rank problems (Ai et al., 2018a; Pang et al., 2020). By modeling and comparing
multiple documents together, multivariate scoring functions naturally capture
the local context information and produce state-of-the-art performances on
many learning-to-rank benchmarks with human-annotated relevance labels.
Whether the superior performance of multivariate scoring functions would hold
in unbiased learning to rank is still unknown.

To leverage the full power of click data and multivariate scoring functions,
we explore the potential of multivariate scoring functions in AutoULTR.
Specifically, we investigate the compatibility of DLA (Ai et al., 2018b), an
AutoULTR algorithm, with two existing multivariate scoring functions, SetRank
(Pang et al., 2020), and DLCM (Ai et al., 2018a). Our theoretical analysis
shows that only a subset of multivariate scoring functions could perform well
in ULTR. Specifically, we prove that being permutation invariant is a crucial
factor determining whether a multivariate scoring function could be applied to
the existing AutoULTR framework. Experiment results with synthetic clicks on
two large-scale publicly available benchmarks showed that the DLA with
permutation-invariant multivariate scoring functions significantly outperforms
DLA with uni-variate scoring functions and permutation-variant multivariate
scoring functions.

##  2\. Related work

AutoULTR, which has the advantage of estimating propensity and relevance
simultaneously, has drawn much attention recently. For example, Ai et al. (Ai
et al., 2018b) proposed Dual Learning Algorithm (DLA) based on counterfactual
learning, and Wang et al. (Wang et al., 2018) proposed a regression-based EM
algorithm. On the other hand, for multivariate scoring functions, there are
several ways to take multiple documents as input. For example, DLCM (Ai et
al., 2018a) employs a RNN model to give score, SetRank(Pang et al., 2020)
utilizes self-attention mechanism. To the best of our knowledge, however,
research on multivariate scoring functions in AutoULTR has not been fully
explored, which is exactly the focus of this paper.

##  3\. PROBLEM FORMULATION

In this section, we investigate existing AutoULTR algorithms in theory and
prove that permutation invariance is a sufficient and necessary condition that
determines whether multivariate scoring functions could be applied to existing
AutoULTR algorithms. A summary of the notations used in this paper is shown in
Table 1.

Table 1. A summary of notations. $Q,q$ |  All possible query $Q$ and a query instance $q\sim P(q)$.
---|---
$S$,$\mathcal{F}$,$\theta$, $E$,$\mathcal{G}$, $\phi$ |  A multivariant relevance estimation function $\mathcal{F}$ parameterized by $\theta$ for ranking system $S$ and a propensity estimation function $\mathcal{G}$ parameterized by $\phi$ for propensity model $E$ .
$l$, $\widetilde{l}$,$\widetilde{\mathcal{L}}$ |  $l$ is local loss, while $\widetilde{l}$ is unbiased estimation of $l$ and $\widetilde{\mathcal{L}}$ is the unbiased estimation of global loss.
$\pi_{q}$, $d_{i}$, $i$, $\operatorname{\textit{{x}}}_{i}$, $\operatorname{\textit{{X}}}$, $y$ |  A ranked list $\pi_{q}$ produced by $S$ for $q$, a document $d_{i}$ with features $\operatorname{\textit{{x}}}_{i}$ on the $i$-th position in $\pi_{q}$ and its relevance $y$. $\operatorname{\textit{{X}}}$ is the feature matrix for whole $\pi_{q}$.
$\mathbf{o}_{q}$, $\mathbf{r}_{q}$, $\mathbf{c}_{q}$ |  Bernoulli variables that represent whether a document is observed ($\mathbf{o}_{q}$), perceived as relevant ($\mathbf{r}_{q}$) and clicked ($\mathbf{c}_{q}$ ).

###  3.1. Univariate and Multivariate Scoring

In a standard learning-to-rank system, given a specific query $q$ and its
associated retrieved document set $D=[d_{1},d_{2},\dots,d_{N}]$, a vector
$\operatorname{\textit{{x}}}_{i}\in\mathbb{R}^{H}$ can be extracted and used
as the feature representation for $d_{i}$. Let $\pi_{q}$ be the ranked list
for query $q$. Then there will be a feature matrix for a ranked list
$\pi_{q}$:

$\operatorname{\textit{{X}}}=[\operatorname{\textit{{x}}}_{1},\operatorname{\textit{{x}}}_{2},\dots,\operatorname{\textit{{x}}}_{N}]^{T},where\operatorname{\textit{{X}}}\in\mathbb{R}^{N\times
H}$

Then, uni-variate ranking function $f_{\theta}(\operatorname{\textit{{x}}})$
and multivariant scoring function
$\mathcal{F}_{\theta}(\operatorname{\textit{{X}}})$ for a ranked list can be
defined as:

$\begin{split}f_{\theta}(\operatorname{\textit{{X}}})&=[f_{\theta}(\operatorname{\textit{{x}}}_{1}),f_{\theta}(\operatorname{\textit{{x}}}_{2}),\dots,f_{\theta}(\operatorname{\textit{{x}}}_{N})]\\\
\mathcal{F}_{\theta}(\operatorname{\textit{{X}}})&=[\mathcal{F}^{1}_{\theta}(\operatorname{\textit{{X}}}),\mathcal{F}^{2}_{\theta}(\operatorname{\textit{{X}}})^{,}\dots,\mathcal{F}_{\theta}^{N}(\operatorname{\textit{{X}}})]\end{split}$

where $\theta$ is the parameter. The main difference is that multivariant
scoring functions take the whole list as input, while uni-variate scoring
functions only score one document a time.

###  3.2. AutoULTR Framework

In this paper, we adopt DLA(Ai et al., 2018b), an AutoULTR framework which
treats the problem of learning a propensity model from click data (i.e., the
estimation of bias in clicks) as a dual problem of constructing an unbiased
learning-to-rank model. Formally, let $o_{q}$, $r_{q}$ and $c_{q}$ be the sets
of Bernoulli variables that represent whether a document in $\pi_{q}$ is
observed, perceived as relevant, and clicked by a user, respectively. In DLA,
an unbiased ranking system $S$ and a propensity model $E$ can be jointly
learned by optimizing the local AttRank losses(Ai et al., 2018a) as

(1)
$\begin{split}{l}(E,q)&=-\sum_{i=1}^{i=|\pi_{q}|}o_{q}^{i}\times\log\mathcal{G}^{i}_{\phi}(\pi_{q})\\\
{l}(S,q)&=-\sum_{i=1}^{i=|\pi_{q}|}r_{q}^{i}\times\log\mathcal{F}^{i}_{\theta}(\operatorname{\textit{{X}}}_{q})\end{split}{}$
(2)
$\begin{split}\sum_{i=1}^{i=|\pi_{q}|}\mathcal{G}^{i}_{\phi}(\pi_{q})=1,\sum_{i=1}^{i=|\pi_{q}|}\mathcal{F}^{i}_{\theta}(\operatorname{\textit{{X}}}_{q})=1\end{split}{}$

where $\mathcal{G}_{\phi}$ and $\mathcal{F_{\theta}}$, parameterized by $\phi$
and $\theta$, compute the propensity scores and relevance scores of each
document in the ranked list with a softmax function constrained by Eq.(2). To
compute ${l}(S,q)$ and ${l}(E,q)$, we need to know the actual relevance (i.e.
$r_{q}^{i}$) and observation (i.e., $o_{q}^{i}$) information of each document.
However, in practice, the only data we can get is click (i.e. $c_{q}$), and
$r_{q}$ and $o_{q}$ are unknown latent variables. In order to deal with
clicks, a common assumption used by most studies is

(3) $P(c^{i}_{q}=1)=P(o^{i}_{q}=1)P(r^{i}_{q}=1)$

which means that users click a search result ($c^{i}_{q}=1$) only when it is
both observed ($o^{i}_{q}=1$) and perceived as relevant ($r^{i}_{q}=1$), and
$o^{i}_{q}$ and $r^{i}_{q}$ are independent to each other. With this
assumption, unbiased estimation of $l(S,q)$ and $l(E,q)$ can be achieved
through inverse propensity weighting (IPW) (Joachims et al., 2017b) and
inverse relevance weighting (IRW) (Ai et al., 2018b) as

(4)
$\begin{split}\widetilde{l}_{IRW}(E,q)&=-\sum_{i=1,c_{q}^{i}=1}^{i=|\pi_{q}|}\frac{\mathcal{F}^{1}_{\theta}(\operatorname{\textit{{X}}}_{q})}{\mathcal{F}^{i}_{\theta}(\operatorname{\textit{{X}}}_{q})}\times\log\mathcal{G}^{i}_{\phi}(\pi_{q})\\\
\widetilde{l}_{IPW}(S,q)&=-\sum_{i=1,c_{q}^{i}=1}^{i=|\pi_{q}|}\frac{\mathcal{G}^{1}_{\phi}(\pi_{q})}{\mathcal{G}^{i}_{\phi}(\pi_{q})}\times\log\mathcal{F}^{i}_{\theta}(\operatorname{\textit{{X}}}_{q})\end{split}{}$
$\operatorname{\mathbb{E}}_{r_{q}}[\widetilde{l}_{IRW}(E,q)]\stackrel{{\scriptstyle\Delta}}{{=}}l(E,q),\operatorname{\mathbb{E}}_{o_{q}}[\widetilde{l}_{IPW}(S,q)]\stackrel{{\scriptstyle\Delta}}{{=}}l(S,q),$

where $\stackrel{{\scriptstyle\Delta}}{{=}}$ means equal or linearly
correlated with a positive constant factor. Then the final optimization losses
in DLA are

(5) $\widetilde{\mathcal{L}}(S)=\sum_{q\in
Q}\widetilde{l}_{IPW}(S,q),~{}~{}~{}~{}~{}~{}\widetilde{\mathcal{L}}(E)=\sum_{q\in
Q}\widetilde{l}_{IRW}(E,q)$

where $Q$ is the set of all possible queries. During training, we update
$\theta$ and $\phi$ with the derivatives of $\widetilde{l}_{IPW}(S,q)$ and
$\widetilde{l}_{IRW}(E,q)$ respectively and repeat the process until the
algorithm converges.

###  3.3. Convergence Analysis

In this section, we analyze the compatibility of multivariate scoring
functions and DLA in theory. Firstly, we give definition of permutation
invariance as:

###### Definition 3.1.

Let $S_{n}$ be the set of all permutations of indices $\\{1,\dots,n\\}$, A
function $f$: $X^{n}\xrightarrow{}Y^{n}$ is permutation invariant (Lee et al.,
2019) iff for any permutation function $\Pi$, $f(\Pi(X))=\Pi(f(X))$ , i.e.,

$f(x_{\Pi(1)},\dots,x_{\Pi(n)})=[f^{\Pi(1)}(X),\dots,f^{\Pi(n)}(X)]$

where $X=[x_{1},\dots,x_{n}]$, $f^{\Pi(i)}(X)$ is the $\Pi(i)\text{-}th$
dimension of $f(X)$.

For simplicity, we consider position bias (Joachims et al., 2017a) as the only
bias in click data. Then we have
$\mathcal{G}^{i}_{\phi}=\mathcal{G}^{i}_{\phi}(\pi_{q})$, which means
propensity is independent with query. Let $\Pi(i)=j$ mean putting
$\operatorname{\textit{{x}}}_{j}$ on $i\text{-}th$ position of permutated
matrix $\Pi(\operatorname{\textit{{X}}})$. In theory, DLA will converge when

(6)
$\begin{split}\frac{\partial\widetilde{\mathcal{L}}(E)}{\partial\mathcal{G}^{i}_{\phi}}=0\implies\frac{\mathcal{G}^{1}_{\phi}}{\mathcal{G}^{i}_{\phi}}&=\frac{\frac{\operatorname{\mathbb{E}}[c^{1}_{q}]}{\operatorname{\mathbb{E}}[c^{i}_{q}]}}{\operatorname{\mathbb{E}}[\frac{\mathcal{F}^{1}_{\theta}(\operatorname{\textit{{X}}}_{q})}{\mathcal{F}^{i}_{\theta}(\operatorname{\textit{{X}}}_{q})}]}=\frac{\frac{\operatorname{\mathbb{E}}[r^{1}_{q}]}{\operatorname{\mathbb{E}}[r^{i}_{q}]}}{\operatorname{\mathbb{E}}[\frac{\mathcal{F}^{1}_{\theta}(\operatorname{\textit{{X}}}_{q})}{\mathcal{F}^{i}_{\theta}(\operatorname{\textit{{X}}}_{q})}]}\frac{\operatorname{\mathbb{E}}[o^{1}]}{\operatorname{\mathbb{E}}[o^{i}]}\end{split}{}$

Considering any permutation funciton $\Pi$, the original $i\text{-}{th}$
document in $\pi_{q}$ is in the $\Pi^{-1}(i)\text{-}th$ document in the
permuted list, where $\Pi^{-1}$ is the inverse function of $\Pi$. Note that in
the following analysis, the default ranking of documents is original ranking
$\pi_{q}$ shown to users if not explicitly pointed out. For a permutated
ranking, we have

(7)
$\begin{split}\frac{\mathcal{G}^{\Pi^{-1}(1)}_{\phi}}{\mathcal{G}^{\Pi^{-1}(i)}_{\phi}}&=\frac{\frac{\operatorname{\mathbb{E}}[\Pi(r_{q})^{\Pi^{-1}(1)}]}{\operatorname{\mathbb{E}}[\Pi(r_{q})^{\Pi^{-1}(i)}]}}{\operatorname{\mathbb{E}}[\frac{\mathcal{F}_{\theta}^{\Pi^{-1}(1)}(\Pi(\operatorname{\textit{{X}}}_{q}))}{\mathcal{F}_{\theta}^{\Pi^{-1}(i)}(\Pi(\operatorname{\textit{{X}}}_{q}))}]}\frac{\operatorname{\mathbb{E}}[o^{\Pi^{-1}(1)}]}{\operatorname{\mathbb{E}}[o^{\Pi^{-1}(i)}]}\end{split}{}$

####  3.3.1. Necessary Condition

When DLA converges and propensity is correctly estimated, we have

(8) $\begin{split}\forall\Pi,\forall
i,~{}~{}~{}~{}\frac{\mathcal{G}^{\Pi^{-1}(1)}_{\phi}}{\mathcal{G}^{\Pi^{-1}(i)}_{\phi}}&=\frac{\operatorname{\mathbb{E}}[o^{\Pi^{-1}(1)}]}{\operatorname{\mathbb{E}}[o^{\Pi^{-1}(i)}]},\frac{\mathcal{G}^{1}_{\phi}}{\mathcal{G}^{i}_{\phi}}=\frac{\operatorname{\mathbb{E}}[o^{1}]}{\operatorname{\mathbb{E}}[o^{i}]}\end{split}{}$

Assuming that the relevance of a document $d_{i}$ would not change after
moving to a different position, then we have

(9) $\Pi(r_{q})^{\Pi^{-1}(i)}=r^{i}_{q}$

Considering Equations 2, 9, 8, 7 and 6, we can get

(10)
$\frac{\mathcal{F}^{1}_{\theta}(\operatorname{\textit{{X}}})}{\mathcal{F}^{i}_{\theta}(\operatorname{\textit{{X}}})}=\frac{\mathcal{F}_{\theta}^{\Pi^{-1}(1)}(\Pi(\operatorname{\textit{{X}}}))}{\mathcal{F}_{\theta}^{\Pi^{-1}(i)}(\Pi(\operatorname{\textit{{X}}}))}\iff\mathcal{F}^{i}_{\theta}(\operatorname{\textit{{X}}})=\mathcal{F}_{\theta}^{\Pi^{-1}(i)}(\Pi(\operatorname{\textit{{X}}}))$

Then, we insert $i=\Pi(j)$ in Eq.10, and we have

(11) $\forall\Pi,\forall
j,~{}~{}~{}~{}\mathcal{F}_{\theta}^{j}(\Pi(\operatorname{\textit{{X}}}))=\mathcal{F}_{\theta}^{\Pi(j)}(\operatorname{\textit{{X}}})$

which means that $\mathcal{F}_{\theta}$ is permutation invariant according to
Definition 3.1. This indicates that permutation invariance is a necessary
condition for the convergence of DLA.

####  3.3.2. Sufficient Condition

Suppose that $\mathcal{F}_{\theta}$ is permutation invariant, then the
estimated relevance score for a document from $\mathcal{F}_{\theta}$ is
independent of its position. Because $\mathcal{G}_{\phi}$ only takes the
positions as input, $\mathcal{F}_{\theta}$ and $\mathcal{G}_{\phi}$ are
independent to each other and can separately estimate the relevance and
propensity during training. As proven by Ai et al. (Ai et al., 2018b), DLA is
guaranteed to converge in this case, which means that permutation invariance
can be a sufficient condition for the convergence of DLA.

##  4\. Experiment

So far, we have proven that permutation invariance is the sufficient and
necessary condition for learning-to-rank models to converge in DLA in theory.
In this section, we describe our experiments on two large-scale benchmarks for
further demonstrations.

###  4.1. Simulation Experiment Settings

####  4.1.1. Datasets and Click Simulation

To fully explore the performance of multivariate scoring functions in
AutoULTR, we conducted experiments on Yahoo! LETOR set
1111https://webscope.sandbox.yahoo.com,and Istella-S LETOR
222http://blog.istella.it/istella-learning-to-rank-dataset/ with derived click
data. Similar to previous studies (Joachims et al., 2017b), we trained a
SVMrank model333http://www.cs.cornell.edu/people/tj/svm_light/svm_rank.html
(which we refer to as Prod.) using 1% of the training data with real relevance
judgements to generate the original ranked list $\pi_{q}$. We then sampled
clicks ($c_{q}^{i}$) on documents according to Eq. (3) with $o_{q}^{i}$, and
$r_{q}^{i}$ as,

$\begin{split}P(o_{q}^{i}=1|\pi_{q})&=P(o_{i}=1)=\rho_{i}\\\
P(r_{q}^{i}=1|\pi_{q})&=\epsilon+(1-\epsilon)\frac{2^{y}-1}{2^{y_{max}}-1}\end{split}{}$

where $\rho$ is acquired through eye-traching experiments (Joachims et al.,
2017a), $y\in[0,4]$ is the 5-level relevance label in both datasets where
$y_{max}=4$, and $\epsilon$ is used to model click noise so that irrelevant
document($y=0$) can also be clicked. For simplicity, we fixed the value of
$\epsilon$ as 0.1.

####  4.1.2. Models and Evaluation Measures

In this paper, we focus on two state-of-art multivariate scoring functions.
The first one is DLCM(Ai et al., 2018a), a RNN model with gated recurrent
unit(GRU) that treats the final network state as context to score each
document. It is permutation variant by nature. The second one is SetRank(Pang
et al., 2020), constructed with multi-head self-attention networks, which is
permutation invariant. For DLCM, we adopt three kinds of input orders, namely
the original ranking of documents (i.e., DLCMinit) created by Prod.; the
reverse of the original ranking (i.e., DLCMrever), and a random permutation of
the original ranking (i.e., DLCMrand). For comparison, we include a uni-
variate scoring function based on deep neural networks (DNN) as our baseline.
We also include a DNN model that directly use clicks as relevance labels,
which is referred to as DNNnavie. The source code can be found
here444https://github.com/Taosheng-ty/CIKM_2020_Multivariate_AutoULTR.git.

All models were tuned and selected based on their performances on the
validation set according to $nDCG@10$. Each model was trained for five times
and reported the mean performance The batch size was set to be 64. Learning
rate was tuned between 0.1 and 0.01, and we stoped training after 60k steps.
During training, we set the size of ranked list as 10, while during validating
and testing, we tested our ranking model on all documents to each query. We
reported both ERR and nDCG metrics at ranks of 3 and 10 to show ranking
performance. Besides, in order to show performance of propensity estimation,
we computed the mean square error (MSE) between the true inverse propensity
weights $(\rho_{1}/\rho_{i})$ and the estimated inverse propensity weights
$(\mathcal{G}^{1}/\mathcal{G}^{i})$ as

$MSE_{propen}=\frac{1}{|\pi_{q}|}\sum_{i=1}^{|\pi_{q}|}(\frac{\mathcal{G}^{1}}{\mathcal{G}^{i}}-\frac{\rho_{1}}{\rho_{i}})^{2}\vspace{-0.4cm}$

Table 2. Performance comparison of different scoring functions in AutoULTR.
Significant improvements or degradations with respect to DNN are indicated
with $\textup{{+}}/\textup{{-}}$ ($p<0.05$).

Scoring Model | ERR @3 | nDCG @3 | ERR @10 | nDCG @10 | $MSE_{propen}$
---|---|---|---|---|---
(a) Yahoo!
DLCMrever | 0.414${}^{\textup{{-}}}$ | 0.665${}^{\textup{{-}}}$ | 0.452${}^{\textup{{-}}}$ | 0.739${}^{\textup{{-}}}$ | 7.40${}^{\textup{{-}}}$
DLCMinit | 0.427 | 0.686${}^{\textup{{-}}}$ | 0.464 | 0.756${}^{\textup{{-}}}$ | 9.31${}^{\textup{{-}}}$
DLCMrand | 0.425${}^{\textup{{-}}}$ | 0.680${}^{\textup{{-}}}$ | 0.462${}^{\textup{{-}}}$ | 0.752${}^{\textup{{-}}}$ | 0.015
SetRank | 0.428 | 0.694${}^{\textup{{+}}}$ | 0.464 | 0.762${}^{\textup{{+}}}$ | 0.097
DNN | 0.427 | 0.692 | 0.464 | 0.760 | 0.048
DNNnaive | 0.411${}^{\textup{{-}}}$ | 0.664${}^{\textup{{-}}}$ | 0.449 ${}^{\textup{{-}}}$ | 0.740 ${}^{\textup{{-}}}$ | -
Prod. | 0.374${}^{\textup{{-}}}$ | 0.611${}^{\textup{{-}}}$ | 0.416${}^{\textup{{-}}}$ | 0.705${}^{\textup{{-}}}$ | -
(b) Istella-s
DLCMrever | 0.676${}^{\textup{{-}}}$ | 0.601${}^{\textup{{-}}}$ | 0.703${}^{\textup{{-}}}$ | 0.695${}^{\textup{{-}}}$ | 17.5${}^{\textup{{-}}}$
DLCMinit | 0.700 | 0.629 | 0.724 | 0.707${}^{\textup{{-}}}$ | 16.1${}^{\textup{{-}}}$
DLCMrand | 0.690${}^{\textup{{-}}}$ | 0.620${}^{\textup{{-}}}$ | 0.714${}^{\textup{{-}}}$ | 0.710${}^{\textup{{-}}}$ | 0.023
SetRank | 0.706 | 0.636 | 0.730 | 0.721${}^{\textup{{+}}}$ | 0.135${}^{\textup{{-}}}$
DNN | 0.704 | 0.633 | 0.727 | 0.716 | 0.033
DNNnaive | 0.683${}^{\textup{{-}}}$ | 0.610${}^{\textup{{-}}}$ | 0.709${}^{\textup{{-}}}$ | 0.700${}^{\textup{{-}}}$ | -
Prod. | 0.640${}^{\textup{{-}}}$ | 0.562${}^{\textup{{-}}}$ | 0.669${}^{\textup{{-}}}$ | 0.663${}^{\textup{{-}}}$ | -

Figure 1. Test performance on Yahoo! LETOR set 1. Figure 2. Test performance
on Istella-s.

###  4.2. Experimental Results and Analysis

A summary of the results are shown in Table 2, Fig.1 and Fig.2.

####  4.2.1. Permutation variant and invariant ranking model.

As we can see from Table 2, DNN and SetRank, two permutation invariant ranking
models, work well with DLA and outperform DNNnaive, which directly trains DNN
with click data. However, DLCMinit and DLCMrever show terrible performance on
estimating propensity (i.e., high MSE) and poor ranking performance when
compared to DNN and SetRank. The results indicate that AutoULTR with
permutation variant functions is not guaranteed to converge and get an
unbiased ranker.

####  4.2.2. Comparison between uni-variant and multivariant ranking model.

Here we only consider SetRank and DNN, which are multivariant and uni-variant
respectively. Both SetRank and DNN are permutation invariant and theoretically
principled to converge with AutoULTR. From Fig. 1 and Fig. 2, we can see that
the ranking performance of SetRank significantly outperforms DNN, especially
on Istella-S LETOR. The results confirm the arguments from previous studies
that multivariate scoring functions are superior to uni-variate ones because
the former can capture the contextual information and cross-document
interactions.

####  4.2.3. Comparison of DLCM with different input order.

We noticed that DLCMrand could get a perfect estimation of the propensity but
failed to get ranking performance as good as SetRank and DNN. We think the
reason might be that random input order makes permutation variant models hard
to remember any pattern in order, thus empirically achieve permutation
invariance. As for ranking performance, we can interpret it from the RNN
structure. In DLCM, the final input has the most impact on the final network
state, which is viewed as context to help score each document. Random input
sequence results in a random context which would make DLCMrand hard to score
documents. This could also explain the bad performance of DLCMrever as it
always takes documents in the reverse order of the original ranking produced
by Prod.

##  5\. CONCLUSION AND FUTURE WORK

In this work, we explore the potential of multivariate scoring functions in
AutoULTR. Based on existing AutoULTR algorithms, We prove that permutation
invariance is a crucial factor for a multivariate scoring function to be
included in AutoULTR. With two existing multivariate functions and one
AutoULTR algorithm, we conduct experiments based on two benchmark datasets,
the results of which align with our theoretical analysis. AutoULTR models with
permutation-invariant multivariate scoring functions significantly outperform
those with uni-variate scoring functions and permutation-variant multivariate
scoring functions. Our work represents an initial attempt to include
multivariate scoring in AutoULTR. In the future, we may base on our analysis
to propose novel multivariate scoring functions for AutoULTR.

###### Acknowledgements.

This work was supported in part by the School of Computing, University of
Utah. Any opinions, findings and conclusions or recommendations expressed in
this material are those of the authors and do not necessarily reflect those of
the sponsor.

## References

  * (1)
  * Ai et al. (2018a) Qingyao Ai, Keping Bi, Jiafeng Guo, and W Bruce Croft. 2018a.  Learning a deep listwise context model for ranking refinement. In _The 41st International ACM SIGIR Conference on Research & Development in Information Retrieval_. 135–144.
  * Ai et al. (2018b) Qingyao Ai, Keping Bi, Cheng Luo, Jiafeng Guo, and W Bruce Croft. 2018b.  Unbiased learning to rank with unbiased propensity estimation. In _The 41st International ACM SIGIR Conference on Research & Development in Information Retrieval_. 385–394.
  * Joachims et al. (2017a) Thorsten Joachims, Laura Granka, Bing Pan, Helene Hembrooke, and Geri Gay. 2017a.  Accurately interpreting clickthrough data as implicit feedback. In _ACM SIGIR Forum_ , Vol. 51. Acm New York, NY, USA, 4–11.
  * Joachims et al. (2017b) Thorsten Joachims, Adith Swaminathan, and Tobias Schnabel. 2017b.  Unbiased learning-to-rank with biased feedback. In _Proceedings of the Tenth ACM International Conference on Web Search and Data Mining_. 781–789.
  * Lee et al. (2019) Juho Lee, Yoonho Lee, Jungtaek Kim, Adam Kosiorek, Seungjin Choi, and Yee Whye Teh. 2019\.  Set transformer: A framework for attention-based permutation-invariant neural networks. In _International Conference on Machine Learning_. 3744–3753.
  * Pang et al. (2020) Liang Pang, Jun Xu, Qingyao Ai, Yanyan Lan, Xueqi Cheng, and Jirong Wen. 2020\.  Setrank: Learning a permutation-invariant ranking model for information retrieval. In _Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval_. 499–508.
  * Wang et al. (2018) Xuanhui Wang, Nadav Golbandi, Michael Bendersky, Donald Metzler, and Marc Najork. 2018\.  Position bias estimation for unbiased learning to rank in personal search. In _Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining_. 610–618.


# Leveraging a Randomized Key Matrix to Enhance the Security of Symmetric
Substitution Ciphers

Shubham Gandhi1, Om Khare1, Mihika Dravid1, Mihika Sanghvi1, Sunil Mane1,
Aadesh Gajaralwar2, Saloni Gandhi3 1 Department of Computer Science and
Engineering
COEP Technological University
Pune, Maharashtra, India 2 Department of Computer Engineering
BRACT’s Vishwakarma Institute of Information Technology
Pune, Maharashtra, India 3Independent Researcher

###### Abstract

An innovative strategy to enhance the security of symmetric substitution
ciphers is presented, through the implementation of a randomized key matrix
suitable for various file formats, including but not limited to binary and
text files. Despite their historical relevance, symmetric substitution ciphers
have been limited by vulnerabilities to cryptanalytic methods like frequency
analysis and known plaintext attacks. The aim of our research is to mitigate
these vulnerabilities by employing a polyalphabetic substitution strategy that
incorporates a distinct randomized key matrix. This matrix plays a pivotal
role in generating a unique random key, comprising characters, encompassing
both uppercase and lowercase letters, numeric, and special characters, to
derive the corresponding ciphertext. The effectiveness of the proposed
methodology in enhancing the security of conventional substitution methods for
file encryption and decryption is supported by comprehensive testing and
analysis, which encompass computational speed, frequency analysis, keyspace
examination, Kasiski test, entropy analysis, and the utilization of a large
language model.

###### Index Terms:

Encryption, Substitution Cipher, Randomized Key Matrix, Keyspace, Frequency
Analysis, Kasiski Analysis, Decryption.

##  I Introduction

###  I-A Problem Statement

Cryptography plays an instrumental role in securing information communicated
through computer systems, involving the conversion of data into an
unintelligible format, thereby ensuring that only the intended recipients
possess the ability to decipher and utilize it. Despite their historical
significance, classical substitution ciphers such as Caesar, Playfair, and
Vigenère can be targeted by various cryptanalysis and are vulnerable to
modern-day cyber threats. The need arises to explore innovative strategies for
enhancing the security of substitution ciphers while maintaining their
elegance and accessibility. The objective of this paper is to address the
limitations of traditional substitution ciphers by proposing the integration
of a randomized key matrix—a novel approach that enhances security and updates
the traditional method to align with contemporary demands.

###  I-B Motivation

Complex algorithms such as Advanced Encryption Standard (AES), Data Encryption
Standard (DES), Triple Data Encryption Standard (3DES), Rivest Cipher 6 (RC6),
Rivest Cipher 2 (RC2), and Blowfish have been yielded by modern cryptographic
advancements. Motivated by the critical need to address the vulnerabilities
inherent in classical substitution ciphers such as frequency analysis attacks,
small keyspace, and known-plaintext attacks, while harnessing their simplicity
and historical value, this research aims to enhance the security of
substitution ciphers while retaining their simplicity and efficiency.

###  I-C Objectives

The development of a novel approach to enhance the security of substitution
ciphers, by integrating a randomized key matrix to address the vulnerabilities
inherent in conventional substitution ciphers is the primary objective of this
research. Their resistance against various sophisticated attack strategies is
intended to be bolstered. Additionally, an exploration of existing
cryptography techniques and modern enhancements to substitution cipher
techniques is undertaken through a comprehensive literature review.

Figure 1: Subset of the Key Matrix

##  II Related Work

Cryptography plays a vital role in safeguarding computer communications by
transforming data into an unintelligible format, preventing unauthorized
access, and ensuring efficient and secure data transfers. Within cryptography,
Symmetric and Asymmetric methodologies are the two recognized
categories.[2][3] A critical factor in ensuring communication security is the
key size, which varies between the two approaches. Symmetric cryptography
employs smaller keys than asymmetric cryptography, making it potentially less
secure for highly sensitive data.[4] The encryption process utilizes the
American Standard Code for Information Interchange (ASCII) values of the data
to be encrypted while introducing a modified string as a shared key for both
encryption and decryption. This single key is used for both procedures, with
minor adjustments, and is applicable when the input and key lengths are the
same. While asymmetric cryptography requires more computational time than
symmetric cryptography, making it complex for large data volumes, its larger
key size leads to a two-step process where public key cryptography is first
used for key exchange, followed by encryption or decryption via symmetric key
cryptography [5][6]. The computational time in cryptography includes
encryption, decryption, key generation, and key exchange, with encryption and
decryption time linked to the conversion of plaintext to ciphertext and
ciphertext to plaintext respectively. The duration of key generation varies
based on key length. Key exchange time relies on the communication channel
between sender and receiver.

Substitution ciphers represent a fundamental category of encryption methods
that operate by substituting one element for another according to predefined
rules. Extensive research and enhancements have been conducted on the
classical Caesar cipher.[7] A hybrid version of the classical and modern
cipher properties has been proposed to improve the Caesar cipher,
incorporating a random number generation technique for key generation
operations. This extended Caesar cipher includes alphanumeric characters and
the key used for the Caesar Substitution is derived using a key Matrix Trace
value restricted to Modulo 94. The Matrix elements are generated using a
recursive random number generation equation. The second stage of encryption
has been performed using columnar transposition with arbitrary random order
column selection, significantly enhancing resistance to brute force attacks.
Another proposal[8] presents a modified hybrid of the Caesar cipher and
Vigenère cipher to increase the diffusion and confusion characteristics of the
ciphertext by incorporating techniques from modern ciphers such as XORing the
key to the first letter of the plain text and proceeding iteratively with each
subsequent character. [9] An enhancement to Ceasar cipher in which the method
of encryption depends on the position of the bit in the message, where the
sender transposes the bits by shifting characters in odd positions to the left
and characters in even positions to the right.
The Vigenère cipher, [10] a substitution cipher, works by selecting a keyword
that determines the shifts for the encryption process. Each letter of the
keyword corresponds to a shift value. The plaintext letters are shifted by
these values cyclically to create the ciphertext [11]. Additionally, a
cryptosystem based on the Vigenère cipher has been proposed, utilizing a
multilevel encryption scheme. It involves using a Vigenère table to obtain a
new ciphertext from an equivalent fixed-length plaintext and key. This new
ciphertext then becomes a key for encrypting the original plaintext, creating
a final ciphertext. The decryption process is reversed by the receiver [12].
Shifting focus to the Playfair cipher, [13] this method operates on character
blocks by converting plaintext diagrams to ciphertext diagrams using a pre-
shared key. Further modifications of the Playfair cipher such as utilizing
different matrix sizes for the key. Comparative analysis indicates that while
the size of the plaintext has minimal effect, larger key sizes lead to
stronger encryption, and increasing the matrix size enhances encryption
results. Incorporating hybrid approaches, [14] combines the Vigenère and
columnar transposition ciphers. The hybrid technique applies a columnar
transposition cipher to the plaintext using a randomly chosen key to generate
an initial ciphertext. This ciphertext then becomes the key for the subsequent
Vigenere encryption. This approach adds an extra layer of complexity,
enhancing the security of the final ciphertext against existing cryptanalysis
methods.

Figure 2: Reference for substitution

##  III Methodology

A comprehensive methodology has been developed for our proposed symmetric
encryption technique, addressing the limitations of classical substitution
ciphers such as their limited keyspace and vulnerability to cryptanalysis. The
methodology encompasses a series of steps, namely, key matrix generation,
random key generation, encryption, and decryption. In the case of encryption,
input is provided in the form of plaintext and key length, while during
decryption, input consists of ciphertext and key. The length of the key is
subject to variation from 1 to a maximum of 16, implying an inversely
proportional relationship between security and computational speed.

###  III-A Key Matrix Generation

A key matrix with dimensions of 95x94 is created by the algorithm, utilizing a
diverse range of ASCII characters such as upper and lowercase alphabets, and
numeric and special characters. This matrix serves as the foundation for our
proposed methodology. While the first row of the key matrix remains constant,
subsequent rows are sequentially populated following a specific pattern. In
each row, the initial character functions as a unique identifier for that
particular row in the key matrix. A subset of the key matrix is illustrated in
Figure 1.

###  III-B Key Generation Process

The flexibility to select an encryption key length is offered by the
algorithm, with a maximum limit of 16 characters. This constraint strikes a
balance between security and computational efficiency. The process of
generating a random encryption key involves the following sequential steps:

  1. 1.

Row Selection from Key Matrix: A specific number of rows from the key matrix
are randomly picked by the algorithm. The number of chosen rows corresponds to
the selected key length. The foundation of the encryption key is formed by
these selected rows.

  2. 2.

Substitution with Unique Sets: Within the selected key rows, a set is formed
by combining one character from each of the chosen rows, and this set is
utilized to substitute a single character in the plaintext. The size of this
set corresponds to the selected key length. The algorithm’s overall security
is significantly enhanced by this polyalphabetic substitution mechanism.

By implementing character substitutions in this manner, several security
benefits are yielded by the algorithm. An added layer of complexity is
introduced by the non-linear and non-deterministic approach to substitutions,
which considerably increases the difficulty of the decryption process for
potential attackers. Furthermore, the algorithm’s resilience against brute-
force attacks is substantially fortified through the utilization of diverse
characters in conjunction with a sizable key matrix.

###  III-C Encryption

Using the newly established character sets as a reference for encryption as
illustrated in Figure 2, the index of each plaintext character within this
custom set is identified by the algorithm. Subsequently, the identified
plaintext character is replaced by its corresponding set of encrypted
characters. After each character in the plaintext is replaced with a set of
characters where the size of the set is the key length, the corresponding
cipher text is formed, and the key is the first character of the randomly
selected rows in the key matrix.

In essence, from the set of selected rows, each individual letter in the
plaintext undergoes substitution. This substitution process involves creating
a combination of characters derived from all the selected rows. The resulting
encrypted character, stemming from this multi-row combination, is then
integrated into the ciphertext.The encryption workflow is illustrated in
Figure 3.

Figure 3: Encryption Workflow

###  III-D Decryption

The decryption process involves the reversal of the encryption process. It is
initiated by utilizing the encryption key to identify the rows within the key
matrix. Each row is distinguishable by its initial character, which serves as
a unique identifier. The content of these identified rows is combined to
retrieve the original character corresponding to the encrypted set of
characters in the cipher text, facilitated by the algorithm.

Upon the recovery of this original character, it is incorporated into the
expanding plaintext. This process is iterated for every encrypted character in
the ciphertext, gradually reconstructing the original plaintext. The
decryption workflow is illustrated in Figure 4.

Figure 4: Decryption Workflow

##  IV Experimental Evaluation

The experimental evaluation section of this research constitutes a
comprehensive exploration of the proposed encryption technique’s capabilities
and resilience. Through a series of meticulously designed experiments, we
delve into various aspects of the encryption method’s performance and
security. From computational speed comparisons with traditional substitution
ciphers to rigorous frequency analysis, keyspace examination, and robustness
evaluation against known cryptanalysis techniques, our experimental approach
aims to provide a holistic understanding of the proposed encryption
technique’s strengths and limitations. Furthermore, we extend our
investigation to include challenges posed by advanced technologies, such as
Large Language Models (LLMs), as we analyze their impact on the security of
our encryption method.

###  IV-A Dataset Preparation

In the context of our experimental evaluation, a diverse dataset was prepared,
encompassing various types of texts such as plain English sentences, technical
documents, and excerpts from literary works. The objective of the dataset is
to capture real-world scenarios in which the security of text-based
information assumes importance.

###  IV-B Implementation Details

The proposed substitution cipher algorithm was implemented as outlined in the
methodology. The key length was designated as 8 characters, aiming to strike a
balance between security and computational efficiency. As a basis for
comparison, classical substitution cipher algorithms including Ceasar,
Playfair, and Vigenère were implemented, wherein each character within the
plaintext was replaced with a predetermined character from a singular key.

Figure 5: Comparison of Encryption Speeds for Various Substitution Ciphers
Figure 6: Comparison of Decryption Speeds for Various Substitution Ciphers

###  IV-C Computational Speed Analysis

Utilization of a laptop equipped with a 2.80GHz CPU was executed to assess
encryption time, and decryption time [15][16] across a spectrum of file
sizes—namely, 10KB, 500KB, and 1MB. The prescribed key size of 8 was
maintained. Competitive speeds are exhibited by our approach, even in
comparison to simpler substitution techniques such as Caesar, Vigenère, and
Playfair, particularly for diminutive file sizes. The necessary time was
computed using (1). The Encryption and Decryption time for various
substitution ciphers are illustrated in Figure 5 and Figure 6 respectively.

$\textit{Computation Time}={\textit{End Time}}-{\textit{Start Time}}$ (1)

where the computation time is computed by subtracting the start time from the
end time

###  IV-D Frequency Analysis

Figure 7: Character Frequency Analysis

Insightful results have been yielded by the conducted frequency analysis [17]
on the ciphertext generated through the application of our proposed
substitution cipher method. Upon analyzing the histogram of character
occurrences, the uniform distribution indicates a polyalphabetic nature and a
diverse range of characters, which spans uppercase and lowercase letters,
special characters, and numeric characters. The non-uniform distribution of
character probabilities further emphasizes this intricacy, revealing a nuanced
transformation process. Remarkably, characters such as ‘v’ and ’B’ emerge with
the highest probabilities, while comparable probabilities among characters
like ‘y’, ‘@’, ‘z’, and ‘?’ highlight a balanced usage. It is noteworthy that
common English letters appear with lowered probabilities, effectively
disrupting conventional language frequencies. Special characters and numeric
symbols also play a significant role, thereby confounding frequency analysis
expectations. By encompassing a broad range of characters and introducing non-
standard frequencies, the capacity of our proposed method to enhance the
security of substitution ciphers is showcased, effectively deterring
traditional frequency-based attacks. The character frequency distribution
graph is illustrated in Figure 7.

###  IV-E Key Space Analysis

Keyspace analysis plays a crucial role in the evaluation of cipher security by
quantifying the number of potential keys that an attacker must consider for
breaking the encryption through brute force. Keyspace is the total number of
possible values of keys in a crypto algorithm. A comprehensive analysis of the
keyspace strength across four distinct cryptographic algorithms—namely, the
classic Caesar cipher, the more advanced Playfair cipher, and our novel
encryption scheme—is undertaken. Their corresponding keyspace is outlined in
Table I.

Commencing with the Caesar cipher, the keyspace is found to be limited to a
mere 25 possibilities, thus emphasizing its vulnerability to brute-force
attacks. In contrast, enhanced security is offered by the Vigenère cipher due
to a larger keyspace, which is determined by the length of the secret keyword.
The Playfair cipher, leverages a 5x5 letter grid, resulting in an impressive
keyspace of 1.55 x 1025 unique configurations, rendering it notably resilient
against cryptographic attacks.

In comparison, our cipher showcases an extraordinary keyspace of 4.40 x 1025.
This keyspace’s unprecedented magnitude substantially enhances our cipher’s
security profile, effectively rendering exhaustive search attacks like brute
force practically infeasible.

TABLE I: Keyspace Analysis Cipher | Keyspace
---|---
Caesar | 25
Playfair | $1.55\times 10^{25}$
Randomized Key Matrix | $4.40\times 10^{25}$

###  IV-F Kasiski Analysis

A Kasiski test [18][19] was conducted to simulate an attack and assess the
resilience of our approach. The Kasiski test is a potent cryptanalysis
technique employed to ascertain the length of the encryption key in
polyalphabetic substitution ciphers.

The ciphertext provided below in Figure 8, generated by our algorithm with a
key length of 6, is taken into consideration.

Figure 8: Ciphertext for Kasiski Analysis

Initially, the occurrence of similar character sequences in our ciphertext is
recorded. In this case, the character ‘4’ appears 16 times in the ciphertext
at positions 2, 27, 45, 52, 57, 67, 85, 99, 109, 130, 139, 147, 165, 181, 189,
and 231. Subsequently, the distances between these occurrences and the first
occurrence are calculated and result in 25, 43, 50, 55, 65, 83, 97, 107, 128,
137, 145, 163, 179, 187, and 229 respectively. After calculating the Greatest
Common Divisor (GCD) of the distances, which is 1 in this case, the resulting
value likely represents the key length used for generating the ciphertext.
However, this value does not match the actual key length in this case.

Our experimentation with the Kasiski test unveiled intriguing outcomes. The
test displayed noteworthy accuracy in predicting key lengths less than 3,
achieving accurate estimations. However, as the key length exceeded this
threshold, the precision of predictions notably declined, surpassing the
traditional ciphers. Consequently, this impedes the efficient application of
frequency analysis on the substrings produced through key-length division.

###  IV-G Entropy Analysis

The calculation of Shannon entropy using (2) [20] provides insights into the
degree of disorder and unpredictability within encrypted messages. The entropy
formula is expressed as follows:

$\textit{Entropy}=-\sum_{i}P(x_{i})\log_{2}P(x_{i})$ (2)

Where $P(x_{i})$ represents the probability of occurrence of character
$x_{i}$.

Figure 9: Ciphertext for Entropy Analysis

In our experimentation, an entropy value of approximately 6.495 was obtained
for the ciphertext provided in Fig 9, with a fixed key length of 6. This high
entropy value indicates a substantial level of randomness and unpredictability
within the ciphertext, suggesting a stronger level of security against attacks
attempting to exploit patterns in encrypted data.

###  IV-H Resilience to Large Language Models

A state-of-the-art Large Language Model (LLM) named Bidirectional Encoder
Representations from Transformers (BERT) was employed[21]. The model was
subjected to training using a dataset comprising 1000 pairs of plaintext-
ciphertext samples, each intricately linked to a corresponding key length. The
primary objective was to determine whether the plaintext could be adeptly
predicted by BERT through extrapolation from the ciphertext and key length,
effectively reversing the intricate encryption process. While impressive
accuracy was demonstrated by BERT for key length 1, a significant decrease in
performance was observed with the increase in key length. This decline can be
attributed to the inherently randomized nature of our cipher, which poses a
challenge to BERT’s cryptanalysis capabilities. Moreover, the augmented key
length introduced heightened complexity, further testing the boundaries of
BERT’s analytical capabilities.

The robust and resilient nature of our proposed methodology in the modern
world of cryptography is underscored by its resilience against contemporary
cryptographic analysis techniques.

##  V RESULTS AND ANALYSIS

###  V-A Noteworthy Observations

Significant contributions to the advancement of traditional substitution
ciphers are made. The key contributions can be summarized as follows:

####  V-A1 Unparalleled Keyspace Strength

With a staggering keyspace of $4.40\times 10^{25}$, the mere 25 possibilities
of the Caesar cipher are vastly outperformed, and the impressive $1.55\times
10^{25}$ unique configurations that the Playfair cipher offers are even
exceeded, establishing its advancement over traditional substitution
techniques.

####  V-A2 Diverse Character Spectrum

A prominent role was assumed by special characters and numeric symbols,
confounding conventional expectations of frequency analysis. Security is
further bolstered by the nonlinear and nondeterministic nature of the proposed
polyalphabetic encryption technique, as non-standard frequencies are
introduced. Consequently, traditional frequency-based attacks, a common threat
to substitution-based ciphers, are rendered significantly less effective.

####  V-A3 Cryptanalysis Resilience

Outperforming the traditional Vigenère cipher in the Kasiski test, and
evaluated against an LLM like BERT, as key length increased, heightened
complexity led to a noticeable decline in performance. This decrease in
accuracy is attributed to the cipher’s inherent randomized nature, which
presents a challenge to BERT’s cryptanalysis capabilities. The introduction of
an augmented key length further escalated complexity.

##  VI Conclusion

Classical substitution ciphers find revitalization through the integration of
a randomized key matrix, effectively addressing the limitations of traditional
methods while maintaining their simplicity and accessibility. Competitive
computational speeds are not only achieved by the proposed methodology but
also by the demonstration of remarkable resilience against frequency-based
attacks, thus mitigating the vulnerabilities that substitution ciphers face.
The extensive keyspace offered by the method serves as a robust defense
mechanism against exhaustive search attacks like brute force. Additionally,
the adaptation of the method to contemporary demands is showcased by its
resilience to LLM, such as BERT.

Looking ahead, promising avenues for further exploration and application of
the technique emerge. The optimization of key sizes to suit diverse
application scenarios stands as a key direction for future research, enabling
the tailoring of the method to specific security requirements. Further
research may aim to ensure that the size of the ciphertext does not exceed
that of the plaintext. Furthermore, the real-world implementation of the
method in contexts such as low-powered sensors and offline encryption will
bridge the gap between theoretical understanding and practical deployment,
thus validating its efficacy in real-time scenarios.

## References

  * [1] F. Maqsood, M. Ahmed, M. M. Ali, and M. A. Shah, “Cryptography: A comparative analysis for modern techniques,” _International Journal of Advanced Computer Science and Applications_ , vol. 8, no. 6, 2017.
  * [2] S. Chandra, S. Paira, S. S. Alam, and G. Sanyal, “A comparative survey of symmetric and asymmetric key cryptography,” in _2014 International Conference on Electronics, Communication and Computational Engineering (ICECCE)_ , 2014, pp. 83–93.
  * [3] M. N. Alenezi, H. Alabdulrazzaq, and N. Q. Mohammad, “Symmetric encryption algorithms: Review and evaluation study,” _International Journal of Communication Networks and Information Security_ , vol. 12, no. 2, pp. 256–272, 2020.
  * [4] A. Mathur, “A research paper: An ascii value based data encryption algorithm and its comparison with other symmetric data encryption algorithms,” 2012. [Online]. Available: https://api.semanticscholar.org/CorpusID:124895837
  * [5] F. Maqsood, M. Ahmed, M. M. Ali, and M. A. Shah, “Cryptography: A comparative analysis for modern techniques,” _International Journal of Advanced Computer Science and Applications_ , vol. 8, no. 6, 2017. [Online]. Available: http://dx.doi.org/10.14569/IJACSA.2017.080659
  * [6] R. Tripathi and S. Agrawal, “Comparative study of symmetric and asymmetric cryptography techniques,” 2014. [Online]. Available: https://api.semanticscholar.org/CorpusID:212572880
  * [7] S. G. Srikantaswamy, “IMPROVED CAESAR CIPHER WITH RANDOM NUMBER GENERATION TECHNIQUE AND MULTISTAGE ENCRYPTION,” Mar. 2019. [Online]. Available: https://doi.org/10.5281/zenodo.2605906
  * [8] O. E. Omolara, A. I. Oludare, and S. Abdulahi, “Developing a modified hybrid caesar cipher and vigenere cipher for secure data communication,” _Computer Engineering and Intelligent Systems_ , vol. 5, pp. 34–46, 2014\. [Online]. Available: https://api.semanticscholar.org/CorpusID:212510664
  * [9] A. H. Disina, “Robust caesar cipher against frequency cryptanalysis using bi-directional shifting.” 2014. [Online]. Available: https://api.semanticscholar.org/CorpusID:59585616
  * [10] M. R. S. Navale, M. A. N. Jalgeri, and M. B. B. Jagadale, “Survey on various substitution techniques for cryptography.”
  * [11] A.-A. Mohammed and A. Olaniyan, “Vigenere cipher: Trends, review and possible modifications,” _International Journal of Computer Applications_ , vol. 135, pp. 46–50, 02 2016.
  * [12] D. Mandal and A. Deepti, “A cryptosystem based on vigenere cipher by using mulitlevel encryption scheme,” _IJCSIT_ , vol. 7, pp. 2096–2099, 08 2016\.
  * [13] P. Goyal, G. Sharma, and S. Kushwah, “Network security: A survey paper on playfair cipher and its variants,” _International Journal of Urban Design for Ubiquitous Computing_ , vol. 3, pp. 1–8, 03 2015.
  * [14] Q. Kester, “A hybrid cryptosystem based on vigenere cipher and columnar transposition cipher,” _CoRR_ , vol. abs/1307.7786, 2013. [Online]. Available: http://arxiv.org/abs/1307.7786
  * [15] A.-K. Al Tamimi, “Performance analysis of data encryption algorithms,” _available at weblink: http://www. cse. wustl. edu/~ jain/cse567-06/ftp/encryption_perf/index. html_ , 2006.
  * [16] M. Panda, “Performance analysis of encryption algorithms for security,” in _2016 International Conference on Signal Processing, Communication, Power and Embedded System (SCOPES)_ , 2016, pp. 278–284.
  * [17] N. Sharma, H. Meghwal, M. Mehta, and T. Kumar, “A review on playfair substitution cipher and frequency analysis attack on playfair,” in _2018 2nd International Conference on Trends in Electronics and Informatics (ICOEI)_ , 2018, pp. 1–9.
  * [18] M. Zulkifli and Z. W. Mohd, “Attack on cryptography,” _Comput. Secur_ , vol. 12, no. 5, pp. 33–45, 2008.
  * [19] A. L. Hananto, A. Solehudin, A. S. Y. Irawan, and B. Priyatna, “Analyzing the kasiski method against vigenere cipher,” 2019.
  * [20] G. A. J. Saskara and B. Rahardjo, “Design and implementation randomized cryptography algorithm detection using chaos algorithm.”
  * [21] N. Kambhatla, “Decipherment of substitution ciphers with neural language models,” 2018.