First, you should carry out a threat analysis and determine the attack scenarios that the encryption is supposed to protect you against. Without such an analysis, all you're doing is sprinkling magic crypto dust over your database and hoping that it will somehow protect you from any and all possible threats. (Spoiler: It probably won't.)
For example, some more or less plausible threats might include:
- a remote attacker gaining access to the database via SQL injection;
- a remote attacker gaining access to an entire server, including all data and keys stored on it, via a remote code execution (and/or privilege escalation) vulnerability;
- a remote attacker guessing the password to a privileged account;
- an employee with physical access to the servers carelessly disposing of a disk that used to contain sensitive data;
- a privileged employee carelessly copying sensitive data to an insecure or publicly accessible location;
- a privileged employee maliciously accessing or modifying sensitive data; and/or
- a privileged employee's workstation being infected with malware.
Encryption can protect against some of these threats, but not all of them, and the extent to which it can protect against some of those threats depends on the degree of compartmentalization (e.g. separating publicly accessible services onto dedicated servers, implementing strict firewall rules, requiring secure multi-factor authentication for all accounts, storing active encryption keys in a hardware security module, splitting inactive master keys into multiple shares and storing them in separate locations, etc.) that you're willing to implement and endure.
Of course, it's also possible that your sole proximate reason for encrypting your data is to pass a certification that requires it. In that case, you may wish to review the certification standards and determine what they require of your encryption and what threats they expect it to counter.
Depending on your specific requirements and threat model, it's possible that your need for encryption of data at rest might be sufficiently served simply by activating built-in encryption features of your database software, or even just by storing the database on an encrypted disk. If so, that's certainly the simplest option, even though it protects only against a limited set of attacks.
Database front-end such as CryptDB may also be useful, although again, you should carefully review their ability to protect you against the threats you've determined to be relevant while still providing the access to the data that you need.
If you must implement your own database column encryption, and if symmetric-key encryption is sufficient for your needs, I would strongly recommend using AES-SIV (or possibly AES-GCM-SIV). If you don't need to do equality comparisons on the encrypted fields, use SIV with a unique random nonce for each field (and consider including the table and column names and the row's primary key as associated data). If you do need the ability to compare encrypted fields for equality without decrypting them, use SIV without a nonce (but preferably still with the table and column names as associated data).
(If you find yourself wanting to do any kind of searching or comparisons on encrypted data besides simple equality comparison, I would strongly suggest reviewing your design and trying to find an alternative solution. While there do exist various "order-preserving" and/or "searchable" encryption schemes that claim to provide this functionality, they do not — and fundamentally cannot — meet the level of security normally expected of a modern encryption scheme, as the ability to perform such comparisons unavoidably leaks information about the encrypted data. Even nonceless SIV should be used with caution, since it leaks the equality of encrypted values.)
In some cases, e.g. if you want your server to be able to add new encrypted values to the database but not to be able to decrypt existing data once it has been added, you may want to use a public-key encryption scheme. In particular, you will probably want a hybrid cryptosystem such as ECIES, where the public-key part of the system is used to generate and encrypt a random symmetric cipher key, and this random symmetric key is then used to encrypt the data itself. The main disadvantages of such systems compared to AES-SIV are their extra complexity and their higher overhead costs (both in terms of processing time and storage requirements). Their main advantage, of course, is that the confidentiality of the data is not compromised even if an attacker gains access to the public encryption key.
