26838 research outputs found
Sort by
Verifiable conjunctive searchable symmetric encryption with result pattern hiding
No full textSymmetric Searchable Encryption (SSE) guarantees the security of outsourced data without sacrificing search capability. Supporting conjunctive multi-keyword search makes the SSE more practical. However, existing conjunctive SSE schemes commonly face two issues: leaking the Keyword Pair Result Pattern (KPRP) and works only when the server is honest. This paper presents the first Verifiable Conjunctive Searchable Symmetric Encryption (VCSSE) without the KPRP leakage. Our approach considers any VSSE scheme as a black box and deploys a customized iteration of the recent Result-Hiding Filter, referred to as the Verifiable Result-Hiding Filter, to develop a VCSSE that prevents the disclosure of KPRP. In addition to successfully integrating both verifiability and KPRP-hiding, our scheme also avoids non-negligible false positives, in contrast to approaches that deploy the Bloom Filter. Furthermore, we introduce an extension to our solution that supports dynamic databases. In addition to the aforementioned security properties, our approach achieves forward privacy and backward privacy in dynamic settings, while also ensuring fault-tolerance for verifiability. This implies that our scheme remains resilient to incorrect updates originating from incautious clients in the malicious server setting. While ensuring all the mentioned security properties, our schemes deliver optimal sublinear complexity performance
Shortest undirected paths in de Bruijn graphs
Get PDFComputing shortest directed paths in de Bruijn graphs is well studied and well understood. This is not the case for computing undirected paths, which is much more challenging algorithmically. In this paper, we present a general framework for computing shortest undirected paths in arbitrary de Bruijn graphs, that is, arbitrary subgraphs of the complete de Bruijn graph. We then present an application of our techniques for making any arbitrary order-k de Bruijn graph G(V, E) weakly connected by adding a set of edges of minimum total cost. This improves the running time of the recent (2 − 2/d)-approximation algorithm by Bernardini et al. [CPM 2024] from O(k|V |2) to O(k|V |log d) time, where d is the number of weakly connected components of graph G
Tolerant testing of stabilizer states with a polynomial gap via a generalized uncertainty relation
Get PDFWe prove a conjecture of Arunachalam & Dutt on the existence of a tolerant stabilizer testing algorithm, and achieve an exponential improvement in the parameters of the tester. Key to our argument is a generalized uncertainty relation for sets of Pauli operators, based on the Lovász theta function
The Ground-Set-Cost Budgeted Maximum Coverage Problem
Get PDFWe study the following natural variant of the budgeted maximum coverage problem: We are given a budget B and a hypergraph, where each vertex has a non-negative cost and a non-negative profit. The goal is to select a set of hyperedges such that the total cost of the vertices covered by T is at most B and the total profit of all covered vertices is maximized. This is a natural generalization of the maximum coverage problem. Our interest in this problem stems from its application to bid optimization in sponsored search auctions. It is easily seen that this problem is at least as hard as budgeted maximum coverage (where the costs are associated with the selected hyperedges instead of the covered vertices). This implies -inapproximability for any. Furthermore, standard greedy approaches do not yield constant factor approximations for our variant of the problem. In fact, through a reduction from Densest k-Subgraph, it can be established that our problem is inapproximable up to a constant factor, conditional on the exponential time hypothesis. Our main results are as follows: (i.) We obtain a -approximation algorithm for graphs. (ii.) We derive a fully polynomial-time approximation scheme (FPTAS) if the incidence graph of the hypergraph is a forest (i.e., the hypergraph is Berge-acyclic). We extend this result to incidence graphs with a fixed-size feedback hyperedge node set. (iii.) We give a -approximation algorithm for all, where d is the maximum vertex degree
DP-TLDM: Differentially Private Tabular Latent Diffusion Model
No full textSynthetic data from generative models emerges as the privacy-preserving data sharing solution. Such a synthetic data set shall resemble the original data without revealing identifiable private information. Till date, the prior focus on limited types of tabular synthesizers and small number of privacy attacks, particularly on Generative Adversarial Networks, and overlooks membership inference attacks and defense strategies, i.e., differential privacy. Motivated by the conundrum of keeping high data quality and low privacy risk of synthetic data tables, we propose DP-TLDM, Differentially Private Tabular Latent Diffusion Model, which is composed of an autoencoder network to encode the tabular data and a latent diffusion model to synthesize the latent tables. Following the emerging f-DP framework, we apply DP-SGD to train the auto-encoder in combination with batch clipping and use the separation value as the privacy metric to better capture the privacy gain from DP algorithms. Our empirical evaluation demonstrates that DP-TLDM is capable of achieving a meaningful theoretical privacy guarantee while also significantly enhancing the utility of synthetic data. Specifically, compared to other DP-protected tabular generative models, DP-TLDM improves the synthetic quality by an average of 35% in data resemblance, 15% in the utility for downstream tasks, and 50% in data discriminability, all while preserving a comparable level of privacy risk
EVENTSETPROCESSOR: An engine for efficiently combining high-energy physics data
No full textCERN's Large Hadron Collider (LHC), the world's largest high-energy physics (HEP) instrument, collects tens of petabytes of data per year. The LHC's next phase is expected to produce up to ten times more data, which calls for novel, more efficient ways of storing and processing these data.HEP collider data are prepared and provided to physicists as read-only data sets, stored in a custom columnar data format. While traditionally all data needed for a particular analysis were captured in a single data set, the increasing scale of the LHC and the advent of modern analysis techniques now requires analysis workflows to use data from different data sets. However, the processing model established across the HEP community does not yet provide a straightforward way to achieve this and currently relies heavily on data duplication to produce the desired data sets. This leads to significant overhead in analysis workflows, both in runtime and storage.To reduce this overhead, we propose more efficient ways to combine HEP data sets. Specifically, we design union and join operations, as defined in relational algebra, to combine HEP data sets at runtime, eliminating therefore the need for data duplication. In this paper, we specify these operations for HEP data and introduce EVENTSETPROCESSOR - an engine that implements these operations for HEP data processing. Through a first prototype, we show that this engine integrates well in existing HEP workflows, and that it can perform up to twice as fast as the current approach
Sandwich BUFF: Achieving non-resignability using iterative hash functions
Get PDFWe revisit the BUFF transform, which was proposed by Cremers et al. (S&P'21) as a means to achieve security properties beyond standard unforgeability for digital signature schemes. One of these properties, non-resignability (NR), has recently drawn some attention due to a strong impossibility result for the original definition of the property. Recent follow-up work then considered a variant (sNR) of the original definition, and showed that it is satisfied by the BUFF transform when the underlying hash function is modeled as a random oracle - while the original impossibility result still applies for the plain model. This raises the natural question of whether the BUFF transform satisfies sNR in a more fine-grained use of the random oracle model, when we consider a real-life iterative-hash-function design (such as Merkle-Damgaard or Sponge) and instead idealize the round function. Our discoveries in this direction are two-fold:
First, contrary to what one might expect, we show that there is a simple attack on the non-resignability property sNR of the BUFF-transform when instantiated with an iterative hash function. The attack relies on leaking an intermediate result of the hash computation to the adversary who is challenged to "resign" the message. This negative result once more shows the subtlety in the non-resignability property.
Second, on the positive side, we propose a small modification to the original BUFF transform, which we call Sandwich BUFF (for reasons to become clear), and prove the non-resignability property sNR of Sandwich BUFF both for Merkle-Damgaard-based hash functions in the random oracle model, and for Sponge-based hash functions in the random permutation model
Exploring entropy-based solutions for trajectory prediction in virtual reality
Get PDFThis work explores the potential of entropy-based metrics to enhance the prediction of user navigation in Virtual Reality (VR). Specifically, we consider three entropy-based metrics: entropy of trajectories, which measures the overall variability and predictability of user behaviour; instantaneous entropy, which provides real-time assessments of movement predictability; and entropy of saliency maps, which offers insights into content-driven attention patterns. Through an exploratory behavioural analysis, we show that users with low entropy exhibit consistent and predictable navigation patterns, while high-entropy users pose greater challenges for prediction models. Building on these findings, we introduce three novel entropy-based solutions for VR trajectory prediction: a position-only baseline augmented with entropy information, an LSTM-based architecture with an entropy-based adaptive attention layer (E-AALSTM), and a multi-head attention-based architecture with adaptive attention (AMH). The proposed models performs as good as state-of-the-art methods, while improving stability and robustness in specific scenarios. This work highlights the importance of having an holistic metric to characterise the user behaviour in VR, and thus enhance trajectory prediction frameworks
From aligned models to trusted interfaces : explainable health intervention and transparent health information seeeking
No full textThis thesis presents research on two interrelated themes in applying large language models (LLMs) to health contexts: (1) the model theme, aligning LLMs with domain expertise for digital counseling. (2) the interface theme, exploring people’s trust in LLM-powered health information.
Specifically, the first theme focuses on improving the explainability and controllability of LLMs for therapeutic dialogue generation. Initial evaluation showed that LLMs struggle to produce emotionally nuanced and contextually appropriate reflections in Motivational Interviewing (MI). To address this, we created expert-annotated bilingual MI dataset that captures therapeutic communication strategies. Building on this, a Script-Strategy Aligned Generation (SSAG) was proposed, where the LLM first predicts a therapeutic strategy before generating dialogue. This structured approach enhanced both explainability and adherence to evidence-based principles, offering a more controllable way to integrate LLMs into digital psychotherapy.
Research on the second theme explored trust in LLM-powered health information seeking. The first study compared LLM-powered conversational search with use of a traditional web-based search engine. The results showed that participants express more trust in LLM’s conversational responses. Research also revealed a preference for text-based interfaces over speech-based and embodied interfaces. Crucially, a mixed-methods study on source attribution showed that while LLM-generated information was highly trusted, content explicitly labeled as human-sourced was perceived as more trustworthy than content labeled as AI-generated, regardless of its actual origin. These findings underscore the nuanced relationship between source transparency and trust.
By bridging model alignment with human-centric assessment, this work provides new knowledge for designing explainable, transparent, and trustworthy LLM-powered applications in digital health
Two-dimensional forest fires with boundary ignitions
Get PDFIn the classical Drossel-Schwabl forest fire process, vertices of a lattice become occupied at rate 1, and they are hit by lightning at some tiny rate, which causes entire connected components to burn. In this paper, we study a variant where fires are coming from the boundary of the forest instead. In particular we prove for every positive (including) that, for the forest fire process without recoveries on an box in the triangular lattice, where each point on the boundary of the box has ignition rate, the probability that the center of the box gets burnt tends to 0 as (but substantially slower than the one-arm probability of critical Bernoulli percolation). And, for the case where the forest is the upper-half plane, we show (still for the version without recoveries) that no infinite occupied cluster emerges. We also discuss analogs of some of these results for the corresponding models with recoveries, and explain how our results and proofs give valuable insight on a process considered earlier by Graf (Electron J Probab 19:8, 2014), (Electron Commun Probab 21:39, 2016)