Martin-Lof ランダムネスとは、確率過程から得られたデータ系列がランダムであるか否かを、アルゴリズムの観点から特徴づけたものである。Martin-Lof ランダムな系列の全体の集合は確率測度１を持つが、それでは、確率１で成立する種々の確率法則を、「すべての Martin-Lof ランダムな系列に対して成立する」という形の表現に拡張することは可能であろうか。実際、独立同分布過程における「大数の強法則」や「重複対数の法則」などではこの拡張は比較的容易であるが、一般の確率過程においては困難な問題である。本発表では、V'yugin による Shannon-McMillan-Breiman 定理の拡張を、有限次マルコフ近似を用いることによって別証明を与える。また、ユニバーサルデータ圧縮法の原理をなす Wyner-Ziv-Ornstein-Weiss の再帰時間定理についても、順定理部分においてランダム系列版への拡張を行う。

昼食

Oblivious Transfer (OT) and Bit Commitment (BC) appear to be fundamental in the cryptographic protocol design. These are important tools for providing privacy in secure computation between two parties who do not trust each other. OT is about transmitting data such that the sender is guaranteed that the data will be partially erased during the transmission, but he does not know what exactly the receiver gets. BC scheme is a tool for transmitting an evidence about a piece of information such that the receiver cannot learn it without the sender's help, while the sender cannot open something different from what he had committed to.

Secure two-party computation can be build based on OT, while BC implies zero-knowledge proofs. We shall consider implementations of OT and BC with unconditional (aka information-theoretic) security for both parties. Unconditional security provides protection against computationally unbounded adversaries, hence it does not depend on unproven intractability assumptions like integer factoring or discrete logarithm.

It is well known that unconditional security cannot be provided for both parties "from scratch", i.e. based on noiseless communication and local randomness. Some restriction on the parties' communication/ abilities must be imposed. We assume that they are connected by a noisy channel. This is a very natural assumption since noise is inherently present in any real communication. Hence, the noise turns out to be an ally of cryptographers while being an enemy of telecommunication engineers.

Our talk is organised as follows:
-) Introduction of oblivious transfer and bit commitment and their security definitions
-) Motivation on why these protocols are important
-) History of development for this research area (constructions for
BC and OT based on various noisy channel models; variants of BC and OT; reductions between these variants and noisy primitives)
-) Mathematical background and useful tools: privacy amplification, universal hashing, error correcting codes
-) Some constructions for BC and OT
-) Current research in this area
-) Open questions