In this work, we introduce and study contextual search in general principal-agent games, where a principal repeatedly interacts with agents by offering contracts based on contextual information and historical feedback, without knowing the agents’ true costs or rewards. Our model generalizes classical contextual pricing by accommodating richer agent action spaces. Over \(T\) rounds with \(d\)-dimensional contexts, we establish an asymptotically tight exponential \(T^{1-\Theta(1/d)}\) bound in terms of the pessimistic Stackelberg regret, benchmarked against the best utility for the principal that is consistent with the observed feedback.

Updatable oblivious key management (UOKMS) allow users to outsource encrypted data along with a symmetric key-generating token to a cloud server. The designated recipient uses this token and interacts with multiple key servers to derive the decryption key and then access the data. To ensure secure access and prevent impersonation attacks, users must authenticate to each key server using distinct credentials during key derivation. This introduces computational overhead that scales linearly with the number of key servers, especially posing challenges for resource-constrained devices. Moreover, UOKMS assumes that users' devices are fully trustworthy, but real-world cases show that they may be embedded with backdoors that covertly exfiltrate cryptographic secrets. To address these challenges, we propose a secure re-randomized password-derived public/secret key pairs generation mechanism that protects the symmetric key-generating token, eliminates interactive authentication with key servers, and resists password-guessing attacks. Our design incorporates a protocol-aware reverse firewall that mitigates backdoor threats by generating unbiased randomness and transforming interactive messages through re-randomization and de-randomization. Building on this, we develop ATTEST, a password-based data protection scheme for cloud storage against backdoor attacks. Security and performance evaluations demonstrate that ATTEST offers strong security with practical efficiency.

Anonymous Single-Sign-On (ASSO) enables users to authenticate with an identity server and obtain a master token that grants anonymous access to multiple services. We analyze existing password-based ASSO schemes and identify two fundamental security vulnerabilities. First, an adversary may enumerate potential passwords of a target user and forge valid authentication requests to the identity server. By analyzing the master tokens returned by the identity server using a designated equation, the adversary can recover the user’s password.We refer to this attack as Master Token Password Inference Attacks (MT-PIA). Second, a malicious manufacturer may embed a biased randomness source in users’ devices, causing cryptographic operations to produce predictable outputs. This enables the manufacturer to efficiently recover users’ secrets, which is known as subversion attacks. To mitigate MT-PIA, we propose a secure master token generation mechanism that protects users’ master tokens using two factors: a password and a security key. This mechanism prevents adversaries from forging valid authentication requests and ensures that, even if they intercept master tokens from the identity server, they cannot infer users’ passwords without users’ associated security keys. To counter subversion attacks, we design a cryptographic reverse firewall–based randomness generation mechanism. In this design, a reverse firewall is deployed between each user’s device and the external to assist in generating uniformly distributed randomness. Leveraging these two mechanisms, we develop a security-enhanced ASSO scheme, referred to as SE-ASSO, and conduct a comprehensive evaluation demonstrating its strong security and practicality for real-world deployment.

The facility location game is an extensively studied problem in mechanism design. In the classical model, the cost of each agent is her distance to the nearest facility. In this paper, we consider a novel model where each facility charges an entrance fee, which is a function of the facility's location. Thus, in our model, the cost of each agent is the sum of the distance to the facility and the entrance fee of the facility. The generalized model captures more real-life scenarios. In our model, the entrance fee function can be an arbitrary function, and the corresponding preferences of agents may not be single-peaked anymore: this makes the problem complex and requires new techniques in the analysis. We systematically study the model and design strategyproof mechanisms with nice approximation ratios and also complement these with nearly-tight impossibility results. Specifically, for one-facility and two-facility games, we provide upper and lower bounds for the approximation ratios given by deterministic and randomized mechanisms, with respect to the utilitarian and egalitarian objectives. Most of our bounds are tight, and these bounds are independent of the entrance fee functions. Our results also match the results of the classical model.