homomorphic encryption and monads?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

homomorphic encryption and monads?

Jason Dagit-2
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).

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:
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?

Jason

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: homomorphic encryption and monads?

Max Rabkin-2
On Wed, Jul 15, 2009 at 11:54 PM, Jason Dagit<[hidden email]> 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
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: 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<[hidden email]> 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
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe