The search for counterexamples to the Four Color Conjecture originated snarks, a very special class of cubic graphs. In this paper, we consider the equitable total coloring of snarks. A total ...coloring is equitable if the number of elements colored with each color differs by at most one, and the least integer for which a graph has such a coloring is called its equitable total chromatic number. In 2002, Wang conjectured that the equitable total chromatic number of a graph is at most ∆ + 2, and this was proved for cubic graphs. Therefore, the equitable total chromatic number of a cubic graph is either 4 or 5. We provide evidence to a negative answer to the question proposed in 2016 about the existence of a Type 1 cubic graph with girth greater than 4 and equitable total chromatic number 5, by determining equitable 4-total colorings for every member of three infinite families of snarks with girth 5.
It is conjectured by Berge and Fulkerson that every bridgeless cubic graph has six perfect matchings such that each edge is contained in exactly two of them. An infinite family R, of cyclically ...5-edge-connected rotation snarks, was discovered in European J. Combin. 2021 by Máčajová and Škoviera. In this paper, the Berge-Fulkerson conjecture is verified for the family R, and furthermore, a sup-family of R. Catlin’s contractible configuration and Tutte’s integer flow are applied here as the key methods.
Lift-and-Shift Abdolmaleki, Behzad; Ramacher, Sebastian; Slamanig, Daniel
Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security,
10/2020
Conference Proceeding
Zero-knowledge proofs and in particular succinct non-interactive zero-knowledge proofs (so called zk-SNARKs) are getting increasingly used in real-world applications, with cryptocurrencies being the ...prime example. Simulation extractability (SE) is a strong security notion for zk-SNARKs which informally ensures non-malleability of proofs. The high importance of this property is acknowledged by leading companies in this field such as Zcash and underpinned by various attacks against the malleability of cryptographic primitives in the past. Another problematic issue for the practical use of zk-SNARKs is the requirement of a fully trusted setup, as especially for large-scale decentralized applications finding a trusted party that runs the setup is practically impossible. Quite recently, the study of approaches to relax or even remove the trust in the setup procedure, and in particular subversion as well as updatable zk-SNARKs (with latter being the most promising approach), has been initiated and received considerable attention since then. Unfortunately, so far SE-SNARKs with the aforementioned properties are only constructed in an ad-hoc manner and no generic techniques are available.
In this paper, we are interested in such generic techniques and therefore firstly revisit the only available lifting technique due to Kosba et al. (called COCO) to generically obtain SE-SNARKs. By exploring the design space of many recently proposed SNARK- and STARK-friendly symmetric-key primitives we thereby achieve significant improvements in the prover computation and proof size. Unfortunately, the COCO framework as well as our improved version (called OCOCO) is not compatible with updatable SNARKs. Consequently, we propose a novel generic lifting transformation called LAMASSU. It is built using different underlying ideas compared to COCO (and OCOCO). In contrast to COCO it only requires key-homomorphic signatures (which allow to shift keys) covering well studied schemes such as Schnorr or ECDSA. This makes LAMASSU highly interesting, as by using the novel concept of so called updatable signatures, which we introduce in this paper, we can prove that LAMASSU preserves the subversion and in particular updatable properties of the underlying zk-SNARK. This makes LAMASSU the first technique to also generically obtain SE subversion and updatable SNARKs. As its performance compares favorably to OCOCO, LAMASSU is an attractive alternative that in contrast to COCO is only based on well established cryptographic assumptions.
A conjecture of Berge predicts that every bridgeless cubic graph can have its edges covered with at most five perfect matchings. If the graph in question has no 3-edge-colouring, then at least four ...perfect matchings are necessary. It was proved by Esperet and Mazzuoccolo (2014) 3 that it is NP-complete to decide whether four perfect matchings are enough to cover the edges of a bridgeless cubic graph. A disadvantage of the proof (noted by the authors) is that the constructed graphs have 2-cuts. In this paper we show that small cuts can be altogether avoided and that the problem remains NP-complete even for nontrivial snarks – that is, cyclically 4-edge-connected cubic graphs with no 3-edge-colouring. As a by-product, we provide a rich family of nontrivial snarks that cannot be covered with four perfect matchings. The methods rely on the theory of tetrahedral flows developed in Máčajová and Škoviera (2021) 9.
A Roman dominating function (RDF) on a graph G is a function f:V(G)→{0,1,2} such that every vertex u∈V(G) with f(u)=0 is adjacent to at least one vertex v∈V(G) with f(v)=2. An independent Roman ...dominating function (IRDF) f on a graph G is a Roman dominating function such that the set of vertices u∈V(G) with f(u)∈{1,2} form an independent set on G. The weight of f is f(V(G))=∑v∈V(G)f(v). The minimum weight of an RDF (IRDF) on G is the Roman domination number (independent Roman domination number) of G, denoted by γR(G) (iR(G)). The (independent) Roman domination problem asks for an (independent) Roman dominating function with minimum weight. In this work, we prove that the decision version of the (independent) Roman domination problem is NP-complete even when restricted to planar bipartite graphs with maximum degree three. Moreover, we study the (independent) Roman domination number on three infinite families of snarks. More specifically, we determine the (independent) Roman domination number for generalized Blanuša snarks and we present lower and upper bounds for the (independent) Roman domination number of Goldberg snarks and Loupekine Snarks.
The colouring defect of a cubic graph, introduced by Steffen in 2015, is the minimum number of edges that are left uncovered by any set of three perfect matchings. Since a cubic graph has defect 0 if ...and only if it is 3-edge-colourable, this invariant can measure how much a cubic graph differs from a 3-edge-colourable graph. Our aim is to examine the relationship of colouring defect to oddness, an extensively studied measure of uncolourability of cubic graphs, defined as the smallest number of odd circuits in a 2-factor. We show that there exist cyclically 5-edge-connected snarks (cubic graphs with no 3-edge-colouring) of oddness 2 and arbitrarily large colouring defect. This result is achieved by means of a construction of cyclically 5-edge-connected snarks with oddness 2 and arbitrarily large girth. The fact that our graphs are cyclically 5-edge-connected significantly strengthens a similar result of Jin and Steffen (2017), which only guarantees graphs with cyclic connectivity at most 3. At the same time, our result improves Kochol's original construction of snarks with large girth (1996) in that it provides infinitely many nontrivial snarks of any prescribed girth g≥5, not just girth at least g.
Artificial Internet of Things (AIoT) is that the system collects all kinds of information in real-time through various sensors, and intelligence analysis of the data through machine learning in the ...terminal equipment, edge domains, or cloud centers, including positioning, comparison, forecasting, scheduling, etc. which brings about the data security and privacy issues. The blockchain is a tamper-evident, unforgeable distributed ledger that protects security and privacy through the famous algorithm zk-SNARK, which is also widely used in virtual digital currencies such as Zcash. In addition, by using zk-SNARK technology in the Loopring DEX 3.0 in Ethereum, not only decentralization but also transaction performance can be guaranteed. However, there are three main problems of zk-SNARK, one is the need to guarantee calculation accuracy, two is the long time to generate evidence, especially when using Lagrangian interpolation to QAP the transaction data requires more computation; the last is the poor scalability, especially when nodes need to recalculate all data when adding new transactions. In this paper, we propose a modified zk-SNARK based on Newtonian interpolation, improve the QAP part of zk-SNARK by Newtonian interpolation, and verify the correctness of the scheme through instantiation. Finally, we analyze the computational efficiency of the two interpolation methods, and the results show that Newton interpolation solves the above two problems in the original zk-SNARK, and significantly reduces the time complexity of the algorithm, which can further promote the application of blockchain in data management of AIoT.
PDF
