All Over The Map

Computing grids offer computing as a service allowing users to adopt a pay as you go billing model. A grid can be viewed as a collection of inexpensive managed nodes with some billing and job management software. As computer grids become commercially available, two fundamental challenges exist; trust asymmetry [2] and movement of data to and from the grid. Current grid solutions have many fundamental security problems, such as requiring sharing of keys and, trusting of the infrastructure deployed by the grid service provider. Traditional approaches attempt to secure an operating system so that operations on plain text can be carried out without concern. Many users will never trust a service provider enough and use delegation of computing. This clear text approach, assumes the user of the service trusts the third party. Several approaches are examined; global encrypted operations, one time pads, Quantum Computation[3], [4] , and Quantum Teleportation [6]. There are commercial products which implement Secure Processing. Two representative products from IBM[12] and Intel both require that the third party, the grid service provider have a key which allows the trusted party to decrypt and encrypt the data. A Homomorphic Computer would not have this security weakness.

“A system that does not require the user of the service to reveal the key to the provider of the service is inherently more secure than one where the key must be provided to the supplier of the service.”

There are several approaches to computing without sharing of keys; Hardware Pads, Homomorphic Computer and Quantum Computing. 1) P. Dinda has proposed an an approach which uses hardware and one time pads to for solving the trust asymmetry problem. One approach uses algorithms and requires new central processing units which have specialized adders and multipliers to operate on encrypted representations of numbers. 2) P. Dinda suggests an approach using one time pads. This approach computes on clear text quantities and XORs the input and output of the CPU with a onetime pad. A Homomorphic computer performs fundamental operations on encrypted numbers. Early work by Rivest et al, demonstrated that encrypted addition was possible[10]. More recent research by Ahituv indicates that consistent operations may not be possible for addition subtraction and division[1]. Pierre-Alain Fouque, has researched and implemented a solution for Excel based on Gauss fields[7] which does not use Privacy Homomorphisms. There are two new aspects to this type of computer. The registers for holding numbers are orders of magnitude larger than current computers and the ALUs are much larger in bit size. 3) Current research directs us towards new developments in Quantum Computing and Quantum Teleportation which could potentially solve the trust asymmetry problem. Quantum Cryptography and Quantum Teleportation do not require the sharing of keys and and have the additional property that observation of the computation is not possible and transportation of the data via teleportation does not allow interlopers to see valid data.

References
[1] N. Ahituv, Y Lapid and S Neumann (1987) “Processing Encrypted Data”, in Communications of the ACM vol 30, pp. 777-780.
[2] Claus Boyens, Oliver Günther: Trust Is not Enough: Privacy and Security in ASP and Web Service Environments. ADBIS 2002: 8-22
[3] G. Brassard, S Braunstein, R Cleve, Teleportation as a quantum computation, Physica D 120 43-47 (1998)
[4] Chuang, I. L., Laflamme, R., Yamamoto, Y., “Decoherence and a Simple Quantum Computer,” (1995).
[5] P. Dinda, Addressing the Trust Asymmetry Problem In Grid Computing With Encrypted Computation, Proceedings of the Seventh Workshop on Langauges, Compilers and Run-time Support for Scalable Systems (LCR 2004).
[6] D. Deutsch, A. Ekert, “Quantum Computation,” Physics World, March (1998).
[7] Pierre-Alain Fouque, Jacques Stern, Jan-Geert Wackers: CryptoComputing with Rationals. Financial Cryptography 2002: 136-146
[8] R. Johnson, D. Molnar, D. Song, and D. Wagner “Homomorphic Signature Schemes.” RSA2002 Conference, Cryptographer’s Track. LNCS 2271.
[9] Lee, H., W. Harrison, and J. Alves-Foss, The use of Encrypted Functions for Mobile Agent Security, 37th Hawaii International Conference on System Sciences (HICSS-37), January 2004, 10 pages, CDROM
[10] Anderson C. A. Nascimento, Akira Otsuka, Hideki Imai, Jörn Müller-Quade: Unconditionally Secure Homomorphic Pre-distributed Commitments. AAECC 2003: 87-97
[11] R. Rivest, L. Adleman, and M Dertouzous. On data banks and privacy homomorphisims. In Foundations of secure Computation, pages 169-178. Academic Press, 1978.
[12] Smith, S.W., Weingart, S.H.., Building a High performance, Programmable Secure Coprocessor. In Computer Networks, Special Issue on Computer network security, Nr 31(1999), S. 831-860