[Haskell-cafe] homomorphic encryption and monads?

[Dan Weston]

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<dagit at codersbase.com> 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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>