# LR-Net: A Block-based Convolutional Neural Network for Low-Resolution Image
Classification

$\text{Ashkan Ganj}^{1}$, $\text{Mohsen Ebadpour}^{2}$, $\text{Mahdi
Darvish}^{1}$, $\text{Hamid Bahador}^{1,*}$

* Corresponding author<EMAIL_ADDRESS>1Department of Electrical and Computer Engineering, University of Mohaghegh Ardabili, Ardabil, Iran
2Department of Computer Engineering, Amirkabir University of Technology,
Tehran, Iran

###### Abstract

The success of CNN-based architecture on image classification in learning and
extracting features made them so popular these days, but the task of image
classification becomes more challenging when we apply state of art models to
classify noisy and low-quality images. It is still difficult for models to
extract meaningful features from this type of image due to its low resolution
and lack of meaningful global features. Moreover, high-resolution images need
more layers to train which means they take more time and computational power
to train. Our method also addresses the problem of vanishing gradients as the
layers become deeper in the deep neural networks that we mentioned earlier. In
order to address all these issues, we developed a novel image classification
architecture, composed of blocks that are designed to learn both low-level and
global features from blurred and noisy low-resolution images. Our design of
the blocks was heavily influenced by Residual Connections and Inception
modules in order to increase performance and reduce parameter sizes. We also
assess our work using the MNIST family datasets, with a particular emphasis on
the Oracle-MNIST dataset, which is the most difficult to classify due to its
low-quality and noisy images. We have performed in-depth tests that
demonstrate the presented architecture is faster and more accurate than
existing cutting-edge convolutional neural networks. Furthermore, due to the
unique properties of our model, it can produce a better result with fewer
parameters. The source code of the project is available at this Github
repository.

###### Index Terms:

Image classification, Image Processing, Convolutional neural networks, Deep
learning

##  I Introduction

In the last yeras Deep convolutional neural networks changed the era of
computer vision. They can be used in most of the computer vision tasks such as
object detection [1, 2], image classification [3, 4], or instance image
segmentation [2]. It is better to use a convolutional neural network rather
than a feed-forward network since it allows parameter sharing and
dimensionality reduction. In CNN, the feature of parameter sharing leads to
reduction of the number of parameters, therefore, the computations are also
reduced. Based on CNNs, the principal idea is that pixels and their
surroundings have semantic meaning within each image, while elements of
interest can appear anywhere within the image. Similarly to MLPs, CNN’s have
layers, but they’re not fully connected: they’ve got filters, which are sets
of cube-shaped weights that are applied to the whole image.

Since AlexNet’s [5] remarkable success in the ILSVRC-2012 image classification
competition, which combined GPU and CNN, further research has focused on
enhancing the CNN architecture and integrating it with new concepts to get
higher performance.VGG[6], GoogleLeNet[7], and ResNet[8] are three popular
attempts to improve performance by using CNNs.To improve performance, the
Visual Geometry Group (VGG)[6] is looking into deeper network performance by
extracting as many features as possible from high-resolution photos, or the
Inception module network (GoogleNet)[7] is attempting to perform multiple
operations (pooling, convolution) in parallel with different filter sizes
(3x3, 5x5, etc.) to reduce the possibility of making trade-offs. For example,
in CNN models, the choice of pooling stages and deciding about the kernel size
are two critical trade-offs that have a great impact on the outcome. ResNet[8]
generates residual learning blocks by employing identity mapping shortcut
connections. As a result, with hundreds or even thousands of layers, the
neural network model can overcome the gradient vanishing problem. Furthermore,
DenseNet[9] and others found that reorganizing connections between layers of a
network improves learning and representation.

All of the models mentioned above have one thing in common: they work better
with high-resolution images. However, the issue is that high-resolution images
are not always possible due to image age or bandwidth and computation
limitations. After testing some of the most advanced models, such as
Inception-v3[10], with low-resolution images, such as Oracle-MNIST[11], which
contain a lot of natural noise as well, we observed a performance degradation
in models compared with their results with high-resolution images. Because
DNNs and CNNs are built on the same architecture, this problem appears to be
common[12]. Overall, it has been recognized that poor image quality has a
significant impact on the performance of deep neural networks in computer
vision tasks, as noted here[13]. Many factors influence the quality of an
image in the real world. Most of the time, we cannot get a pure and high-
resolution image, and most images have some level of noise and degradation,
which will diminish the final result. So in this paper, we try to directly
address this problem with a new architecture by utilizing the idea of
inception[7] to get as many features as possible from images by using
different kernels and combining them with some residual connections[8] to
solve problems like vanishing gradients and the problem of dimensionality in
deep neural networks.

This paper commences with introducing some related works in the following
section. Next, it explains the approach proposed and presented the
experimental setup, and talk about the result of training in sections III and
IV, respectively, and finally, we have a conclusion in section V.

##  II Related Work

The use of Convolutional Neural Networks (CNNs) has been a key method of
recognizing images, such as classifying them [14, 7], recognizing actions[15],
and locate objects [16]. As deep learning models require a lot of training
instances to be able to converge, Pre-trained models have been implemented to
process small- and medium-sized datasets. There seems to be a noticeable
improvement in accuracy with the method mentioned above. Nevertheless, because
of the pretrained weights to large datasets (e.g., ImageNet[17]), it is more
time consuming and computationally intensive than ever.

According to Han et al.[18] and Wang et al.[11], in order to challenge deep
learning models, they created benchmark datasets that are acceptable and share
the same characteristics of MNIST, namely that the datasets are small in size
and encoded in an easy way to use. Images from both Fashion and Oracle are
converted into a format compatible with the MNIST dataset. Thus, they can use
MNIST’s original dataset instantly regardless of the machine learning system.
Also, noted datasets contain more complex information than simple digits
extracted from the MNIST.

Several innovative models for classifying $2\times*28$ images were presented
in the literature [19]. In order to characterize the images in the fashion-
MNIST dataset using convolutional neural networks, the authors prepared three
types of neural networks. The model exhibits amazing results on the benchmark
dataset. An extensive correlation was established between various CNN
structures (for example, VGG16) on various datasets (for example, Image Net)
using the leNet-5 network designed for fashion-MNIST. As one example, a custom
CNN type with stacked convolution layers of VGG 16 achieved an accuracy rate
of 93.07 percent on the Fashion MNIST in its published study [20]. Various
models of CNNs were introduced to determine which of them is most suitable for
characterization and identification in terms of their accuracy. The deep
learning architectures that were applied were LeNet-5, AlexNet, VGG-16, and
ResNet.

In most cases, the models perform exceptionally well on specific data, but
they do not generalize well to similar datasets. As an example, [21] proposed
a shallow convolutional neural network using batch normalization techniques in
order to accelerate training convergence and improve accuracy. The noted
network consists of only four layers with small convolution kernels, resulting
in a low time and space complexity. Even though the model achieved top
accuracy on the digits MNIST dataset[22], it was not able to perform
sufficiently on both CIFAR[14] and Fashion MNIST[18].

It is the intention of most of the recently developed Deep convolutional
neural networks (DCNNs) that they utilize Inception and Residual connections
as the basis to implement bigger deep networks. In order to make the model
more accurate and detailed, the parameters of the architecture are increased
substantially as the size and depth of the model increases. The complex nature
of this training increases the complexity of the model, which, in turn,
increases the amount of resources required to run it. Recurrence is a
difficult property to incorporate in popular Inception architectures, but it
is crucial to improving training and testing accuracy by requiring fewer
computational resources. Some researchers have attempted to implement more
complex DCNN architectures such as GoogleNet [7], or residual networks with
1001 layers [23] that are capable of high recognition accuracy when applied to
different benchmark datasets.

As we intend to tackle the problem of handling the low resolution image and
its classification, we consider the CNN’s first layers as feature extractors,
after that, images are classified by taking advantage of these features. In
order to maximize efficiency, a custom CNN block is designed. As compared to
mainstream DCNN architectures, this model not only guarantees a higher
recognition accuracy while requiring fewer computation parameters but also
contributes to the overall training process of the deep learning approach as a
whole.

##  III Method

###  III-A problem overview

In this section, we are going to talk about the reason that we decided to
introduce a new architecture for image classification. After doing some tests
with some famous state-of-the-art models on the Oracle-MNIST[11], we find out
a noticeable decrease in the performance of the models. With some further
experiments, we realized that the relation between classiﬁcation accuracy and
the resolution of images is close to being linear, in all the cases[24], and
this problem seems to be common in most image classification algorithms. Even
images with small degradation or noise, which is not noticeable by humans can
cause performance problems for models. According to our findings, we believe
that the primary cause of this problem is the architecture of the models, and
in order to solve the issue, we believe that new algorithms and architectures
need to be developed. In this paper, we introduced a new architecture for
addressing this problem.

Figure 1: An illustration of the overall architecture of the model is shown in
this figure, along with details on each of the blocks. Our block architecture
is influenced by both Inception and Residual Net concepts. The block can be
divided into two different sides, from which we can extract specific features.
As part of our approach, three kernels ($3\times 3$, $5\times 5$, $7\times 7$)
were used for feature extraction and a $1\times 1$ kernel was used for feature
combining at the last step.

###  III-B Overall Architecture

As you can see from the figure. 1, our architecture consists of 3 Multi-kernel
blocks that stack on top of each other, including the steps that our models
take to learn the features and details. After that, we add some Fully
connected layers and the last layer with a sigmoid activation function for
classifying the outputs. The proposed architecture uses the concept of
inception and residual connections in MK blocks to provide robust performance
for classifying images. As we know the inception modules were introduced as a
way to reduce computational expenses in CNN, and we knew that the simple
models couldn’t solve this problem so we tried to get the inception module
idea and use it with a combination of residual connections to improve accuracy
and reduce computation overhead. Since our neural network deals with a wide
variety of images with varying salient parts or features, so using an
inception base idea is essential for this architecture.

As our input images are low-resolution images, the useful details usually
exist in fewer pixels, and for each window or kernel, the information that can
be extracted is rarely found, so the filter size in our models is descending,
which means that for larger sizes, we will have smaller kernel sizes.
Additionally, the padding of each convolutional layer is the same since the
results must be concatenated.

Figure 2: The building block of the deep residual network.

The Multi-Kernel block (MK-block) contains several residual connections, as
shown in 1. Rather than learning unreferenced functions, these links learn
residual functions by referencing the layer inputs. The stacked nonlinear
layers are let to fit another mapping of $F(x):=H(x)\times x$ that corresponds
to the desired underlying mapping $H(x)$. $F(x)+x$ is formed from the initial
mapping (see 2). The residual mapping is generally easier to tweak than the
original one. In theory, fitting an identity mapping by a stack of nonlinear
functions requires less effort than pushing the residual to zero if an
identity mapping is optimal.

###  III-C Multi-Kernel block

Figure 3: MK-block’s first layer shows details of kernel connections as well
as how information is shared between them.

As we mentioned earlier, our model was constructed by stacking 3 Multi-Kernel
blocks(Mk-kernel) on top of each other. Our architecture relies heavily on
these identical blocks. At the first layer(figure. 3) of our block, we have 3
different kernels ($3\times 3$, $5\times 5$, $7\times 7$). The connection of
these 3 kernels is critical.Because, we want to share the information in a way
that our model doesn’t experience a big jump in kernel and feature. In other
words, we connect the result of kernels that have meaningful relationships
between them. For example, we have a connection between kernels $3\times 3$
and $5\times 5$ because the information that they exchange is useful. However,
we do not have a connection between $3\times 3$ and $7\times 7$, because the
information that they will share is unusable, and the second reason to have
this type of connection is that we want to process the low-resolution
information. This is because as we know, the big kernels extract more global
information, while smaller kernels extract detail and local information. If
you look at figure 1, you will see that we have a connection between $3\times
3$, $5\times 5$, and $7\times 7$. The reason we made this connection is that
the $5\times 5$ kernel can create a balance between the $3\times 3$ and
$7\times 7$ images in a way that the model will better understand which parts
of the image will have a local view and which parts will have a global view.

We divide our block into two parts in the second layer. On the right side, we
connect the nodes with kernel $5\times 5$ and kernel $7\times 7$ together, and
at this step, the model attempts to conclude the information in big kernels
without considering details, and it will use this information at the last
layer when we want to aggregate all the features. Our next layer is a $3\times
3$ Conv layer that gathers the last details from small sizes, or we can say
that we will do local features extraction or low-level features extraction
based on global features. The model will try to extract as much detail and
low-level features as it can in the continuation of conv2D with kernel
$3\times 3$, since in the previous layer we extracted some low-level features,
and so we repeat this operation again. The reason we need this step is that we
need good performance on noisy and blurry images. At the end of the process,
the extracted features should be applied with any weight from the previous
steps.

The last point to note is the way we chose the number of filters. In our
images, we have two types of features some of them are local and some of them
are global features. When we choose small filters, the model will extract the
small and detailed features, which will perform poorly with low-quality and
noisy images, while when we choose larger kernels, a much more complex neural
network will be needed to extract all useful images. As a result, we decided
to implement the inception concept, which uses different image sizes across
layers. Because our goal is to classify the low-resolution images. So, we
decided to have more $3\times 3$ kernels than $7\times 7$ and $5\times 5$
kernels.

##  IV Experiments

###  IV-A Datasets

TABLE I: Information regarding the size and number of instances of datasets used for evaluation and training in this paper. Dataset name | Training data | Validation data | Test data
---|---|---|---
Instances | Size | Instances | Size | Instances | Size
Digit MNIST | – | 64.73 | – | 88.41 | – | 94.13
Fashion MNIST[18] | 71.1 | 63.32 | 36.4 | 88.70 | 20.7 | 94.93
Oracle MNIST[11] | 49.4 | 68.55 | 22.3 | 91.73 | 14.1 | 96.28

We use MNIST-family datasets to evaluate our work results and compare them
with other state-of-art models to show the superiority of our model. The MNIST
family datasets have both the characteristics we want to study which are noise
and low-quality image. The table I shows a summary all the information
provided in the next parts.

Figure 4: Training and validation loss over epochs generated by training the
custom CNN model on (a) MNIST Fashion, (b) Digit MNIST, and (c) Oracle MNIST
datasets. The gradual increment in accuracy suggests the efficiency of the
network for learning practical features of the image with an optimal
convergence pace.

Mnist Digit Dataset - The fact that most of the models use this dataset and
that it also meets our requirement for a low-resolution image led us to choose
it as a way to demonstrate the power of our architecture while providing a
good way to compare our results with those of other state-of-the-art models.
The MNIST dataset was created using NIST’s Special Databases 3 and 1, which
include binary images of handwritten integers. Initially, NIST classified SD-3
as the training set and SD-1 as the test set. SD-3, on the other hand, is much
cleaner and easier to discern than SD-1. The MNIST training set contains
30,000 SD-3 patterns and 30,000 SD-1 patterns. Our test set included 5,000
SD-3 patterns and 5,000 SD-1 patterns. The SD-1 has 58,527 digit images
authored by 500 different writers. In contrast to SD-3, where blocks of data
from each writer appear in sequence, the data in SD-1 is fragmented.

Fashion Mnist Dataset - Fashion-MNIST[18] is a dataset of Zalando article
photos, with 60,000 examples in the training set and 10,000 examples in the
test set. Each example is a 28x28 grayscale image paired with a label from one
of ten categories. Fashion-MNIST is intended to be a drop-in replacement for
the original MNIST dataset for evaluating machine learning algorithms. The
image size and structure are the same as in the training and testing splits.

Each image is 28 pixels high and 28 pixels wide, for a total of 784 pixels.
Each pixel has a single pixel-value associated with it, which indicates how
light or dark that pixel is, with larger numbers indicating darker. This pixel
value is an integer ranging from 0 to 255. There are 785 columns in the
training and test data sets. The class labels are listed in the first column.
The first represents the clothing, while the second represents the
accessories. The remaining columns contain the corresponding image’s pixel
values.

Oracle Mnist Dataset -  The Oracle-MNIST dataset [11] contains 30,222 ancient
characters from ten categories in $28\times 28$ grayscale image format for
pattern classification, with special challenges in image noise and distortion.
The training set has 27,222 images, while the exam set has 300 images per
class. It uses the same data structure as the original MNIST dataset, making
it compatible with all existing classifiers and systems. However, it is more
difficult to train a classification model on it without overfitting and low
performance. Images of ancient characters suffer from 1) incredibly serious
and unusual noises created by three thousand years of burial and aging, as
well as 2) significantly different writing styles in ancient Chinese, both of
which make them realistic for machine learning study.

We chose this dataset due to its noisy and low-resolution characteristics.
This aspect of the dataset makes it extremely difficult for a standard model
to classify the images. Figures x and y show that the Inception v3 [7] and
Vgg-16 [6] models are not performing optimally, and we can see an obvious
degradation in the models’ performance.

###  IV-B Training setup

To improve the reliability of our results, we use the same setup and input
size for training and testing all models. The images have been resized to
$35\times 35\times 1$ in order to preserve the standard input size for models
like Inception-v3 [7] and VGG-16 [6], which don’t function properly with
$28\times 28$. For training the models we use Google-Colab with an NVIDIA
Tesla T4 GPU with 16GB memory, with a batch size of 256. For analyzing the
model’s behavior over a long period of time, models were trained for 200
epochs. However, for publishing the model we use a callback function that
stops the training after 30 unchanged epochs on validation loss this technique
is applied to save time and prevent overfitting.

###  IV-C Results

In this section, the results of our work will be presented and we will have a
comparison between our model’s accuracy and loss against other models to
evaluate the effectiveness of introduced architecture in low-resolution image
classification tasks.

As shown in Fig. 4, our model easily outperformed 3 other state-of-art models
in terms of accuracy in all 3 datasets, without experiencing overfitting or a
gradient exploding problem. It is important to note that the introduced model
is a simpler and easier model than the other two. We can see this by looking
at the number of parameters in table II, and despite the lower number of
parameters, it outperformed the other famous models due to the unique MK-
blocks we introduced in this section III. By looking at the tables and charts
one point that we can understand is that the model’s performance is directly
impacted by the image’s detail and noise. For example, the model’s accuracy is
lower on Oracle-MNIST[11] dataset because the dataset contains a lot of noisy
images, and also the inner-variance in the labels affects the performance of
the model, but compared to other state-of-the-art models, the introduced
method can achieve a higher and acceptable result with an accuracy of 95.13
according to table II. We were expecting these results because of our unique
block-based architecture that we introduced in section III. In each block, we
used a number of residual connections between the input and upper levels of
each layer in order to maintain the features. This turns out to be very
effective at increasing the meaningful features of models and also enabled us
to overcome the gradient exploding problem that we have in deeper networks.
Using residual connections in combination with different kernel sizes in each
layer leads to achieving better results, as we can see in both the table II
and Fig. 4.

]

Figure 5: A bar chart illustrating the accuracy of the proposed block-based
network. Three datasets are considered: MNIST Digit, MNIST Fashion, and Oracle
MNIST.

###  IV-D Comparative Evaluation

TABLE II: The accuracy and number of parameters of 4 different image classification algorithms on 3 famous mnist datasets Model Name |  Digit MNIST |  Fashion MNIST[18] |  Oracle MNIST[11] |  Number of Parameters
---|---|---|---|---
Inception-V3 | 93.31 | 94.44 | 92.6 | 23,851,784
VGG-16 | 92.4 | 74.2 | 52.6 | 138,357,544
Ours | 99.47 | 95.03 | 95.13 | 1,028,234

The purpose of this section is to compare our methods with VGG-16 [6] and
Inception-V3 [10] on three popular datasets: MNIST-Digit, MNIST-Fashion [18],
and Oracle-MNIST [11]. As we discussed earlier in sectioin III, we used the
idea of the inception module and the Res-Net connection in order to improve
the accuracy and performance of the model on low-resolution images.

According to Fig. 5, our newly developed model outperforms both other models.
We get better results by reducing the number of parameters, which reduces
computation overhead and increases speed. As shown in table II, our model is
much more accurate than other models in the MNIST dataset with 99.47 accuracy.
Because, this dataset is an easy and simple dataset so, we anticipated this
kind of performance for this dataset. In the second dataset (fashion-
mnist[18]), which is a harder dataset to classify due to the image complexity
we have on images, our model can achieve a better accuracy compared to other
and by looking at Fig. 4, we can see the model keeps its robustness during
training.

The real challenge comes with Oracle-MNIST [11], since it is a newly collected
dataset with unique characteristics. As indicated in this section IV-A, there
is some natural noise and blur in images. As a result, the images have very
poor quality, which will reduce the performance of the models. Based on our
tests, which are available in the table. II. The old two state-of-the-art
models (inception-v3 [10], VGG-16 [6]) had very poor performance on Oracle-
MNIST [11], despite their higher number of parameters and complexity of their
architecture (table II). However, our model achieves a better result on this
dataset and it is able to classify images with greater confidence while having
less power consumption than inception-v3 [10] and VGG-16 [6] due to its lower
number of parameters.

##  V Conclusion and Future Work

In this paper, a novel architecture for low-resolution image classification is
proposed and examined. Using the results of our study, we can conclude that
this model can outperform many of the state-of-the-art models that are
currently available in image classification tasks. In addition, the presence
of modules similar to those seen at inception may contribute to these results.
With the help of these two ideas, we were able to create a model that was
simpler and more efficient comparing to others. The model was evaluated on
MNIST family datasets and is generalizable to other low-resolution ones.

As a future work, there are several modifications that can be performed to
make our model more robust against noises and make it faster by reducing the
number of parameters. According to our findings, the image size decreased
dramatically after the first MK-block, so having the same number of filters
for the second and third MK blocks would not be optimal, which increases
computational costs and would be undesirable. The goal is to introduce a new
hyperparameter for the number of filters in the second and third blocks in
order to make these blocks more flexible for the individual image. Another way
to manage this problem is to use deconvolution to increase the image size
after each block. This will increase feature extraction and make the system
more robust overall.

## References

  * [1] V. Mazzia, A. Khaliq, F. Salvetti, and M. Chiaberge, “Real-time apple detection system using embedded systems with hardware accelerators: An edge ai application,” IEEE Access, vol. 8, pp. 9102–9114, 2020.
  * [2] K. He, G. Gkioxari, P. Dollár, and R. Girshick, “Mask r-cnn,” in 2017 IEEE International Conference on Computer Vision (ICCV), pp. 2980–2988, 2017\.
  * [3] C. Szegedy, W. Liu, Y. Jia, P. Sermanet, S. Reed, D. Anguelov, D. Erhan, V. Vanhoucke, and A. Rabinovich, “Going deeper with convolutions,” in 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 1–9, 2015.
  * [4] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 770–778, 2016.
  * [5] A. Krizhevsky, I. Sutskever, and G. E. Hinton, “Imagenet classification with deep convolutional neural networks,” in Proceedings of the 25th International Conference on Neural Information Processing Systems - Volume 1, NIPS’12, (Red Hook, NY, USA), p. 1097–1105, Curran Associates Inc., 2012\.
  * [6] K. Simonyan and A. Zisserman, “Very deep convolutional networks for large-scale image recognition,” arXiv preprint arXiv:1409.1556, 2014.
  * [7] C. Szegedy, W. Liu, Y. Jia, P. Sermanet, S. Reed, D. Anguelov, D. Erhan, V. Vanhoucke, and A. Rabinovich, “Going deeper with convolutions,” in Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 1–9, 2015.
  * [8] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770–778, 2016.
  * [9] G. Huang, Z. Liu, L. Van Der Maaten, and K. Q. Weinberger, “Densely connected convolutional networks,” in Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 4700–4708, 2017.
  * [10] C. Szegedy, V. Vanhoucke, S. Ioffe, J. Shlens, and Z. Wojna, “Rethinking the inception architecture for computer vision,” in Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2818–2826, 2016.
  * [11] M. Wang and W. Deng, “Oracle-mnist: a realistic image dataset for benchmarking machine learning algorithms,” arXiv preprint arXiv:2205.09442, pp. 1–7, 2022.
  * [12] S. Dodge and L. Karam, “Understanding how image quality affects deep neural networks,” in 2016 eighth international conference on quality of multimedia experience (QoMEX), pp. 1–6, IEEE, 2016.
  * [13] M. Koziarski and B. Cyganek, “Impact of low resolution on image recognition with deep neural networks: An experimental study,” International Journal of Applied Mathematics and Computer Science, vol. 28, pp. 735 – 744, 2018.
  * [14] A. Krizhevsky, I. Sutskever, and G. E. Hinton, “Imagenet classification with deep convolutional neural networks,” Advances in neural information processing systems, vol. 25, 2012.
  * [15] G. Gkioxari, R. Girshick, and J. Malik, “Contextual action recognition with r* cnn,” in Proceedings of the IEEE international conference on computer vision, pp. 1080–1088, 2015.
  * [16] S. Bell, C. L. Zitnick, K. Bala, and R. Girshick, “Inside-outside net: Detecting objects in context with skip pooling and recurrent neural networks,” in Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2874–2883, 2016.
  * [17] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei, “Imagenet: A large-scale hierarchical image database,” in 2009 IEEE conference on computer vision and pattern recognition, pp. 248–255, Ieee, 2009.
  * [18] H. Xiao, K. Rasul, and R. Vollgraf, “Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms,” 2017.
  * [19] D. Hirata and N. Takahashi, “Ensemble learning in cnn augmented with fully connected subnetworks,” arXiv preprint arXiv:2003.08562, 2020.
  * [20] K. Greeshma and K. Sreekumar, “Hyperparameter optimization and regularization on fashion-mnist classification,” International Journal of Recent Technology and Engineering (IJRTE), vol. 8, no. 2, pp. 3713–3719, 2019.
  * [21] F. Lei, X. Liu, Q. Dai, and B. W.-K. Ling, “Shallow convolutional neural network for image classification,” SN Applied Sciences, vol. 2, no. 1, pp. 1–8, 2020.
  * [22] L. Deng, “The mnist database of handwritten digit images for machine learning research,” IEEE Signal Processing Magazine, vol. 29, no. 6, pp. 141–142, 2012.
  * [23] K. He, X. Zhang, S. Ren, and J. Sun, “Identity mappings in deep residual networks,” in European conference on computer vision, pp. 630–645, Springer, 2016.
  * [24] M. Koziarski and B. Cyganek, “Impact of low resolution on image recognition with deep neural networks: An experimental study,” International Journal of Applied Mathematics and Computer Science, vol. 28, pp. 735–744, 12 2018.


11institutetext: IIIT Bangalore, IN
<EMAIL_ADDRESS>
# Attacks on a Privacy-Preserving Publish-Subscribe System and
a Ride-Hailing Service

Srinivas Vivek

###### Abstract

A privacy-preserving Context-Aware Publish-Subscribe System (CA-PSS) enables
an intermediary (broker) to match the content from a publisher and the
subscription by a subscriber based on the current context while preserving
confidentiality of the subscriptions and notifications. While a privacy-
preserving Ride-Hailing Service (RHS) enables an intermediary (service
provider) to match a ride request with a taxi driver in a privacy-friendly
manner. In this work, we attack a privacy-preserving CA-PSS proposed by Nabeel
et al. (2013), where we show that any entity in the system including the
broker can learn the confidential subscriptions of the subscribers. We also
attack a privacy-preserving RHS called lpRide proposed by Yu et al. (2019),
where we show that any rider/driver can efficiently recover the secret keys of
all other riders and drivers. Also, we show that any rider/driver will be able
to learn the location of any rider. The attacks are based on our cryptanalysis
of the modified Paillier cryptosystem proposed by Nabeel et al. that forms a
building block for both the above protocols.

###### Keywords:

P

rivacy, Publish-Subscribe System, Ride-Hailing Service, Homomorphic
Encryption, Modified Paillier Cryptosystem, lpRide

##  1 Introduction

Publish-Subscribe systems (also written as pub/sub systems) are a well-known
paradigm to disseminate information among multiple parties in a distributed
and asynchronous manner. Subscribers subscribe for content from publishers,
who create content and push notifications to the intermediaries’ network (aka.
brokers). Brokers route the content to subscribers based on their
subscription. A Context-Aware Publish-Subscribe System (CA-PSS) extends a
pub/sub system by taking into account the subscriber context. For instance,
the context could be the location of a subscriber in a traffic information
service, and the content from a publisher could correspond to the traffic
situation in the neighbourhood of the subscriber. Hence, the context of a
subscriber could change frequently over time. It is important to protect the
confidentially of the context, subscription and notification. The goal of a
Privacy-Preserving CA-PSS (PP-CA-PSS) is to protect the above confidential
information. The scheme from Nabeel et al. [NABB13a] is one of the early
proposals of a privacy-preserving CA-PSS. There have many works on this topic
and we refer to [Mun18, CBDA+] and references therein for more details.

On the other hand, a Ride-Hailing Service (RHS) too provides location-based
services. RHSs have become increasingly popular in recent years. Uber, Ola,
Lyft, Didi, Grab, etc. are some popular RHSs. With these services also comes
the risk of misuse of personal data. The Ride matching Service Providers
(RSPs) collect personal information regarding the riders and drivers along
with their ride statistics. There have been many instances of violation of
individual privacy of the users using these RHSs [Nor20]. A Privacy-Preserving
RHS (PP-RHS) aims to provide privacy guarantees to the users of the RHS,
namely, riders and drivers. Recent years have witnessed many proposals of PP-
RHS [PDJ+17, PDE+17, KFZC18, BLM+19, HNW+18, LJFX19, YSJ+19, WZL+18, YJZ+19].
Recently, the ORide RHS’s [PDE+17] security was revisited in [KMV21].

The focus of this work is on the PP-CA-PSS from [NABB13a] and the lpRride PP-
RHS proposed by Yu et al. [YSJ+19]. These two seemingly disparate protocols
share the following common features: a) both offer or potentially can offer
location-based services, and b) both the protocols are based on the modified
Paillier cryptosystem that was proposed in [NABB13a]. The modified Paillier
cryptosystem (yet another variant of the Paillier cryptosystem [Pai99]) is an
additively homomorphic (digital signature-like) cryptosystem and both the
protocols use this cryptosystem to blind the subscriptions and notifications
(resp. locations of riders and taxis) but still can perform subscription-
notification matching (resp. ride-matching) on the blinded data using the
additive homomorphism property.

###  1.1 Our Contribution

In this work, we analyse the security of the PP-CA-PSS from [NABB13a] and the
lpRide protocol. For the PP-CA-PSS we demonstrate an attack where any entity
in the system including the broker can fully learn the confidential
subscriptions of the subscribers. This invalidates the claim in [NABB13a] that
subscriptions remain confidential. We would like to note that we do not target
notifications from publishers or the content. Yet, subscriptions can leak
confidential information such as locations of subscribers.

On the lpRide protocol we exhibit a key recovery attack by any rider or driver
that can efficiently recover the secret keys of all other riders and drivers.
Also, we show that any rider or driver will be able to learn the location of
any rider. We were unable to recover drivers’ locations as they are blinded by
random values.

All our adversaries are honest-but-curious. The basis of our attack is our
cryptanalysis of the modified Paillier cryptosystem mentioned above. In
particular, we show that anyone will be able to forge the “signatures” and
that these signatures are deterministic. Hence, this result is of independent
interest to the security of protocols that are based on the modified Paillier
cryptosystem. It is somewhat surprising that a simple attack on this
cryptosystem went unnoticed despite many follow-up works of [NABB13a].

In Section 2, we recall and then cryptanalyse the modified Paillier
cryptosystem. In Section 3, we briefly recall the PP-CA-PSS, and then describe
our attack. In Section 4, we briefly recall the lpRide protocol, and then
describe our attack. Section 5 concludes the paper.

##  2 Cryptanalysis of Modified Paillier Cryptosystem

###  2.1 Recall of the Modified Paillier Cryptosystem

As mentioned earlier, the modified Paillier cryptosystem was proposed in
[NABB13a]. A preliminary use of this cryptosystem was already made in [NSB12].
As the name suggests, this cryptosystem is a variant of the Paillier
encryption scheme [Pai99]. It consists of the following three algorithms:

  * •

Key generation: choose two distinct large primes $p$ and $q$. Compute
$N=p\cdot q$ and $\lambda=\mathrm{lcm}(p-1,q-1),$ the Carmichael function of
$N$. Randomly sample a base
$g_{p}\overset{\$}{\leftarrow}\mathbb{Z}_{N^{2}}^{*}$, such that the order of
$g_{p}$ is a multiple of $N$. The latter condition can be ensured by checking
the condition

$\gcd(L(g_{p}^{\lambda}\pmod{N^{2}}),\;N)=1,$

where

$L(x)=\frac{x-1}{N},$ (1)

for

$x\in\\{y\;|\;y\in\mathbb{Z}_{\geq 0},\;y<N^{2},\;y\equiv 1\pmod{N}\\}.$

Compute

$\mu=\left(L(g_{p}^{\lambda}\pmod{N^{2}})\right)^{-1}\pmod{N}.$ (2)

The public “decryption” key is

$PK^{\prime}=(N,g_{p},\mu),$

and the secret “encryption” key is

$SK^{\prime}=\lambda.$

  * •

Encryption $E^{\prime}(m,r,SK^{\prime})$: let the plaintext
$m\in\mathbb{Z}_{N}$. Sample a random value
$r\overset{\$}{\leftarrow}\mathbb{Z}_{N}^{*}$. Compute the “ciphertext”

$c=g_{p}^{m\lambda}r^{N\lambda}\pmod{N^{2}}.$ (3)

When the randomness and the secret key is implicit from the context, we simply
denote the encryption of a message $m$ as $E^{\prime}(m)$.

  * •

Decryption $D^{\prime}(c,PK^{\prime})$: compute the plaintext

$m=L(c\pmod{N^{2}})\cdot\mu\pmod{N}.$ (4)

The scheme described above resembles a digital signature scheme more than an
encryption scheme, but we will follow the terminology from the previous works.
Note that in the original Paillier scheme [Pai99], the public key is
$(N,g_{p})$ and the secret key is $(\lambda,\mu)$. Hence, in the modified
scheme described above $\mu$ is made a public parameter in order to make the
decryption algorithm a) to be publicly computable (that is, make it like the
verification algorithm of a digital signature scheme), and b) more efficient.
The rationale to make $\mu$ public is the claim in [NABB13a] that it is hard
to compute the discrete logarithm of $\mu$ w.r.t. base $g_{p}$ to obtain
$\lambda$. Also, note that the modified scheme is also additively homomorphic,
i.e.,

$E^{\prime}(m_{1}+m_{2},r_{1}r_{2})=E^{\prime}(m_{1},r_{1})\cdot
E^{\prime}(m_{2},r_{2}),$

and

${E^{\prime}}^{m_{2}}(m_{1},r_{1})=E^{\prime}(m_{1}m_{2},r_{1}^{m_{2}}).$

###  2.2 Cryptanalysis

We now show that the modified Paillier scheme is insecure. Namely, an
adversary having access only to the public key can produce encryptions of
messages, contrary to the claims in [YSJ+19, NABB13a] that only those who
possess the secret key would be able to encrypt. Moreover, we also show that
the ciphertexts are deterministic.

###### Lemma 1

The ciphertexts of the modified Paillier cryptosystem (see (3)) are
deterministic.

###### Proof

Since $c=g_{p}^{m\lambda}r^{N\lambda}\pmod{N^{2}}$, by the properties of the
Carmichael function $\lambda$, we have $r^{N\lambda}\equiv 1\pmod{N^{2}}$ (see
for e.g., [Pai99, pp. 2]). Hence
$c=\left(g_{p}^{\lambda}\right)^{m}\pmod{N^{2}}$ and is independent of $r$. ∎

Next, we show how to efficiently compute $g_{p}^{\lambda}\pmod{N^{2}}$ from
the public key.

###### Lemma 2

$g_{p}^{\lambda}\pmod{N^{2}}=N\cdot(\mu^{-1}\pmod{N})+1$.

###### Proof

From (2),

$L(g_{p}^{\lambda}\pmod{N^{2}})\;\equiv\;\mu^{-1}\pmod{N}.$

Since $1\leq L(g_{p}^{\lambda}\pmod{N^{2}})<N$ , the lemma follows from the
definition of the $L$ function in (1). ∎

From Lemmas 1 and 2 and their proofs, we have

###### Corollary 1

$E^{\prime}(m)=(N\cdot(\mu^{-1}\pmod{N})+1)^{m}\pmod{N^{2}}$.

Hence, anyone with access to the public key can easily produce the (unique)
ciphertext corresponding to a given message without knowing the secret key (or
equivalently, will be able to forge the signature). Note that we were able to
compute $g_{p}^{\lambda}\pmod{N^{2}}$ without explicitly computing $\lambda$.
This constitutes a complete break of the modified Paillier cryptosystem.

##  3 Attack on the PP-CA-PSS from [NABB13a]

###  3.1 Recall of the scheme

For completeness, we briefly recall the relevant steps of the privacy-
preserving context-aware publish-subscribe system from [NABB13a] that are
necessary to understand our attack. For other details, we refer the reader to
[NABB13a] and its full version [NABB13b]. This protocol consists of the
following types of entities:

  * •

Context manager: it is a trusted third party (TTP) responsible for
initialising the system and registering other entities. There is a context
manager for each context (e.g. location) and the context could change
frequently. It provides secret keys to publishers (resp. subscribers) to
encrypt (resp. decrypt) the content payload during the initialisation phase
and there will be no further interaction with publishers/subscribers unless
the system must be reinitialised.

  * •

Publisher: owner of the messages/content that they like to publish and notify
the subscribers.

  * •

Subscriber: entity interested to subscribe for the content from the
publishers.

  * •

Broker: intermediary that matches the blinded/encrypted notifications and
subscriptions, and if there is a match, then forward the encrypted message to
the corresponding subscriber.

The threat model assumed in [NABB13a] is that the context manager is fully
trusted. The brokers are assumed to be honest-but-curious, i.e., they honestly
follow the protocol but are curious to learn the confidential notifications
and subscriptions. Publishers are expected to not collude with any other
entity and to follow the protocol honestly. Subscribers are not trusted.
Brokers may collude with one another and also collude with malicious
subscribers.

The steps of the protocol are as follows:

  * •

System initialisation: The context manager generates the parameters of the
modified Paillier cryptosystem. It maintains a set of contexts $\mathcal{C}$.
Each context $C_{i}\in\mathcal{C}$ is a tuple
$C_{i}=(\lambda_{i},\mu_{i},t_{i},r_{i})$, where $\lambda_{i}$ and $\mu_{i}$
are modified Paillier parameters described in Section 2. Implicit in the
description is the modulus $N_{i}$ that is different for each context, and
$t_{i},r_{i}\overset{\$}{\leftarrow}\mathbb{Z}_{N_{i}}$ are random values.
Brokers only match notifications with subscriptions within the same context.
The parameters $\lambda_{i}$ and $t_{i}$ are private to the context manager
but $\mu_{i}$ (also $N_{i}$) are public.

The context manager also deploys an Attribute-based Group Key Management (AB-
GKM) scheme [NB14] to manage the secret keys issued to the subscribers that is
used to decrypt the payload message of the notification. An AB-GKM scheme
enables group key management while also enabling fine-grained access control
among a group of users each of whom is identified by a set of attributes.
Subscribers need to provide their identity attributes (in an oblivious manner)
to the context manager and obtain the secrets that is also shared with the
subscribed publishers by the context manager. These secrets are later used to
derive the secret encryption key for the publisher to encrypt the payload
content, and also derive decryption keys for the subscribers. Since in this
work we do not target the encrypted payload content, we omit the details
corresponding to the AB-GKM scheme.

  * •

Subscriber registration: every subscriber registers with the context manager.
A subscriber with context $C_{i}$ receives the following parameters during the
registration:

$(E^{\prime}(-r_{i}),\;E^{\prime}(-1),\;g^{-t_{i}}E^{\prime}(-r_{i})),$

where $g\overset{\$}{\leftarrow}\mathbb{Z}_{N^{2}}^{*}$. The subscriber uses
these parameters to “blind” its subscriptions. Since $\mu_{i}$ is public, the
subscriber may decrypt $E^{\prime}(-r_{i})$ using the decryption procedure
$D^{\prime}$ to obtain $r_{i}$. Note that the parameter $r_{i}$ is common to
all the subscribers within a given context. It is claimed in [NABB13a] that
the subscriber can neither recover $g^{-t_{i}}$ nor $t_{i}$ from
$g^{-t_{i}}E^{\prime}(-r_{i})$. Needless to say, it was believed until now
that the ciphertexts $E^{\prime}(-r_{i})$ are randomised.

As briefly mentioned above, the subscribers also receive their secret of the
AB-GKM scheme depending on the identity attributes they possess but without
revealing them to the context manager.

  * •

Publisher registration: every publisher too registers with the context
manager. A publisher with context $C_{i}$ receives the following parameters
during the registration:

$(E^{\prime}(r_{i}),\;E^{\prime}(1),\;g^{t_{i}}E^{\prime}(r_{i})).$

As in the case of subscribers, the publisher uses these parameters to blind
its notifications. In addition to the modified Paillier parameters, the
publishers also receive the set of secrets for the AB-GKM scheme issued to the
subscribers, from the context manager. The publisher uses these secrets to
derive a secret encryption key to selectively encrypt the payload of the
notification of a subscriber depending on the latter’s subscription.

  * •

Notifications: in this system, every notification and subscription is
represented as a Boolean expression over a set of attribute/value pairs. The
publisher blinds a value $v$ $(0\leq v<2^{\ell}\ll N_{i})$ for an attribute
$a$ as follows:

$\displaystyle v^{\prime}=$ $\displaystyle\;g^{t_{i}}\cdot
E^{\prime}(r_{i})\cdot E^{\prime}(r_{i}(v-1))\cdot E^{\prime}(r_{v})$
$\displaystyle=$ $\displaystyle\;g^{t_{i}}\cdot E^{\prime}(r_{i}v+r_{v}),$ (5)

where $r_{v}$ is a suitably sampled random value in $\mathbb{Z}_{N_{i}}$. For
reasons that will be more clear when describing the matching phase, the value
$r_{v}$ is chosen such that $0\leq r_{i}(v-x)+r_{v}\leq N_{i}/2$ for
$x\in\\{0,1,\ldots,v\\}$, else $N_{i}/2<r_{i}(v-x)+r_{v}<N_{i}$ for
$x\in\\{v+1,v+2,\ldots,2^{\ell}-1\\}$.

The publisher also generates the encryption key $k$ of the AB-GKM scheme using
the secret it received from the context manager for the corresponding
subscriber. The publisher then encrypts the payload (denoted as
$\mathit{payload}$) of the notification $\langle a_{i}=v_{i}\rangle_{i\in I}$
as $\mathcal{E}_{k}(\mathit{payload})$.

  * •

Subscriptions: suppose a subscriber wants to subscribe for the attribute $a$
with the value $x$. It blinds $x$ as follows:

$\displaystyle x^{\prime}=$ $\displaystyle\;g^{-t_{i}}\cdot
E^{\prime}(-r_{i})\cdot E^{\prime}(r_{i}(1-x))$ $\displaystyle=$
$\displaystyle\;g^{-t_{i}}\cdot E^{\prime}(-r_{i}x).$ (6)

For each such attribute/value pairs $(a,x)$, a tuple $(a,x^{\prime},\alpha)$,
where $\alpha\in\\{<,\geq\\}$ is sent to the broker. Each such atomic
subscription thus allows a homomorphic greater/less than comparison between
the value and the notification. These atomic subscriptions are combined using
a Boolean formula to create the complete subscription.

  * •

Broker matching: the brokers are assumed to know the public parameters for all
the contexts $C_{i}$. Suppose a broker receives the blinded subscription
$x^{\prime}$ and the blinded notification $v^{\prime}$ for the attribute $a$.
It first computes $x^{\prime}\cdot v^{\prime}$ and, since the blinding values
$g^{t_{i}}$ and $g^{-t_{i}}$ get cancelled, the product is now a typical
modified Paillier ciphertext that can be decrypted using the public
parameters. It then decrypts the ciphertext to obtain the randomised
difference between the original values $x$ and $v$ as follows:

$d^{\prime}=D^{\prime}(x^{\prime}\cdot v^{\prime})=r_{i}(v-x)+r_{v}.$ (7)

The broker decides $v\geq x$ if $d^{\prime}\leq N_{i}/2$, otherwise $v<x$. For
a full/composite subscription, the broker evaluates the Boolean formula. After
successful matching, it forwards the encrypted payload
$\mathcal{E}_{k}(\mathit{payload})$ to the subscriber. The subscriber having
valid credentials will be able to derive the secret key $k$ and decrypt the
payload ciphertext.

###  3.2 Attack on the scheme

The basis of our attack on the PP-CA-PSS scheme from [NABB13a] is our attack
on the modified Paillier cryptosystem that we presented in Section 2. First,
we show that any registered publisher or subscriber will be able to compute
the blinding value $g^{t_{i}}$ used to hide notifications and subscriptions,
respectively.

###### Lemma 3

Within a context $C_{i}$, any publisher or subscriber will be able to
efficiently compute $g^{t_{i}}$.

###### Proof

Consider the case of a subscriber who receives the tuple
$(E^{\prime}(-r_{i}),\allowbreak\;E^{\prime}(-1),\allowbreak\;g^{-t_{i}}E^{\prime}(-r_{i}))$
from the context manager during its registration. From Lemma 1, the value of
$E^{\prime}(-r_{i})$ is unique and so is the value $g^{-t_{i}}\cdot\allowbreak
E^{\prime}(-r_{i})$. Hence by dividing the latter by the former, the
subscriber can easily recover the value $g^{-t_{i}}$. Analogously, the
publisher too can recover the blinding value. ∎

Hence, the claim in [NABB13a] that publishers/subscriber cannot efficiently
recover $g^{t_{i}}$ is incorrect.

###### Corollary 2

Within a context $C_{i}$, any broker, by colluding with a subscriber, will be
able to efficiently recover the subscription $x$ from its blinded subscription
$x^{\prime}$.

The above corollary follows immediately from the above lemma since a broker
can collude with any subscriber and learn the blinding value $g^{t_{i}}$ (and
hence $g^{-t_{i}}$) and the parameter $r_{i}$, and then remove the blinds from
the blinded subscription $x^{\prime}$ (see (• ‣ 3.1)) and eventually decrypt
the ciphertext $E^{\prime}(-r_{i}x)$ to recover $x$.

The broker can also attempt to recover the notifications from publishers but
since these values $v$ are blinded by the random values $r_{v}$ (see (• ‣
3.1)), we do not know how to recover the notifications. As already observed in
[NABB13a], there will be a small leakage on the value of $v-x$ leaked by the
randomised difference $d^{\prime}$ (see (7)) since $r_{v}$ is not sampled from
the uniform distribution. Since we now know $x$, this directly translates to a
small leakage on the value of the notification $v$ itself. Also, note that we
do not get learn anything about the payload of the notification.

##  4 Attack on the lpRide RHS Protocol

###  4.1 Recall of lpRide

For completeness, we briefly recall the relevant steps of the lpRide RHS
protocol that are necessary to understand our attack. For other details, we
refer to [YSJ+19]. The lpRide protocol consists of the following entities:

  * •

Authority: responsible for the registration of riders and taxis/drivers.

  * •

RSP: the ride matching service provider that provides the online service of
matching riders’ encrypted locations with the “nearest” taxis whose locations
too are encrypted.

  * •

Rider: a rider $u$ provides the encryption of its location $l_{u}$ to the RSP
to request a nearby taxi.

  * •

Taxi (aka. driver): a taxi $t_{k}$ provides the encryption of its location
$l_{t_{k}}$ to the RSP and waits for a match with its potential client.

The threat model assumed in [YSJ+19] is that the authority is fully trusted
and that its communications with other entities happen over authenticated
channels. The riders and taxis are honest-but-curious so is the RSP. Further,
it is assumed that the RSP will not collude with any rider or taxi.

The steps of the lpRide protocol are as follows:

  * •

System initialisation: the RSP prepares the road network embedding [SKS03] and
partitions it into zones. The authority initialises the system parameters
$(PK,SK)\overset{}{\leftarrow}\textrm{Init}_{\textrm{auth}}(\ell,\kappa)$, and
by using the modified Paillier cryptosystem generates and broadcasts its
public key

$PK=(N,g_{p},g,\bm{\mu},\ell,\kappa),$ (8)

where $\ell$ is the bit length of the location coordinates in the road network
embedding, $\kappa-1\leq\log_{2}N-2$ is the size of the random values used to
blind the location coordinates of drivers, and
$g\overset{\$}{\leftarrow}\mathbb{Z}_{N^{2}}^{*}$ is a random base, and
$\bm{\mu}=\langle\mu_{i}\rangle_{0\leq i\leq\omega}$ is a $\omega$-tuple of
modified Paillier cryptosystem public parameter $\mu$. The secret key is

$SK=(\bm{\lambda},\bm{\epsilon},\bm{\xi}),$

where $\bm{\lambda}=\langle\lambda_{i}\rangle_{0\leq i\leq\omega}$ is a
$\omega$-tuple of modified Paillier cryptosystem secret parameter $\lambda$.
The parameters $\bm{\epsilon}=\langle\epsilon_{i}\rangle_{1\leq i\leq\omega}$
and $\bm{\xi}=\langle\xi_{i}\rangle_{1\leq i\leq\omega}$ are $\omega$-tuples
of random values from $\mathbb{Z}_{N}$.

###### Remark 1

In the lpRide protocol, the same modulus $N$, and the same bases $g_{p}$ and
$g$ are suggested to be used for all the coordinates $1\leq i\leq\omega$. In
this case, $\lambda_{i}$ are all identical, so are all $\mu_{i}$. But the
protocol can be easily generalised to use different moduli and bases (and our
attack applies for this variant too).

  * •

Rider and Taxi registration:

    * –

Rider registration: the authority assigns a rider $u$ its secret key
$sk_{u}\overset{}{\leftarrow}\textrm{RiderKeyGen}(u,PK,SK)$. It chooses a set
of random integers $\langle r_{i}\rangle_{0\leq i\leq\omega}$ from
$\mathbb{Z}_{N}^{*}$, and computes

$\displaystyle E^{\prime}(-1)$
$\displaystyle=g_{p}^{-\lambda_{0}}r_{0}^{\lambda_{0}N}\pmod{N^{2}},$
$\displaystyle g^{-\epsilon_{i}}E^{\prime}(-1)$
$\displaystyle=g^{-\epsilon_{i}}g_{p}^{-\lambda_{i}}r_{i}^{\lambda_{i}N}\pmod{N^{2}},$
$\displaystyle g^{-\xi_{i}}E^{\prime}(-1)$
$\displaystyle=g^{-\xi_{i}}g_{p}^{-\lambda_{i}}r_{i}^{\lambda_{i}N}\pmod{N^{2}}.$

Then, the secret key of the rider is

$sk_{u}=(E^{\prime}(-1),\langle g^{-\epsilon_{i}}E^{\prime}(-1)\rangle_{1\leq
i\leq\omega},\langle g^{-\xi_{i}}E^{\prime}(-1)\rangle_{1\leq i\leq\omega}).$
(9)

Note that $g^{-\epsilon_{i}}$ and $g^{-\xi_{i}}$ serve as blinding values. It
is claimed in [YSJ+19], as was done in [NABB13a], that the rider can neither
recover $g^{-\epsilon_{i}}$ (resp. $g^{-\xi_{i}}$) nor ${\epsilon_{i}}$ (resp.
${\xi_{i}}$) from $g^{-\epsilon_{i}}E^{\prime}(-1)$ (resp.
$g^{-\xi_{i}}E^{\prime}(-1)$).

    * –

Taxi registration: the authority assigns a taxi $t_{k}$ its secret key
$sk_{t_{k}}\overset{}{\leftarrow}\textrm{TaxiKeyGen}(t_{k},PK,SK)$. It chooses
a set of random integers $\langle r^{\prime}_{i}\rangle_{0\leq i\leq\omega}$
from $\mathbb{Z}_{N}^{*}$, and computes

$\displaystyle E^{\prime}(1)$
$\displaystyle=g_{p}^{\lambda_{0}}{r^{\prime}}_{0}^{\lambda_{0}N}\pmod{N^{2}},$
$\displaystyle g^{\epsilon_{i}}E^{\prime}(1)$
$\displaystyle=g^{\epsilon_{i}}g_{p}^{\lambda_{i}}{r^{\prime}}_{i}^{\lambda_{i}N}\pmod{N^{2}},$
$\displaystyle g^{\xi_{i}}E^{\prime}(1)$
$\displaystyle=g^{\xi_{i}}g_{p}^{\lambda_{i}}{r^{\prime}}_{i}^{\lambda_{i}N}\pmod{N^{2}}.$

Then, the secret key of the taxi is

$sk_{t_{k}}=(E^{\prime}(1),\langle g^{\epsilon_{i}}E^{\prime}(1)\rangle_{1\leq
i\leq\omega},\langle g^{\xi_{i}}E^{\prime}(1)\rangle_{1\leq i\leq\omega}).$
(10)

  * •

Ride request: a rider $u$ generates an encrypted ride request
$\widehat{R}_{u}\overset{}{\leftarrow}\textrm{ReqGen}\allowbreak(\bm{c}_{u},sk_{u})$
by computing its location $\bm{c}_{u}=\langle\bm{c}_{u}[i]\rangle_{1\leq
i\leq\omega}$ in the embedded road network encoding, where
$0\leq\bm{c}_{u}[i]<2^{\ell}$ is an integer. Then, two vectors of blinded
ciphertexts $\widehat{\bm{c}}_{u}^{+}$ and $\widehat{\bm{c}}_{u}^{-}$ are
computed from $\bm{c}_{u}$ and $sk_{u}$ by element-wise multiplication.

    * –

$\widehat{\bm{c}}_{u}^{+}=\langle\widehat{\bm{c}}^{+}_{u}[i]\rangle_{1\leq
i\leq\omega}$, where

$\widehat{\bm{c}}_{u}^{+}[i]=sk_{u}[2]\cdot
sk_{u}[1]^{-\bm{c}_{u}[i]-1}=g^{-\epsilon_{i}}E^{\prime}(\bm{c}_{u}[i]).$ (11)

    * –

$\widehat{\bm{c}}_{u}^{-}=\langle\widehat{\bm{c}}^{-}_{u}[i]\rangle_{1\leq
i\leq\omega}$, where

$\widehat{\bm{c}}_{u}^{-}[i]=sk_{u}[3]\cdot
sk_{u}[1]^{\bm{c}_{u}[i]-1}=g^{-\xi_{i}}E^{\prime}(-\bm{c}_{u}[i]).$ (12)

The rider sends
$\widehat{R}_{u}=(\widehat{\bm{c}}_{u}^{+},\widehat{\bm{c}}_{u}^{-},z_{u})$ to
the RSP, where $z_{u}$ is the identity of the zone of the rider.

  * •

Taxi location update: a taxi $t_{k}$ computes its encrypted updated location
$\widehat{L}_{t_{k}}\overset{}{\leftarrow}\textrm{TaxiUpdate}(\bm{c}_{t_{k}},sk_{t_{k}})$
by computing its location
$\bm{c}_{t_{k}}=\langle\bm{c}_{t_{k}}[i]\rangle_{1\leq i\leq\omega}$ in the
embedded road network encoding, where $0\leq\bm{c}_{t_{k}}[i]<2^{\ell}$ is an
integer. Two vectors $\bm{r}_{1}=\langle\bm{r}_{1}[i]\rangle_{1\leq
i\leq\omega}$ and $\bm{r}_{2}=\langle\bm{r}_{2}[i]\rangle_{1\leq i\leq\omega}$
of $\kappa-1$-bit random integers are sampled. These random values are used to
blind the driver locations and, eventually, the differences of the distances
between rider and drivers. Then, two vectors of blinded ciphertexts
$\widehat{\bm{c}}_{t_{k}}^{+}$ and $\widehat{\bm{c}}_{t_{k}}^{-}$ are computed
from $\bm{c}_{t_{k}}$ and $sk_{t_{k}}$ by element-wise multiplication.

    * –

$\widehat{\bm{c}}_{t_{k}}^{+}=\langle\widehat{\bm{c}}^{+}_{t_{k}}[i]\rangle_{1\leq
i\leq\omega}$, where

$\displaystyle\widehat{\bm{c}}_{t_{k}}^{+}[i]$
$\displaystyle=sk_{t_{k}}[3]\cdot
sk_{t_{k}}[1]^{\bm{c}_{t_{k}}[i]-1+\bm{r}_{1}[i]}$
$\displaystyle=g^{\xi_{i}}E^{\prime}(\bm{c}_{t_{k}}[i]+\bm{r}_{1}[i]).$ (13)

    * –

$\widehat{\bm{c}}_{t_{k}}^{-}=\langle\widehat{\bm{c}}^{-}_{t_{k}}[i]\rangle_{1\leq
i\leq\omega}$, where

$\displaystyle\widehat{\bm{c}}_{t_{k}}^{-}[i]$
$\displaystyle=sk_{t_{k}}[2]\cdot
sk_{t_{k}}[1]^{-\bm{c}_{t_{k}}[i]-1+\bm{r}_{2}[i]}$
$\displaystyle=g^{\epsilon_{i}}E^{\prime}(-\bm{c}_{t_{k}}[i]+\bm{r}_{2}[i]).$
(14)

The taxi $t_{k}$ sends
$\widehat{L}_{t_{k}}=(\widehat{\bm{c}}_{t_{k}}^{+},\widehat{\bm{c}}_{t_{k}}^{-},z_{t_{k}})$
to the RSP, where $z_{t_{k}}$ is the identity of the zone of the taxi.

  * •

Ride matching: the RSP receives the ride request $\widehat{R}_{u}$ and the set
of taxi locations $\\{\widehat{L}_{t_{k}}\\}_{t_{k}\in\mathcal{T}}$ and
filters the list of taxis based on the zone information of the rider. Then, it
computes the products
$\widehat{\bm{c}}_{t_{k}}^{+}[i]\widehat{\bm{c}}_{u}^{-}[i]$ and
$\widehat{\bm{c}}_{t_{k}}^{-}[i]\widehat{\bm{c}}_{u}^{+}[i]$ for all $1\leq
i\leq\omega$. Note that the blinding values $g^{\xi_{i}}$ or
$g^{\epsilon_{i}}$ or their inverses that are present in the individual
ciphertexts gets cancelled upon multiplication of the ciphertexts, and hence
the products are typical modified Paillier ciphertexts that can be decrypted
with the public key $PK$. Note that the resulting difference of plaintexts is
still blinded by the random values $\bm{r}_{1}$ and $\bm{r}_{2}$. A detailed
procedure to recover the sign of the differences from these decrypted blinded
sums is given [YSJ+19] and we do not recall it here as it is not needed for
the present purpose.

###  4.2 Attack on lpRide

The basis of our attack on lpRide is again our attack on the modified Paillier
cryptosystem that we presented in Section 2. In particular, Corollary 1 shows
that any one with the knowledge of the public key $PK$ of lpRide will be able
to compute the modified Paillier ciphertexts. First, we show that any
registered rider or a taxi will be able to compute the secret keys of all the
other riders and drivers.

###### Lemma 4

The secret keys of riders (resp. taxis) are identical. Moreover, knowing any
one secret key will suffice to compute all the remaining secret keys of riders
and drivers.

###### Proof

The first part of the lemma follows directly from Lemma 1. For the second
part, suppose a rider $u$ has its secret key

$sk_{u}=(E^{\prime}(-1),\langle g^{-\epsilon_{i}}E^{\prime}(-1)\rangle_{1\leq
i\leq\omega},\langle g^{-\xi_{i}}E^{\prime}(-1)\rangle_{1\leq i\leq\omega}).$

From Corollary 1, it can efficiently compute the (unique value of)
$E^{\prime}(-1)$ and $E^{\prime}(-1)$. Hence, any rider (analogously, any
taxi) can easily determine all the values $g^{\epsilon_{i}}$, $g^{\xi_{i}}$.
Once these values are obtained, it can compute the (identical) secret keys of
all the taxis. Similarly, any taxi can easily compute the secret keys of all
the riders and other taxis. ∎

The above attack effectively makes the role of the trusted authority redundant
as any registered rider or taxi will be able to add others into the system
without the consent of the authority.

###### Lemma 5

Any rider or taxi will be able to infer the locations of all the riders.

###### Proof

From the proof of Lemma 4, any rider or taxi can easily determine all the
values $g^{\epsilon_{i}}$ and $g^{\xi_{i}}$. Using these computed values, it
can unmask the ciphertexts (see (11) and (12)) that correspond to the
locations of the riders, and eventually decrypt them using the public key
$PK$. Note that these location values are not blinded by the random values
$\bm{r}_{1}$ and $\bm{r}_{2}$ unlike the case of taxi location data. ∎

###### Remark 2

Note that the RSP will not be able to learn the blinding values
$g^{\epsilon_{i}}$ or $g^{\xi_{i}}$ or the exact locations of the riders since
it assumed that it cannot collaborate with any rider or driver. However, if
the RSP is allowed to disguise itself as a rider or a driver, then it will be
able to learn all the secret keys and locations of the rider.

##  5 Conclusion

We demonstrated an attack on the PP-CA-PSS from [NABB13a] where any honest-
but-curious entity (publisher/broker/subscriber) can learn the subscriptions
of any subscriber. We also exhibited a key recovery attack on the lpRide RHS
protocol [YSJ+19] by any honest-but-curious rider or driver who can
efficiently recover the secret keys of all other riders and drivers, and also
learn the location of any rider. The basis of our attack is our cryptanalysis
of the modified Paillier cryptosystem. Since the notifications in the case of
PP-CA-PSS protocol and the driver locations in the case of lpRide are blinded
by random values, we do not know how to recover these values, if at all it is
possible. It will be interesting to explore this attack scenario. Also, it
will be interesting to explore candidate constructions that are equivalent to
the functionality of the modified Paillier cryptosystem but offer better
security.

## Acknowledgements

This work was funded by the INSPIRE Faculty Award (by DST, Govt. of India) for
the author.

## References

  * [BLM+19] M. Baza, N. Lasla, M. Mahmoud, G. Srivastava, and M. Abdallah.  B-Ride: Ride sharing with privacy-preservation, trust and fair payment atop public blockchain.  IEEE Transactions on Network Science and Engineering, pages 1–1, 2019.
  * [CBDA+] Shujie Cui, Sana Belguith, Pramodya De Alwis, Muhammad Rizwan Asghar, and Giovanni Russello.  Collusion defender: Preserving subscribers’ privacy in publish and subscribe systems.  IEEE Transactions on Dependable and Secure Computing.  To appear.
  * [HNW+18] Y. He, J. Ni, X. Wang, B. Niu, F. Li, and X. Shen.  Privacy-preserving partner selection for ride-sharing services.  IEEE Transactions on Vehicular Technology, 67(7):5994–6005, 2018\.
  * [KFZC18] Youssef Khazbak, Jingyao Fan, Sencun Zhu, and Guohong Cao.  Preserving Location Privacy in Ride-Hailing Service.  In 2018 IEEE Conference on Communications and Network Security, CNS 2018, Beijing, China, May 30 - June 1, 2018, pages 1–9. IEEE, 2018.
  * [KMV21] Deepak Kumaraswamy, Shyam Murthy, and Srinivas Vivek.  Revisiting driver anonymity in oride.  CoRR, abs/2101.06419, 2021.
  * [LJFX19] Yuchuan Luo, Xiaohua Jia, Shaojing Fu, and Ming Xu.  pRide: Privacy-Preserving Ride Matching Over Road Networks for Online Ride-Hailing Service.  IEEE Trans. Information Forensics and Security, 14(7):1791–1802, 2019.
  * [Mun18] Javier Munster.  Securing publish/subscribe.  Master’s thesis, University of Toronto, 2018.  http://msrg.org/publications/pdf_files/2018/JMthesis-Securing_Publish-Subcribe.pdf.
  * [NABB13a] Mohamed Nabeel, Stefan Appel, Elisa Bertino, and Alejandro P. Buchmann.  Privacy preserving context aware publish subscribe systems.  In Javier López, Xinyi Huang, and Ravi S. Sandhu, editors, Network and System Security - 7th International Conference, NSS 2013, Madrid, Spain, June 3-4, 2013. Proceedings, volume 7873 of Lecture Notes in Computer Science, pages 465–478. Springer, 2013.
  * [NABB13b] Mohamed Nabeel, Stefan Appel, Elisa Bertino, and Alejandro P. Buchmann.  Privacy preserving context aware publish subscribe systems 2013-1.  Technical Report CCTECH-6, Cyber Center Technical Reports, Purdue University, 2013.
  * [NB14] Mohamed Nabeel and Elisa Bertino.  Attribute based group key management.  Trans. Data Priv., 7(3):309–336, 2014.
  * [Nor20] NortonLifeLock.  Uber Announces New Data Breach Affecting 57 million Riders and Drivers.  https://us.norton.com/internetsecurity-emerging-threats-uber-breach-57-million.html, 2020\.  Retrieved: April 10, 2020.
  * [NSB12] Mohamed Nabeel, Ning Shang, and Elisa Bertino.  Efficient privacy preserving content based publish subscribe systems.  In Vijay Atluri, Jaideep Vaidya, Axel Kern, and Murat Kantarcioglu, editors, 17th ACM Symposium on Access Control Models and Technologies, SACMAT ’12, Newark, NJ, USA - June 20 - 22, 2012, pages 133–144. ACM, 2012\.
  * [Pai99] Pascal Paillier.  Public-key cryptosystems based on composite degree residuosity classes.  In Jacques Stern, editor, Advances in Cryptology - EUROCRYPT ’99, International Conference on the Theory and Application of Cryptographic Techniques, Prague, Czech Republic, May 2-6, 1999, Proceeding, volume 1592 of Lecture Notes in Computer Science, pages 223–238. Springer, 1999.
  * [PDE+17] Anh Pham, Italo Dacosta, Guillaume Endignoux, Juan Ramón Troncoso-Pastoriza, Kévin Huguenin, and Jean-Pierre Hubaux.  ORide: A Privacy-Preserving yet Accountable Ride-Hailing Service.  In Engin Kirda and Thomas Ristenpart, editors, 26th USENIX Security Symposium, USENIX Security 2017, Vancouver, BC, Canada, August 16-18, 2017, pages 1235–1252. USENIX Association, 2017.
  * [PDJ+17] Anh Pham, Italo Dacosta, Bastien Jacot-Guillarmod, Kévin Huguenin, Taha Hajar, Florian Tramèr, Virgil D. Gligor, and Jean-Pierre Hubaux.  PrivateRide: A Privacy-Enhanced Ride-Hailing Service.  PoPETs, 2017(2):38–56, 2017.
  * [SKS03] Cyrus Shahabi, Mohammad R. Kolahdouzan, and Mehdi Sharifzadeh.  A road network embedding technique for k-nearest neighbor search in moving object databases.  GeoInformatica, 7(3):255–273, 2003.
  * [WZL+18] F. Wang, H. Zhu, X. Liu, R. Lu, F. Li, H. Li, and S. Zhang.  Efficient and privacy-preserving dynamic spatial query scheme for ride-hailing services.  IEEE Transactions on Vehicular Technology, 67(11):11084–11097, 2018\.
  * [YJZ+19] H. Yu, X. Jia, H. Zhang, X. Yu, and J. Shu.  PSRide: Privacy-preserving shared ride matching for online ride hailing systems.  IEEE Transactions on Dependable and Secure Computing, pages 1–1, 2019.
  * [YSJ+19] Haining Yu, Jiangang Shu, Xiaohua Jia, Hongli Zhang, and Xiangzhan Yu.  lpRide: Lightweight and privacy-preserving ride matching over road networks in online ride hailing systems.  IEEE Trans. Vehicular Technology, 68(11):10418–10428, 2019.