Certain sequence of arithmetic progressions and a new key sharing method (Q2202903): Difference between revisions

Let \(A(x, y)\) denote an arithmetic progression with leading term \(x\), and common difference \(y\). The paper under review deals with sequences of arithmetic progressions, \( \langle A(a_0, d_0), A(a_1, d_1), \ldots \rangle\) satisfying the following property: \((a_i + jd_i)(a_i+1 + jd_i+1) \equiv 1\ (\bmod\ a_i + (j + 1)d_i)\). If the common differences \(d_i\) are in decreasing order, the above sequence is uniquely defined for pair of co-prime numbers \((a_0, d_0)\). We denote this unique sequence of progressions by \(G(a_0, d_0)\). In this case the sequence consists only of finitely many distinct arithmetic progressions. Certain consecutive progressions of the \(G(a_0, d_0)\) follow an additive property which lead to define a computational problem (CHP) which it is shown that it is equivalent to the computation of modular square roots of a quadratic residue of the form \(x^2+4y\). Since square root computations modulo an integer \(n\) and factoring \(n\) (i.e, IFP problem) are (probabilistic) equivalent, a computational (probabilistic) equivalence between CHP and IFP is obtained. As an application of this equivalence, a method for sharing random keys securely between users is proposed and a comparison with RSA and Rabin systems is given. Moreover, the advantages of the method, and its potential use-case in the post quantum scenario are discussed.