Database outsourcing is an idea to eliminate the burden of database management from organizations. Since data is a critical asset of organizations, preserving its privacy from outside adversary and untrusted server should be warranted. In this paper, we present a distributed scheme based on storing shares of data on different servers and separating indexes from data on a distinct server. Shamir's secret sharing scheme is used for distributing data to data share servers. A B+-tree index on the order preserved encrypted values for each searchable attribute is stored in the index server. To process a query, the client receives responses including record numbers from the index server and asks these records from data share servers. The final result is computed by the client using data shares. While the proposed approach is secure against different database attacks, it supports exact match, range, aggregation, and pattern matching queries efficiently. Simulation results show the prominence of our approach in comparison with the bucketing scheme as it imposes lower computation and communication costs on the client.
 H. Hacigümüs, B. Iyer, C. Li, and S. Mehrotra, "Executing SQL over encrypted data in the database-service-provider model," Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 216-227, 2002.
 D. Agrawal, A. Abbadi, F. Emekci and A. Metwally, "Database management as a service: challenges and opportunities," Proceedings of the 25th IEEE International Conference on Data Engineering (ICDE), pp. 1709-1716, 2009.
 S. Chung, Anti-Tamper Databases: Querying Encrypted Databases, Ph.D. Thesis, Case Western Reserve University, Cleveland, Ohio, USA, 2006.
 B. Hore, S. Mehrotra and G. Tsudik, "A privacy preserving index for range queries," Proceedings of the 13th International Conference on Very Large Data Bases (VLDB), pp. 720-731, 2004.
 E. Mykletun and G. Tsudik, "Aggregation Queries in the Database-As-a-Service Model," Data and Applications Security XX, DBSEC'06, LNCS, vol. 4127, pp. 89-103, 2006.
 Y. Tang and J. Yun, "A Method for Reducing False Hits in Querying Encrypted Databases," Proceedings of the 8th IEEE International Conference on E-Commerce Technology and the 3rd IEEE International Conference on Enterprise Computing, E-Commerce, and E-Services (CECEEE), pp. 164-171, 2006.
 H. Wang, Secure Query Answering and Privacy Preserving Data Publishing, Ph.D. Thesis, The University of British Columbia, Vancouver, British Columbia, Canada, 2007.
 E. Damiani, S. De Capitani di Vimercati, S. Jajodia, S. Paraboschi, and P. Samarati, "Balancing confidentiality and efficiency in untrusted relational DBMSs," Proceedings of the 10th ACM Conference on Computer and Communications Security (CCS), pp. 93-102, 2003.
 A. Shamir, "How to share a secret," Communications of the ACM, vol. 22, no. 11, pp. 612-613, 1979.
 Y. Tang and L. Zhang, "Adaptive Bucket Formation in Encrypted Databases," Proceedings of the IEEE International Conference on E-Technology, E-Commerce and E-Service (EEE), pp. 116-119, 2005.
 Y. Tang, J. Yun and Q. Zhou, "A Multi agent Based Method for Reconstructing Buckets in Encrypted Databases," Proceedings of the IEEE/WIC/ACM International Conference on Intelligent Agent Technology (IAT), pp. 546-570, 2006.
 N. Ahituv, Y. Lapid, and S. Neumann, "Processing encrypted data," Communications of the ACM, vol. 30, no. 9, pp. 777-780, 1987.
 E. Brickell and Y. Yacobi, "On privacy homomorphisms," Advances in Cryptology, Eurocrypt'87, LNCS, vol. 304, pp. 117-125, 1988.
 J. Domingo-Ferrer, "A provably secure additive and multiplicative privacy homomorphism," Proceedings of the 5th International Conference on Information Security (ISC), pp. 471-483, 2002.
 J. Domingo-Ferrer, "Privacy homomorphisms for statistical confidentiality," Quaderns d'Estadística i Investigació Operativa (Qüestiió), vol. 20, no. 3, pp. 505-521, 1996.
 R. L. Rivest, L. M. Adleman, and M. Dertouzos, "On Data Banks and Privacy Homomorphisms," In Foundations of Secure Computation, Academic Press, pp. 169-179, 1978.
 H. Hacigümüs, B. Iyer, and S. Mehrotra, "Efficient Execution of Aggregation Queries over Encrypted Relational Databases," Proceedings of the 9th International Conference on Database Systems for Advanced Applications (DASFAA), pp. 125-136, 2004.
 A. Menezes, P. van Oorschot, and S. Vanstone, Handbook of Applied Cryptography, CRC Press, 1996.
 R. Agrawal, J. Kieman, R. Srikant, and Y. Xu, "Order-preserving encryption for numeric data," Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 563-574, 2004.
 F. Mansoori, A Method for Executing Queries on Encrypted Databases without Firstly Decrypting Them, M.Sc. Thesis, Sharif University of Technology, Tehran, Tehran, Iran, 2008.
 G. Aggarwal, M. Bawa, P. Ganesan, H. Garcia-Molina, K. Kenthapadi, R. Motwani, U. Srivastava, D. Thomas, and Y. Xu, "Two can keep a secret: A distributed architecture for secure database services," Proceedings of the 2nd Biennial Conference on Innovative Data Systems Research, pp. 186-192, 2005.
 V. Ciriani, S. De Capitani di Vimercati, S. Foresti, S. Jajodia, S. Paraboschi, and P. Samarati, "Fragmentation and encryption to enforce privacy in data storage," Proceedings of the 12th European Symposium on Research in Computer Security, pp. 171-186, 2007.
 V. Ciriani, S. De Capitani di Vimercati, S. Foresti, S. Jajodia, S. Paraboschi, and P. Samarati, "Fragmentation design for efficient query execution over sensitive distributed databases," Proceedings of the 29th IEEE International Conference on Distributed Computing Systems, pp. 32-39, 2009.
 P. Samarati, V. Ciriani, and S. Foresti, "Keep a few: outsourcing data while maintaining confidentiality", Proceedings of the 14th European Conference on Research in Computer Security, pp. 440-455, 2009.
 R. Brinkman, J. M. Doumen, and W. Jonker, "Using secret sharing for searching in encrypted data," Secure Data Management, VLDB'04, LNCS, vol. 3178, pp. 18-27, 2004.
 G. R. Blakley, "Safeguarding cryptographic keys," Proceedings of the AFIPS National Computer Conference, pp. 313-317, 1979.
 S. King, Some Results in Linear Secret Sharing, Ph.D. Thesis, The University of Wisconsin-Milwaukee, Milwaukee, Wisconsin, USA, 2000.
 O. Goldreich, Secure Multi-Party Computation, Working Draft, version 1.3, 2001.