[Haskell-cafe] homomorphic encryption and monads?

Jason Dagit dagit at codersbase.com
Wed Jul 15 17:54:17 EDT 2009


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).

So for example, suppose you wrote a function that worked on encrypted email
to determine if it spam, maybe it looks like this:
isSpam :: Cypher String -> Cypher Bool

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".

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

Which we could use to implement isSpam:

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

I initially thought that doWork should be (>>=), but it seems the type of
the function should either be (a -> b) or (Cypher a -> Cypher b).  That is,
return :: a -> Cypher a, is not available.  All the data should already be
encrypted.  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.

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.

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

Or perhaps, it should be:

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

Which would match the type of return.

If that is the type of return, then we probably want:
(>>=) :: Cypher (a -> b) -> ((a -> b) -> Cypher (c -> d)) -> Cypher (c -> d)

At this point, I'm not actually sure if the second type for enCypher makes
any sense.  But, if it does, then I think it says the purpose of the monad
is to act on the transformations and not the data.  That is, instead of
focusing on the data as being held in the cypher, we are thinking of the
functions as being transformed into a cypher space.

Has anyone else been thinking about this?

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090715/a7403f48/attachment.html

More information about the Haskell-Cafe mailing list