We have a database table of encrypted log entries, each encrypted entry containing information about the user who created the entry. The entry is encrypted with the encryption key of the particular user.
Users may login into web GUI and enter their decryption key to fetch and decrypt their log entries from the server, without exposing other entries. The problem is there is no way to identify the user prior to decryption (this is a requirement). Also, the user or an attacker having an access to the server possessing the user's decryption key must not be able to decrypt other users log entries.
Second requirement is the performance. There are hundreds of thousands of rows, so decrypting all rows by trial and error doesn't sound viable.
Is there some existing scheme solving this chicken and egg dilemma?