MarriageTheoremのこと

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

_ 見つけた論文：The ElGamal cryptosystem over circulant matrices（Ayan Mahalanobis, arXiv:1109.6416）

Can one use the discrete logarithm problem in matrix groups, to build a better and secure cryptosystem? We argue, it is indeed the case. This makes the group of circulant matrices suitable and attractive for lightweight cryptography.

（追記：IACR ePrintにも同じ論文が上がっていた。ちなみに中身はまだ読んでいない。）

_ ↑ざっと読んでみたが、Theorem 1（暗号方式の一方向性が考えている群上のDH問題と等価だと主張している定理）の証明が怪しいように見えてしまう。本当に大丈夫なんだろうか。

_ ついでに見つけた別の論文：Homomorphic encryption from codes（Andrej Bogdanov and Chin Ho Lee, IACR ePrint 2011/622）。

Abstract: We propose a new homomorphic encryption scheme based on the hardness of decoding under independent random noise from certain affine families of codes. Unlike in previous lattice-based homomorphic encryption schemes, where the message is hidden in the noisy part of the ciphertext, our scheme carries the message in the affine part of the transformation and applies noise only to achieve security. Our scheme can tolerate noise of arbitrary magnitude, as long as the noise vector has sufficiently small hamming weight (and its entries are independent).

Our design achieves "proto-homomorphic" properties in an elementary manner: message addition and multiplication are emulated by pointwise addition and multiplication of the ciphertext vectors. Moreover, the extremely simple nature of our decryption makes the scheme easily amenable to bootstrapping. However, some complications are caused by the inherent presence of noticeable encryption error. Our main technical contribution is the development of two new techniques for handling this error in the homomorphic evaluation process.

We also provide a definitional framework for homomorphic encryption that may be useful elsewhere.

STOC 2012の採録論文リストに同じ名前と同じ著者の論文があったので、それのプレプリント版ということなのだろう。

_ 「大学生数学基本調査」私案

以前の日記にも書いた日本数学会「「大学生数学基本調査」に基づく数学教育への提言」の件。私に限らず色々な方々が設問についてツッコミを入れているけれども、批判するだけなのもどうかと思ったので、私なりに書き換えた設問の案を以下に記しておくことにする。
なお、設問の内容や題材の選択にも思うところはあるのだが、その点は出題者の意思を尊重して、設問の内容そのものは極力もとの設問に沿うよう心がけた（が、どうしても納得できない点については変更を加えてある）。

1-1 カードが100枚あり、それぞれ1から9までの整数のどれかが書かれています。カードに書かれた数字の平均を計算すると、ちょうど5になりました。この結果から確実に正しいといえることには○を、そうでないものには×を記入し、そう考えた理由を下の空欄で説明して下さい。（記入欄は省略。以下同様。）
(1) 数字が5より小さいカードと5より大きいカードは同じ枚数だけある。
(2) カード100枚の数字の合計は、5 × 100 = 500 に等しい。
(3) カード100枚を、書かれた数字によって「1か2か3」「4か5か6」「7か8か9」の三つの組に分けると、「4か5か6」の組のカードが最も多い。

1-2 次の報告から確実に正しいといえることには○を、そうでないものには×を記入して下さい。（追記）また、そう考えた理由を空欄で説明して下さい。（追記終わり）
「教室の中の男の子たちと女の子たちが、それぞれ前か後ろを向いて座っています。後ろを向いている子供はみんな女の子です。そして、本を読んでいる男の子は一人もいません。」
(1) 男の子はみんな前を向いている。
(2) 前を向いている女の子はいない。
(3) 前を向いていて、しかも本を読んでいる子供は、一人もいない。

2-1 偶数と奇数を一つずつたすと、答えはどうなるかを考えます。
(1) 偶数や奇数とはどのような数でしょうか。それぞれ、定義を空欄に記入して下さい。
(2) 偶数と奇数を一つずつたすと、答えはどうなるでしょうか。次の選択肢のうち正しいものに○を記入し、そうなる理由を空欄で説明して下さい。
(a) いつも必ず偶数になる。
(b) いつも必ず奇数になる。
(c) 偶数になることも奇数になることもある。

2-2 2次関数 $y = -x^2 + 6x - 8$ のグラフを、なるべくその形や位置関係がわかりやすいように描くとしたら、あなたはこのグラフのどのような特徴に注目して図を描きますか。その特徴を三つ答えて下さい。

3 右の図の線分を、正確に3等分したいと思います。定規（直線を引くのに使います）とコンパス（円を描くのに使います）を使ってそのような作図をする手順を、箇条書きにしてわかりやすく説明して下さい。ただし、図形の実際の長さや幅などを測ってはいけません。なお、説明に図を使う場合は、正確でなくても大まかな形を描くだけでかまいません。

そこまで精読していないので誤字などはご容赦ください（ご指摘いただければ直します）。
（追記）ちなみに、twitterでも書いたのだが、本当に実効性のある調査をするためには、対象となる大学生だけでなく、当然に「数学的能力がある」と看做されるべき比較対象群、例えば理系専門職従事者にも同じ調査を行うべきと思う。もし後者の集団の正答率が悪いとしたら、後者の集団の数学的能力が低い可能性よりも、設問が数学的能力を問うには不適切であった可能性が高いだろうから。
（追記）設問を少し直しました。