MarriageTheoremのこと

_ プレプリント確認状況：arXiv:math 7月8日分まで、IACR ePrint 2012/545まで

_ 気になった論文１：Enhanced Chosen-Ciphertext Security and Applications (Dana Dachman-Soled and Georg Fuchsbauer and Payman Mohassel and Adam O'Neill, IACR ePrint archive 2012/543)

We introduce and study a new notion of enhanced chosen-ciphertext security (ECCA) for public- key encryption. Loosely speaking, in ECCA, when the decryption oracle returns a plaintext to the adversary, it also provides coins under which the returned plaintext encrypts to the queried ciphertext (when they exist). Our results mainly concern the case where such coins can also be recovered efficiently. We provide constructions of ECCA encryption from adaptive trapdoor functions as defined by Kiltz et al. (EUROCRYPT 2010), resulting in ECCA encryption from standard number-theoretic assumptions. We then give two applications of ECCA encryption: (1) We use it as a unifying concept in showing equivalence of adaptive trapdoor functions and tag-based adaptive trapdoor functions (namely, we show that both primitives are equivalent to ECCA encryption), resolving a main open question of Kiltz et al. (2) We show that ECCA encryption can be used to securely realize an approach to public-key encryption with non-interactive opening (PKENO) suggested by Damg{\aa}rd and Thorbek (EUROCRYPT 2007), resulting in new and practical PKENO schemes quite different from those in prior work. We believe our results indicate that ECCA is an intriguing notion that may prove useful in further work.

_ 気になった論文２：Factoring integer using elliptic curves over rational number field $\mathbb{Q}$ (Xiumei Li, Jinxiang Zeng, arXiv:1207.0274)

For the integer $ D=pq$ of the product of two distinct odd primes, we construct an elliptic curve $E_{2rD}:y^2=x^3-2rDx$ over $\mathbb Q$, where $r$ is a parameter dependent on the classes of $p$ and $q$ modulo 8, and show, under the parity conjecture, that the elliptic curve has rank one and $v_p(x([k]Q))\not=v_q(x([k]Q))$ for odd $k$ and a generator $Q$ of the free part of $E_{2rD}(\mathbb Q)$. Thus we can recover $p$ and $q$ from the data $D$ and $ x([k]Q))$. Furthermore, under the Generalized Riemann hypothesis, we prove that one can take $r

_ 気になった論文３：Pseudo-finite hard instances for a student-teacher game with a Nisan-Wigderson generator (Jan Krajíček, arXiv:1207.0393)

For an NP intersect coNP function g of the Nisan-Wigderson type and a string b outside its range we consider a two player game on a common input a to the function. One player, a computationally limited Student, tries to find a bit of g(a) that differs from the corresponding bit of b. He can query a computationally unlimited Teacher for the witnesses of the values of constantly many bits of g(a). The Student computes the queries from a and from Teacher's answers to his previous queries. It was proved by Krajicek (2011) that if g is based on a hard bit of a one-way permutation then no Student computed by a polynomial size circuit can succeed on all a. In this paper we give a lower bound on the number of inputs a any such Student must fail on. Using that we show that there is a pseudo-finite set of hard instances on which all uniform students must fail. The hard-core set is defined in a non-standard model of true arithmetic and has applications in a forcing construction relevant to proof complexity.

_ 気になった論文４：A New Efficient Asymmetric Cryptosystem Based on the Square Root Problem (M. R. K. Ariffin, M. A. Asbullah, N. A. Abu, arXiv:1207.1157)

The square root modulo problem is a known primitive in designing an asymmetric cryptosystem. It was first attempted by Rabin. Decryption failure of the Rabin cryptosystem caused by the 4-to-1 decryption output is overcome efficiently in this work. The proposed scheme (known as the AA_\beta- cryptosystem) has its encryption speed having a complexity order faster than the Diffie-Hellman Key Exchange, El-Gammal, RSA and ECC. It can also transmit a larger data set securely when compared to existing asymmetric schemes. It has a simple mathematical structure. Thus, it would have low computational requirements and would enable communication devices with low computing power to deploy secure communication procedures efficiently.