Re: [Haskell-cafe] homomorphic encryption and monads?

I think there may be a problem here. "Homomorphic encryption is a form of encryption where one can perform a specific algebraic operation on the plaintext by performing a (possibly different) algebraic operation on the ciphertext. " The word "specific" means that the functor is discrete, not continuous. Only Integer can be encoded. Also, the arrow mapping is partial: fmap does not accept arbitrary any (a -> b) but only a natural transformation pair (in,out). That would make Encryption an indexed arrow, something like class Arrow a => In a b where in :: a b Integer class Arrow a => Out a c where out :: a Integer c instance (In a b, Out a c) => Arrow a b c where arr f = in >>> f >>> out Dan Max Rabkin wrote:

On Wed, Jul 15, 2009 at 11:54 PM, Jason Dagit wrote:

...

Hello,

I have just a very vague understanding of what homomorphic encryption is, but I was wondering if homomorphic encryption behaves as a one-way monad (like IO).

An interesting idea. Let's see where this leads.

...

I could be mistaken about the way this works, but it seems that isSpam can't return a plain 'Bool' because then you could know things about the encrypted data without having to decrypt it first. So that is why I think it has to return "Cypher Bool".

Yes, this is the idea behind homomorphic encryption: you can do some work on an encrypted input, and get an encrypted output.

Your categorical spidey-sense should be tingling right now, and indeed it did, but you interpreted it wrong (but it's a common trap)

...

And because it's a homomorphic encryption, you could have something like doWork: doWork :: Cypher a -> (a -> b) -> Cypher b

Looks good. This type should send your spidey-sense into the red.

...

Which we could use to implement isSpam:

isSpam s = doWork s spamTest where spamTest :: String -> Bool

Thinking about it a bit more, since we never have to decrypt the data to work with it, it seems that (a -> b) is wrong as well, because we don't have the key or whatever to do the decrypting.

(a -> b) is not wrong. Homomorphic encryption gives you exactly this *magic* function that takes an ordinary f :: a -> b, and applies it to a Cypher a, giving you a Cypher b. No deciphering happens. The function get lifted/mapped into Cypher.

...

So, then it seems reasonable that the only type for doWork is this: doWork :: Cypher a -> (Cypher a -> Cypher b) -> Cypher b

Which doesn't really seem all that useful now.

Indeed. That is just (a restricted version of) the type of 'flip ($)', a rather uninteresting (though not useless) function.

...

On the other hand, maybe we have an algorithm which can take a function on normal values and gives us a function on Cypher values:

enCypher :: (a -> b) -> Cypher a -> Cypher b

This is exactly what you have. This is just the flipped version of your first doWork.

And this function is better known as fmap. Cypher is a Functor.

Because they have special syntax, are widely used in IO, and have a scary name (and perhaps for other, better reasons too), Monads seem to attract special attention.

Functor and Applicative get much less love, but both are valuable and interesting typeclasses (they form a hierarchy: every monad is an applicative functor, and ever applicative functor is a functor). And hopefully your spidey-sense now has a Functor-detector :)

I was planning to show that Cypher can't be a monad or an applicative functor, but their seems to be a hole in my thinking. Hopefully I can fix it, and hopefully everything I've said up to now has been correct.

--Max _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe