MarriageTheoremのこと

_ プレプリント確認状況：arXiv:math 2012年2月23日分まで、arXiv:quant-ph 2012年5月31日分まで、IACR ePrint：2012/250まで

_ 気になった論文その１："Cryptography from tensor problems"（Leonard J. Schulman, IACR ePrint 2012/244）

We describe a new proposal for a trap-door one-way function. The new proposal belongs to the ``multivariate quadratic'' family but the trap-door is different from existing methods, and is simpler.
Known quantum algorithms do not appear to help an adversary attack this trap-door. (Beyond the asymptotic square-root-speedup which applies to all oracle search problems.)

_ 気になった論文その２："A Secret Sharing Scheme Based on Group Presentations and the Word Problem"（Maggie Habeeb and Delaram Kahrobaei and Vladimir Shpilrain, IACR ePrint 2012/246）

A $(t,n)$-threshold secret sharing scheme is a method to distribute a secret among $n$ participants in such a way that any $t$ participants can recover the secret, but no $t-1$ participants can. In this paper, we propose two secret sharing schemes using non-abelian groups. One scheme is the special case where all the participants must get together to recover the secret. The other one is a $(t,n)$-threshold scheme that is a combination of Shamir's scheme and the group-theoretic scheme proposed in this paper.

_ 気になった論文その３："Binary and q-ary Tardos codes, revisited"（Boris Skoric and Jan-Jaap Oosterwijk, IACR ePrint 2012/249）

The Tardos code is a much studied collusion-resistant fingerprinting code, with the special property that it has asymptotically optimal length $m\propto c_0^2$, where $c_0$ is the number of colluders.
In this paper we simplify the security proofs for this code, making use of the Bernstein inequality and Bennett inequality instead of the typically used Markov inequality. This simplified proof technique also slightly improves the tightness of the bound on the false negative error probability. We present new results on code length optimization, for both small and asymptotically large coalition sizes.