Secure k-Nearest Neighbor(k-NN)query aims to find k nearest data of a given query from an encrypted database in a cloud server without revealing privacy to the untrusted cloud and has wide applications in many areas,s...
详细信息
Secure k-Nearest Neighbor(k-NN)query aims to find k nearest data of a given query from an encrypted database in a cloud server without revealing privacy to the untrusted cloud and has wide applications in many areas,such as privacy-preservingmachine elearning gand secure biometric *** solutions have been put forward to solve this challenging ***,the existing schemes still suffer from various limitations in terms of efficiency and *** this paper,we propose a new encrypt-then-index strategy for the secure k-NN query,which can simultaneously achieve sub-linear search complexity(efficiency)and support dynamical update over the encrypted database(flexibility).Specifically,we propose a novel algorithm to transform the encrypted database and encrypted query points in the *** indexing the transformed database using spatial data structures such as the R-tree index,our strategy enables sub-linear complexity for secure k-NN queries and allows users to dynamically update the encrypted *** the best of our knowledge,the proposed strategy is the first to simultaneously provide these two *** theoretical analysis and extensive experiments,we formally prove the security and demonstrate the efficiency of our scheme.
Cloud computing platforms have created the possibility for computationally limited users to delegate demanding tasks to strong but untrusted servers. Verifiable computing algorithms help build trust in such interactio...
详细信息
Cloud computing platforms have created the possibility for computationally limited users to delegate demanding tasks to strong but untrusted servers. Verifiable computing algorithms help build trust in such interactions by enabling the server to provide a proof of correctness of his results which the user can check very efficiently. In this article, we present a doubly-efficient interactive algorithm for verifiable polynomial evaluation. Unlike the mainstream literature on verifiable computing, the soundness of our algorithm is information-theoretic and cannot be broken by a computationally unbounded server. By relying on basic properties of error correcting codes, our algorithm enforces a dishonest server to provide false results to problems which become progressively easier to verify. After roughly log d rounds, the user can verify the response of the server against a look-up table that has been pre-computed during an initialization phase. For a polynomial of degree d, we achieve a user complexity of O(d(epsilon)), a server complexity of O(d(1+epsilon)), a round complexity of O(log d) and an initialization complexity of O(d(1+epsilon)).
We consider interior and exterior initial boundary value problems for the three-dimensional wave (d'Alembert) equation. First, we reduce a given problem to an equivalent operator equation with respect to unknown s...
详细信息
We consider interior and exterior initial boundary value problems for the three-dimensional wave (d'Alembert) equation. First, we reduce a given problem to an equivalent operator equation with respect to unknown sources defined only at the boundary of the original domain. In doing so, the Huygens' principle enables us to obtain the operator equation in a form that involves only finite and non-increasing pre-history of the solution in time. Next, we discretize the resulting boundary equation and solve it efficiently by the method of difference potentials (MDP). The overall numerical algorithm handles boundaries of general shape using regular structured grids with no deterioration of accuracy. For long simulation times it offers sub-linear complexity with respect to the grid dimension, i.e., is asymptotically cheaper than the cost of a typical explicit scheme. In addition, our algorithm allows one to share the computational cost between multiple similar problems. On multiprocessor (multi-core) platforms, it benefits from what can be considered an effective parallelization in time. (C) 2018 Elsevier Inc. All rights reserved.
We consider a continuous-time variant of the classical Economic Lot-Sizing (ELS) problem. In this variant, the setup cost is a continuous function with lower bound K-min > 0, the demand and holding costs are integr...
详细信息
We consider a continuous-time variant of the classical Economic Lot-Sizing (ELS) problem. In this variant, the setup cost is a continuous function with lower bound K-min > 0, the demand and holding costs are integrable functions of time and arbitrary replenishment policies are allowed. Starting from the assumption that certain operations involving the setup and holding cost functions can be carried out efficiently, we show that this variant admits a simple approximation scheme based on dynamic programming: if the optimal cost of an instance is OPT, we can find a solution with cost at most (1 + epsilon)OPT using no more than O (1/epsilon(2) OPT/K-min log OPT/K-min) of these operations. We argue, however, that this algorithm could be improved on instances where the setup costs are generally "very large" compared with Kmin. This leads us to introduce a notion of input-size parameter sigma that is significantly smaller than. OPT/K-min on instances of this type, and then to define an approximation scheme that executes O (1/epsilon(2) sigma(2) log(2) (OPT/K-min)) operations. Besides dynamic programming, this second approximation scheme builds on a novel algorithmic approach for Economic Lot Sizing problems. (C) 2016 Elsevier B.V. All rights reserved.
暂无评论