Is there a encryption scheme in literature, where I can do something like

$$F_{k_1}^{-1} \big( F_{k_2}(A) + R \big) = A + O(R)$$

where, $A$ is a $m \times n$ real matrix, $R$ is a $m \times n$ real matrix that contains some random noise, and (preferably, $k_1 \neq k_2$)

essentially what I want is a scheme where if the encryption of my matrix $A$ 'picks up' some noise, the decryption should not be heavily effected, and the noise after the decryption is of order $O(R)$

EDIT: Since there has been no concrete answers yet, let's relax the the $k$s.. what if we are willing to have $k_1 = k_2$?

  • $\begingroup$ In other words, decryption should be Lipschitz? $\;$ $\endgroup$ – user991 Feb 2 '15 at 4:49
  • $\begingroup$ I am not too sure I understood what it meant, but can there be a Lipschitz function for an encryption scheme in the first place? $\endgroup$ – Subhayan Feb 2 '15 at 10:23
  • 1
    $\begingroup$ Oh, I see that my comment would only have been right if the keys were the same and the expression was supposed to work for all $R$. $\;$ $\endgroup$ – user991 Feb 2 '15 at 10:36
  • 2
    $\begingroup$ I would suggest lattice encryption because it's based on addition. check out this scheme: [[BrVa11]](cs.toronto.edu/~vinodv/BV-Crypto2011.pdf) (go section 1.1, "the basic scheme"). It's just a trail, not sure this one works because it seems if you add $r$ you decrypt to $m+r\bmod2$ but because of short vector problem you can have troubles relating it to $m$. $\endgroup$ – Cédric Van Rompay Feb 2 '15 at 15:46
  • 1
    $\begingroup$ Following the suggestion of Cédric Van Rompay, there is probably a connexion with the general Lattice problems. I recommand you to dig the construction of Ajtai-Dwork cryptoSystem, which present in my sense some similarities with your problem. Cf also the attack of Phong & J. Stern here: antoanthongtin.vn/Portals/0/UploadImages/kiennt2/KyYeu/… $\endgroup$ – Robert NACIRI Feb 3 '15 at 8:40

Your Answer

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

Browse other questions tagged or ask your own question.