Is it a good idea to use Lagrange/Newtonian interpolation for encryption?

Question

I see that Lagrange interpolation is commonly used for secret sharing, but could it be used for encryption?

The goal is to reduce database I/O and compute new values on the fly. Suppose the use case involves that a client C sends to a server S a message m and a number n that C wants to be appended to m with some encoding. S returns to C the updated message m'. So, over time m becomes a list of numbers. Suppose C must not see the values of those numbers. Would it be a good idea to adopt this approach:

1. Given a working list of numbers $[e_0,e_1,e_2,\ldots,e_p]$ on S, formulate the equation $y = e_0 + e_1 \times x + e_2 \times x^2 + \ldots + e_p \times x^p$ and compute $p$ points using that equation.
2. Pick one point and store it in S's database. Encode the remaining $p-1$ points in the message $m'$ and send it to the client C.
3. When C sends the message back, S decrypts the message by decoding the message and reading the missing point from its database. S applies Lagrange/Newtoian interpolation to retrieve $e_n$.
4. repeat.

Indeed, the message could just be encrypted, but AFAIK, Lagrange/Newtonian interpolation is $O(n^2)$ (so the proposed decryption is $n^2$) and the encryption part here is only $O(n)$ given that it involves only simple substitutions. In comparison, AFAIK, both encryption and decryption with RSA are $O(n^2)$.

The database will still need to be read each time a message is received (to retrieve the missing number), but I think it's relatively lightweight given that each row only needs to contain two attributes (id and missing_point). In contrast, if every number is to be stored in the database, it'd seem to be rather heavy. Is this approach an overkill? If not, is it sound?

Hopefully my description is clear enough.

Answer 1

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.