[Haskell-cafe] homomorphic encryption and monads?
max.rabkin at gmail.com
Wed Jul 15 18:42:52 EDT 2009
On Wed, Jul 15, 2009 at 11:54 PM, Jason Dagit<dagit at codersbase.com> wrote:
> 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 :: 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.
More information about the Haskell-Cafe