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.
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.
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.
As a recent cryptography protocol, Zero-Knowledge Succinct Non-Interactive Argument of Knowledge (zk-SNARK) allows one party to prove that it possesses certain information without revealing ...information to these untrusted proof provers. This mechanism has the ability to provide the function for constructing and verifying information integrity without privacy leaking. However, the computation kernels of zk-SNARK consume too much computing power and produce a significant performance bottleneck with the growing data volume and security requirement. In this paper, we take advantage of Graphic Processing Unit (GPU) to enhance zk-SNARK efficiency by accelerating the most time-consuming computation kernels: modular multiplication and Number-Theoretic Transform (NTT)/Inverse Number-Theoretic Transform (INTT) in Elliptic Curve Cryptography (ECC) pairing with two major improvements: (1) Adopting interval limbs multiply-add quaternary operation to directly accelerate ECC pairing by making full advantage of information entropy within the limited hardware bit width; (2) Data layout and shuffle methods in GPU global memory and shared memory for data space consistency maintenance accelerating NTT/INTT which indirectly works on ECC pairing. To the best of our knowledge, our work would be the first exploration to accelerate these improvements on GPU. The measured results show that our methods are able to accelerate modular multiplication and NTT/INNT by 1.22× and 4.67× times respectively compared with the previous GPU implementation. With these accelerated kernels, we are able to achieve 3.14× speedup for Groth16, which is the most efficient zk-SNARK implementation working on BLS12-381 ECC field. With the bottleneck tackled, our work will expand the deployment scenarios of zk-SNARK in Zero Knowledge Proof (ZKP).
•To accelerate zk-SNARK, we propose one mathematical scheme and its implementation.•We improve Montgomery algorithm for modular exponentiation & NTT/INTT as ECC kernels.•Our mathematical scheme well exploits the utilization of hardware bitwidth.•We propose a large data transposition method for NTT/INTT parallelism in GPU memory.•The improved zk-SNARK & multiplication reduction based kernels are tested effective.