MarriageTheoremのこと

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

_ 気になった論文1：Random Digit Representation of Integers, Nicolas Meloni and M. Anwar Hasan, http://eprint.iacr.org/2015/622

Modular exponentiation is core to today's main stream public key cryptographic systems. In this article, we generalize the classical fractional $w$NAF method for modular exponentiation -- the classical method uses a digit set of the form $\{1,3,\dots,m\}$ which is extended here to any set of odd integers of the form $\{1,d_2,\dots, d_n\}$. We give a formula for the average density of non-zero terms in this new representation and discuss its asymptotic behavior when those digits are randomly chosen from a given set. We also propose a specific method for the precomputation phase of the exponentiation algorithm.

_ 気になった論文2：Phasing: Private Set Intersection using Permutation-based Hashing, Benny Pinkas and Thomas Schneider and Gil Segev and Michael Zohner, http://eprint.iacr.org/2015/634

Private Set Intersection (PSI) allows two parties to compute the intersection of private sets while revealing nothing more than the intersection itself. PSI needs to be applied to large data sets in scenarios such as measurement of ad conversion rates, data sharing, or contact discovery. Existing PSI protocols do not scale up well, and therefore some applications use insecure solutions instead. We describe a new approach for designing PSI protocols based on permutation-based hashing, which enables to reduce the length of items mapped to bins while ensuring that no collisions occur. We denote this approach as Phasing, for Permutation-based Hashing Set Intersection. Phasing can dramatically improve the performance of PSI protocols whose overhead depends on the length of the representations of input items. We apply Phasing to design a new approach for circuit-based PSI protocols. The resulting protocol is up to 5 times faster than the previously best Sort-Compare-Shuffle circuit of Huang et al. (NDSS 2012). We also apply Phasing to the OT-based PSI protocol of Pinkas et al. (USENIX Security 2014), which is the fastest PSI protocol to date. Together with additional improvements that reduce the computation complexity by a logarithmic factor, the resulting protocol improves run-time by a factor of up to 20 and can also have similar communication overhead as the previously best PSI protocol in that respect. The new protocol is only moderately less efficient than an insecure PSI protocol that is currently used by real-world applications, and is therefore the first secure PSI protocol that is scalable to the demands and the constraints of current real-world settings.

_ 気になった論文3：Noise-free Symmetric Fully Homomorphic Encryption based on noncommutative rings, Jing Li and Licheng Wang, http://eprint.iacr.org/2015/641

In this paper, we propose a noise-free symmetric fully homomorphic encryption (FHE) based on matrices over noncommutative rings. The scheme is secure against chosen plaintext attacks based on the factorization problem of matrices over noncommutative rings as well as the hardness of an overdefined system of multivariate polynomial equations over the given non-commutative algebraic structure. Meanwhile, the new proposal is efficient in terms of computational cost and the sizes of plaintext/ciphertext. On the basis of this framework, a verifiable FHE is proposed, where the receiver can check the validity of ciphertexts. Furthermore, any attacker fails to construct a valid ciphertext without making query of encryption oracle, then the verifiable FHE scheme maybe secure against non-adaptively chosen ciphertext attacks (IND-CCA1).