What is the best way to store a lot of user-encrypted data?
As a rule of thumb: If your data is well structured, well known (in advance) and of a limited size per entry (no mega BLOBs), relational databases are really good at storing it. Even if you don't use the advanced indexing features.

Managing space, especially empty space in data files, is a very hard problem to solve. Relational databases have been dealing with this for over 20 years now - and it is worth making use of them just for that. In addition to this, relational databases get you the benefits of a long history of performance tuning. They run highly optimised native code so you don't have to struggle with poor Java implementations, bad network stacks, overuse of memcpy, garbage collection, coarse locking and all the other pathologies new products (especially the noSQL stuff) tends to have.

To store encrypted data, use the BINARY data types. MSSQL, MySQL and Postgres all support these types. You may not want to do operations directly on these types (though you CAN do binary manipulation if you want to). Also note that it is relatively easy to implement the encryption/decryption in the database itself  as all of the above support crypto libraries. You will also benefit from indexing on the key/foreign columns so you can find your data fast. A relational database is an excellent key/value store for small value types - SQL Server will easily get you over 1-10M key/value lookups/sec even on a small box - I expect MySQL and PostGres would deliver results in the same ballpark.

It is also easy to find programmers who can query a relational database efficiently. SQL has been around for a very long time and it is an extraordinarily powerful language. MSSQL will even give you automated parallel execution. Some programmers wont "get" it - but if they don't, chances are they also won't grok parallelism or lambda expressions (two crucial skills of a modern coder).

On top of all of this goodness, you also get powerful backup and monitoring tools for all of the standard relational databases.

So basically, unless you have a REALLY good reason to use NoSQL - just use relational databases.