Most existing privacy-preserving spatial keyword query schemes rely on exact keyword matching, which cannot effectively capture the keyword relevance between user queries and spatial objects. Moreover, they often neglect the individual preferences of users for different keywords. To overcome these limitations, we propose SSKQ-UP, a novel and efficient privacy-preserving spatial keyword query scheme that supports personalized ranking. The index structure of SSKQ-UP is an R-tree based on Geohash code, called HR-tree. The internal nodes of HR-tree store Geohash codes to achieve rapid spatial pruning. The leaf nodes store the Geohash code of the spatial objects and the Term Frequency-Inverse Document Frequency (TF-IDF) vectors, facilitating filtering based on the spatial range and keywords. Users can submit queries with weight vectors to reflect their keyword preferences. The cloud computes cosine similarity between the query weight vector and the TF-IDF vectors of candidate objects to identify the top-k most relevant results. To ensure privacy, both index and query vectors are encrypted using an Enhanced Asymmetric Scalar Product Encryption (EASPE) algorithm. Security analysis confirms that the proposed scheme is IND-CPA secure. Extensive experiments validate the practicality and efficiency of our scheme, demonstrating superior performance compared to existing methods.

Cloud-assisted computation empowers resource-constrained clients to efficiently tackle computationally intensive tasks by outsourcing them to resource-rich cloud servers. In the current era of Big Data, the widespread need to solve large-scale modular linear systems of equations ($\mathcal {LMLSE}$) of the form$\mathbf {A}\mathbf {x}\equiv \mathbf {b}\;{\rm mod}\;{q}$poses a significant challenge, particularly for lightweight devices. This paper delves into the secure outsourcing of$\mathcal {LMLSE}$under a malicious single-server model and, to the best of our knowledge, introduces the inaugural protocol tailored to this specific context. The cornerstone of our protocol lies in the innovation of a novel matrix encryption method based on sparse unimodular matrix transformations. This novel technique bestows our protocol with several key advantages. First and foremost, it ensures robust privacy for all computation inputs, encompassing$\mathbf {A},\mathbf {b}, q$, and the output$\mathbf {x}$, as validated by thorough theoretical analysis. Second, the protocol delivers optimal verifiability, enabling clients to detect cloud server misbehavior with an unparalleled probability of 1. Furthermore, it boasts high efficiency, requiring only a single interaction between the client and the cloud server, significantly reducing local-client time costs. For an$m$-by-$n$matrix$\mathbf {A}$, a given parameter$\lambda =\omega (\log q)$, and$\rho =2.371552$, the time complexity is diminished from$O(\max \lbrace m n^{\rho -1}, m^{\rho -2} n^{2}\rbrace \cdot (\log q)^{2})$to$O((mn+m^{2})\lambda \log q+mn(\log q)^{2})$. The comprehensive results of our experimental performance evaluations substantiate the protocol's practical efficiency and effectiveness.

Solving quadratic congruence equations is an expensive operation widely employed in cryptographic constructions for secure Internet of Things applications. Recently, two outsourcing algorithms were proposed by Zhanget al.to solve quadratic congruence equations by employing Cippolla’s algorithm. It was claimed that all the inputs and outputs can be obscured in these two algorithms. However, we present two passive attacks in this article to show that all the inputs and outputs can be recovered efficiently by just a curious server, which implies the two outsourcing algorithms are insecure. To fix them, we further propose an improved outsourcing algorithm to solve quadratic congruence equations, which is more efficient and the privacy of actual inputs and outputs can be protected very well.

With the vigorous development and gradual maturity of machine learning (ML) technologies, the AI-assisted disease diagnosis and prediction ($\mathcal {AADP}$) system has been extensively studied and can be expected to be intensively deployed in the real world. However, as the scale of ML data increases exponentially, the training and application of ML models impose a great burden on resource-constrained terminals. Designing cloud/edge server-aided$\mathcal {AADP}$protocols is becoming a popular topic. Whereas, the sensitivity of ML data, the intellectual property of ML models, and the uncontrollability of servers bring great security challenges to this promising computing paradigm. In this article, we initialize a new four-party framework for the$\mathcal {AADP}$system which consists of users, third-party test institution, AI doctor, and cloud/edge server. With this framework, we design two high-efficiency and secure outsourcing$\mathcal {AADP}$protocols under two different security models. By comprehensively employing secure hash functions, Householder transformations, and random permutations, we realize the following design objectives: 1) user’s actual identification is invisible to the other parties; 2) user’s feature vector is blinded to the AI doctor and the server; 3) the ML model of the AI doctor is confidential to the server; 4) AI doctor can obtain decent computational savings compared with achieving the diagnosis task by itself; and 5) AI doctor can verify the server’s misbehaviors with a nonnegligible probability under the security model with a fully malicious server. We argue these claims with rigid theoretical proofs and corroborate them with extensive experimental analysis.

Given a binary sequence with length$n$, determining its minimal rational fraction representation (MRFR) has important applications in the design and cryptanalysis of stream ciphers. There are many studies of this problem since Klapper and Goresky first introduced an adaptive rational approximation algorithm with a time complexity of$O(n^{2}\log n\log \log n)$. In this paper, we revisit this problem by considering both adaptive and non-adaptive efficient algorithms. Compared with the state-of-art methods, we make several contributions to the problem of finding MRFR. Firstly, we find a general and precise recursive relationship between the minimal bases for two adjacent lattices generated by successive truncation sequences. This enables us to improve the currently fastest adaptive algorithm proposed by Liet al.. Secondly, by optimizing a time-consuming step of the well-known Lagrange reduction algorithm for 2-dimensional lattices, we obtain a non-adaptive, and yet practically faster MRFR-solving algorithm namedglobalEuclidean algorithm. Thirdly, we identify theoretical flaws on some non-adaptive methods in the literature by counter-examples and correct the problems by designing modified Euclidean algorithm namedpartialEuclidean algorithm. Meanwhile, we further reduce the time complexity of existing algorithm from$O(n^{2})$to$O(n\log ^{2}n\log \log n)$by invoking the half-gcd algorithm. We also conduct a comprehensive experimental comparative analysis on the above algorithms to validate our theoretical analysis.

In cryptography and algorithmic number theory, modular inversion is viewed as one of the most common and time-consuming operations. It is hard to be directly accomplished on resource-constrained clients (e.g., mobile devices and IC cards) since modular inversion involves a great amount of operations on large numbers in practice. To address the above problem, this paper proposes a novel unimodular matrix transformation technique to realize secure outsourcing of modular inversion. This technique makes our algorithm achieve several amazing properties. First, to the best of our knowledge, it is the first secure outsourcing computation algorithm that supports arbitrary and variable modulus, which eliminates the restriction in previous work that the protected modulus has to be a fixed composite number. Second, our algorithm is based on the single untrusted program model, which avoids the non-collusion assumption between multiple servers. Third, for each given instance of modular inversion, it only needs one round interaction between the client and the cloud server, and enables the client to verify the correctness of the results returned from the cloud server with the (optimal) probability 1. Furthermore, we propose an extended secure outsourcing algorithm that can solve modular inversion in multi-variable case. Theoretical analysis and experimental results show that our proposed algorithms achieve remarkable local-client’s computational savings. At last, as two important and helpful applications of our algorithms, the outsourced implementations of the key generation of RSA algorithm and the Chinese Reminder Theorem are given.

Rivest-Shamir-Adleman (RSA) is one of the widely deployed public-key algorithms. Yet, its decryption facet is very time consuming for resource-constrained Internet-of-Thing (IoT) devices, as it is based on the modular exponentiation of a large number. Although several variants of RSA have been designed to accelerate decryption, the outcomes have been far from satisfactory. Therefore, it is of imminent importance to investigate how to securely outsource RSA decryption to computational powerful parties as an alternative solution. In this article, we introduce the first efficient and secure outsourcing scheme for RSA decryption in IoT. Though RSA decryption is achieved via modular exponentiation, existing secure outsourcing schemes for modular exponentiation either assume the modulus to be prime and are not applicable to RSA or incur massive computation costs and are heavy laden in practice. To address these issues, we have designed our scheme based on the Chinese remainder theorem (CRT). In our scheme, the private keys (including the exponent and the modulus) and the plaintext are concealed concurrently, and the proposed scheme is highly efficient for both client and cloud. In addition, our scheme enables the client to detect any misbehavior of the cloud server with a probability of 99.17%. To validate the effectiveness of our proposed scheme, we provide rigorous proofs of security and verifiability, as well as efficiency analysis. The effectiveness and efficiency of our scheme are further confirmed based on experimental results.

Solving quadratic congruences is a widely applied operation in cryptographic protocols to ensure the data secrecy in the Internet of Things (IoT). Yet it requires unaffordable computation resource for resource-constrained IoT devices when bulk of this type of operations need to be performed. How to efficiently and effectively solve quadratic congruences on IoT devices becomes a challenging issue. To address this problem, in this article, we propose two practical and secure outsourcing algorithms for solving quadratic congruences. Our proposed algorithms enable the IoT devices to outsource the heavy computation of solving quadratic congruences to a single cloud server, and therefore, achieve high efficiency for IoT devices. Meanwhile, we obscure the input and the output so that the outsourcing process does not leak the privacy of the computation, and the IoT devices in our algorithms can detect any misbehavior of the cloud server with a probability of 1. In addition, we take the Rabin encryption algorithm as an example to show how our proposed algorithms can be applied to IoT applications. The theoretical analysis and experimental results support the fact that our proposed algorithms are secure and efficient.

In this paper, we present an improvement of the Nguyen-Vidick heuristic sieve algorithm for shortest vector problem in general lattices, which time complexity is 20.3836n polynomial computations, and space complexity is 20.2557n. In the new algorithm, we introduce a new sieve technique with two-level instead of the previous one-level sieve, and complete the complexity estimation by calculating the irregular spherical cap covering.