Is a two-party function, possibly with randomized output, securely computable? We provide a finite procedure to answer this question, thereby settling a foundational, three-decade-old open problem in secure computation and information complexity.Beaver-Chor-Kushilevitz [11], [22], [8] answered this question for deterministic output functions. Basu et al. [3] recently gave a geometric characterization of randomized functions securely computable with bounded communication complexity. Randomized functions can have arbitrarily high communication complexity, even for fixed input-output sets [5]. Without an upper bound on the communication complexity, the decidability of the question of whether a given two-party function with randomized output is securely computable was a formidable challenge.We reduce answering this question to proving specific lamination hulls are semi-algebraic. Lamination hulls are an infinite union of recursively defined sets independently motivated by the hydrodynamics literature. We connect this technical objective to solving a system of linear inequalities over convex sets in high dimensions, where inequalities represent the natural containment relation. We present a Gaussian elimination-inspired algorithm to compute the smallest simultaneous solutions to such systems. After that, using these solutions, we prove that our lamination hulls are semi-algebraic.Our technical solution introduces a novel set operator called positive geometric join. In our application context, it characterizes algebraically well-behaved sets that generalize polytopes, which we call hemihedra. The positive geometric join operator and hemihedral sets should interest the broader mathematics and computer science community. These advancements should help further information complexity investigations more broadly via the recently established connection by Basu et al. [3].

In a seminal work, Ishai et al. (FOCS-2006) studied the viability of designing unconditionally secure protocols for key agreement and secure multi-party computation (MPC) using an anonymous bulletin board (ABB) as a building block. While their results establish the feasibility of key agreement and honest-majority MPC in the ABB model, the optimality of protocols with respect to their round and communication complexity is not studied. This paper enriches this study of unconditional security in the ABB model in multiple ways. •We present a key agreement protocol with a novel combinatorial insight to offer a 200% throughput over the (FOCS-2006) study; i.e., using the same number of messages, we can (almost) double the bit-length of the agreed key. We also prove the near optimality of our approach. •We offer unconditionally secure protocols for the (random) string oblivious transfer functionalities. We present a 1-round chosen message random string oblivious transfer and show how to extend it to a non-interactive (random) string oblivious transfer protocol and a 2-round chosen message string oblivious transfer. •We prove a 1-round communication lower bound for BEC under certain conditions. Central to our technical contributions is the abstraction of a distributional variant of the random ABB functionality. Investigating the concrete efficiency of founding MPC from this primitive leads to fascinating new mathematical challenges in well-established MPC models, which will be of broader interest to the community.

What is the round and communication complexity of secure computation? The seminal results of Chor-Kushilevitz-Beaver (STOC-1989, FOCS-1989, DIMACS-1989) answer this question for computations with deterministic output. However, this question has remained unanswered for computations with randomized output. Our work answers this question for two-party secure function evaluation functionalities. We introduce a geometric encoding of all candidate secure protocols for a given computation as points in a high-dimensional space. The following results follow by analyzing the properties of these sets of points.1)It is decidable to determine if a given computation has a secure protocol within round or communication constraints.2)We construct one such protocol if it exists.3)Otherwise, we present an obstruction to achieving security.Our technical contributions imply new information complexity bounds for secure computation.

Side-channel attacks have repeatedly falsified the assumption that cryptosystems are black boxes. Leakage-resilient cryptography studies the robustness of cryptographic constructions when an unforeseen revelation of information occurs. In this context, recently, Benhamouda, Degwekar, Ishai, and Rabin (CRYPTO–2018) motivated the study of the local leakage resilience of secret-sharing schemes against an adversary who obtains independent leakage from each secret share.Motivated by applications in secure computation, Benhamouda et al. (CRYPTO–2018) initiated the study of the local leakage resilience of Shamir’s secret-sharing scheme, an essential primitive for nearly all threshold cryptography. The objective is to achieve local leakage resilience with as small a fractional reconstruction threshold as possible. Previously, Benhamouda et al. showed that the reconstruction threshold k being at least 0.907 times the number of parties n is sufficient for Shamir’s secretsharing scheme to be resilient against arbitrary single-bit local leakage from each secret share. After that, Maji et al. (CRYPTO–2021) and Benhamouda et al. (Journal of Cryptology–2021) independently lowered this threshold to k/n ⩾ 0.8675 and k/n ⩾0.85, respectively.This paper contributes to this line of research and proves that k/n ⩾ 0.78 is sufficient. Next, motivated by applications in GMW-style leakage-resilient secure computation, our work extends this bound to a more general adversary who corrupts some parties (obtaining their entire secret shares) and obtains leakage from the remaining honest parties’ secret shares.Our technical analysis proceeds by Fourier analysis and accurately estimates an exponential sum arising in this analysis.

Historically, side-channel attacks have revealed partial information about the intermediate values and secrets of computations to compromise the security of cryptographic primitives. The objective of leakage-resilient cryptography is to model such avenues of information leakage and study techniques to realize them securely. This work studies the local leakage-resilience of prominent secret-sharing schemes like Shamir's secret-sharing scheme and the additive secret-sharing scheme against probing attacks that leak physical-bits from the memory hardware storing the secret shares. Consider the additive secret-sharing scheme among$k$parties over a prime field such that the prime needs$\lambda$-bits for its binary representation, where$\lambda$is the security parameter. We prove that$k$must be at least$\omega(\log\lambda/\log\log\lambda)$for the scheme to be secure against even one physical-bit leakage from each secret share. This result improves the previous state-of-the-art result where an identical lower bound was known for one-bit general leakage from each secret share (Benhamouda, Degwekar, Ishai, and Rabin, CRYPTO–2018). This lower bound on the reconstruction threshold extends to Shamir's secret-sharing scheme if one does not carefully choose the evaluation places for generating the secret shares. For this scheme, our result additionally improves another lower bound on the reconstruction threshold$k$of Shamir's secret-sharing scheme (Nielsen and Simkin, EUROCRYPT–2020) when the total number of parties is$\mathcal{O}(\lambda\log\lambda/\log\log\lambda)$. Our work provides the analysis of the recently-proposed (explicit) physical-bit leakage attack of Maji, Nguyen, Paskin-Cherniavsky, Suad, and Wang (EUROCRYPT–2021), namely the “parity of parity” attack. This analysis relies on lower-bounding the “discrepancy” of the Irwin-Hall probability distribution.

We describe a tool, MatchMaps, that generates sameAs and partOf matches between spatial objects (such as shops, shopping centres, etc.) in crowd-sourced and authoritative geospatial datasets. MatchMaps uses reasoning in qualitative spatial logic, description logic and truth maintenance techniques, to produce a consistent set of matches. We report the results of an initial evaluation of MatchMaps by experts from Ordnance Survey (Great Britain’s National Mapping Authority). In both the case studies considered, MatchMaps was able to correctly match spatial objects (high precision and recall) with minimal human intervention.

The CURIOS project explores how digital archives for rural community heritage groups can be made more sustainable so that volunteer members can maintain a lasting digital presence. It is developing software tools to help remote rural communities to collaboratively maintain and present information about their cultural heritage. The objective is to investigate the use of semantic web/linked data technology to build a general, flexible and "future proof" software platform that could help such projects to develop digital archives and to be sustainable over time. As an interdisciplinary project we aim to synthesise a narrative that draws from both social science and computer science perspectives by critically reflecting upon the novel approach taken and the on-going results that are being produced.

The Semantic Web represents an evolution of the World Wide Web towards one of entities and their relationships, rather than pages and links. Such a progression makes it possible to represent, integrate, query and reason about structured online data. Recent years have witnessed tremendous growth of mobile computing, represented by the widespread adoption of smart phones and tablets. The versatility of such smart devices and the capabilities of semantic technologies form a great foundation for a ubiquitous Semantic Web that will contribute to further realising the true potential of both disciplines. In this paper, the authors argue for values provided by the ubiquitous Semantic Web using a mobile service discovery scenario. They also provide a brief overview of state-of-the-art research in this emerging area. Finally, the authors conclude with a summary of challenges and important research problems.

In many logic-based BDI agent programming languages, plan selection involves inferencing over some underlying knowledge representation. While context-sensitive plan selection facilitates the development of flexible, declarative programs, the overhead of evaluating repeated queries to the agent's beliefs and goals can result in poor run time performance. In this paper we present an approach to multi-cycle query caching for logic-based BDI agent programming languages. We extend the abstract performance model presented in (Alechina et al. 2012) to quantify the costs and benefits of caching query results over multiple deliberation cycles. We also present results of experiments with prototype implementations of both single- and multi-cycle caching in three logic-based BDI agent platforms, which demonstrate that significant performance improvements are achievable in practice.

A new approach for pin detection in a reconfigurable platform for electronic system prototyping is proposed. It makes use of image processing techniques to first, extract pin core regions by a two-pass process: a top-down multi-level erosion process to remove touching parts of pin regions, followed by a bottom-up pin core recovery process to recover core regions removed by the first process. Once all pin cores have been isolated, regions associated to every pin can be determined by a simple segmentation procedure based on the shortest distance principle. The proposed approach has successfully extracted the pin maps from many circuit footprint images, even in cases of touching pin regions. The results produced by the proposed method have also been compared with those obtained from the reference Watershed algorithm and this shows that our approach provides better results in terms of pin recovery and pin positioning accuracy for the type of images produced by our electronic prototyping system.