^September October – 2010 ^November

The notion of Generalized Oblivious Transfer (GOT) was introduced by Ishai and Kushilevitz. In a GOT protocol, Alice holds a set $U$ of messages. A decreasing monotone collection of subsets of $U$ defines the retrieval restrictions. Bob is allowed to learn any permissible subset of messages from that collection, but nothing else, while Alice must remain oblivious regarding the selection that Bob made. We propose a simple and efficient GOT protocol that employs secret sharing. We compare it to another secret sharing based solution for that problem that was recently proposed by Shankar, Srinathan and Pandu Rangan. In particular, we show that the access structures that are realized by the two solutions are related through a duality-type relation that we introduce here. We show that there are examples which favor our solution over the second one, while in other examples the contrary holds. Two applications of GOT are considered — priced oblivious transfer, and oblivious evaluation of multivariate polynomials.

Coin-tossing protocols are protocols that generate a random bit with uniform distribution. These protocols are used as a building block in many cryptographic protocols. Cleve [STOC 1986] has shown that if at least half of the parties can be malicious, then, in any r-round coin-tossing protocol, the malicious parties can cause a bias of Omega(1=r) to the bit that the honest parties output. However, for more than two decades the best known protocols had bias t pr , where t is the number of corrupted parties. Recently, in a surprising result, Moran, Naor, and Segev [TCC 2009] have shown that there is an r-round two-party coin-tossing protocol with the optimal bias of O(1=r). We extend Moran et al. results to the multiparty model when less than 2/3 of the parties are malicious. The bias of our protocol is proportional to 1=r and depends on the gap between the number of malicious parties and the number of honest parties in the protocol. Speci cally, for a constant number of parties or when the number of malicious parties is somewhat larger than half, we present an r-round m-party coin-tossing protocol with optimal bias of O(1=r).

We will discuss some management problems that a minimarket manager may encounter. We consider the simplistic situation in which there are two checkout counters, with one of them operating as an express line. As will be explained, managing this extra simple situation is usually problematic. We will then give examples of some favorable circumstances in which the management problem suddenly becomes easy. Some of these examples are surprising to say the least and involve some of the greatest achievements of human intelect. No prior minimarket work experience is assumed.

In many fields observations are performed irregularly along time, due to either measurement limitations or lack of a constant immanent rate. While discrete-time Markov models (as Dynamic Bayesian Networks) introduce either inefficient computation or an information loss to reasoning about such processes, continuous-time Markov models assume either a discrete state space (as Continuous-Time Bayesian Networks), or a flat continuous state space (as stochastic differential equations). To address these problems, we present a new modeling class called Irregular-Time Bayesian Networks (ITBNs), generalizing Dynamic Bayesian Networks, allowing substantially more compact representations, and increasing the expressively of the temporal dynamics. In addition, a globally optimal solution is guaranteed when learning temporal systems, provided that they are fully observed at the same irregularly spaced time-points, and a semiparametric subclass of ITBNs is introduced to allow further adaptation to the irregular nature of the available data.