5 ms·

"cryptographic deduplication" How is that even possible? Surely a custom crypto scheme is needed?

jcr 14y ago
I wish I could tell you. I understand some of the parts involved but do not understand the method completely, so it's best for everyone that I don't speculate blindly. The Ciphertite web site is a far better reference than I could ever be. I'll go to the top of the building and light up the tptacek bat signal.
sp332 14y ago
Yes, it's possible with certain kinds of algorithms. A while back IBM found a way to do general computation on data without decrypting it, like adding encrypted dollar amounts together etc. But it's about a million times slower than normal data processing.
- betterunix 14y ago
  General computation on encrypted data was discovered by a graduate student at Stanford named Craig Gentry. He now works for IBM, and has been pretty active in that field, along with a handful of other experts. It's very slow, sure, but over the past 4 years speeds have increased to the point where it is reasonable to start talking about practical applications. It is also worth pointing out that systems supported restricted classes of functions preceded Gentry's work. If you are willing to limit yourself to NC1 functions (i.e. those that can be represented as boolean circuits with depth that is the logarithm of the input size), you can use oblivious transfer or the SYY construction (cannot recall their names off the top of my head). If you only need products in certain groups, you can use ElGamal. If you only need an XOR, you can use the Goldwasser-Micali system. Also, there are garbled circuits, which date back to the 1980s. That is a somewhat different notion of computing on encrypted data, since it requires messages to be sent every time the computation is performed. Garbled circuits are substantially faster than FHE right now, although that may change due to FHE's low communication overhead and the rate at which FHE speeds have been improving. Also in this category are multiparty protocols that use arithmetic circuits, which have seen at least one major real-world use: http://fc09.ifca.ai/papers/15_Secure_MPC_goes_live.pdf http://fc09.ifca.ai/papers/15_Secure_MPC_goes_live.pdf
conformal 14y ago
cyphertite uses a private (per-user) deduplication pool, not a global deduplication pool like dropbox and many other online storage providers. Example 1 - user1 uploads file1, then at a later time user1 tries to upload file1 again. the 2nd occurrence of the data in file1 is recognized as a duplicate of what has already been stored, so the service does not re-upload the bulk data of file1. this saves bandwidth, time, cpu cycles etc. Example 2 - user1 uploads file1, then at a later time user2 uploads file1. in a private (per-user) deduplication pool, both user1 and user2 would need to separately upload a copy of file1, but in a global deduplication pool, user2 would not need to actually upload the bulk file data since it can reference data that user1 uploaded earlier. the upshot here is that each user has their own separate crypto keys that are used client-side, similar to spideroak, tarsnap, etc. i could get into the details here, but it's pretty well summarized in our infographic and crypto whitepaper https://www.cyphertite.com/papers/CT_InfoGraphic.pdf https://www.cyphertite.com/papers/CT_InfoGraphic.pdf https://www.cyphertite.com/papers/WP_Crypto.pdf https://www.cyphertite.com/papers/WP_Crypto.pdf

jcr 14y ago

I wish I could tell you. I understand some of the parts involved but do not understand the method completely, so it's best for everyone that I don't speculate blindly. The Ciphertite web site is a far better reference than I could ever be. I'll go to the top of the building and light up the tptacek bat signal.

sp332 14y ago

Yes, it's possible with certain kinds of algorithms. A while back IBM found a way to do general computation on data without decrypting it, like adding encrypted dollar amounts together etc. But it's about a million times slower than normal data processing.

betterunix 14y ago
General computation on encrypted data was discovered by a graduate student at Stanford named Craig Gentry. He now works for IBM, and has been pretty active in that field, along with a handful of other experts. It's very slow, sure, but over the past 4 years speeds have increased to the point where it is reasonable to start talking about practical applications. It is also worth pointing out that systems supported restricted classes of functions preceded Gentry's work. If you are willing to limit yourself to NC1 functions (i.e. those that can be represented as boolean circuits with depth that is the logarithm of the input size), you can use oblivious transfer or the SYY construction (cannot recall their names off the top of my head). If you only need products in certain groups, you can use ElGamal. If you only need an XOR, you can use the Goldwasser-Micali system. Also, there are garbled circuits, which date back to the 1980s. That is a somewhat different notion of computing on encrypted data, since it requires messages to be sent every time the computation is performed. Garbled circuits are substantially faster than FHE right now, although that may change due to FHE's low communication overhead and the rate at which FHE speeds have been improving. Also in this category are multiparty protocols that use arithmetic circuits, which have seen at least one major real-world use: http://fc09.ifca.ai/papers/15_Secure_MPC_goes_live.pdf http://fc09.ifca.ai/papers/15_Secure_MPC_goes_live.pdf

conformal 14y ago

cyphertite uses a private (per-user) deduplication pool, not a global deduplication pool like dropbox and many other online storage providers. Example 1 - user1 uploads file1, then at a later time user1 tries to upload file1 again. the 2nd occurrence of the data in file1 is recognized as a duplicate of what has already been stored, so the service does not re-upload the bulk data of file1. this saves bandwidth, time, cpu cycles etc. Example 2 - user1 uploads file1, then at a later time user2 uploads file1. in a private (per-user) deduplication pool, both user1 and user2 would need to separately upload a copy of file1, but in a global deduplication pool, user2 would not need to actually upload the bulk file data since it can reference data that user1 uploaded earlier. the upshot here is that each user has their own separate crypto keys that are used client-side, similar to spideroak, tarsnap, etc. i could get into the details here, but it's pretty well summarized in our infographic and crypto whitepaper https://www.cyphertite.com/papers/CT_InfoGraphic.pdf https://www.cyphertite.com/papers/CT_InfoGraphic.pdf https://www.cyphertite.com/papers/WP_Crypto.pdf https://www.cyphertite.com/papers/WP_Crypto.pdf