[Haskell-cafe] homomorphic encryption and monads?
westondan at imageworks.com
Wed Jul 15 19:56:38 EDT 2009
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
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
Max Rabkin wrote:
> 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.
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
More information about the Haskell-Cafe