基于ECC的广义门限签密方案设计

为了满足群组之间相互通信时同时需要加密和认证的要求,设计了一个基于椭圆曲线密码体制的广义门限签密方案,该方案能够同时实现,门限签密和,门限共享解签密。在门限共享解签密阶段,利用Chaum-Pedersen离散对数等式知识证明协议的思想实现了对群组成员中恶意成员的检测。通过对该方案进行的安全性分析和效率分析结果表明,该方案可以用较小的计算代价和通信代价安全地实现群组通信中的保密和认证。     

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

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

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.