Is it a good idea to use Lagrange/Newtonian interpolation for encryption?
I don't think this scheme would make sense, either from a performance or a crypto-design perspective.

From a crypto-design perspective, simply encrypting with a block cipher would be better.  Encrypting with a block cipher, or other suitable symmetric-key encryption scheme, takes running time that is linear in the length of the data to be encrypted (not $O(n^2)$).  You can encrypt data faster than you can send it out over the network.  So, there is no need for such a fancy construction.

From a database performance perspective, I also suspect this won't make sense.  You are not reducing the total amount of I/O; instead of storing data in the database, you are sending it over the network (at least twice, and probably many times).  This seems like a horrible tradeoff.