3 ms·

It is trivial to create almost any encryption scheme from a fully homomorphic algorithm: You create a program, which after all is just a set of simple instruct

It is trivial to create almost any encryption scheme from a fully homomorphic algorithm: You create a program, which after all is just a set of simple instructions. If you can do homomorphic add, mul and mod you have everything you need, and I believe you can work with just a few bit operations. So you make a homomorphically encrypted program that has an encryptor en decryptor routine, themselves encrypted (and can thus safely contain a private key), and that program then does the operations requested, which does indeed get you an encrypted result. Then you ask the encrypted program to please decrypt the answer. It can validate that question however it wants (implementing privacy policies seems like it would be a good way to do that here), and if it agrees, it decrypts the answer. There's all sorts of schemas you can build into this to do replay protection. For the truly paranoid such a program can be created with a random encryption key that is then deleted as soon as the program is created. Then there is no trust of anyone at all. You could implement bitcoin, or a totally secure root of trust of for example the dns root zone on the internet. The only problem is that changing the program becomes impossible for anyone, which may be a good thing. And you keep homomorphic guarantees: No need for trust. No need for trusting the CPU your homomorphic program executes on, or it's memory. NO information, not the code, not the temporary values, not the memory, not the stack ever, at any time in the program's execution, exists unencrypted. (paraphrasing a paper that pointed out that implementing bitcoin-like systems with homomorphic encryption is very easy indeed, which is a similar problem)

sterlind 7y ago
unfortunately FHE doesn't work like you describe. in FHE, the answer output is always indistinguishable from random noise. in fact, the "encrypted decryptor" routine you're describing is more or less how bootstrapping works - the ciphertext is double-encrypted to the bootstrapping key, the circuit evaluates decryption of the encrypted ciphertext to produce a fresh ciphertext against the bootstrapping key, then a key switching operation exchanges the bootstrapping key for the evaluation key. * needing certain policies to be met for decryption is the field of attribute-based encryption. * only being able to evaluate certain functions of a ciphertext to decrypted plaintext is the field of functional encryption. * the general holy grail you're describing is program obfuscation - a secure black box that evaluates an arbitrary circuit on an input. unfortunately there are strong impossibility results in program obfuscation, though there's some theoretical progress towards weaker obfuscation or much more limited types of circuits, involving extremely inefficient mathematical wizardry that's regularly being badly broken by cryptanalysis. in summary, you've confused FHE with program obfuscation, and the decryptor routine you describe is just bootstrapping.

sterlind 7y ago

unfortunately FHE doesn't work like you describe. in FHE, the answer output is always indistinguishable from random noise. in fact, the "encrypted decryptor" routine you're describing is more or less how bootstrapping works - the ciphertext is double-encrypted to the bootstrapping key, the circuit evaluates decryption of the encrypted ciphertext to produce a fresh ciphertext against the bootstrapping key, then a key switching operation exchanges the bootstrapping key for the evaluation key. * needing certain policies to be met for decryption is the field of attribute-based encryption. * only being able to evaluate certain functions of a ciphertext to decrypted plaintext is the field of functional encryption. * the general holy grail you're describing is program obfuscation - a secure black box that evaluates an arbitrary circuit on an input. unfortunately there are strong impossibility results in program obfuscation, though there's some theoretical progress towards weaker obfuscation or much more limited types of circuits, involving extremely inefficient mathematical wizardry that's regularly being badly broken by cryptanalysis. in summary, you've confused FHE with program obfuscation, and the decryptor routine you describe is just bootstrapping.