基于自证明公钥和零知识证明的身份认证协议

在分析几种典型零知识身份认证协议的基础上,利用Girault自证明公钥原理、结合椭圆曲线公钥密码的优点提出一种基于自证明公钥和零知识证明的身份认证协议,并为协议增加了密钥协商功能。分析表明该方案具有较高的安全性,与同类方案相比,该方案对存储空间、网络通信量和计算开销的要求较低,有较高的效率。     

面向HDFS的可证明安全的单点登录协议

针对Hadoop Distributed File System（HDFS）的安全机制中密钥管理复杂、用户需进行多次身份认证的问题,提出一个适合HDFS的基于身份的单点登录协议。协议采用了基于身份的密码技术实现了用户的单点登录,同时根据各个节点上一次为用户提供服务的情况对用户登录票据的流转过程进行了优化,并且运用Capser形式化证明工具对协议的安全性进行了证明。协议降低了HDFS在密钥管理上的开销,解决了用户访问HDFS可能需要频繁认证的问题,提高了登录票据流转的效率,同时协议还具有较高的安全性。理论分析和安全性验证表明,本协议对HDFS的安全高效运行有较大的帮助。     

Tuples of Disjoint $\mathsf{NP}$ -Sets

Disjoint -pairs are a well studied complexity-theoretic concept with important applications in cryptography and propositional proof complexity. In this paper we introduce a natural generalization of the notion of disjoint -pairs to disjoint k-tuples of -sets for k≥2. We define subclasses of the class of all disjoint k-tuples of -sets. These subclasses are associated with a propositional proof system and possess complete tuples which are defined from the proof system. In our main result we show that complete disjoint -pairs exist if and only if complete disjoint k-tuples of -sets exist for all k≥2. Further, this is equivalent to the existence of a propositional proof system in which the disjointness of all k-tuples is shortly provable. We also show that a strengthening of this conditions characterizes the existence of optimal proof systems. An extended abstract of this paper appeared in the proceedings of the conference CSR 2006 (Lecture Notes in Computer Science 3967, 80–91, 2006). Supported by DFG grant KO 1053/5-1.     

Supporting students’ participation in authentic proof activities in computer supported collaborative learning (CSCL) environments

In this paper, I review both mathematics education and CSCL literature and discuss how we can better take advantage of CSCL tools for developing mathematical proof skills. I introduce a model of proof in school mathematics that incorporates both empirical and deductive ways of knowing. I argue that two major forces have given rise to this conception of proving: a particular learning perspective promoted in reform documents and a genre of computer tools, namely dynamic geometry software, which affords this perspective of learning within the context of mathematical proof. Tracing the move from absolutism to fallibilism in the philosophy of mathematics, I highlight the vital role of community in the production of mathematical knowledge. This leads me to an examination of a certain CSCL tool whose design is guided by knowledge-building pedagogy. I argue that knowledge building is a suitable pedagogical approach for the proof model presented in this paper. Furthermore, I suggest software modifications that will better support learners’ participation in authentic proof tasks.     

Classical Modal Display Logic in the Calculus of Structures and Minimal Cut-free Deep Inference Calculi for S5

We begin by showing how to faithfully encode the Classical ModalDisplay Logic (CMDL) of Wansing into the Calculus of Structures(CoS) of Guglielmi. Since every CMDL calculus enjoys cut-elimination,we obtain a cut-elimination theorem for all corresponding CoScalculi. We then show how our result leads to a minimal cut-freeCoS calculus for modal logic S5. No other existing CoS calculifor S5 enjoy both these properties simultaneously.     

Implementing tactics and tacticals in a higher-order logic programming language

We argue that a logic programming language with a higher-order intuitionistic logic as its foundation can be used both to naturally specify and implement tactic-style theorem provers. The language extends traditional logic programming languages by replacing first-order terms with simply-typed -terms, replacing first-order unification with higher-order unification, and allowing implication and universal quantification in queries and the bodies of clauses. Inference rules for a variety of inference systems can be naturally specified in this language. The higher-order features of the language contribute to a concise specification of provisos concerning variable occurrences in formulas and the discharge of assumptions present in many inference systems. Tactics and tacticals, which provide a framework for high-level control over search for proofs, can be directly and naturally implemented in the extended language. This framework serves as a starting point for implementing theorem provers and proof systems that can integrate many diversified operations on formulas and proofs for a variety of logics. We present an extensive set of examples that have been implemented in the higher-order logic programming language Prolog.     

Exponential lower bounds for the pigeonhole principle

In this paper we prove an exponential lower bound on the size of bounded-depth Frege proofs for the pigeonhole principle (PHP). We also obtain an (loglogn)-depth lower bound for any polynomial-sized Frege proof of the pigeonhole principle. Our theorem nearly completes the search for the exact complexity of the PHP, as S. Buss has constructed polynomial-size, logn-depth Frege proofs for the PHP. The main lemma in our proof can be viewed as a general Håstad-style Switching Lemma for restrictions that are partial matchings. Our lower bounds for the pigeonhole principle improve on previous superpolynomial lower bounds.