Helmholtz Center for Information Security
CISPA – Helmholtz-Zentrum für InformationssicherheitNot a member yet
3406 research outputs found
Sort by
Universal Ring Signatures in the Standard Model
No full textRing signatures allow a user to sign messages on behalf of an ad hoc set of users - a ring - while hiding her identity. The original motivation for ring signatures was whistleblowing [Rivest et al. ASIACRYPT’01]: a high government employee can anonymously leak sensitive information while certifying that it comes from a reliable source, namely by signing the leak. However, essentially all known ring signature schemes require the members of the ring to publish a structured verification key that is compatible with the scheme. This creates somewhat of a paradox since, if a user does not want to be framed for whistleblowing, they will stay clear of signature schemes that support ring signatures.
In this work, we formalize the concept of universal ring signatures (URS). A URS enables a user to issue a ring signature with respect to a ring of users, independently of the signature schemes they are using. In particular, none of the verification keys in the ring need to come from the same scheme. Thus, in principle, URS presents an effective solution for whistleblowing.
The main goal of this work is to study the feasibility of URS, especially in the standard model (i.e. no random oracles or common reference strings). We present several constructions of URS, offering different trade-offs between assumptions required, the level of security achieved, and the size of signatures:
Our first construction is based on superpolynomial hardness assumptions of standard primitives. It achieves compact signatures. That means the size of a signature depends only logarithmically on the size of the ring and on the number of signature schemes involved.
We then proceed to study the feasibility of constructing URS from standard polynomially-hard assumptions only. We construct a non-compact URS from witness encryption and additional standard assumptions.
Finally, we show how to modify the non-compact construction into a compact one by relying on indistinguishability obfuscation
Naming the most Anomalous Cluster in Hilbert Space for Structures with Attribute Information
Get PDFWe consider datasets consisting of arbitrarily structured en- tities (e.g., molecules, sequences, graphs, etc) whose sim- ilarity can be assessed with a reproducing kernel (or a family thereof). These entities are assumed to additionally have a set of named attributes (e.g.: number_of_atoms, stock_price, etc). These attributes can be used to classify the structured entities in discrete sets (e.g., ‘number_of_atoms < 3’, ‘stock_price ≤ 100’, etc) and can effectively serve as Boolean predicates. Our goal is to use this side-information to provide named kernel-based anomaly detection. To this end, we propose a method which is able to find among all possible entity subsets that can be described as a conjunction of the available predicates either a) the optimal cluster within the Reproducing Kernel Hilbert Space, or b) the most anomalous subset within the same space. Our method employs combinatorial optimisation of an adaptation of the Maximum-Mean-Discrepancy measure that captures the above intuition. Additionally, we propose a cri- terion to select the optimal one out of a family of kernels in a way that preserves the available side-information. Finally, we provide several real world datasets that demonstrate the usefulness of our proposed method
Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds
Get PDFThe goal of this work is to give precise bounds on the counting complexity of a family of generalized coloring problems (list homomorphisms) on bounded-treewidth graphs.
Given graphs G, H, and lists L(v)\subseteq V(H) for every v\in V(G), a list homomorphism is a function f:V(G)\to V(H) that preserves the edges (i.e., uv\in E(G) implies f(u)f(v)\in E(H)) and respects the lists (i.e., f(v)\in L(v)).
Standard techniques show that if G is given with a tree decomposition of width t, then the number of list homomorphisms can be counted in time |V(H)|^t\cdot n^O(1). Our main result is determining, for every fixed graph H, how much the base |V(H)| in the running time can be improved. For a connected graph H we define irr(H) in the following way: if H has a loop or is nonbipartite, then irr(H) is the maximum size of a set S\subseteq V(H) where any two vertices have different neighborhoods; if H is bipartite, then irr(H) is the maximum size of such a set that is fully in one of the bipartition classes. For disconnected H, we define irr(H) as the maximum of irr(C) over every connected component C of H.
It follows from earlier results that if irr(H)=1, then the problem of counting list homomorphisms to H is polynomial-time solvable, and otherwise it is #P-hard.
We show that, for every fixed graph H, the number of list homomorphisms from (G,L) to H
- can be counted in time irr(H)^t\cdot n^O(1) if a tree decomposition of G having width at most t is given in the input, and
- given that irr(H)\ge 2, cannot be counted in time (irr(H)-\epsilon)^t\cdot n^O(1) for any \epsilon>0, even if a tree decomposition of G having width at most t is given in the input, unless the Counting Strong Exponential-Time Hypothesis (#SETH) fails.
Thereby we give a precise and complete complexity classification featuring matching upper and lower bounds for all target graphs with or without loops
Teacher Model Fingerprinting Attacks Against Transfer Learning
Get PDFTransfer learning has become a common solution to address
training data scarcity in practice. It trains a specified student model by reusing or fine-tuning early layers of a well-trained teacher model that is usually publicly available. However, besides utility improvement, the transferred public knowledge also brings potential threats to model confidentiality, and even further raises other security and privacy issues.
In this paper, we present the first comprehensive investigation of the teacher model exposure threat in the transfer learning context, aiming to gain a deeper insight into the tension between public knowledge and model confidentiality. To this end, we propose a teacher model fingerprinting attack to infer the origin of a student model, i.e., the teacher model it transfers from. Specifically, we propose a novel optimizationbased method to carefully generate queries to probe the student model to realize our attack. Unlike existing model reverse engineering approaches, our proposed fingerprinting method neither relies on fine-grained model outputs, e.g., posteriors, nor auxiliary information of the model architecture or training dataset. We systematically evaluate the effectiveness of our proposed attack. The empirical results demonstrate that our attack can accurately identify the model origin with few probing queries. Moreover, we show that the proposed attack can serve as a stepping stone to facilitating other attacks against machine learning models, such as model stealing
Towards Tight Security Bounds for OMAC, XCBC and TMAC
Get PDFOMAC -- a single-keyed variant of CBC-MAC by Iwata and
Kurosawa -- is a widely used and standardized (NIST FIPS 800-38B, ISO/IEC 29167-10:2017) message authentication code (MAC) algorithm. The best security bound for OMAC is due to Nandi who proved that OMAC's pseudorandom function (PRF) advantage is upper bounded by O(q^2\ell/2^n), where n, q, and \ell, denote the block size of the underlying block cipher, the number of queries, and the maximum permissible query length (in terms of n-bit blocks), respectively. In contrast, there
is no attack with matching lower bound. Indeed, the best known attack on OMAC is the folklore birthday attack achieving a lower bound of \Omega(q^2/2^n). In this work, we close this gap for a large range of message lengths. Specifically, we show that OMAC's PRF security is upper bounded by O(q^2/2^n + q\ell^2/2^n). In practical terms, this means that for a 128-bit block cipher, and message lengths up to 64 Gigabyte, OMAC
can process up to 264 messages before rekeying (same as the birthday bound). In comparison, the previous bound only allows 248 messages. As a side-effect of our proof technique, we also derive similar tight security bounds for XCBC (by Black and Rogaway) and TMAC (by Kurosawa and Iwata). As a direct consequence of this work, we have established tight security bounds (in a wide range of \ell) for all the CBC-MAC variants, except for the original CBC-MAC
Tamarin: Verification of Large-Scale, Real-World, Cryptographic Protocols
No full textTamarin is a mature, state-of-the-art tool for cryptographic protocol verification. We survey some of the larger tour de force results achieved and show how Tamarin can formalize protocols, adversary models, and properties, and scale to substantial, real world, verification problems
On (1+ϵ)-Approximate Block Sparse Recovery
No full textLearning approximately block sparse vectors using a small number of linear measurements is a standard task in the sparse recovery/compressed sensing literature. Schemes achieving a constant factor approximation are long known, e.g. using model-based RIP. We give a new scheme achieving (1+\epsilon) approximation, which runs in near linear time in the length of the vector and is likely to be optimal up to constant factors. As an intriguing side result, we obtain the simplest known scheme measurement-optimal \ell_2/\ell_2 sparse recovery scheme recorded in the literature. The main component of our algorithm is a subtle variant of the classic CountSketch data structure where the random signs are substituted by gaussians and the number of repetitions (rows) is tuned to smaller than usual
Gossiping for Communication-Efficient Broadcast
No full textByzantine Broadcast is crucial for many cryptographic pro- tocols such as secret sharing, multiparty computation and blockchain consensus. In this paper we apply gossiping (propagating a message by sending to a few random parties who in turn do the same, until the mes- sage is delivered) and propose new communication-efficient protocols, under dishonest majority, for Single-Sender Broadcast (BC) and Parallel Broadcast (PBC), improving the state-of-the-art in several ways.
As our first warm-up result, we give a randomized protocol for BC which achieves O(n^2κ^2) communication complexity from plain public key setup assumptions. This is the first protocol with subcubic communication in this setting, but does so only against static adversaries.
Using some ideas from our BC protocol, we then move to our central con- tribution and present two protocols for PBC that are secure against adap- tive adversaries. To the best of our knowledge we are the first to study PBC specifically: All previous approaches for parallel BC (PBC) naively run n instances of single-sender Broadcast, increasing the communication complexity by an undesirable factor of n. Our insight of avoiding black- box invocations of BC is particularly crucial for achieving our asymptotic improvements. In particular:
1. Our first PBC protocol achieves O(n^3κ^2) communication complexity and relies only on plain public key setup assumptions.
2. Our second PBC protocol uses trusted setup and achieves nearly optimal communication complexity O(n^2κ^4).
Both PBC protocols yield an almost linear improvement over the best known solutions involving n parallel invocations of the respective BC protocols such as those of Dolev and Strong (SIAM Journal on Comput- ing, 1983) and Chan et al. (Public Key Cryptography, 2020). Central to our PBC protocols is a new problem that we define and solve, that we call “Converge”. In Converge, parties must run an adaptively-secure and efficient protocol such that by the end of the protocol, the honest parties that remain possess a superset of the union of the inputs of the initial honest parties
Software Verification of Hyperproperties Beyond k-Safety
No full textTemporal hyperproperties are system properties that relate multiple execution traces. For (finite-state) hardware, temporal hyperproperties are supported by model checking algorithms and tools for general temporal logics like HyperLTL exist. For (infinite-state) software, the analysis of temporal hyperproperties has, so far, been limited to -safety properties, i.e., properties that stipulate the absence of a bad interaction between any set of up to traces. In this paper, we present the first method to verify HyperLTL properties in infinite-state systems. A -property stipulates that for any traces there \emph{exist} traces such that the resulting traces do not interact badly. The combination of universal and existential quantification is key to express many properties beyond -safety including, for example, generalized non-interference or program refinement. Our method is based on a strategic instantiation of the existential quantification combined with a program reduction; both in the context of a fixed predicate abstraction. In our framework the strategy and reduction \emph{collaborate}, giving a very general proof system
Industrial practitioners' mental models of adversarial machine learning
No full textAlthough machine learning is widely used in practice, little is known about practitioners' understanding of potential security challenges. In this work, we close this substantial gap and contribute a qualitative study focusing on developers' mental models of the machine learning pipeline and potentially vulnerable components. Similar studies have helped in other security fields to discover root causes or improve risk communication. Our study reveals two facets of practitioners' mental models of machine learning security. Firstly, practitioners often confuse machine learning security with threats and defences that are not directly related to machine learning. Secondly, in contrast to most academic research, our participants perceive security of machine learning as not solely related to individual models, but rather in the context of entire workflows that consist of multiple components. Jointly with our additional findings, these two facets provide a foundation to substantiate mental models for machine learning security and have implications for the integration of adversarial machine learning into corporate workflows, decreasing practitioners' reported uncertainty, and appropriate regulatory frameworks for machine learning security