One embodiment of the present invention provides a system that decrypts an encrypted column in a row. During operation, the system receives the encrypted column in the row. The system then determines a security domain associated with the encrypted column in the row, wherein the security domain represents a set of columns in rows encrypted using the same key. Next, the system determines a key associated with the security domain. The system then decrypts the encrypted column in the row using the key. Note that using a security domain to represent a set of columns in rows enables the database to grant access to data within the database at arbitrary levels of granularity.