Homomorphic encryption implementation
hcrypt.com
hcrypt.com
Add cyphertexts (= XOR)
Multiply cyphertexts (= AND)
Add with carry in and carry out
Add with carry out
https://en.wikipedia.org/wiki/Group_homomorphism
The way I've understood it is that only addition has been possible so far. With a multiplication operation, you can get a field, and do "everything" with the real/complex numbers.
Not so. The notion's far more general: https://en.wikipedia.org/wiki/Ring_homomorphism
This gives us a notion of homomorphisms between fields.
https://en.wikipedia.org/wiki/Homomorphism for more general notions of homomorphisms.
Add with carry-out seems like it could be use to build some complex systems.
As Google tries to gobble up even more of everyone's data and every waking habit as they try to improve Google Now and other services, the privacy concerns are only going to grow bigger. It will be not just a drain on their public image (just like it is on Facebook's image), but it would also give competitors a lot more opportunities to take jabs at them. Think Scroogled, but 10 fold.
Homomorphic encryption would pretty much fix all of that, and they wouldn't even need to give up their data collection (or not as much).
No, the people for which this is really useful is large non-IT companies like Boeing or healthcare companies etc. They have huge data processing or storage requirements, and frequently have to run around hoops in order to ensure data is not transmitted in a way that would breach commercial agreements or confidentiality requirements. The problem is that frequently these workloads (especially for companies like Boeing) will involve much data, and HE tends to come with a large size increase and performance drop - so it's often too costly, which is a shame.
The cynical part of me wants to say that it's very similar to a standard mapreduce, and the security properties came for free/very little.
If they can efficiently apply FHE to your data and produce an encrypted set of ads that only you can unscramble, they'll make plenty of money.
It's not at all clear that this is feasible, but if I had billions of dollars burning a hole in my pocket, I'd probably fund FHE research.
This would be great for an encrypted file synchronization project I am working on; being able to diff an encrypted file would be amazing.
EDIT: Though now that I think about it you might be able to code a custom diff circuit for FHE that borders on feasibility. It depends on the algorithm used, really. File diff seems spiritually similar to some of the bioinformatics work being done with privacy-preserving edit distance computation on encrypted DNA sequences.
EDIT2: Here's a paper that discusses an FHE 'hardware platform': http://eprint.iacr.org/2014/106.pdf
The consistent feedback I get about file sync (from techies) is they really don't want to be uploading a whole file every time they change something. I agree, but to have client-side encryption such that you're data is protected from the server host as well as people who gain access to said server seems to preclude efficient sync with current tech. Which is again too bad.
I am no crypto expert so rolling my own / building off this FHE is not really possible. I do understand usage of things like AES and RSA well enough though to know that adequate security precludes diffing/efficient sync.
I disagree. You can deterministically chunk the large file with one of the existing rolling checksum schemes, and then use the chunks as your primitive instead of whole files. The server only sees encrypted chunks. The client knows to only upload changed chunks.
That still leaves important choices to be made about cipher mode, key management, etc. But it's not intractable.
My understanding is that CBC is among the most secure forms of AES encryption because it is essentially impossible to have patterns in data (unlike EBC). Practically speaking then one must assume that it is common to upload most of a file. Any software that boasts this security cannot effectively 'diff' your files.
EDIT: Formatting
If you manage to merge small files into the same blocks, you even gain some privacy because the server can't even tell the number of files anymore.
[1] also has a discussion of the trade-offs of the different modes of operation for whole disk encryption. That seems related here because nobody wants to rewrite the whole disk after changing the first byte.
[1] -- https://news.ycombinator.com/item?id=7787791
[2] -- http://en.wikipedia.org/wiki/Block_cipher_mode_of_operation#...
But he also said, that if someone finds a way to truly create an FHE-Scheme that works for unlimited amounts of edits, then it would be truly a ground-breaking thing to the whole crypto community. It's highly welcomed, but he is not that optimistic about it for the near future.
Basically, generate a tarball, split that into chunks at e.g. zero bytes (tarsnap uses a smarter algorithm), upload any chunks that the server does not have.
"On the (Im)possibility of Obfuscating Programs"
"In this work, we initiate a theoretical investigation of obfuscation. Our main result is that, even under very weak formalizations of the above intuition, obfuscation is impossible."
I haven't spent too much time meditating on the implications of the paper, so I was hoping to hear from someone who has. Does this paper strike a mortal blow to FHE? Or is this paper pointing out a result that can be ignored in practice?
When I get a few hours I'll spend some time trying to come up with examples of what the paper is talking about and hopefully discover the truth for myself, but if someone here has already done that, please chime in!
IOW, FHE means: "I know I added your numbers, but I don't know what they are or what their sum is. Here's the encrypted sum."
[1] First sentence: Informally, an obfuscator O is an (efficient, probabilistic) “compiler” that takes as input a program (or circuit) P and produces a new program O(P) that has the same functionality as P yet is “unintelligible” in some sense.
What Black box obfuscation demands which is impossible is "Take this plaintext, do a step in an obfuscated Turing machine and return me the plaintext solution", i.e. there's no obfuscation which makes it "hard" to determine the operations for arbitrary Turing machines/circuits given plaintext I/O.
Do you have a source on that? Because it sounds suspect. FHE works by constructing a (malleability-exploiting) circuit to implement the desired logic on the (malleable) ciphertext. So it seems it would have to decrypt the relevant step in that Turing machine to build the circuit.
With FHE the untrusted party can (usually) provide inputs (e.g. you can give them encryption of 1 and 0 that they can supply at some point in the circuit). But they cannot get _any_ non-encrypted output from the function without knowing the encryption keys (which would let them see everything).
FHE for secret operations is very straight forward. You first define a universal circuit— that is a circuit that can compute the result of any circuit (of the size) depending on its inputs. You then have the FHE environment run that universal circuit with the operations you really want specified as an input.
The result precluding blackbox obfuscation is really more about the formalism than a true practical impossibility, see Gentry's recent candidate indistinguishably obfuscation for NC circuts, which he boosts into full obfuscation for arbitrary circuts by implementing a pair of homorphic encryption decryption circuits under it.
Okay, the issue isn't whether you can obfuscate, but whether you can do it in a stronger sense than "regular" FHE or plain ol binaries or deliberate obfuscation. And what you've described doesn't do that.
The universal FHE circuit still sees the operations "you really want to execute", as it has to implement them in the first place. It's certainly obscured "gee, what do all these ANDs in this structure mean", but that's no different from eg an FHE scheme where you compute the circuit for the specific input size/function pair you want to compute rather than let the untrusted server generate it from knowledge of the algorithm you pass it.
So yeah, it's obfuscated, but no more than you get through regular computing; FHE has added nothing in this respect.
There's no contradiction: If you have the plaintext input, you are required to have at least a (non garbled) function describing your operation, so it doesn't imply obfuscation.
Anything that can be written as a function can exploit FHE, as long as the output doesn't grow (i.e. you have to account for growth before)
Input = FHE(data|opcode1|opcode2|...|opcodeN)
The server won't know what are the (opcode1|...|opcodeN) if the FHE scheme is properly implemented. That is, the actual implementation would be something like
Input' = FHE(data|opcode1|opcode2|...|opcodeN|randomness)
Output' = InverseHE(FHEval(Input'))
Output = Output' - randomness
I.e. the server can't uncover the (data,opcode1,...,opcodeN) tuple by enumeration if exp(randomness) is large enough. Is this what you had in mind?
It still has to execute the opcodes, revealing the computation in that sense. All the randomness adds (if I understand your example) is additional "junk" computation, that's unrelated to the output you really want -- but that's no different than you can already get with "plain" FHE, with obfuscation, or with adding pointless operations to a regular program.
Additionally, you should keep in mind that when doing the weird virtual machine thing you are not dealing with a single program. There are in fact 4. The actual program, call this P, you want to run on your data, the program to encrypt your program P along with its data, call this E, the virtual machine to run this encrypted program on the server, call this V, and finally the program to decrypt the result from running V on the output of E, call this E'.
Clearly, if we compose all these programs and run it on some data D, we get E'(V(E(P, D))) = P(D). However, the server doesn't know E, D and P and certainly doesn't know E'. The only thing the server knows is the value of E(P, D) and what V is. I haven't looked at the paper to deeply but I suspect it's vitally important to their result that you have some type of oracle that given a D, tells you the output of P(D), but the server cannot have that or else it would be pointless wasting your time with this FHE thing.
From the abstract: "Informally, an obfuscator O is an (efficient, probabilistic) “compiler” that takes as input a program (or circuit) P and produces a new program O(P) that has the same functionality as P yet is “unintelligible” in some sense"
That sounds like an exact description of FHE, and the paper seems to claim something is impossible. So I'm trying to figure out: If the paper isn't claiming FHE is impossible, then what is that "something" and how does it relate to FHE?
With HE, you operate on encrypted data and what you get out is still encrypted data - you never have knowledge of what the data is, you just know you've done something to it. So I could perhaps add two encrypted numbers together to obtain something I know to be the sum (but have no idea what the sum is).
Something doesn't seem quite right, though. Programs are data. If it's possible to perform operations on data without knowing the data, then shouldn't it be possible to perform (useful) computation without revealing the algorithm? If not, why not?
The closest analogy (I think you are trying to get to this) is that one might be able to make a series of operations that would execute an encrypted program. The problem is that this would result in encrypted output.
Thanks for your time. That's what I was trying to get to, yes. Would you help me understand why encrypted output would be a problem for the interpreter? If the input data is encrypted, and the data defines a program which can be executed, and the result of that execution is more encrypted data, then (for example) why can't that encrypted data be fed back into the interpreter as further input? Or transmitted over the network to a computer with the decryption key (so that the encrypted output can be used in a meaningful way, without revealing to the original computer what was computed)? In other words, why is encrypted output any more of a problem than operating on encrypted data in the first place?
The point of FHE, however, is to encrypt private data to send it to a third party to perform operations on that data without that third party having the keys necessary to decrypt the data (and thus see what it is). With FHE, the third party can modify the data but must then send the encrypted result back to the client who then uses the original keys to decrypt the result and look at it. The client can't see exactly which operations were performed and the third party can't see the original data.
I don't know if a FHE based interpreter is possible but since you need to have the original keys to read from an FHE payload, I don't think so.
The point of HE is that you can do add and mul. FHE extends HE to do arbitrary computation. "Is x equal to 5?" is an arbitrary computation, so it seems like FHE must support it.
If comparison ops are supported, then you can make an FHE based interpreter. Thus far, no one has been able to explain why specifically it wouldn't be possible. And if it's possible, then programs are naturally obfuscated: the interpreter is operating on encrypted bytecode input. But the original paper I cited says this is impossible! So there seems to be an interesting mystery here.
They can; the output is an encrypted boolean.
> And if it's possible, then programs are naturally obfuscated: the interpreter is operating on encrypted bytecode input. But the original paper I cited says this is impossible!
No it doesn't. Isn't your paper talking about an obfuscated program Ob(P) that does the same thing as P? P takes plaintext to plaintext, so Ob(P) takes plaintext to plaintext.
Homomorphic encryption is a different thing. Hom(P), if it exists, takes ciphertext to ciphertext. (Or possibly plaintext to ciphertext if it's a public-key cryptosystem.)
A conditional branch would become an encrypted conditional branch. That means, you wouldn't be able to infer the branch from the encrypted output.
Let's take a simple example. I have an algorithm X which takes two integers and returns an integer.
Let's say I want to run this algorithm on a third-party VPS. I obfuscate the algorithm X, in order to hide the operations that X does. Let's called the obfuscated version OX.
I host the OX algorithm on the third-party server, and start supplying it pairs of integers. The third-party is observing the set of inputs and outputs:
(4, 4) => 8
(3, 2) => 5
(1, 0) => 1
Now, however, if I use HE, I will get an algorithm (HX) which takes encrypted input and spits out encrypted output. A third-party will see the corresponding log of inputs and outputs like this:
h3830120cjfakj, 102309123clals => 293sdlzlxdf
94ka3lkc.zdkf, 102kksdllz => 1923939nddd
Note that the output size is fixed too. So yeah, any program you actually try implement this way is going to involve a very roundabout (er, circuitous) process. If-branching? Hah! That just means you get to designate half the remaining portion of the circuit to one branch and the other half to the other branch. While loops? You get to unroll each step into another set of gates.
Here's my post from when I first discovered the FHE paper: http://blog.tyrannyofthemouse.com/2013/05/i-added-your-numbe...
You may be thinking of HE. HE only allows add and mult operations. FHE extends HE to perform arbitrary computation.
(EDIT: To reply, click on "link". That will let you type out a reply while bypassing the flamewar prevention system. "Link" is next to my username, next to the "parent" link.)
If it's possible to add or multiply without knowing what's being added or multiplied, then it seems like it should be possible to do computation without revealing the algorithm being used.
I think you're being too handwavy about what FHE is capable of. FHE means that specific operations performed on encrypted data result in data that, when decrypted, have the right result in cleartext. It's not "hiding the data". So it can't run your encrypted bytecode, only transform it into other, also encrypted bytecode, which it also can't interpret. Executing encrypted bytecode doesn't really make sense, because the bytecode tells its interpreter what to do. Either the interpreter can read that information and do it, or it can't. The former means its not encrypted in the first place, and the latter means it won't work. You're trying to use a scheme by which the interpreter doesn't how to evaluate a function, but evaluates it correctly anyway.
So my understanding of FHE is that it can take an arbitrary circuit (any arbitrary program) and convert it into a circuit which operates on encrypted data.
That means it must be possible to write the equivalent of
if (op == OP_ADD) { /* interpret addition bytecode */ }
else if (op == OB_MUL) { /* interpret multiplication bytecode */ }
...
Now, when the program executes, it's obviously possible to monitor it and watch what's being done. However, until it executes, the bytecode remains secret. That means it should be possible to ship programs which are impossible to analyze until they're actually executed.
It's a common malware technique to write a program which contains an encrypted subprogram, which is only decryptable on a certain target machine. (For example, you could use a specific computer's MAC address as an ecryption key, which means no reverse engineer can analyze it except on that specific machine.)
FHE, on the other hand, provides the opportunity to ship a turing-complete interpreter to everyone, which executes encrypted bytecodes which can't be analyzed until execution time. That means a FHE program could be a timebomb set to wipe your harddrive at some specific date and you wouldn't know it, since the best you could determine beforehand is "this interpreter sometimes tries to execute shell commands" without actually seeing which commands it's capable of executing in practice until it's too late.
That's the trick. It isn't. Let's loosely stick to your example.
if (var == op)
{
do this
}
else
{
do that
}
0 La var //look at var
1 CMPa op //var==op?
2 BEQ 5 //yes
3 <do that>
4 JMP 6
5 <do this>
6 <continue>
PC = ((branch AND zero-flag) XOR (PC+1 AND !zero-flag))
PC = ((5 AND 1) XOR (3 AND 0))
PC = ((5 AND 0) XOR (3 AND 1))
res_add = OP1 + OP2
res_sub = OP1 - OP2
res_mul = OP1 * OP2
res_div = OP1 / OP2
result = ((res_add AND OP==ADD) XOR (res_sub AND OP==SUB) XOR (res_mul AND OP==MUL) XOR (res_div AND OP==DIV))
{x&0x2} = {0x2}
If you guys figured out how to securely implement control ( halting, loops, etc ), without functional encryption, that would be a huge breakthrough in FHE.
To be precise, the state of the machine includes the flags, the PC and memory. It's easy to implement a simple stack pattern in circuits but you don't need it in order to implement arbitrary functions.
We already published the solution for encrypted memory access and encrypted program flow control (without unfolding) but halting is an issue you (at least to my knowledge) cannot solve under the assumptions we made.
VII. OPEN ISSUES AND FUTURE WORK
...
One of the main issues of our concept is the termination problem. To solve this problem, a crypto-system that can selectively decrypt information is required.
I'll e-mail you guys offline.
Do you happen to have an email address I could reach you at with further questions? (If you don't want to post it publicly, please feel free to email me if you'd like: sillysaurus3@gmail.com)
if (op == OP_ADD) { /* interpret addition bytecode */ }
where "op" is encrypted data.
Hmm, this is a point of confusion for me then, because isn't that exactly what FHE allows you to do (and in fact its entire point)? HE allows you to add or multiply encrypted values, and FHE extends HE so that you can perform arbitrary computation. That must mean the == operator is supported, so it seems like it must be possible to do this.
Also, thank you for talking through this with me. It's much appreciated.
FHE doesn't extend HE in the sense that it adds operation types other than addition and multiplication but it allows unlimited chaining of the two operations. This in turn enables arbitrary operations because you can express any function (i. e. any chain of atomic operations) by means of additions mod 2 and multiplications mod 2 (which is equivalent to XOR and AND) when you turn it into a boolean circuit representation. The contribution of FHE is a way to a) clean operands from noise or to b) do not add noise to the operands in the first place because noise is the limiting factor for circuit depth in HE, where "depth" means the number of possible subsequent multiplications.
> That must mean the == operator is supported, so it seems like it must be possible to do this.
OK, I understand what you meant with the code now, but the problem is you won't know the answer to your equality comparison. In the same way that add(encryptedIntegerA, encryptedIntegerB) gives you encryptedIntegerC whose value is unknown but which you know decrypts to a + b, you know that equals(encryptedIntegerA, encryptedIntegerB) results in encryptedBooleanC, but you don't know whether that decrypts to true or false. So what do you execute next? It's not that it doesn't know until runtime which branch to take; it's that it doesn't know ever. The whole point FHE is that the executing machine doesn't know the answers themselves, just what they encrypt to. So I'm not sure--no matter how much meta eval you make it do--how it can decide what code to actually execute without decrypting something.
Edit: though I appear to be wrong about this. From Wikipedia:
If the morphisms of some wide supercategory of C include the primitive recursive functions or even all computable functions, then any encryption operation which qualifies as an endofunctor of this supercategory is "more fully" homeomorphic since additional operations on encrypted data (for example conditionals and loops) are possible.
That certainly supports your point. I suppose--more speculation by me-- it must compute both sides of the conditional (in this case, execute the OP_ADD branch and the OP_MULT branch) and then pick one in a way that makes it impossible to tell which "won". That would make a bytecode interperter really impractical, since it would have to compute a huge superset of what any actual bytecode program does, but not logically impossible.
You don't need to know the answer, though.
if (x == 5) { print "hello world"; }
else { print "goodbye world"; }
If I'm wrong about this, I don't understand why.
The ability to evaluate statements such as x == 5 falls under the realm of functional encryption ( see Boneh, Sahai, and Waters for a good intro http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.383... ).
You have to be very careful when mixing functional schemes with FHE schemes as it is very easy to create a completely insecure system.
For example, if you could evaluate arbitrary circuits consider what happens if you can evaluate equals and bitwise AND, two simple circuits.
({x}&{0x1}) == {0x1}
({x}&{0x2}) == {0x2}
({x}&{0x4}) == {0x4}
One more thing worth mentioning is that a direct comparison of ciphertexts doesn't work for semantically secure schemes. Anything that is IND-CPA, for example RSA-OAEP, will have the same plaintext encrypt to two different ciphertexts. Giving the untrusted server the ability to determine whether two ciphertexts will destroy the semantic security of the scheme, by definition.
Think of it this way: A conditional is "if this, do that." If the conditional is true, then the branch is executed. The output of the branch is still encrypted, but it's not true that you need the decryption key just to evaluate the branch. Right?
Theoretically speaking, I doubt this method holds: there is no theoretical analysis of it at all in the papers to support it. It certainly doesn't hold in the virtual blackbox model, which is what the theorem alluded above assumes.
The idea is that a correct obfuscator should only obfuscate and not change the program's semantics, which means that it can't change constants that may be displayed to the users, like hardcoded integers and strings. If you use these in a Quine [2] structure to be able to retrieve your original code, then the obfuscator can't do anything: it it breaks the Quine it is not a correct obfuscator, if it doesn't then you can trivially get back the original code. And what is interesting here is that it is possible to take any source code and make a Quine which has it as a payload (it will do the same thing as the original source code except that it will also be a Quine), which is something we had done already for another paper [3].
[1] http://eprint.iacr.org/2011/497