1
$\begingroup$

Using homomorphic encryption, I would like to be able to take an encrypted integer and either add 1 or -1 for a new encrypted value. I do not want the encrypted value to be recoverable - just the following:

  • $\varepsilon(x) = (\varepsilon(x) \oplus \varepsilon(-1)) \oplus \varepsilon(1) = (\varepsilon(x) \oplus \varepsilon(1)) \oplus \varepsilon(-1),$
  • $\varepsilon(x+1) = \varepsilon(x) \oplus \varepsilon(1) \ \mathrm{and}$
  • $\varepsilon(x-1) = \varepsilon(x) \oplus \varepsilon(-1)$
  • $\forall x \in \mathbb{Z}$

$x$ can never be recovered because the secret key will not be known (an original $\varepsilon(x')$ is chosen as $0$ and it will only be manipulated or used in encrypted form). It is ok (and perhaps even desirable) if $\varepsilon(x + n)$, computed (only) recursively as a series of single increments or decrements, is worse than $O(n)$ but no worse than about $O(n \log n)$ and there should be no limit on $n$ - that is, the further I go in a direction, it gets a little harder to keep going, but not impractically so.

It seems to me that this is perhaps within practicality for Gentry's scheme if the hints for $\mathrm{sK}$ can be reused forever for $\mathrm{recrypt}()$, but I might be misunderstanding this (or all of it). Then, Gentry might be overkill, since I don't seem to need multiplication ($\varepsilon(-1)$ does not need to be calculated as $\varepsilon(1) \otimes \varepsilon(-1) $, right?). I think any PHE supporting unlimited additions is good enough. Gentry's numbers "stiffen" - but is that the case with all systems? If they stiffen at about $O(n \log n)$ that's what I'm hoping for worst case.

I'd like to implement this in F# but 1) I need a good choice of algorithm supported by .NET or with an implementation in F#, and 2) How can I disable padding in such a scheme which normally one would be crazy to want to do?

The purpose is to create a dimension whose origin is unknown, but which can be navigated relatively. I'm below novice at math and latex and formalisms so if my attempts above are totally asinine, I apologize. Do you recognize an equivalent scheme that doesn't require HE?

$\endgroup$

1 Answer 1

3
$\begingroup$

You don't need fully homomorphic encryption for this. In particular, you don't need to use Gentry's scheme. Any standard scheme for additively homomorphic encryption will be fine. For instance, Paillier should work fine, as should exponential El Gamal.

Search this site and you can find lots of information on additively homomorphic encryption. See, e.g., Can Elgamal be made additively homomorphic and how could it be used for E-voting? and https://crypto.stackexchange.com/a/9003/351 and https://crypto.stackexchange.com/a/12704/351 and https://crypto.stackexchange.com/a/9139/351. Also, search the literature for work on "encrypted counters" and you should find additional stuff that might be helpful.

This is not the site to ask how to implement crypto in F#; ask on StackOverflow for coding questions. Your questions about padding make no sense to me. The real question is what algorithm to use. Once you know what algorithm to use, just implement it (that's just a straightforward matter of programming).

$\endgroup$
5
  • $\begingroup$ Thanks! The padding thing was due to my impression that HE is an undesirable property normal crypto uses and thus padding is added which interferes with HE, i.e. multiplication in RSA. But whatever, this is good info, thanks. $\endgroup$ Jan 31, 2014 at 3:29
  • $\begingroup$ But if I wanted to extend this to multiple dimensions, I'd need Gentry? $(\varepsilon(x), \varepsilon(y), \varepsilon(z))$ is not as ideal as $\varepsilon((x, y, z))$ because I don't want the components to be reusable independently like that. Is there an encoding of $(x, y, z)$ that makes it compatible with the simple $\oplus$? $\endgroup$ Jan 31, 2014 at 13:38
  • 2
    $\begingroup$ @uosɐſ So what you are saying is you'd like to be able to encrypt 3 values at once so that operations on those will happen in parallel? Kind of like the SIMD work done in some of the FHE papers? If that is your question, I think you should pick a crypto system (paillier or exponential elgamal)then ask a separate question specifically relating to that system and how you would enable SIMD-like operations. $\endgroup$
    – mikeazo
    Jan 31, 2014 at 13:49
  • $\begingroup$ @uosɐſ, that's a different question, so it should be posted separately as a separate question. One question per question, please: this is not a discussion forum, so it's important to keep things focused. I think I might be able to propose some candidate solutions, but I don't want to post it here. $\endgroup$
    – D.W.
    Jan 31, 2014 at 19:16
  • $\begingroup$ ok, ready: Homomorphic encryption for vector addition I did not mention SIMD because I didn't want to steal your thunder. $\endgroup$ Jan 31, 2014 at 21:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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