[cryptography] Paillier Crypto for homomorphic computation

[Adam Back]

No recall that the simplified paillier is c=g^m*r^n mod n^2 so
multiplication gives addition:

g^a*r1^n * g^b*r2^n = g^{a+b}*(r1*r2)^n

ie multiplication of ciphertexts gives you homomorphic addition of
plaintexts.

but g^a*r1^n ^ (g^b*r2^n) != g^{a*b}*r3^n

(the core part is g^a ^ (g^b) = g^{a*g^b} != g^{a*b}).

what does work is as I said raising to the power of a constant eg k:

(g^m*r^n)^k = g^{k*m}*(r^k)^n so you can still decrypt and the 
operation is multiply by constant k).

Adam

On Wed, Aug 07, 2013 at 09:26:02AM +0100, Joss Wright wrote:
>On Wed, Aug 07, 2013 at 01:09:07AM +0200, Adam Back wrote:
>> I dont get it.  Paillier is additively homomorphic only.  (And obviously by
>> implication multiplyable by non-encrypted constants.)
>
>Minor point, but by raising one Paillier ciphertext to the power of
>another you get multiplication without revealing the factor.
>
>>
>> RSA is multiplicatively homomorphic.  And Elgamal additive.
>>
>> Why is paillier proposed as "might scale homomorphic" the interesting
>> property is dual homomorphic crypto which Gentry and variants provide (but
>> at impractical computational and large space overhead huge).  Dual or fully
>> homomorphic is the interesting property because then you can do arbitrary
>> computations (using multiplication as single-bit AND and addition as
>> single-bit OR and building a CPU from gates - still expensive even if the
>> base algorithm was as efficient as Paillier/RSA/Elgamal but interesting).
>>
>> Also why would they send the "encrypted numbers" to two peers and have them
>> do the encrypted computation?  The whole point is its zero-trust secure from
>> the point of view of the client - client encrypts, server does computations
>> on encrypted values, sends encrypted result back to client, client decrypts
>> - and you dont need to trust the server.  No need for threshold crypto,
>> having multiple peers do some kind of multi-party computation etc.
>>
>> Adam
>>
>> On Tue, Aug 06, 2013 at 08:11:52PM +0200, Eugen Leitl wrote:
>> >----- Forwarded message from dan at geer.org -----
>> >
>> >Date: Mon, 05 Aug 2013 14:43:28 -0400
>> >From: dan at geer.org
>> >To: cryptography at randombit.net
>> >Subject: [cryptography] fwd: Paillier Crypto
>> >
>> >
>> >>http://9ac345a5509a.github.io/p2p-paillier/
>> >>
>> >>This is a form of Homomorphic Encryption that might actually scale,
>> >>given the right cloud backend. It verges on the spookiness of
>> >>Quantum.
>> >>
>> >>Support logic that might shed light on the true performance of
>> >>Paillier.
>> >>
>> >>http://plaintext.crypto.lo.gy/article/658/encounter
>> >
>> >
>> >--dan
>> >
>> >_______________________________________________
>> >cryptography mailing list
>> >cryptography at randombit.net
>> >http://lists.randombit.net/mailman/listinfo/cryptography
>> >
>> >----- End forwarded message -----
>> >--
>> >Eugen* Leitl <a href="http://leitl.org">leitl</a> http://leitl.org
>> >______________________________________________________________
>> >ICBM: 48.07100, 11.36820 http://ativel.com http://postbiota.org
>> >AC894EC5: 38A5 5F46 A4FF 59B8 336B  47EE F46E 3489 AC89 4EC5
>
>-- 
>Joss Wright | @JossWright
>http://www.pseudonymity.net