MarriageTheoremのこと

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

_ 気になった論文1：Survey on Cryptographic Obfuscation, Máté Horváth, http://eprint.iacr.org/2015/412

The recent result of Garg et al. (FOCS 2013) changed the previously pessimistic attitude towards general purpose cryptographic obfuscation. Since their first candidate construction, several authors proposed newer and newer schemes with more persuasive security arguments and better efficiency. At the same time, indistinguishability obfuscation proved its extreme usefulness by becoming the basis of many solutions for long-standing open problems in cryptography e.g. functional or witness encryption and others. In this survey, we give an overview of recent research, focusing on the theoretical results on general purpose obfuscation, particularly, indistinguishability obfuscation.

_ 気になった論文2：Conversions among Several Classes of Predicate Encryption and Their Applications, Shota Yamada and Nuttapong Attrapadung and Goichiro Hanaoka, http://eprint.iacr.org/2015/431

Predicate encryption is an advanced form of public-key encryption that yield high flexibility in terms of access control. In the literature, many predicate encryption schemes have been proposed such as fuzzy-IBE, KP-ABE, CP-ABE, (doubly) spatial encryption (DSE), and ABE for arithmetic span programs. In this paper, we study relations among them and show that some of them are in fact equivalent by giving conversions among them. More specifically, our main contributions are as follows:

- We show that monotonic, small universe KP-ABE (CP-ABE) with bounds on the size of attribute sets and span programs (or linear secret sharing matrix) can be converted into DSE. Furthermore, we show that DSE implies non-monotonic CP-ABE (and KP-ABE) with the same bounds on parameters. This implies that monotonic/non-monotonic KP/CP-ABE (with the bounds) and DSE are all equivalent in the sense that one implies another.

- We also show that if we start from KP-ABE without bounds on the size of span programs (but bounds on the size of attribute sets), we can obtain ABE for arithmetic span programs. The other direction is also shown: ABE for arithmetic span programs can be converted into KP-ABE.These results imply, somewhat surprisingly, KP-ABE without bounds on span program sizes is in fact equivalent to ABE for arithmetic span programs, which was thought to be more expressive or at least incomparable.

By applying these conversions to existing schemes, we obtain many non-trivial consequences. We obtain the first non-monotonic, large universe CP-ABE (that supports span programs) with constant-size ciphertexts, the first ABE for arithmetic span programs with adaptive security, the first ciphertext-policy version of ABE for arithmetic span programs, the first KP-ABE with constant-size private keys, and even more.

We also obtain the first attribute-based signature scheme that supports non-monotone span programs and achieves constant-size signatures via our technique.