Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA structural analysis of the A5/1 state transition graph
208
0
0.0
(
0
)
Added by
EPTCS
Publication date
2012
fields
Informatics Engineering
and research's language is
English
Authors
Andreas Beckmann
Ask ChatGPT about the research
No Arabic abstract
We describe efficient algorithms to analyze the cycle structure of the graph induced by the state transition function of the A5/1 stream cipher used in GSM mobile phones and report on the results of the implementation. The analysis is performed in five steps utilizing HPC clusters, GPGPU and external memory computation. A great reduction of this huge state transition graph of 2^64 nodes is achieved by focusing on special nodes in the first step and removing leaf nodes that can be detected with limited effort in the second step. This step does not break the overall structure of the graph and keeps at least one node on every cycle. In the third step the nodes of the reduced graph are connected by weighted edges. Since the number of nodes is still huge an efficient bitslice approach is presented that is implemented with NVIDIAs CUDA framework and executed on several GPUs concurrently. An external memory algorithm based on the STXXL library and its parallel pipelining feature further reduces the graph in the fourth step. The result is a graph containing only cycles that can be further analyzed in internal memory to count the number and size of the cycles. This full analysis which previously would take months can now be completed within a few days and allows to present structural results for the full graph for the first time. The structure of the A5/1 graph deviates notably from the theoretical results for random mappings.
rate research
Read More
Blockchain protocols differ in fundamental ways, including the mechanics of selecting users to produce blocks (e.g., proof-of-work vs. proof-of-stake) and the method to establish consensus (e.g., longest chain rules vs. Byzantine fault-tolerant (BFT) inspired protocols). These fundamental differences have hindered apples-to-apples comparisons between different categories of blockchain protocols and, in turn, the development of theory to formally discuss their relative merits. This paper presents a parsimonious abstraction sufficient for capturing and comparing properties of many well-known permissionless blockchain protocols, simultaneously capturing essential properties of both proof-of-work (PoW) and proof-of-stake (PoS) protocols, and of both longest-chain-type and BFT-type protocols. Our framework blackboxes the precise mechanics of the user selection process, allowing us to isolate the properties of the selection process that are significant for protocol design. We demonstrate the utility of our general framework with several concrete results: 1. We prove a CAP-type impossibility theorem asserting that liveness with an unknown level of participation rules out security in a partially synchronous setting. 2. Delving deeper into the partially synchronous setting, we prove that a necessary and sufficient condition for security is the production of certificates, meaning stand-alone proofs of block confirmation. 3. Restricting to synchronous settings, we prove that typical protocols with a known level of participation (including longest chain-type PoS protocols) can be adapted to provide certificates, but those with an unknown level of participation cannot. 4. Finally, we use our framework to articulate a modular two-step approach to blockchain security analysis that effectively reduces the permissionless case to the permissioned case.
Digital watermarks have been considered a promising way to fight software piracy. Graph-based watermarking schemes encode authorship/ownership data as control-flow graph of dummy code. In 2012, Chroni and Nikolopoulos developed an ingenious such scheme which was claimed to withstand attacks in the form of a single edge removal. We extend the work of those authors in various aspects. First, we give a formal characterization of the class of graphs generated by their encoding function. Then, we formulate a linear-time algorithm which recovers from ill-intentioned removals of $k leq 2$ edges, therefore proving their claim. Furthermore, we provide a simpler decoding function and an algorithm to restore watermarks with an arbitrary number of missing edges whenever at all possible. By disclosing and improving upon the resilience of Chroni and Nikolopouloss watermark, our results reinforce the interest in regarding it as a possible solution to numerous applications.
Recent work of Erlingsson, Feldman, Mironov, Raghunathan, Talwar, and Thakurta [EFMRTT19] demonstrates that random shuffling amplifies differential privacy guarantees of locally randomized data. Such amplification implies substantially stronger privacy guarantees for systems in which data is contributed anonymously [BEMMRLRKTS17] and has lead to significant interest in the shuffle model of privacy [CSUZZ19; EFMRTT19]. We show that random shuffling of $n$ data records that are input to $varepsilon_0$-differentially private local randomizers results in an $(O((1-e^{-varepsilon_0})sqrt{frac{e^{varepsilon_0}log(1/delta)}{n}}), delta)$-differentially private algorithm. This significantly improves over previous work and achieves the asymptotically optimal dependence in $varepsilon_0$. Our result is based on a new approach that is simpler than previous work and extends to approximate differential privacy with nearly the same guarantees. Importantly, our work also yields an algorithm for deriving tighter bounds on the resulting $varepsilon$ and $delta$ as well as Renyi differential privacy guarantees. We show numerically that our algorithm gets to within a small constant factor of the optimal bound. As a direct corollary of our analysis we derive a simple and nearly optimal algorithm for frequency estimation in the shuffle model of privacy. We also observe that our result implies the first asymptotically optimal privacy analysis of noisy stochastic gradient descent that applies to sampling without replacement.
Local certification consists in assigning labels to the nodes of a network to certify that some given property is satisfied, in such a way that the labels can be checked locally. In the last few years, certification of graph classes received a considerable attention. The goal is to certify that a graph $G$ belongs to a given graph class~$mathcal{G}$. Such certifications with labels of size $O(log n)$ (where $n$ is the size of the network) exist for trees, planar graphs and graphs embedded on surfaces. Feuilloley et al. ask if this can be extended to any class of graphs defined by a finite set of forbidden minors. In this work, we develop new decomposition tools for graph certification, and apply them to show that for every small enough minor $H$, $H$-minor-free graphs can indeed be certified with labels of size $O(log n)$. We also show matching lower bounds with a simple new proof technique.
The Ripple network is one of the most prominent blockchain platforms and its native XRP token currently has one of the highest cryptocurrency market capitalizations. The Ripple consensus protocol powers this network and is generally considered to a Byzantine fault-tolerant agreement protocol, which can reach consensus in the presence of faulty or malicious nodes. In contrast to traditional Byzantine agreement protocols, there is no global knowledge of all participating nodes in Ripple consensus; instead, each node declares a list of other nodes that it trusts and from which it considers votes. Previous work has brought up concerns about the liveness and safety of the consensus protocol under the general assumptions stated initially by Ripple, and there is currently no appropriate understanding of its workings and its properties in the literature. This paper closes this gap and makes two contributions. It first provides a detailed, abstract description of the protocol, which has been derived from the source code. Second, the paper points out that the abstract protocol may violate safety and liveness in several simple executions under relatively benign network assumptions.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
