Mihai Todor
Reputation
225
Top tag
Next privilege 250 Rep.
 May19 awarded Teacher May18 revised DGK Cryptosystem Encryption Speedup Added a small clarification regarding the decryption procedure. May18 accepted DGK Cryptosystem Encryption Speedup May15 answered DGK Cryptosystem Encryption Speedup May15 revised DGK Cryptosystem Encryption Speedup Corrected a formula. May14 comment DGK Cryptosystem Encryption Speedup That is a very good remark, @poncho. Let me try to explain the motivation: This is supposed to be a building block used for comparing private inputs. Alice will generate the keys, encrypt data with the public key and send ciphertexts to Bob, who performs homomorphic operations on them and then sends the results back to Alice. I'm working in the semi-honest model, so it is assumed that both parties are honest but curious and they follow the protocol no matter what. Now, this allows Alice to use parts of the private key for speeding up the encryption process, since Bob will not encrypt anything. May14 asked DGK Cryptosystem Encryption Speedup May9 comment Chinese Remainder Theorem and RSA Thank you very much. I can see that your knowledge of this subject is really good, but I am looking in 2 distinct books at the formulation of the CRT and I am failing to see how this simple statement that you presented above derives from it. The CRT states that a solution for a system of r linear congruences exists and is unique modulo n, where $n = \prod_{i=0}^rn_i$, but how do you use this? The "General Case" on Wikipedia doesn't help: en.wikipedia.org/wiki/Chinese_remainder_theorem#General_case May9 awarded Supporter May9 accepted Chinese Remainder Theorem and RSA May9 comment Chinese Remainder Theorem and RSA That's a really nice and detailed proof, but I need more help to understand it: First, how did you end up with this formula: $M_1 = (M^d \bmod N) \bmod p = ((M \bmod p)^{d \mod p-1}) \bmod p$? Could you please detail it? I don't understand how you applied Fermat's "Little" Theorem to obtain it. It's clear how you've proven the formulae for the recombination step, but I'm not able to understand how does the CRT work in this case. How do you "immediately deduce that" $m = (M^d \bmod N) \mod pq$? May9 comment Chinese Remainder Theorem and RSA @Ninefingers: Yes, I know, it's just that comments don't show previews and, anyway, I'll try to use it next time. Thanks. May9 revised Chinese Remainder Theorem and RSA added 15 characters in body May9 comment Chinese Remainder Theorem and RSA It's not clear to me how the CRT is applied to derive this formula: m = m_2 + (h * q), where h = q_inv * (m_1 - m_2) (mod p). I would really appreciate it if you could detail this procedure. May9 awarded Editor May9 revised Chinese Remainder Theorem and RSA added 105 characters in body May9 comment Chinese Remainder Theorem and RSA @mikeazo: The security update is not relevant for this conversation at the moment. If I manage to understand the way the CRT is applied for RSA, then I should be able to figure the rest out by myself, because it is similar. Please ignore my reference to DGK for now. May9 asked Chinese Remainder Theorem and RSA May4 awarded Student May3 awarded Scholar