Homomorphic encryption is the cryptographic party trick that keeps getting closer to practical: you can hand a server encrypted numbers, let it compute on them, and get back an encrypted result it never could read. The math works. The problem has always been cost. A single multiplication of two ciphertexts produces a larger, noisier ciphertext, and the standard fix — an operation called relinearization — is one of the heaviest steps in the whole scheme.
That is the cost US10541805B2, “Variable relinearization in homomorphic encryption,” is built around. Granted to Microsoft Technology Licensing on January 21, 2020 and classified under H04L 9/008 — the CPC subclass that specifically covers homomorphic encryption — the patent describes not relinearizing after every multiplication but choosing when to do it.
Read the independent claim rather than the abstract and the engineering judgment becomes visible. The method tolerates a ciphertext growing past its usual two-element size for a stretch of operations, then relinearizes once, later, when the savings justify the cost. A circuit that performs several multiplications in a row no longer pays the relinearization tax at each step; it pays once, strategically.
Why this is a genuine optimization rather than a relabeling: relinearization requires the so-called evaluation keys and a sequence of modular operations that dominate runtime in real homomorphic workloads. Deferring it changes the asymptotics of a multiplication-heavy computation. The trade is more memory and slightly larger ciphertexts in exchange for fewer of the most expensive operations — a classic time-versus-space dial, here exposed as a cryptographic parameter.
It is worth naming what the patent is and is not. This is an issued grant, kind code B2, not a pending application: the claim cleared examination and defines enforceable scope. And it is a method patent, not a product. It does not by itself prove any shipping library implements variable relinearization, though Microsoft's open SEAL homomorphic-encryption library is the obvious context in which the same research group works.
The reason it matters on this desk is that the homomorphic-encryption race is now being won and lost on performance, not feasibility. Everyone can compute on ciphertext; the open question is whether it is fast enough to deploy. A patent that stakes a claim to one of the few levers on that cost — when, not whether, to relinearize — is exactly the kind of unglamorous, load-bearing IP that decides which scheme is practical.