密码学和生物信息学中两类组合构形研究

论文摘要

组合设计理论的发展已经和其他很多数学学科相互交融，比如群论、图论、数论、有限域和有限几何等等。同时，组合设计也在其他各个学科领域中得到了越来越多的应用，比如试验设计、编码、密码、计算机科学和生物信息技术等等。组合结构的引入为这些领域提供了强有力的工具。本文着重研究了混合函数和格子区组的存在性。这两种组合结构分别来源于密码学和分子生物学的应用问题。为了扩展密码系统的消息空间，同时还要保持系统的安全性，Ristenpart和Rogaway定义了混合函数，用于混合来源于同一个集合的两个输入。Stinson扩展了混合函数的定义，使得函数的两个输入可以来自不同大小的两个集合。同时，Stinson还给出了广义混合函数的一般性构造，基本解决了广义混合函数的存在性问题（剩下10个参数没有解决）。在本文中，我们通过直接构造和递归构造的方法，证明了广义混合函数在这10个参数下也是存在的。在分子生物学里，群试是一个试验设计的基本工具。例如，用来有效的在DNA库中筛选出包含某些特定因子的正的克隆。格子区组设计正是诞生于此，这个概念第一次由Fu，Hang，Jimbo，Mutohand和Shiue提出。因为格子区组在DNA库筛选中的高效率性和方便性，使得越来越多的人对它感兴趣，从而对它进行广泛地研究。本文列出了在格子区组存在性研究中的一些主要结果，并着重对可分解的D3×3（Ks（9））的存在性进行了研究。可分解D3×3（Ks（9））存在的必要条件是s≡1（mod 4）。我们先利用差方法构造了几个必要的小参数设计，再利用这些设计递归构造证明了当s=8n+1，其中n（?）{2，3，6}时，可分解D3×3（Ks（9））的存在性。对于s=17，25，49，以及s=8n+5时的情形，我们已经得到了一些关键的设计，整个问题的解决还需要继续研究。

论文目录

• 摘要
• Abstract
• Table of Contents
• 1 Generalized Mix Function with Applications to Cryptography
• 1.1 Introduction
• 1.1.1 Domain Extension of a Cipher
• 1.1.2 Mix Function
• 1.1.3 Generalized Mix Function
• 1.2 The Existence and Construction of Generalized Mix Functions
• 1.2.1 Known Results and Theorems
• 1.2.2 Direct Construction
• 1.2.3 Recursive Construction
• 1.2.4 Conclusion
• 2 Grid-Block Designs with Applications to Bioinformatics
• 2.1 Introduction
• 2.1.1 Group Testing
• 2.1.2 Applications in Molecular Biology
• 2.2 Grid-Block Design
• 2.2.1 Some Known Results for the Existence of Grid-block Designs
• 2.2.2 Group Divisible Grid-block Design and Some Useful Designs
• 3×3（K_s（9））s'>2.3 The Existence of Resolvable D_3×3（K_s（9））s
• 2.3.1 Some Crucial Small Designs
• 3×3（K_s（9））s When s ≡ 1 （mod 8）'>2.3.2 The Existence of Resolvable D_3×3（K_s（9））s When s ≡ 1 （mod 8）
• 3×3（K_s（t））s Related to the Existence of Resolvable D_3×3（K_s（9））s'>2.3.3 Other FD_3×3（K_s（t））s Related to the Existence of Resolvable D_3×3（K_s（9））s
• Concluding Remarks
• Publication in Master Stage
• Bibliography
• Acknowledgement