Re^2: Deterministic asymmetric encryption [Crypt::RSA]

Thank your for your feedback.

Crypt::CBC with just about any back end (incl, say, Crypt::Rijndael)

Wouldn't that be Symmetric-key encryption, and not asymmetric encryption as the title suggests?

Why do you want this? It seriously weakens the encryption. Maybe what you really need is a hashing algorithm.

I realize it weakens the encryption. The question is how much?

My motivation is similar to the one described here:

One primary motivation for the use of deterministic encryption is the efficient searching of encrypted data. Suppose a client wants to outsource a database to a possibly untrusted database service provider. If each entry is encrypted using a public-key cryptosystem, anyone can add to the database, and only the distinguished "receiver" who has the secret key can decrypt the database entries.

I want to let anyone (any authorized local user) add to a database. E.g. add(encrypt("A")).
I want the same users to see if a specific entry has been previously added. E.g. exists(encrypt("A")). This is where the deterministic requirement comes from.
I will only let users in possession of a secret key decrypt the data.
The secret key must not be stored on the server offering the services above.

If I understand it correctly, the 4 above requirements can only be accomplished using deterministic asymmetric encryption.

--
No matter how great and destructive your problems may seem now, remember, you've probably only seen the tip of them. [1]

Comment on Re^2: Deterministic asymmetric encryption [Crypt::RSA] Select or Download Code

Replies are listed 'Best First'.
Re^3: Deterministic asymmetric encryption [Crypt::RSA] by ikegami (Patriarch) on Dec 15, 2010 at 21:00 UTC
Wouldn't that be Symmetric-key encryption, and not asymmetric encryption as the title suggests? Oops, yes. I realize it weakens the encryption. The question is how much? First, it introduces information leakage. If two records have the same plain text, the creator of one of those records knows the content of the other record. If the plain text is a password, for example, this could allow someone to know someone else's password. The other concern is that by having more blocks encrypted with the same key, one might be able to attack certain algorithms and maybe even recover the key. The potential impact of using the same key could be lessened if chaining is used (i.e. if the key used to encrypt one block depends on the previous block). Lots of factors affect how much this matters. I want to let anyone (any authorized local user) add to a database. E.g. add(encrypt("A")). It doesn't have to be deterministic to do that. The requirement to use salt (iv) doesn't prevent anyone from adding to the database as long as the salt is included in the database as well. I want the same users to see if a specific entry has been previously added. E.g. exists(encrypt("A")). This requires deterministic encryption or hashing. Hashing algorithms have been vetted against these attacks. A particular encryption algorithms? dunno. So you need deterministic asymmetric encryption, or non-deterministic asymmetric encryption plus hashing.	[reply]
Re^3: Deterministic asymmetric encryption [Crypt::RSA] by SuicideJunkie (Vicar) on Dec 15, 2010 at 19:53 UTC
What if you have: 1) The database server in the data warehouse, with no keys. 2) A small privileged server under your control with both keys 3) Users with the public key When adding an entry, the request goes through the privileged server. It then adds the item to the database, encrypted with the public key. It also updates a table of contents, encrypted with the private key. Public key holders can read the table of contents, but cannot read the database. Private key users can read the database, and already know the table of contents. The private key does not reside on the foreign database server, only on a small stateless proxy server which you fully control. It would probably work better if you just had a really strong "any" encryption and the proxy server for doing writes. Plus the table of contents that anybody with a login can read straight from the database.	[reply]
Re^4: Deterministic asymmetric encryption [Crypt::RSA] by jethro (Monsignor) on Dec 16, 2010 at 09:53 UTC
You assume a small key and data that is uninteresting for unprivileged users. Imagine the data you want to store is just scripts and others should be able to find out if their script is already in there.	[reply]