I'm looking at the SEAL library but I'm trying to figure out what happens in a certain use case.

For example:

  1. Alice encrypts the number 123456 homomorphically and sends it to Bob.

  2. Bob adds 25 and does 3 left rotations on the value. He then sends it back.

  3. Alice decrypts the value and gets 481123.

Following Step (3), is there a way for Alice to find out what operations Bob ran besides just guessing?

Maybe I'm not just confused about how the noise thing works.

  • 1
    $\begingroup$ Are you asking about a specific scheme? The property you're asking about is called circuit privacy and not all homomorphic encryption schemes are circuit private. $\endgroup$ – Maeher Jul 29 '19 at 20:19
  • $\begingroup$ I don't think I am not asking about a specific scheme but maybe I am. The circuit, which I've only briefly looked at before responding to you, is meant to be a secret from Alice. Bob can know it. I'm just trying to find out whether Alice can ever discover what the circuit did when she receives the result of the computation. I guess specifically, would the SEAL library accomplish this? $\endgroup$ – Lfod Jul 29 '19 at 20:26

No, not with SEAL at least. The noise is basically a measure of how much uncertainty there is after the operations are performed. Past a certain point there is simply too much and the decryption may be affected by it (the noise does not "round off" correctly), after which decryption may result in incorrect values. Because of this the "noise budget" is used in the library (invariant_noise_budget). Your results can safely be decrypted as long as the noise budget is positive.

It would probably be possible to gather some information about which types and how many operations (for some operations) occurred by analyzing the noise. Certain operations (rotation for example) do not consume the noise budget and would therefore be undetectable by a noise-analysis attack that depends on the amount of noise. Assuming SEAL does not have any huge flaws in it there shouldn't be any attacks that will let an attacker list out exactly which operations occurred.

| improve this answer | |
  • 1
    $\begingroup$ Moreover, different sequences of operations can increase the noise similarly. For example, performing a single multiplication between two ciphertexts; performing several additions; performing some additions and some plaintext-ciphertext multiplications... $\endgroup$ – Hilder Vitor Lima Pereira Jul 31 '19 at 7:09
  • $\begingroup$ Absolutely. The SEAL library also includes some examples in which the different operations lead to the same results but with less of the noise budget consumed. So even if there was a way to discover (a set of) operations that were performed by analyzing how much noise was generated, it can be somewhat obfuscated by performing equivalent operations with different costs. It only makes sense to outsource the very large computations, so the sheer amount of possibilities from all the noise would quickly make it an intractable problem. $\endgroup$ – user Jul 31 '19 at 11:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.