Collaborate with Strangers to Find Own Preferences

We consider a model with n players and m objects. Each player has a “preference vector” of length m, that models his grades for all objects. The grades are initially unknown to the players. A player can learn his grade for an object by probing that object, but performing a probe incurs cost. The goal of a player is to learn his preference vector with minimal cost, by adopting the results of probes performed by other players. To facilitate communication, we assume that players collaborate by posting their grades for objects on a shared billboard: reading from the billboard is free. We consider players whose preference vectors are popular, i.e., players whose preferences are common to many other players. We present a sequential and a parallel algorithm to solve the problem with logarithmic cost overhead. An extended abstract of this work appeared in the 17th Ann. ACM Symp. on Parallelism in Algorithms and Architecture, Las Vegas, Nevada, July 2005. Research of B. Awerbuch supported by NSF grant ANIR-0240551 and NSF grant CCR-0311795. Research of Y. Azar supported in part by the German-Israeli Foundation and by the Israel Science Foundation. Research of B. Patt-Shamir supported in part by Israel Ministry of Science and Technology and by the Israel Science Foundation.     

Quantum protocols for zero-knowledge systems

Zero-knowledge proof system is an important protocol that can be used as a basic block for construction of other more complex cryptographic protocols. An intrinsic characteristic of a zero-knowledge systems is the assumption that is impossible for the verifier to show to a third party that he has interacted with the prover. However, it has been shown that using quantum correlations the impossibility of transferring proofs can be successfully attacked. In this work we show two new protocols for proof transference, being the first one based on teleportation and the second one without using entangled states. In this last case, we assume that the third party can communicate in advance with both verifier and prover. Following, we present a quantum zero-knowledge protocol based on quantum bit commitment that can be implemented with today technology.     

Tell Me Who I Am: An Interactive Recommendation System

We consider a model of recommendation systems, where each member from a given set of players has a binary preference to each element in a given set of objects: intuitively, each player either likes or dislikes each object. However, the players do not know their preferences. To find his preference of an object, a player may probe it, but each probe incurs unit cost. The goal of the players is to learn their complete preference vector (approximately) while incurring minimal cost. This is possible if many players have similar preference vectors: such a set of players with similar “taste” may split the cost of probing all objects among them, and share the results of their probes by posting them on a public billboard. The problem is that players do not know a priori whose taste is close to theirs. In this paper we present a distributed randomized peer-to-peer algorithm in which each player outputs a vector which is close to the best possible approximation of the player’s real preference vector after a polylogarithmic number of rounds. The algorithm works under adversarial preferences. Previous algorithms either made severely limiting assumptions on the structure of the preference vectors, or had polynomial overhead. Research of N. Alon supported in part by the Israel Science Foundation and by the Von Neumann Fund. B. Awerbuch supported by NSF grants ANIR-0240551, CCF-0515080 and CCR-0311795. Research of Y. Azar supported in part by the German-Israeli Foundation and by the Israel Science Foundation. Research of B. Patt-Shamir supported in part by Israel Ministry of Science and Technology and by the Israel Science Foundation (grant 664/05).     

A Hard Dial-a-Ride Problem that is Easy on Average

In the dial-a-ride-problem (Darp) objects have to be moved between given sources and destinations in a transportation network by means of a server. The goal is to find the shortest transportation for the server. We study the Darp when the underlying transportation network forms a caterpillar. This special case is strongly NP-hard in the worst case. We prove that in a probabilistic setting there exists a polynomial time algorithm that finds an optimal solution with high probability. Moreover, with high probability the optimality of the solution found can be certified efficiently. In addition, we examine the complexity of the Darp in a semirandom setting and in the unweighted case.Research supported by the German Science Foundation (DFG, grant FOR 413/1-1)Research supported by the German Science Foundation (DFG, grant Gr 883/10)Research supported by the German Science Foundation (DFG, grant PR 296/6-3)     

On optimizing the evaluation of a set of expressions

A branch- and-bound type algorithm is developed to optimize the evaluation of a set of expressions. The algorithm proceeds in a depth-first manner and achieves an optimal solution. The algorithm is applied to optimize the evaluation of sets of relational expressions. Analogies to the heuristic information associated with theA* algorithm are investigated. Examples are presented illustrating the use of the algorithm. Pragmatics associated with the algorithm and its application to Boolean optimization are also discussed.Research supported by the National Science Foundation under grant number NSF MCS 79-19418 and by the National Aeronautics and Space Administration under grant number NGR 21-002-270-9.     

Applications of efficient mergeable heaps for optimization problems on trees

Summary It is shown how to use efficient mergeable heaps to improve the running time of two algorithms that solve optimization problems on trees.The work of the author was supported in part by the Israel Commission for Basic Research and National Science Foundation grant MCS78-25301     

Vandermonde and resultant matrices: An abstract approach

We propose an abstract approach to the problems of common divisors and common multiples of rational matrix functions which (in the case of matrix polynomials) have been studied before using Vandermonde and resultant matrices.Supported in part by the Office of Naval Research, Air Force Office of Scientific Research, and the National Science Foundation.The work of this author was partially supported by an NSF grant and was carried out while visiting the University of California, San Diego.     

Diffusion of computer utilization among sociology instructors

Facilitating as well as inhibiting factors underlie the adoption of educational computing innovations. A survey of 213 graduate-degree offering sociology departments found approximately 8% of the instructors utilizing computers for instruction. Responses from 225 of these sociology instructors provide a profile of how computer techniques are integrated into a variety of sociology courses. Instructors utilizing computers for instruction tend to be low in academic rank and in years since the Ph.D. This is probably a consequence of differential training and perhaps of the assignment of lower rank instructors to methods and statistics courses. As computer technology continues to expand some of these patterns of adoption may persist. This study was sponsored by CONDUIT under a grant from the National Science Foundation. In addition, some analysis and report preparation was supported by an NSF grant for a College Faculty Workshop on Computer Science in Social and Behavioral Science Education at the University of Colorado, 1974. Assistance is gratefully acknowledged from James Johnson, Trinka Dunnagan, Daniel Bailey, Don McTavish, John Castellan, and James Bohland.     

Self-stabilization of dynamic systems assuming only read/write atomicity

Summary Three self-stabilizing protocols for distributed systems in the shared memory model are presented. The first protocol is a mutual-exclusion prootocol for tree structured systems. The second protocol is a spanning tree protocol for systems with any connected communication graph. The thrid protocol is obtianed by use offair protoco combination, a simple technique which enables the combination of two self-stabilizing dynamic protocols. The result protocol is a self-stabilizing, mutualexclusion protocol for dynamic systems with a general (connected) communication graph. The presented protocols improve upon previous protocols in two ways: First, it is assumed that the only atomic operations are either read or write to the shared memory. Second, our protocols work for any connected network and even for dynamic network, in which the topology of the network may change during the excution. Shlomi Dolev received his B.Sc. in Civil Engineering and B.A. in Computer Science in 1984 and 1985, and his M.Sc. and Ph.D. in computer Sciene in 1989 and 1992 from the Technion Israel Institute of Technology. He is currently a post-dotoral fellow in the Department of Computer Science at Texas A & M Univeristy. His current research interests include the theoretical aspects of distributed computing and communcation networks. Amos Israeli received his B.Sc. in Mathematics and Physics from Hebrew University in 1976, and his M.Sc. and D.Sc. in Computer Science from the Weizmann Institute in 1980 and the Technion in 1985, respectively. Currently he is a sensior lecturer at the Electrical Engineering Department at the Technion. Prior tot his he was a postdoctoral fellow at the Aiken Computation Laboratory at harvard. His research interests are in Parellel and Distributed Computing and in Robotics. In particular he has worked on the design and analysis of Wait-Free and Self-Stabilizing distributed protocols. Shlomo Moran received his B.Sc. and D.Sc. degrees in matheamtics from Technion, Israel Institute of Technology, Haifa, in 1975 and 1979, respectively. From 1979 to 1981 he was assistant professors and a visiting research specialist at the University of Minnesota, Minneapolis. From 1981 to 1985 he was a senior lecturer at the Department of Computer Science. Technion, and from 1985 to 1986 he visted at IBM Thoas J. Watson Research Center, Yorktown Heights. From 1986 to 1993 he was an associated professor at the Department of Computer Science, Technin. in 1992–3 he visited at AT & T Bell Labs at Murray Hill and at Centrum voor Wiskunde en Informatica, Amsterdam. From 1993 he is a full professor at the Department of Computer Science, Technion. His researchinterests include distributed algorithm, computational complexity, combinatorics and grapth theory.Part of this research was supported in part by Technion V.P.R. Funds — Wellner Research Fund, and by the Foundation for Research in Electronics, Computers and Communictions, administrated by the Israel Academy of Sciences and Humanities.     

基于国密SM2的高效范围证明协议

在范围证明这类特殊的零知识证明协议中,证明者无需提供具体元素信息即可向验证者证明某一承诺的元素在指定集合内.范围证明已被广泛应用于区块链、匿名证书、电子现金、群/环签名等需要身份/数据隐私保护的场景.范围证明协议的设计方法包括平方分解(Square Decomposition)、签名基(Signature-based)、内积(Innerproduct Argument)等,其中使用较为广泛的是Camenisch等在ASIACRYPT 2008会议上提出的签名基方法.然而,Camenisch等提出的范围证明协议不仅需要高耗时的双线性对运算,还涉及繁琐的证书管理,实用性还有待提高.虽然何德彪等(专利申请公布号:CN110311776A)利用国密SM9数字签名算法设计新的协议,避免了证书管理,但仍需要双线性对运算,所以协议的计算开销还较高.为了进一步减少计算量,丰富国产密码的应用,本文采用签名基方法,利用基于国密SM2的标识数字签名算法设计新的集合关系证明协议,有效解决证书管理和双线性对开销问题,在此基础上构造新的数值范围证明协议,支持更大范围的零知识证明.为了证明所设计协议的安全性,本文先证明基于国密SM2的标识数字签名算法在自适应选择消息和身份攻击下具有存在不可伪造性(EUF-CMID-A),在此基础上证明所设计协议满足完备性、可靠性和诚实验证者零知识性.与Camenisch等和何德彪等提出的协议相比,在相同优化参数情况下,本文协议的主要通信带宽约为1568字节,分别减少了41.66%和78.12%;主要计算开销约为491.5075毫秒,分别减少了85.93%和85.85%.这说明了本文设计的协议具有更强的实用性,更能满足前述场景的身份/数据隐私保护与有效性验证需求.     

Parthenon: A parallel theorem prover for non-horn clauses

We describe a parallel resolution theorem prover, called Parthenon, that handles full first order logic. Although there has been much work on parallel implementations of logic programming languages, Parthenon is the first general purpose theorem prover to be developed for a multiprocessor. The system is based on a modification of Warren's SRI model for or-parallelism and implements a variant of Loveland's model elimination procedure. It has been evaluated on various shared memory multiprocessors including a 16-processor Encore Multimax and IBM's 64-processor RP3. We have found that many theorem proving problems exhibit a great deal of potential parallelism. Parthenon has been able to exploit much of this parallelism, producing both good absolute run times and near-linear speedup curves in many cases.This research was partially supported by NSF grant CCR-87-226-33. An earlier version of this paper appeared in the Fourth IEEE Symposium on Logic in Computer Science, Asilomar, CA, June 1989. D.E.L. was partially supported by an NSF graduate fellowship. S.M. was partially supported by an IBM graduate fellowship.     

Symmetric cryptographic protocols for extended millionaires’ problem

Yao’s millionaires’ problem is a fundamental problem in secure multiparty computation, and its solutions have become building blocks of many secure multiparty computation solutions. Unfortunately, most protocols for millionaires’ problem are constructed based on public cryptography, and thus are inefficient. Furthermore, all protocols are designed to solve the basic millionaires’ problem, that is, to privately determine which of two natural numbers is greater. If the numbers are real, existing solutions do ...     

零知识水印验证协议

在数字产品中嵌入数字水印,是对其进行版权保护的一种有力手段.近年来提出了不少数字水印方案,但是它们中大部分都是对称的,即用于水印嵌入和水印检测的密钥是相同的.而许多实际的应用都要求非对称的数字水印方案,即水印检测时所知道的秘密不足以修改、伪造或移去水印.对基于比特承诺和零知识证明的水印验证协议进行了研究.所有权证明者采用基于扩频的对称水印技术,在宿主信号中嵌入水印;水印检测的密钥采用比特承诺的形式提交给验证者,通过证明者和验证者之间的交互协议,验证者可以提取到所嵌入的水印,但无法修改、伪造或移去水印.分别提出了验证一个和多个水印比特的协议,可应用于验证嵌入在图像、音频和视频数据中的扩频水印.     

A formalization of priority inversion

A priority inversion occurs when a low-priority task causes the execution of a higher-priority task to be delayed. The possibility of priority inversions complicates the analysis of systems that use priority-based schedulers because priority inversions invalidate the assumption that a task can be delayed by only higher-priority tasks. This paper formalizes priority inversion and gives sufficient conditions as well as some new protocols for preventing priority inversions.Supported by the Commission of the European Communities under the ESPRIT Programme Basic Research Action Number 3092 (Predictably Dependable Computing Systems) and the Italian Ministry of Research and University, and in part by the Defense Advanced Research Projects Agency (DoD) under NASA Ames grant number NAG-2-593.Supported in part by the Defense Advanced Research Projects Agency (DoD) under NASA Ames grant number NAG 2-593, and by grants from IBM T.J. Watson Research Laboratory, the IBM Endicott Programming Laboratory, Siemens RTL, and Xerox Webster Research Center.Supported in part by the Office of Naval Research under contract N00014-91-J-1219, the National Science Foundation under Grant No. CCR-8701103, DARPA/NSF Grant No. CCR-9014363, and by the IBM Endicott Programming Laboratory.     

Concurrent Maintenance of Rings

A central problem for structured peer-to-peer networks is topology maintenance, that is, how to properly update neighbor variables when nodes join or leave the network, possibly concurrently. In this paper, we consider the maintenance of the ring topology, the basisof several peer-to-peer networks, in the fault-free environment. We design, and prove the correctness of, protocols that maintain a bidirectional ring under both joins and leaves. Our protocols update neighbor variables once a membership change occurs. We prove the correctness of our protocols using an assertional proof method, that is, we first identify a global invariant for a protocol and then show that every action of the protocol preserves the invariant. Our protocols are simple and our proofs are rigorous and explicit.Li and Plaxton are supported by the National Science Foundation Grant CCR–0310970. Misra is supported by the National Science Foundation Grant CCR–0204323     

A Logical Characterization of Forward and Backward Chaining in the Inverse Method

The inverse method is a generalization of resolution that can be applied to non-classical logics. We have recently shown how Andreoli’s focusing strategy can be adapted for the inverse method in linear logic. In this paper we introduce the notion of focusing bias for atoms and show that it gives rise to forward and backward chaining, generalizing both hyperresolution (forward) and SLD resolution (backward) on the Horn fragment. A key feature of our characterization is the structural, rather than purely operational, explanation for forward and backward chaining. A search procedure like the inverse method is thus able to perform both operations as appropriate, even simultaneously. We also present experimental results and an evaluation of the practical benefits of biased atoms for a number of examples from different problem domains. This work has been partially supported by the Office of Naval Research (ONR) under grant MURI N00014-04-1-0724 and by the National Science Foundation (NSF) under grant CCR-0306313. The first author was partially supported by a post-doctoral fellowship from INRIA-Futurs/école Polytechnique.     

A modular drinking philosophers algorithm

Summary A variant of the drinking philosophers algorithm of Chandy and Misra is described and proved correct in a modular way. The algorithm of Chandy and Misra is based on a particular dining philosophers algorithm and relies on certain properties of its implementation. The drinking philosophers algorithm presented in this paper is able to use an arbitrary dining philosophers algorithm as a subroutine; nothing about the implementation needs to be known, only that it solves the dining philosophers problem. An important advantage of this modularity is that by substituting a more time-efficient dining philosophers algorithm than the one used by Chandy and Misra, a drinking philosophers algorithm withO(1) worst-case waiting time is obtained, whereas the drinking philosophers algorithm of Chandy and Misra hasO(n) worst-case waiting time (forn philosophers). Careful definitions are given to distinguish the drinking and dining philosophers problems and to specify varying degrees of concurrency. Jennifer L. Welch received her B.A. in 1979 from the University of Texas at Austin, and her S.M. and Ph.D. from the Massachusetts Institute of Technology in 1984 and 1988 respectively. She has been a member of technical staff at GTE Laboratories Incorporated in Waltham, Massachusetts and an assistant professor at the University of North Carolina at Chapel Hill. She is currently an assistant professor at Texas A&M University. Her research interests include algorithms and lower bounds for distributed computing.Much of this work was performed while this author was at the Laboratory for Computer Science, Massachusetts Institute of Technology, supported by the Advanced Research Projects Agency of the Department of Defense under contract N00014-83-K-0125, the National Science Foundation under grants DCR-83-02391 and CCR-86-11442, the Office of Army Research under contract DAAG29-84-K-0058, and the Office of Naval Research under contract N00014-85-K-0168. This author was also supported in part by NSF grant CCR-9010730, an IBM Faculty Development Award, and NSF Presidential Young Investigator Award CCR-9158478This author was supported by the Office of Naval Research under contract N00014-91-J-1046, the Advanced Research Projects Agency of the Department of Defense under contract N00014-89-J-1988, and the National Science Foundation under grant CCR-89-15206. The photograph and autobiography of Professor N.A. Lynch were published in Volume 6, No. 2, 1992 on page 121     

Modular approach to the design and analysis of password-based security protocols

In this paper, a general framework for designing and analyzing password-based security protocols is presented. First we introduce the concept of "weak computational indistinguishability" based on current progress of password-based security protocols. Then, we focus on cryptographic foundations for password-based security protocols, i.e., the theory of "weak pseudorandomness". Furthermore, based on the theory of weak pseudorandomness, we present a modular approach to design and analysis of password-based security protocols. Finally, applying the modular approach, we design two kinds of password-based security protocols, i.e., password-based session key distribution (PSKD) protocol and protected password change (PPC) protocol. In addition to having forward secrecy and improved efficiency, new protocols are proved secure.     

Tight bounds for shared memory systems accessed by Byzantine processes

We provide efficient constructions and tight bounds for shared memory systems accessed by n processes, up to t of which may exhibit Byzantine failures, in a model previously explored by Malkhi et al. [21]. We show that sticky bits are universal in the Byzantine failure model for n ≥ 3t + 1, an improvement over the previous result requiring n ≥ (2t + 1)(t + 1). Our result follows from a new strong consensus construction that uses sticky bits and tolerates t Byzantine failures among n processes for any n ≥ 3t + 1, the best possible bound on n for strong consensus. We also present tight bounds on the efficiency of implementations of strong consensus objects from sticky bits and similar primitive objects. Research supported in part by a grant from the Israel Science Foundation, and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University. This work was partially completed while at AT&T Labs and while visiting the Institute for Advanced Study, Princeton, NJ. Research supported in part by US-Israel Binational Science Foundation Grant 2002246. This work was partially completed while visiting AT&T Labs. This work was partially completed while at AT&T Labs. Research supported in part by the National Science Foundation under Grant No. CCR-0331584. A preliminary version of the results presented in this paper appeared in [23].     

A prolog technology theorem prover: Implementation by an extended prolog compiler

A Prolog technology theorem prover (PTTP) is an extension of Prolog that is complete for the full first-order predicate calculus. It differs from Prolog in its use of unification with the occurs check for soundness, the model-elimination reduction rule that is added to Prolog inferences to make the inference system complete, and depth-first iterative-deepening search instead of unbounded depthfirst search to make the search strategy complete. A Prolog technology theorem prover has been implemented by an extended Prolog-to-LISP compiler that supports these additional features. It is capable of proving theorems in the full first-order predicate calculus at a rate of thousands of inferences per second.This is a revised and expanded version of a paper presented at the 8th International Conference on Automated Deduction, Oxford, England, July 1986.This research was supported by the Defense Advanced Research Projects Agency under Contract N00039-84-K-0078 with the Naval Electronic Systems Command and by the National Science Foundation under Grant CCR-8611116. The views and conclusions contained herein are those of the author and should not be interpreted as necessarily representing the official policies, either expressed or implied, of the Defense Advanced Research Projects Agency, the National Science Foundation, or the United States government. Approved for public release. Distribution unlimited.