Join Log in
Score:-1
avatar Crypto

Is there some function of $n$ that is a multiple of $\phi(n^2)$?

ua flag
Henry Garrett

Not sure which forum to post this question so here is a link to it from MSE.

This is to adapt the approach of Fermat's Little Theorem to the Paillier encryption system.

I understand that this will occasionally fail (approximately 1 in $\sqrt n$), but I feel this is unlikely enough to ignore. Am I correct in my assumption?

62
1 + 4
SEJPM avatar
us flag
SEJPM
I'm admittedly a bit confused. Do you want an answer to the same question as asked on Math.SE here or do you want an answer to the stated question asking whether $1$ in $\sqrt n$ can reasonably be considered to be small enough to ignore?
0
Reply
ua flag
Henry Garrett
both really. because it's been shown to be insecure I going to have to look for another approach but I'm still interested if $1$ in $\sqrt n$ is small enough to ignore. thanks
0
Reply
SEJPM avatar
us flag
SEJPM
OK, I suggest the following way forward then: This question will receive an answer on whether the considered error probability is small enough to ignore and the linked Math.SE answer stays for context (or is migrated here to Crypto.SE) so we don't have to essentially copy & paste poncho's Math.SE answer somewhere.
0
Reply
Patriot avatar
cn flag
Patriot
The first question is in the title, and the second "question" is elliptical. Both, I take it, appear on two SE sites.
0
Reply
Score:0
SEJPM avatar Crypto
us flag
SEJPM

I understand that this will occasionally fail (approximately $1$ in $\sqrt n$) but I feel this is unlikely enough to ignore?

Yes. From the context it seems that $n$ is supposed to be difficult to factor. This puts it in the range of $2048$-bit length and more, i.e. $n\approx 2^{2048}$. For this kind of number, $\sqrt n$ becomes $\approx 2^{1024}$ and $1/2^{1024}$ is small enough to safely be ignored. As a related example: It is ridiculously more likely to guess a random 256-bit AES key first try than to hit a $1/2^{1024}$ chance.

For a more theoretical treatment: $1$ in $\sqrt n$ belongs to what cryptographers call a negligible function which is the common measure used to gauge whether it's acceptable for an intelligent adversary to have this kind of success probability (with negligible function in the bit length of the secret = secure).

0 + 0
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.