A computer-implemented method comprising: at a data owner: preparing unencrypted data by separating each column of the unencrypted data into dictionaries and attribute vectors, wherein a dictionary is filled with all unique values of an original column, wherein values in the original column are replaced in an attribute vector by value identifiers that correspond to original values, wherein all entries of the dictionaries are encrypted individually with a secret key; deploying the encrypted dictionaries and the attribute vectors for storage in a database administered by a cloud database provider; at a secure environment of the database provider: receiving the secret key; at an untrusted environment of the database provider: receiving an encrypted query; passing the encrypted query to a query pipeline of the database provider, wherein a query optimizer evaluates possible query plans and decides on a query plan for execution of the encrypted query, wherein the query plan is shared with a query engine which processes columns one after another according to the query plan; at the secure environment: receiving, from the query engine located outside of the secure environment, an encrypted query range corresponding to the encrypted query issued by a user; receiving from the query engine, a reference to the dictionary; decrypting the encrypted query range using the secret key; decrypting values of the dictionary according to the secret key; searching (109; 212) the dictionary to produce list of value identifiers matching the encrypted query range; and returning the list of value identifiers to the query engine, and in response to receiving the list of value identifiers: by the query engine: referencing the list of the value identifiers in order to perform a search in the attribute vector stored in the database, generating a list of record identifiers to obtain encrypted values from the dictionaries for a query result, and returning the query result to the user. at a data owner: preparing unencrypted data by separating each column of the unencrypted data into dictionaries and attribute vectors, wherein a dictionary is filled with all unique values of an original column, wherein values in the original column are replaced in an attribute vector by value identifiers that correspond to original values, wherein all entries of the dictionaries are encrypted individually with a secret key; deploying the encrypted dictionaries and the attribute vectors for storage in a database administered by a cloud database provider; preparing unencrypted data by separating each column of the unencrypted data into dictionaries and attribute vectors, wherein a dictionary is filled with all unique values of an original column, wherein values in the original column are replaced in an attribute vector by value identifiers that correspond to original values, wherein all entries of the dictionaries are encrypted individually with a secret key; deploying the encrypted dictionaries and the attribute vectors for storage in a database administered by a cloud database provider; at a secure environment of the database provider: receiving the secret key; at an untrusted environment of the database provider: receiving an encrypted query; passing the encrypted query to a query pipeline of the database provider, wherein a query optimizer evaluates possible query plans and decides on a query plan for execution of the encrypted query, wherein the query plan is shared with a query engine which processes columns one after another according to the query plan; receiving an encrypted query; passing the encrypted query to a query pipeline of the database provider, wherein a query optimizer evaluates possible query plans and decides on a query plan for execution of the encrypted query, wherein the query plan is shared with a query engine which processes columns one after another according to the query plan; at the secure environment: receiving, from the query engine located outside of the secure environment, an encrypted query range corresponding to the encrypted query issued by a user; receiving from the query engine, a reference to the dictionary; decrypting the encrypted query range using the secret key; decrypting values of the dictionary according to the secret key; searching (109; 212) the dictionary to produce list of value identifiers matching the encrypted query range; and returning the list of value identifiers to the query engine, and receiving, from the query engine located outside of the secure environment, an encrypted query range corresponding to the encrypted query issued by a user; receiving from the query engine, a reference to the dictionary; decrypting the encrypted query range using the secret key; decrypting values of the dictionary according to the secret key; searching (109; 212) the dictionary to produce list of value identifiers matching the encrypted query range; and returning the list of value identifiers to the query engine, and in response to receiving the list of value identifiers: by the query engine: referencing the list of the value identifiers in order to perform a search in the attribute vector stored in the database, generating a list of record identifiers to obtain encrypted values from the dictionaries for a query result, and returning the query result to the user. referencing the list of the value identifiers in order to perform a search in the attribute vector stored in the database, generating a list of record identifiers to obtain encrypted values from the dictionaries for a query result, and returning the query result to the user.