220 reputation
210
bio website linkedin.com/in/mtodor
location Delft, Netherlands
age 28
visits member for 2 years
seen Mar 25 at 9:44

Software Engineer


May
19
awarded  Teacher
May
18
revised DGK Cryptosystem Encryption Speedup
Added a small clarification regarding the decryption procedure.
May
18
accepted DGK Cryptosystem Encryption Speedup
May
15
answered DGK Cryptosystem Encryption Speedup
May
15
revised DGK Cryptosystem Encryption Speedup
Corrected a formula.
May
14
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.
May
14
asked DGK Cryptosystem Encryption Speedup
May
9
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
May
9
awarded  Supporter
May
9
accepted Chinese Remainder Theorem and RSA
May
9
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$?
May
9
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.
May
9
revised Chinese Remainder Theorem and RSA
added 15 characters in body
May
9
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.
May
9
awarded  Editor
May
9
revised Chinese Remainder Theorem and RSA
added 105 characters in body
May
9
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.
May
9
asked Chinese Remainder Theorem and RSA
May
4
awarded  Student
May
3
awarded  Scholar