Anonymous-credential (AC) schemes equip users with credentials on attested attributes such that users can later prove possession of a credential certifying (a subset of) those attributes without revealing anything else. In standard AC schemes, such proofs reveal the issuer of the credential, which may be more information than intended or necessary. Lately, there has been significant interest in designing stronger issuer-hiding anonymous-credential schemes that only reveal that the user has a credential from an issuer in a certain policy set. Katz and Sefranek recently showed how to add issuer hiding to BBS-based anonymous credentials. However, their scheme requires per-verifier policy keys with corresponding secret keys needed for verification; this means proofs are no longer publicly verifiable, and may pose a barrier to practical deployment. As another drawback, security of their scheme relies on the generic group model (GGM). In this work, we propose a template for constructing issuer-hiding, BBS-based anonymous credentials that does not require policy keys and whose security can be reduced to security of the BBS signature scheme (in particular, without relying on the GGM). At the core of our template is a technique to randomize BBS public keys and adapt signatures accordingly, which we show also has applications to tight multi-user security of BBS signatures. We design, implement, optimize, and experimentally compare various instantiations of our template that offer tradeoffs in proving time, verification time, and proof size. All instantiations offer good performance for policy sets of up to 64 issuers.

Anonymous Credentials enable privacy-preserving authentication. To ensure non-transferability of credentials among corrupt users, they can additionally be device-bound. Therein, a credential is tied to a key protected by a secure element (SE), usually a hardware component, and any presentation of the credential requires a fresh contribution of the SE. Despite being a fundamental concern of user credentials, device binding for Anonymous Credentials is relatively unstudied. Existing constructions either require multiple calls to the SE, or need the SE to keep state--violating the design principles of resource-limited SEs. Further, constructions that are compatible with the most mature credential scheme BBS rely on the honesty of the SE for privacy, which is hard to vet given that SEs are black-box components. In this work, we thoroughly study Device-Bound Anonymous Credentials (\\($\$\)\backslashtextsf\DBAC\\\($\$\)DBACs). We model \\($\$\)\backslashtextsf\DBAC\\\($\$\)DBACs to ensure not only unforgeability and non-transferability of credentials, but also user privacy, even when the SE is subverted or fully corrupted. We also define blind \\($\$\)\backslashtextsf\DBAC\\\($\$\)DBACs, in which the SE learns nothing about the credential presentations it helped compute. This targets the design of a remote, cloud-based SE which is a deployment model considered for the EU Digital Identity wallet. Finally, we present three simple and round-optimal constructions for device binding of BBS credentials, prove their security in the AGM+ROM, and privacy unconditionally. The SE remains extremely lightweight, computing only a single BLS or Schnorr signature. A blind variant of the BLS-based construction yields the first protocol to enable privacy-preserving device binding for Anonymous Credentials when used with a remote SE.

Oblivious pseudorandom functions (OPRFs) allow the blind evaluation of a pseudorandom function, which makes them a versatile building block that enjoys usage in numerous applications. So far, security of OPRFs is predominantly captured in the Universal Composability (UC) framework, where an ideal functionality covers the expected security and privacy properties. While the OPRF functionality appears intuitive at first, the ideal-world paradigm also comes with a number of challenges: from imposing idealized building blocks when building OPRFs, to the lack of modularity, and requiring intricate UC knowledge to securely maneuver their usage. Game-based definitions are a simpler way to cover security properties. They model each property in a single game, which grants modularity in formalizing, proving, and using OPRFs. Interestingly, the few game-based works on OPRFs each re-invent the security model, with considerable variation. Thus, the advantages of the game-based approach remain out of reach: definitions are not easily accessible and comparability across works is low. In this work, we therefore systematize all existing notions into a clear, hierarchical framework. We unify or separate properties, making hidden relations explicit. This effort reveals the necessity of two novel properties: an intermediate privacy notion and a stronger unpredictability notion. Finally, we analyze the two most prominent constructions in our framework: HashDH and 2HashDH. The former does not achieve UC security, but has advantages in applications that require key rotation or updatability; yet it lacks a security analysis. We show that it achieves most security properties in our framework. We also observe that HashDH and 2HashDH do not satisfy our strongest privacy notion, indicating that the guarantees by the UC functionality are not as well understood as we might expect them to be. Overall, we hope that our framework facilitates the usage and design of OPRFs.

In interaction, the establishment of reference is a collaborative process involving the main speaker and the addressee. Current work on visual natural language generation however minimizes interactivity and concentrates on the complexity of the input. Here, we return to some classical rule-based NLG algorithms, and extend them minimally to achieve incremental referring behavior guided by the listener’s non-verbal feedback in a visual domain. We run a human evaluation study and show that these algorithms create behavior that is effective, though not judged as human-like. An additional, even simpler algorithm that generates finer-grained instructions is shown to be even more effective in ambiguous settings. We speculate that such simple algorithms can act as teachers that can help neural models take a step towards interactivity.

The rapid growth of scientific publications every year makes it infeasible to keep pace with and survey manually, even for a specific field. Keeping up with literature and gaining a birds-eye view in a timely manner is crucial to the pursuit of scientific discovery and innovation. To help gain a clearer understanding of the state and progress of science and the nature of discovery, one can encode key information from these publications and represent them as a network. Observations on the structural evolution of these graphs can offer valuable insights on the dynamics at play. This work describes the construction and analyses the temporal evolution of a knowledge network of keywords (specifically focusing on genes/proteins, diseases and chemicals) from publications in the biomedical sciences domain. We compare and contrast the representations and evolution of these keyword networks types and find significant differences in the network growth, largely corresponding to our intuition. Furthermore, we focus on the formation and evolution of new links, which we argue corresponds to new scientific discoveries. Our findings suggest that these links are progressively formed in short network distance, leading to clusters of extensively studied keywords. This strategy, however, seems to impede ground-breaking innovation, which could be beneficial for research progress.Competing Interest StatementThe authors have declared no competing interest.