Missing Proofs Found

For close to a century, despite the efforts of fine minds that include Hilbert and Ackermann, Tarski and Bernays, ukasiewicz, and Rose and Rosser, various proofs of a number of significant theorems have remained missing – at least not reported in the literature – amply demonstrating the depth of the corresponding problems. The types of such missing proofs are indeed diverse. For one example, a result may be guaranteed provable because of being valid, and yet no proof has been found. For a second example, a theorem may have been proved via metaargument, but the desired axiomatic proof based solely on the use of a given inference rule may have eluded the experts. For a third example, a theorem may have been announced by a master, but no proof was supplied. The finding of missing proofs of the cited types, as well as of other types, is the focus of this article. The means to finding such proofs rests with heavy use of McCune's automated reasoning program OTTER, reliance on a variety of powerful strategies this program offers, and employment of diverse methodologies. Here we present some of our successes and, because it may prove useful for circuit design and program synthesis as well as in the context of mathematics and logic, detail our approach to finding missing proofs. Well-defined and unmet challenges are included.     

Width versus size in resolution proofs

A general theme in the proof of lower bounds on the size of resolution refutations in propositional logic has been that of basing size lower bounds on lower bounds on the width of refutations. Ben-Sasson and Wigderson have proved a general width-size tradeoff result that can be used to prove many of the lower bounds on resolution complexity in a uniform manner. However, it does not apply directly to the well known pigeonhole clauses. The present paper generalizes their width-size tradeoff so that it applies directly to (a monotone transformation of) the pigeonhole clauses.     

Round-optimal zero-knowledge proofs of knowledge for NP

It is well known that all the known black-box zero-knowledge proofs of knowledge for NP are nonconstant-round.Whether there exit constant-round black-box zero-knowledge proofs of knowledge for all NP languages under certain standard assumptions is an open problem.This paper focuses on the problem and gives a positive answer by presenting two constructions of constant-round(black-box) zero-knowledge proofs of knowledge for the HC(hamiltonian cycle) problem.By the recent result of Katz,our second construction which relies on the existence of claw-free functions has optimal round complexity(5-round) assuming the polynomial hierarchy does not collapse.     

On constant-round concurrent non-malleable proof systems

Security under man-in-the-middle attacks is extremely important when protocols are executed on asynchronous networks, as the Internet. Focusing on interactive proof systems, one would like also to achieve unconditional soundness, so that proving a false statement is not possible even for a computationally unbounded adversarial prover. Motivated by such requirements, in this paper we address the problem of designing constant-round protocols in the plain model that enjoy simultaneously non-malleability (i.e., security against man-in-the-middle attacks) and unconditional soundness (i.e., they are proof systems).We first give a construction of a constant-round one-many (i.e., one honest prover, many honest verifiers) concurrent non-malleable zero-knowledge proof (in contrast to argument) system for every NP language in the plain model. We then give a construction of a constant-round concurrent non-malleable witness-indistinguishable proof system for every NP language. Compared with previous results, our constructions are the first constant-round proof systems that in the plain model guarantee simultaneously security against some non-trivial concurrent man-in-the-middle attacks and against unbounded malicious provers.     

Structuring Resolution Proofs by Introducing New Lemmata

Resolution proofs are unstructured by their very nature, since theycannot use substantial lemmata. To impose structure on given resolutionproofs and thereby improve their readability we will introduce new lemmatain a postprocessing step. As these lemmata cannot be generated byresolution, we will employ function introduction rules as presented by Baazand Leitsch and give a correct and complete criterion for theirapplicability to the proofs. Applying function introduction rules toresolution proofs enables us to detect and eliminate certain homomorphicsubproofs immune to the known redundancy elimination rules. For the caseswhen the criterion is satisfied we will characterize the transformation oftree resolution proofs to their condensation-reduced functional extensions,which may result in a double exponential reduction of proof height.Moreover, the proofs obtained by this transformation are more structured andhence more intelligible.     

Constant-round zero-knowledge proofs of knowledge with strict polynomial-time extractors for NP

Barak and Lindell showed that there exist constant-round zero-knowledge arguments of knowledge with strict polynomial-time extractors.This leaves the open problem of whether it is possible to obtain an analogous result regarding constant-round zero-knowledge proofs of knowledge for NP.This paper focuses on this problem and gives a positive answer by presenting a construction of constant-round zero-knowledge proofs of knowledge with strict polynomial-time extractors for NP.     

自计票电子投票方案的分析与改进

Kiayias和Yung首次提出了自计票电子投票方案,使得小规模电子选举不需要任何可信第三方参与,选举的行为公开可验证,有力地保证了选举的秘密性,Groth在此基础上做了改进,使得方案更简洁、高效;然而Groth方案仍只用于双候选人选举,且不允许两个选民同时投票.简要介绍并分析了Groth方案,针对上述两点不足给出改进建议,使新方案更高效且用于多候选人选举.     

NP问题的最优轮复杂性知识的零知识证明

NP问题已有的知识的(黑箱)零知识证明都是非常数轮的,因此,在标准的复杂性假设下,NP问题是否存在常数轮的(黑箱)知识的零知识证明是一个有意义的问题.本文对该问题进行了研究,在一定的假设下给出了HC问题的两个常数轮知识的零知识证明系统.根据Katz最近的研究结果,在多项式分层不坍塌的条件下,本文基于claw-free陷门置换给出的HC问题的5轮知识的零知识证明系统具有最优的轮复杂性.     

A correctness proof of an indenting program

The correctness of an indenting program for Pascal is proved at an intermediate level of rigour. The specifications of the program are given in the companion paper.¹ The program is approximately 330 lines long and consists of four modules: io, lex, stack and indent. We prove first that the individual procedures contained in these modules meet their specifications as given by the entry and exit assertions. A global proof of the main routine then establishes that the interaction between modules is such that the main routine meets the specification of the entire program. We argue that correctness proofs at the level of rigour used here serve very well to transfer one's understanding of a program to others. We believe proofs at this level should become commonplace before more formal proofs can take over to reduce traditional testing to an inconsequential place.     

Alternation in interaction

The traditional studies of multi-prover interactive proof systems have concentrated on cooperating provers. These are systems in which a verifier interacts with a set of provers who collaborate in their attempt to convince the verifier that a word is in a prespecified language L. Results on probabilistically checkable proofs coupled with parallel repetition techniques characterize NP in terms of multi-prover proof systems: languages in NP can be verified through a one-round interaction with two cooperating provers using limited randomness and communication.?Less attention has been paid to the study of competition in this complexity-theoretic setting of interactive proof systems. We consider, for example, one-round proof systems where the first prover is trying to convince the verifier to accept and the second prover is trying to convince the verifier to reject. We build into these proof systems a (crucial) asymmetry between the provers, analogous to quantifier alternation. We show that such proof systems capture, with restrictions on communication and randomness, languages in NP. We generalize this model by defining alternating prover proof systems which we show characterize each level of the polynomial hierarchy. Alternating oracle proof systems are also examined.?The main contribution of this work is the first exact characterization of the polynomial hierarchy in terms of interactive (prover) proof systems. Received: November 19, 1997.     

基于格的高效通用累加器与被累加值的零知识证明

通用累加器作为一种具有数据压缩性质的重要密码学元件,其多应用于隐私保护相关的区块链系统、身份认证系统以及各类权限管理系统.研究发现目前已有的基于小整数解(SIS)问题困难性假设的通用累加器内部计算效率不高,且更新效率低.因此,本文设计并实现了首个基于环小整数解(Ring-SIS)问题困难性假设的高效通用累加器,其更新开...     

Feasible Operations on Proofs: The Logic of Proofs for Bounded Arithmetic

This paper presents a semantics for the logic of proofs in which all the operations on proofs are realized by feasibly computable functions. More precisely, we will show that the completeness of for the semantics of proofs of Peano Arithmetic extends to the semantics of proofs in Buss’ bounded arithmetic . In view of applications in epistemology of in particular and justification logics in general this result shows that explicit knowledge in the propositional framework can be made computationally feasible. This research supported by CUNY Community College Collaborative Incentive Research Grant 91639-0001 “Mathematical Foundations of Knowledge Representation”.     

Cryptographic and Physical Zero-Knowledge Proof Systems for Solutions of Sudoku Puzzles

We consider cryptographic and physical zero-knowledge proof schemes for Sudoku, a popular combinatorial puzzle. We discuss methods that allow one party, the prover, to convince another party, the verifier, that the prover has solved a Sudoku puzzle, without revealing the solution to the verifier. The question of interest is how a prover can show: (i) that there is a solution to the given puzzle, and (ii) that he knows the solution, while not giving away any information about the solution to the verifier. In this paper we consider several protocols that achieve these goals. Broadly speaking, the protocols are either cryptographic or physical. By a cryptographic protocol we mean one in the usual model found in the foundations of cryptography literature. In this model, two machines exchange messages, and the security of the protocol relies on computational hardness. By a physical protocol we mean one that is implementable by humans using common objects, and preferably without the aid of computers. In particular, our physical protocols utilize items such as scratch-off cards, similar to those used in lotteries, or even just simple playing cards. The cryptographic protocols are direct and efficient, and do not involve a reduction to other problems. The physical protocols are meant to be understood by “lay-people” and implementable without the use of computers. Research of R. Gradwohl was supported by US-Israel Binational Science Foundation Grant 2002246. Research of M. Naor was supported in part by a grant from the Israel Science Foundation. Research of B. Pinkas was supported in part by the Israel Science Foundation (grant number 860/06). Research of G.N. Rothblum was supported by NSF grant CNS-0430450 and NSF grant CFF-0635297.     

Recursive Program Optimization through Inductive Synthesis Proof Transformation

The research described in this paper involved developing transformation techniques that increase the efficiency of the original program, the source, by transforming its synthesis proof into one, the target, which yields a computationally more efficient algorithm. We describe a working proof transformation system that, by exploiting the duality between mathematical induction and recursion, employs the novel strategy of optimizing recursive programs by transforming inductive proofs. We compare and contrast this approach with the more traditional approaches to program transformation and highlight the benefits of proof transformation with regards to search, correctness, automatability, and generality.     

Quantum Information and the PCP Theorem

Our main result is that the membership x∈SAT (for x of length n) can be proved by a logarithmic-size quantum state |Ψ〉, together with a polynomial-size classical proof consisting of blocks of length polylog(n) bits each, such that after measuring the state |Ψ〉 the verifier only needs to read one block of the classical proof. This shows that if a short quantum witness is available then a (classical) PCP with only one query is possible. Our second result is that the class QIP/qpoly contains all languages. That is, for any language L (even non-recursive), the membership x∈L (for x of length n) can be proved by a polynomial-size quantum interactive proof, where the verifier is a polynomial-size quantum circuit with working space initiated with some quantum state |Ψ _L,n 〉 (depending only on L and n). Moreover, the interactive proof that we give is of only one round, and the messages communicated are classical. The advice |Ψ _L,n 〉 given to the verifier can also be replaced by a classical probabilistic advice, as long as this advice is kept as a secret from the prover. Our result can hence be interpreted as: the class IP/rpoly contains all languages. For the proof of the second result, we introduce the quantum low-degree-extension of a string of bits. The main result requires an additional machinery of quantum low-degree-test. R. Raz’s research was supported by Israel Science Foundation (ISF) grant.     

Finding Shortest Proofs: An Application of Linked Inference Rules

In this article, we describe a procedure for systematically searching for shortest proofs in logical systems based on the inference rule condensed detachment. The procedure relies on applications of linked UR-resolution and uses demodulation to categorize derivations. Although the procedure is exhaustive in nature – and therefore realistically is applicable only to relatively small problems – it is shown to overcome the obstacles to finding shortest proofs presented by ordinary resolution-style theorem proving.