MarriageTheoremのこと

_ IACR ePrint 2014/599まで確認済み、ECCC 2003年分まで確認済み

_ 気になった論文1：Implicit factorization of unbalanced RSA moduli, Abderrahmane Nitaj and Muhammad Rezal Kamel Ariffin, http://eprint.iacr.org/2014/548

Let N1 = p1q1 and N2 = p2q2 be two RSA moduli, not necessarily of the same bit-size. In 2009, May and Ritzenhofen proposed a method to factor N1 and N2 given the implicit information that p1 and p2 share an amount of least significant bits. In this paper, we propose a generalization of their attack as follows: suppose that some unknown multiples a1p1 and a2p2 of the prime factors p1 and p2 share an amount of their Most Significant Bits (MSBs) or an amount of their Least Significant Bits (LSBs). Using a method based on the continued fraction algorithm, we propose a method that leads to the factorization of N1 and N2. Using simultaneous diophantine approximations and lattice reduction, we extend the method to factor k  3 RSA moduli Ni = piqi, i = 1, . . . , k given the implicit information that there exist unknown multiples a1p1, . . . , akpk sharing an amount of their MSBs or their LSBs. Also, this paper extends many previous works where similar results were obtained when the pi’s share their MSBs or their LSBs.

_ 気になった論文2：On Virtual Grey Box Obfuscation for General Circuits, Nir Bitansky and Ran Canetti and Yael Tauman-Kalai and Omer Paneth, http://eprint.iacr.org/2014/554

An obfuscator $\O$ is Virtual Grey Box (VGB) for a class $\C$ of circuits if, for any $C\in\C$ and any predicate $\pi$, deducing $\pi(C)$ given $\O(C)$ is tantamount to deducing $\pi(C)$ given unbounded computational resources and polynomially many oracle queries to $C$. VGB obfuscation is often significantly more meaningful than indistinguishability obfuscation (IO). In fact, for some circuit families of interest VGB is equivalent to full-fledged Virtual Black Box obfuscation.

We investigate the feasibility of obtaining VGB obfuscation for general circuits. We first formulate a natural strengthening of IO, called {\em strong IO} (SIO). Essentially, $\O$ is SIO for class $\C$ if $\O(C)\approx\O(C')$ whenever the pair $(C,C')$ is taken from a distribution over $\C$ where, for all $x$, $C(x)\neq C'(x)$ only with negligible probability.

We then show that an obfuscator is VGB for a class $\C$ if and only if it is SIO for $\C$. This result is unconditional and holds for any $\C$. We also show that, for some circuit collections, SIO implies virtual black-box obfuscation.

Finally, we formulate a slightly stronger variant of the semantic security property of graded encoding schemes [Pass-Seth-Telang Crypto 14], and show that existing obfuscators, such as the obfuscator of Barak et al. [Eurocrypt 14], are SIO for all circuits in NC$^1$, assuming that the underlying graded encoding scheme satisfies our variant of semantic security.

{\em Put together, we obtain VGB obfuscation for all NC$^1$ circuits under assumptions that are almost the same as those used by Pass et al. to obtain IO for NC$^1$ circuits.} We also show that semantic security is in essence {\em necessary} for showing VGB obfuscation.

_ 某案件の面接審査。狙っていたわけではないのになぜか笑いがとれてしまった件。