1
$\begingroup$

Denote $\mathcal N_r=\{n\in\mathbb Z:\exists\mbox{ distinct equal bit primes }p_1,\dots,p_r:n=p_1p_2\dots p_{r-1}p_r\}$.

$\mathcal N_1$ refers to primes and $\mathcal N_2$ referes to balanced semiprimes used in $RSA$.

  1. Does $\mathcal N_{2^t}$ at $t\in\mathbb N_{>1}$ help beyond single user-single receiver secret channel establishment?

  2. Is there good references?

$\endgroup$
6
  • 1
    $\begingroup$ Does it help ... what, exactly? The question is not clear. $\endgroup$ Commented Aug 7, 2018 at 22:44
  • $\begingroup$ @GerryMyerson Is there a multiparty protocol? In Diffie-Hellman extending to three party is straightforward. $\endgroup$
    – Turbo
    Commented Aug 8, 2018 at 4:31
  • $\begingroup$ i don't know why answer below is getting upvote. This answer was pulled up from crypto.stackexchange.com/questions/11287/…. $\endgroup$
    – Turbo
    Commented Aug 8, 2018 at 8:34
  • $\begingroup$ 'Having more than two prime factors is already supported by the PKCS#1 standard. This is called a "multiprime RSA" algorithm. On the plus size, this may offer some computational performance improvement via the Chinese Remainder Theorem. For instance, if you use a modulus with $k$ factors, the CRT speedup factor is about $k^2.$ However, using too small factors may weaken the modulus. $\endgroup$
    – Turbo
    Commented Aug 8, 2018 at 8:35
  • $\begingroup$ The best known factorization algorithms depend only on the modulus unless the factors are small enough to enter the range feasible with Elliptic Curve Multiplication which has a cost which depends (mostly) on the size of the smallest factor. More generally, a batch RSA algorithm (not multiprime RSA) can be used to speed up batch processing of many RSA signatures at once in a server setting, with substantial speedups. The paper by Boneh and Scacham [here][1] describes these ideas. [1]: hovav.net/ucsd/dist/survey.pdf' $\endgroup$
    – Turbo
    Commented Aug 8, 2018 at 8:35

1 Answer 1

4
$\begingroup$

Having more than two prime factors is already supported by the PKCS#1 standard. This is called a "multiprime RSA" algorithm.

On the plus size, this may offer some computational performance improvement via the Chinese Remainder Theorem. For instance, if you use a modulus with $k$ factors, the CRT speedup factor is about $k^2.$

However, using too small factors may weaken the modulus. The best known factorization algorithms depend only on the modulus unless the factors are small enough to enter the range feasible with Elliptic Curve Multiplication which has a cost which depends (mostly) on the size of the smallest factor.

More generally, a batch RSA algorithm (not multiprime RSA) can be used to speed up batch processing of many RSA signatures at once in a server setting, with substantial speedups. The paper by Boneh and Scacham here describes these ideas.

$\endgroup$
4
  • $\begingroup$ Problem here is whether it helps multiparty secret channel establishment. $\endgroup$
    – Turbo
    Commented Aug 8, 2018 at 4:25
  • $\begingroup$ i don't know why this answer is getting upvote. This answer was pulled up from crypto.stackexchange.com/questions/11287/…. Even there is a typo 'size' should be 'side' (same typo in other answer). I do not know where batch RSA was taken from. It comes no close to answering the problem. At least post from where the answer was taken so people can follow up. $\endgroup$
    – Turbo
    Commented Aug 8, 2018 at 8:39
  • $\begingroup$ If the answer doesn't come close to answering the question, it might be that the question is unclear. $\endgroup$ Commented Aug 8, 2018 at 8:45
  • $\begingroup$ What is unclear here? It says 'help beyond single user-single receiver secret channel establishment?' (the context is clear $\mathcal N_2$ helps single user-single receiver channel establishment which has been known at least since $70$s as 'the RSA' algorithm). $\endgroup$
    – Turbo
    Commented Aug 8, 2018 at 8:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .