MarriageTheoremのこと

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

_ 気になった論文１：Factoring N=p^r q^s for Large r and s, Jean-Sebastien Coron and Jean-Charles Faugere and Guenael Renault and Rina Zeitoun, http://eprint.iacr.org/2015/071

Boneh et al. showed at Crypto 99 that moduli of the form N=p^r q can be factored in polynomial time when r=log p. Their algorithm is based on Coppersmith's technique for finding small roots of polynomial equations. In this paper we show that N=p^r q^s can also be factored in polynomial time when r or s is at least (log p)^3; therefore we identify a new class of integers that can be efficiently factored. We also generalize our algorithm to moduli N with k prime factors; we show that a non-trivial factor of N can be extracted in polynomial-time if one of the k exponents is large enough.

_ 気になった論文２：Re-encryption Verifiability: How to Detect Malicious Activities of a Proxy in Proxy Re-encryption, Satsuya Ohata and Yutaka Kawai and Takahiro Matsuda and Goichiro Hanaoka and Kanta Matsuura, http://eprint.iacr.org/2015/112

In this paper, we introduce a new functionality for proxy re-encryption (PRE) that we call re-encryption verifiability. In a PRE scheme with re-encryption verifiability (which we simply call verifiable PRE, or VPRE), a receiver of a re-encrypted ciphertext can verify whether the received ciphertext is correctly transformed from an original ciphertext by a proxy, and thus can detect illegal activities of the proxy. We formalize the security model for a VPRE scheme, and show that the single-hop uni-directional PRE scheme by Hanaoka et al. (CT-RSA 2012) can be extended to a secure VPRE scheme.

_ 気になった論文３：Constructing and Understanding Chosen Ciphertext Security via Puncturable Key Encapsulation Mechanisms, Takahiro Matsuda and Goichiro Hanaoka, http://eprint.iacr.org/2015/118

In this paper, we introduce and study a new cryptographic primitive that we call "puncturable key encapsulation mechanism" (PKEM), which is a special class of KEMs that satisfy some functional and security requirements that, combined together, imply chosen ciphertext security (CCA security). The purpose of introducing this primitive is to capture certain common patterns in the security proofs of the several existing CCA secure public key encryption (PKE) schemes and KEMs based on general cryptographic primitives which (explicitly or implicitly) use the ideas and techniques of the Dolev-Dwork-Naor (DDN) construction (STOC'91), and "break down" the proofs into smaller steps, so that each small step is easier to work with/verify/understand than directly tackling CCA security.

To see the usefulness of PKEM, we show (1) how several existing constructions of CCA secure PKE/KEM constructed based on general cryptographic primitives can be captured as a PKEM, which enables us to understand these constructions via a unified framework, (2) its connection to detectable CCA security (Hohenberger et al. EUROCRYPT'12), and (3) a new security proof for a KEM-analogue of the DDN construction from a set of assumptions: "sender non-committing encryption" (SNCE) and non-interactive witness indistinguishable proofs.

Then, as our main technical result, we show how to construct a PKEM satisfying our requirements (and thus a CCA secure KEM) from a new set of general cryptographic primitives: "SNCE" and "symmetric key encryption secure for key-dependent messages" (KDM secure SKE). Our construction realizes the "decrypt-then-re-encrypt"-style validity check of a ciphertext which is powerful but in general has a problem of the circularity between a plaintext and a randomness.We show how SNCE and KDM secure SKE can be used together to overcome the circularity. We believe that the connection among three seemingly unrelated notions of encryption primitives, i.e. CCA security, the sender non-committing property, and KDM security, to be of theoretical interest.