Author name cluster

Xavier Boyen

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers

2 author rows

TCS Journal 2021 Journal Article

CCA-security from adaptive all-but-one lossy trapdoor functions

Qinyi Li
Xavier Boyen
Ernest Foo

In this paper, we propose the notion of adaptive all-but-one lossy trapdoor functions (aABO-LTFs), a variant of all-but-one lossy trapdoor functions. An aABO-LTF is parameterised by a set of branches. Given the lossy branch, the function statistically loses the information of its inputs. Given injective branches, the function is injective, and there is a trapdoor that enables efficient function inversion. What differentiates an aABO-LTF and an ABO-LTF is that for an aABO-LTF, the lossy branch is indistinguishable from the other branches even if the adversary gets to ask for function inversions on any injective branches apart from the lossy branch. We demonstrate the usefulness of the adaptivity of aABO-LTFs by providing generic and efficient constructions of an adaptively chosen-ciphertext secure (CCA-secure) public-key encapsulation mechanism (KEM) and an adaptive deterministic public-key encryption (DPKE) without random oracles using aABO-LTFs in a very simple black-box way. Our constructions are direct in the sense of that it avoids generic transformations using one-time signatures or message authentication codes typically found in standard model CCA-secure constructions. Moreover, we show that aABO-LTFs can be instantiated generically by lossy trapdoor primitives, including lossy trapdoor functions (LTFs) and identity-based (lossy) trapdoor functions (IB-LTFs). We also demonstrate that the lattice-based ABO-LTFs proposed by Alwen et al. (CRYPTO'13) are aABO-LTFs. Several existing CCA-secure KEM and DPKE schemes can be described by our generic constrictions. Therefore, our work unifies these seemingly unrelated schemes and explains the design principles behind these schemes.

Details DOI

TCS Journal 2021 Journal Article

Efficient public-key encryption with equality test from lattices

Qinyi Li
Xavier Boyen

Public-key encryption with equality (PKEET) test enables testing if two ciphertexts, possibly under two different public keys, encrypt the same messages. Recent research on PKEET considers the setting where the testing ability is delegated to semi-trusted parties to negate unfettered chosen-plaintext attacks. In this work, we revise and enhance the PKEET security model, and introduce a new property of unmaskability which further prevents an attacker from skirting the test. We then propose a simple and efficient PKEET system with adaptive chosen-ciphertext security, provably secure under our revised security model, from either plain or ring lattice assumptions. The construction adopts a direct approach which significantly departs from the existing way of building such systems. Compared with existing literature, our system relies on weaker learning-with-errors assumptions while also being more efficient and providing better security.

Details DOI

UAI Conference 1999 Conference Paper

Discovering the Hidden Structure of Complex Dynamic Systems

Xavier Boyen
Nir Friedman
Daphne Koller

Dynamic Bayesian networks provide a compact and natural representation for complex dynamic systems. However, in many cases, there is no expert available from whom a model can be elicited. Learning provides an alternative approach for constructing models of dynamic systems. In this paper, we address some of the crucial computational aspects of learning the structure of dynamic systems, particularly those where some relevant variables are partially observed or even entirely unknown. Our approach is based on the Structural Expectation Maximization (SEM) algorithm. The main computational cost of the SEM algorithm is the gathering of expected sufficient statistics. We propose a novel approximation scheme that allows these sufficient statistics to be computed efficiently. We also investigate the fundamental problem of discovering the existence of hidden variables without exhaustive and expensive search. Our approach is based on the observation that, in dynamic systems, ignoring a hidden variable typically results in a violation of the Markov property. Thus, our algorithm searches for such violations in the data, and introduces hidden variables to explain them. We provide empirical results showing that the algorithm is able to learn the dynamics of complex systems in a computationally tractable way.

Details

AAAI Conference 1999 Conference Paper

Exploiting the Architecture of Dynamic Systems

Xavier Boyen
Daphne Koller
Stanford University

Consider the problem of monitoring the state of a complex dynamic system, and predicting its future evolution. Exact algorithms for this task typically maintain a belief state, or distribution over the states at some point in time. Unfortunately, these algorithms fail when applied to complex processes such as those represented as dynamic Bayesian networks (DBNs), as the representation of the belief state grows exponentially with the size of the process. In (Boyen & Koller 1998), we recently proposed an efficient approximate tracking algorithm that maintains an approximate belief state that has a compact representation as a set of independent factors. Its performance depends on the error introduced by approximating a belief state of this process by a factored one. We informally argued that this error is low if the interaction between variables in the processes is “weak”. In this paper, we give formal information-theoretic definitions for notions such as weak interaction and sparse interaction of processes. We use these notions to analyze the conditions under which the error induced by this type of approximation is small. We demonstrate several cases where our results formally support intuitions about strength of interaction.

PDF Details

NeurIPS Conference 1998 Conference Paper

Approximate Learning of Dynamic Models

Xavier Boyen
Daphne Koller

Inference is a key component in learning probabilistic models from par(cid: 173) tially observable data. When learning temporal models, each of the many inference phases requires a traversal over an entire long data se(cid: 173) quence; furthermore, the data structures manipulated are exponentially large, making this process computationally expensive. In [2], we describe an approximate inference algorithm for monitoring stochastic processes, and prove bounds on its approximation error. In this paper, we apply this algorithm as an approximate forward propagation step in an EM algorithm for learning temporal Bayesian networks. We provide a related approxi(cid: 173) mation for the backward step, and prove error bounds for the combined algorithm. We show empirically that, for a real-life domain, EM using our inference algorithm is much faster than EM using exact inference, with almost no degradation in quality of the learned model. We extend our analysis to the online learning task, showing a bound on the error resulting from restricting attention to a small window of observations. We present an online EM learning algorithm for dynamic systems, and show that it learns much faster than standard offline EM.

PDF Details

UAI Conference 1998 Conference Paper

Tractable Inference for Complex Stochastic Processes

Xavier Boyen
Daphne Koller

The monitoring and control of any dynamic system depends crucially on the ability to reason about its current status and its future trajectory. In the case of a stochastic system, these tasks typically involve the use of a belief state---a probability distribution over the state of the process at a given point in time. Unfortunately, the state spaces of complex processes are very large, making an explicit representation of a belief state intractable. Even in dynamic Bayesian networks (DBNs), where the process itself can be represented compactly, the representation of the belief state is intractable. We investigate the idea of maintaining a compact approximation to the true belief state, and analyze the conditions under which the errors due to the approximations taken over the lifetime of the process do not accumulate to make our answers completely irrelevant. We show that the error in a belief state contracts exponentially as the process evolves. Thus, even with multiple approximations, the error in our process remains bounded indefinitely. We show how the additional structure of a DBN can be used to design our approximation scheme, improving its performance significantly. We demonstrate the applicability of our ideas in the context of a monitoring task, showing that orders of magnitude faster inference can be achieved with only a small degradation in accuracy.

Details