Asymmetric Scalar Product Preserving Encryption (ASPE) and Known Plaintext Attack (KPA)

In this blog, we shed light on the need for Asymmetric Scalar Product Preserving Encryption (ASPE), a scheme that enables retrieval of top k nearest points for a given query q. We begin with the motivation, then present the ASPE scheme, and finally demonstrate known-plaintext attack (KPA) on it.

Motivation

In our daily routine, we frequently interact with various online service providers such as hotel booking platforms, cab services, food delivery, and many more. But have you ever wondered how these services keep your data secure?

Let’s take an example of booking an online cab (as shown in Figure 1). Suppose you open a cab-booking application and search for nearest available ride. Behind the scenes, the application stores locations of all cabs in an encrypted form so that they remain hidden from any potential adversary. When you enter your location, the app first encrypts it and then processes it against the encrypted locations of all cabs. After performing the computation securely, application returns the result. Finally, you decrypt the output and get to know the nearest cab you can book.

Figure 1: Online Cab Booking Platform

Asymmetric Scalar Product Preserving Encryption (ASPE)

In 2009, Wong et al. [1] first proposed the ASPE scheme for secure retrieval of k-nearest neighbors over an encrypted database.
This scheme preserves scalar product ordering between two encrypted data points when performing a search over an ASPE-encrypted database.
The scheme consists of three main steps:

1. Key Generation: Select an invertible matrix M ∈ R(d+1)×(d+1) as secret key. Here, d is a given parameter, and R denotes real domain. 

2. Encryption: This step is divided into phases.
  •  Database Encryption: Let n is a database point. Construct a (d+1)-dimensional vector as follows.                                                     n' = (nT, -0.5 ||n||2)T                                                                                     (where ||.||2 is L2-norm (for more about norms we refers the readers to [2], and (.)T is transpose). Encrypt n as follows.                                                                                                                                                             Cn= MTn' = MT(nT, -0.5 ||n||2)T
  • Query Encryption: Let q is a query point. Construct a (d+1)-dimensional point as follows.                                                                   q' = r(qT, 1)T                                                                                                  (where r>0 is a random number). Encrypt q as follows.                                                                                                         Cq= M-1q' = rM-1(qT,1)T 
Note that Cn and Cq satisfies the following property. 
                                     CnTCq = (MTn')T(M-1q') = n'Tq' = r(nTq, -0.5 ||n||2)T

Here, we remark that n1 is nearest to q than n2 iff Cn1TCq  > Cn2TCq [Indicating Euclidean distance].

3. Decryption: The original point n is recovered as follows. 
                                     n = H(MT)-1 n'
(where H is a (d)x(d+1) matrix as follows: H = (I, 0) (where I is d x d identity matrix)).


Known Plaintext Attack (KPA)

A tour on KPA: An adversary can recover the secret key from pairs of plaintexts and their corresponding ciphertexts.

KPA on ASPE: In 2013, Yao et al. [3] first demonstrated the KPA attack on the ASPE scheme. The KPA attack proceeds as follows:

Assume that an adversary possesses  linearly independent vectors of  along with their corresponding ciphertexts Cn. The adversary can then construct following system of linear equations.

Cn1= MTn'1, Cn2= MTn'2, Cn3= MTn'3, ---, Cn(d+1)= MTn'(d+1)

Let A = [Cn1, Cn2, Cn3,......, Cn(d+1)]
B = [n'1, n'2, n'3,......, n'(d+1)]

An adversary may learn secret matrix M as follows. 
M = (AB-1)T

******************
Important Note:
ASPE was the first privacy-preserving scheme designed for secure retrieval of k-nearest neighbors. Over the past few years, several enhanced and modified versions of ASPE have emerged, each claiming to provide secure kNN retrieval. This continues to be an active and evolving area of research.
******************

References

We thanks to...

[1] Wai Kit Wong, David Wai-lok Cheung, Ben Kao, and Nikos Mamoulis. Secure kNN Computation on Encrypted Databases. In Proceedings of the 2009 ACM SIGMOD International Conference on Management of data, pages 139–152, 2009.

[2] https://www.youtube.com/watch?v=NcPUI7aPFhA

[3] Bin Yao, Feifei Li, and Xiaokui Xiao. Secure Nearest Neighbor Revisited. In 2013 IEEE 29th international conference on data engineering (ICDE), pages 733–744. IEEE, 2013.

Comments

Post a Comment

Popular posts from this blog

Homomorphic Encryption: A Basic Idea

Image
Homomorphic encryption has the same aim as other encryption-decryption mechanisms: maintaining confidentiality, security, privacy, etc.  In this blog, we will see homomorphic encryption and its type.  Homomorphic Encryption (HE):  It is an encryption that computes operations over encrypted data without decrypting it (or without the need for a secret key).  Mathematically speaking in a client-server architecture: client has message 'm' and function f. The task of client is to compute f(m). Due to computational expensiveness (maybe one of the reason) client sends encryption of message (say Enc(m)) and 'f' to the server. Server will compute function over encrypted message, that is, f(Enc(m)), and return the result to the client, that is, Enc(f(m)). Client will decrypt it Dec(Enc(f(m)), that is, f(m). Hence, client achieves f(m).  Let's understand HE with our daily life (Tea making process): Figure 1. Here m is message, Enc is encryption, f is function, and Eval in...
Read more

Elliptic Curve Cryptography (ECC) and ECDSA

Image
Elliptic Curve Cryptography (ECC) Elliptic curve (EC) was first introduced by Neal Kobiltz and Victor Miller in 1985. Elliptic curve is a non-singular curve that is operated on a finite field Zq (where q is the order of elliptic curve). EC consists of set of points that satisfies the following equation as follows.                                                                   Y 2 = X 3 + aX + b Where {X,Y,a,b} ∈ Zq, and 4a 3 + 27b 2 ≠ 0. Next, we discuss the encryption and decryption mechanism between two parties (Say α and γ ). Remark 1: Elements selected from party α is represented by capital letters whereas elements selected from party γ is represented by small letters. i) Key Generation: 1. Secret key: Each party α and γ selects secret keys S ∈ Zq and s ∈ Zq. 2. Public key: P ...
Read more

Fast Base Conversion and Its Application

Image
Fast Base Conversion (FBC) is a technique used to convert a number from one modulus space to another. For example, if we have 14 m o d     77 14 \mod 77  and want to convert it to x m o d     390 x \mod 390 , FBC is widely used. Mathematically, it can be represented as follows: Here, the above equation represents an integer x x  in modulus q q , and FBC converts this integer into the modulus space t t . The modulus q q  is the product of small coprime moduli (i.e., q = q 1 q 2 … q k q = q_1 q_2 \dots q_k ​ ), and x x  is an integer such that x ∈ [ 0 , q ) x \in [0, q) . We also note that q q  and t t  are coprime numbers. Here, we remark that it is not necessary for the above equation to produce the exact result for x x . Instead of x m o d     t x \mod t , it will provide x ′ m o d     t x' \mod t . Thus, the output of the above equation is as follows: FBC ( x , q , t )  =  x  +  A q  mod  t , where A ∈ [ 0 , k − 1 ] A \in [0,...
Read more