MarriageTheoremのこと

_ IACR ePrint 2015/411まで確認済み、ECCC 2003年分まで確認済み

_ 気になった論文1：Factoring RSA moduli with weak prime factors, Abderrahmane Nitaj and Tajjeeddine Rachidi, http://eprint.iacr.org/2015/398

In this paper, we study the problem of factoring an RSA modulus $N=pq$ in polynomial time, when $p$ is a weak prime, that is, $p$ can be expressed as $ap=u_0+M_1u_1+\ldots+M_ku_k$ for some $k$ integers $M_1,\ldots, M_k$ and $k+2$ suitably small parameters $a$, $u_0,\ldots u_k$. We further compute a lower bound for the set of weak moduli, that is, moduli made of at least one weak prime, in the interval $[2^{2n},2^{2(n+1)}]$ and show that this number is much larger than the set of RSA prime factors satisfying Coppersmith's conditions, effectively extending the likelihood for factoring RSA moduli. We also prolong our findings to moduli composed of two weak primes.

_ 気になった論文2：New attacks on RSA with Moduli $N=p^rq$, Abderrahmane Nitaj and Tajjeeddine Rachidi, http://eprint.iacr.org/2015/399

We present three attacks on the Prime Power RSA with modulus $N=p^rq$. In the first attack, we consider a public exponent $e$ satisfying an equation $ex-\phi(N)y=z$ where $\phi(N)=p^{r-1}(p-1)(q-1)$. We show that one can factor $N$ if the parameters $|x|$ and $|z|$ satisfy $|xz|<N^\frac{r(r-1)}{(r+1)^2}$ thereby extending the recent results of Sakar~\cite{SARKAR}. In the second attack, we consider two public exponents $e_1$ and $e_2$ and their corresponding private exponents $d_1$ and $d_2$. We show that one can factor $N$ when $d_1$ and $d_2$ share a suitable amount of their most significant bits, that is $|d_1-d_2|<N^{\frac{r(r-1)}{(r+1)^2}}$. The third attack enables us to factor two Prime Power RSA moduli $N_1=p_1^rq_1$ and $N_2=p_2^rq_2$ when $p_1$ and $p_2$ share a suitable amount of their most significant bits, namely, $|p_1-p_2|<\frac{p_1}{2rq_1q_2}$.

_ 気になった論文3：Computation-Trace Indistinguishability Obfuscation and its Applications, Yu-Chi Chen and Sherman S. M. Chow and Kai-Min Chung and Russell W. F. Lai and Wei-Kai Lin and Hong-Sheng Zhou, http://eprint.iacr.org/2015/406

We introduce a new, instance-based notion of indistinguishability obfuscation, called computation-trace indistinguishability obfuscation (CiO), for (parallel) RAM computation. CiO only obfuscates a fixed, single computation instance, as opposed to iO which obfuscates a function on all input instances. Specifically, for $\Pi$ defined by (P, x) consisting of a (parallel) RAM program P and an input x, the obfuscations of two instances $\Pi$ and $\Pi’$ are required to be indistinguishable only when the execution of $\Pi$ and $\Pi’$ generate an identical computation trace; namely, identical sequences of CPU states and memory content. On the other hand, we require the obfuscation to be (i) fully succinct: the runtime of the obfuscator (and thus the size of the obfuscated instance) depends only on the description and input/output size of $\Pi$, but is independent of the time and space complexities of $\Pi$, and (ii) efficiency preserving: the obfuscated instance is a (parallel) RAM program that preserves parallel/total time and space complexities of $\Pi$ up to polylogarithmic factors. As our main results, we construct CiO for parallel RAM (PRAM) computation based on iO for circuits and one-way functions, and demonstrate the power of CiO by the following applications. • With digital signatures, our CiO for PRAM immediately implies the first two-message (publicly- verifiable) delegation scheme for outsourcing PRAM computation, where the delegator’s runtime depends only on the program description and input/output size, and the server’s complexity matches the PRAM complexity of the computation up to polylogarithmic factors. • With public-key encryption, our CiO for PRAM, and a specific oblivious PRAM construction, we construct the first fully succinct randomized encoding (RE) for PRAM computation, where the encoder’s runtime (and thus the encoding size) depends only on the program description and input/output size, and the decoding complexity matches PRAM complexity of the computation up to polylogarithmic factors. • By plugging our fully succinct RE for PRAM into existing transformations, we obtain the first constructions of several cryptographic primitives for PRAM, such as functional encryptions with succinct (PRAM) function keys, succinct reusable garbling schemes, and succinct indistinguishability obfuscations (the later requires sub-exponential security). Notably, this implies that, while CiO is weaker than iO, sub-exponentially secure CiO for PRAM implies sub-exponentially secure iO for PRAM.