Cryptography Reference
In-Depth Information
their own accord and on their own terms.
20.2.1 One-way Functions
One of the simplest ways to build a translucent database is to obscure
some of the columns of the database by passing them through a one-
way function, a mathematical convenience that is easy to compute
but practically impossible to invert. (Use
)
to denote the one way
functions.) So-called cryptographically secure hash functions like
SHA256 are some of the most commonly used one-way functions to-
day, but almost any good cryptographic algorithm can be converted
into acting the same way by disposing of the keys.
A translucent version of a store's database holding the customer's
records might look like this:
h
(
x
h
(
name
)
itemnumber
size
color
ab
9938
c...
4000
XL
green
ab
9938
c...
4000
XL
blue
2
c
42
d
45
...
4002
L
rose
99
ab
993
...
4003
M
yellow
99
ab
993
...
4000
M
green
This table does not store the name of the customer directly. It
stores
)
, which is the result of passing the name through a
one-way function like SHA256. The other three columns are left un-
scrambled, a feature that lets the marketing and inventory depart-
ments study past sales.
Storing the customer's name in this way lets the store track a cus-
tomer's purchases while giving the customer some control over how
the information is used. The store can ask its database to answer a
question like “Which colors for item 4000 are popular?” but it can't
poke around and ask, “Who is buying item 4000?” If the customer re-
turns to the store, though, the customer can calculate
h
(
name
)
and
look up the past item numbers and sizes. Once the customer pro-
vides
h
(
name
)
, the store can provide all of the intrusive services that
itmightwanttoprovide.
There are limitations to this approach. The central database ad-
ministrator can't invert the values of
h
(
name
)
and so the administrator is
often unable to fix entries in the table. Attackers who are targeting
particular individuals and know their names can defeat simple sys-
tems like this by computing
h
(
x
)
on their own— a problem that can
be fixed by asking the users to add a password to the mix and store
h
h
(
x
(
name, password
)
instead.
