Secure outsourcing of sequence comparisons

被引：13
作者：
Atallah M.J. [1 ]
Li J. [1 ]
机构：
[1] CERIAS, Department of Computer Sciences, Purdue University, West Lafayette, IN 47907
来源：
International Journal of Information Security | 2005年 / 4卷 / 4期
关键词：
Edit distance; Privacy; Secure multiparty computation; Secure outsourcing; Sequence comparison;
D O I：
10.1007/s10207-005-0070-3
中图分类号：
学科分类号：
摘要：
Internet computing technologies, like grid computing, enable a weak computational device connected to such a grid to be less limited by its inadequate local computational, storage, and bandwidth resources. However, such a weak computational device (PDA, smartcard, sensor, etc.) often cannot avail itself of the abundant resources available on the network because its data are sensitive. This motivates the design of techniques for computational outsourcing in a privacy-preserving manner, i.e., without revealing to the remote agents whose computational power is being used either one's data or the outcome of the computation. This paper investigates such secure outsourcing for widely applicable sequence comparison problems and gives an efficient protocol for a customer to securely outsource sequence comparisons to two remote agents. The local computations done by the customer are linear in the size of the sequences, and the computational cost and amount of communication done by the external agents are close to the time complexity of the best known algorithm for solving the problem on a single machine. © Springer-Verlag 2005.
引用
收藏
页码：277 / 287
页数：10
相关论文
共 34 条
  • [1] Aho A.V., Hirschberg D.S., Ullman J.D., Bounds on the complexity of the longest common subsequence problem, J. ACM, 23, 1, pp. 1-12, (1976)
  • [2] Atallah M.J., Kerschbaum F., Du W., Secure and private sequence comparisons, 2nd ACM Workshop on Privacy in Electronic Society, (2003)
  • [3] Atallah M.J., Li J., Secure outsourcing of sequence comparisons, 4th Workshop on Privacy Enhancing Technologies, (2004)
  • [4] Atallah M.J., Pantazopoulos K.N., Rice J., Spafford E.H., Secure outsourcing of scientific computations, Adv. Comput., 54, 6, pp. 215-272, (2001)
  • [5] Beguin P., Quisquater J.J., Fast server-aided RSA signatures secure against active attacks, Advances in Cryptology - Crypto 1995, 963, pp. 57-69, (1995)
  • [6] Boneh D., Crescenzo G.D., Ostrovsky R., Persiano P., Public-key encryption with keyword search, Advances in Cryptology - Eurocrypt 2004, 3027, pp. 506-522, (2004)
  • [7] Cachin C., Efficient private bidding and auctions with an oblivious third party, 6th ACM Conference on Computer and Communications Security, pp. 120-127, (1999)
  • [8] Du W., Atallah M.J., Protocols for secure remote database access with approximate matching, 1st ACM Workshop on Security and Privacy in E-commerce, (2000)
  • [9] Fischlin M., A cost-effective pay-per-multiplication comparison method for millionaires, RSA Security 2001 Cryptographer's Track, 2020, pp. 457-471, (2001)
  • [10] Foster I., Kesselman C., The grid: Blueprint for a new computing infrastructure, (1999)
1234