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
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:
- 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.
- 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
Csends the message back,
Sdecrypts the message by decoding the message and reading the missing point from its database.
Sapplies Lagrange/Newtoian interpolation to retrieve $e_n$.
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 (
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.