Cryptographic protection of databases and software
Joan Feigenbaum, Mark Yoffe Liberman, Rebecca N. Wright · DIMACS series in discrete mathematics and theoretical computer science · 1991
We describe experimental work on cryptographic protection of databases and software. The database in our experiment is a natural language dictionary of over 4000 Spanish verbs. Our tentative conclusion is that the overhead cost of computing with encrypted data is fairly small. 1 Introduction It is often desirable to allow a user to access a database D via some program P while preventing her from obtaining a copy of the entire contents of the database. For example, let D be a table of pairs (l i ; r i ), 1 i n, where each l i is the name of a person and P (l i ; D) = r i is the phone number of l i . A typical user of D should be able to obtain the number r i if she knows l i but should not be able to obtain the names and numbers of the people she does not know. More formally, given a database D and program P that accesses it, we wish to construct an encrypted database D 0 and a corresponding program P 0 with the following properties. ffl For any query q, P (q; D) = P 0 (q; D ...