In this paper, we present the exploration of algorithms for the hardware acceleration of multi-scalar multiplication (MSM) on field programmable gate arrays (FPGAs). We have aggregated Verilog and ...System Verilog implementations of popular algorithms for each component in the MSM processing stack, including large integer multiplication, modular reduction, and elliptic curve point addition, doubling, and scalar multiplication. Additionally, we have compared these algorithms in the context of MSM and evaluated their performance. Our results highlight the efficiency of application specific hardware over general purpose processors for computationally intensive operations. Our contribution provides a valuable resource for those interested in using hardware acceleration to improve the efficiency of zero knowledge proof systems.
We study the problem of generation of cycles, chains and graphs of pairing-friendly elliptic curves using in succinct non-interactive arguments for knowledge protocols in blockchain. The task to ...build a "stick" for existing MNT753 cycle is reduced to the factorization problem for big numbers. Together with graphs of pairing friendly elliptic curves we consider auxiliary graphs of their orders (primes or irreducible polynomials) associated to vertices and embedding degrees to edges. Numerical experiments allow us to conjecture that (except of MNT case): 1) for any fixed embedding degrees there exist only finite number of such cycles and, hence, there are no families of such cycles; 2) chains of prime order are very rare; we suppose that there are no polynomial families of such chains. It is hard to find a family of pairing friendly elliptic curves with the base field order q(x) such that \zeta_{k}\in Qx/(q(x)) for k > 6. From other hand our examples show that we can apply Brezing-Weng construction with k=6 and D=3 iteratively to obtain chains of length 3-4. We build 1) a family of 1-chains with embedding degrees 8 and 7, where all orders are given by cyclotomic polynomials; 2) a combination of MNT cycle and near-MNT curve.
Internet of Vehicles (IoV), as an emerging technology, has attracted much research over the years due to rapid advancements in computing paradigms and vehicular and wireless technologies. These ...advancements enable vehicle-to-everything (V2X) communication to offer various services such as traffic management, data exchange, and route scheduling. However, the increase in density and the malicious behaviour of vehicle users have seriously threatened security and privacy concerns in the network. These concerns are related to anonymity, privacy, and verification of the identity of vehicle users. It is crucial to preserve users' privacy to prevent traceability and linkability, besides authentication to track malicious activities in the network. Therefore, in this paper, a novel privacy-preserving lightweight zk-SNARK of polynomial-based authentication protocol is presented. The vehicles are initially registered with a trusted authority (TA) in this protocol. After that, they are authenticated by RSUs, followed by verification of authentication during vehicle handover between RSUs. The proposed protocol is implemented using the Mininet-WiFi tool, and its performance is analyzed by comparing communication latency and computation time for variable vehicular density. An informal security analysis is also done to prove that the proposed protocol provides anonymity, privacy, user verifiability, and untraceability features.
Cubic bridgeless graphs with chromatic index four are called uncolorable. We introduce parameters measuring the uncolorability of those graphs and relate them to each other. For
k=2,3, let
c
k
be the ...maximum size of a
k-colorable subgraph of a cubic graph
G=(
V,
E). We consider
r
3=|
E|−
c
3 and
r
2=
2
3
|E|−c
2
. We show that on one side
r
3 and
r
2 bound each other, but on the other side that the difference between them can be arbitrarily large. We also compare them to the oddness
ω of
G, the smallest possible number of odd circuits in a 2-factor of
G. We construct cyclically 5-edge connected cubic graphs where
r
3 and
ω are arbitrarily far apart, and show that for each 1⩽
c<2 there is a cubic graph such that
ω⩾
cr
3. For
k=2,3, let
ζ
k
denote the largest fraction of edges that can be
k-colored. We give best possible bounds for these parameters, and relate them to each other.
Infinite Classes of Dihedral Snarks Fiori, Carla; Ruini, Beatrice
Mediterranean journal of mathematics,
06/2008, Volume:
5, Issue:
2
Journal Article
Peer reviewed
.
Flower snarks and Goldberg snarks are two infinite families of cyclically 5–edge–connected cubic graphs with girth at least five and chromatic index four. For any odd integer
k
,
k
> 3, there is a ...Flower snark, say
J
k
, of order 4
k
and a Goldberg snark, say
B
k
, of order 8
k
. We determine the automorphism groups of
J
k
and
B
k
for every
k
and prove that they are isomorphic to the dihedral group
D
4
k
of order 4
k
.
In this paper we propose and implement a digital permissioned decentralized anonymous payment scheme that finds a balance between anonymity and auditability. This approach allows banks to ensure that ...their clients are not participating in illegal financial transactions, whilst clients stay in control over their sensitive, personal information. Existing anonymous payment schemes often provide good privacy, but only little or mostly no auditability. We provide both by extending the Zerocash zk-SNARK based approach and adding functionality that allows for customer due diligence 'at the gate'. Clients can do fully anonymous transactions up to a certain amount per time unit and larger transactions are forced to include verifiably encrypted transactions details that can only be opened by a select group of 'judges'.
In this paper we consider the circular edge coloring of four families of Class 2 graphs. For the first two we establish the exact value of the circular chromatic index. For the next two, namely ...Goldberg and Isaacs snarks we derive an upper bound on this graph invariant. Finally, we consider the computational complexity of some problems related to circular edge coloring.
Anonymous authentication is an important factor for Internet of Things (loT) applications such as Smart Grids and Vehicle Ad hoc Networks. The zero-knowledge Succinct Non-interactive Arguments of ...Knowledge (zk-SNARK) is one of the popular methods that has been used for transacting anonymously in public blockchains. However, a heavy computational process is involved during the generation of zk-SNARK proofs (zk-SNARKs). This intensive computation is a significant barrier that prevents resource-constrained loT devices from implementing zk-SNARKs for anonymous transactions. Therefore, this paper proposes a public blockchain-based lightweight anonymous authentication platform for low-power loT devices using zk-SNARKs. A lightweight anonymous authentication protocol is designed using the SHA256 hash function. The heavy proving processes of the zk-SNARK protocol are offloaded to a powerful loT machine. A proof of concept has been designed to verify the proposed platform is capable to provide anonymous authentication with the help of zk-SNARKs and InterPlanetary File System. The security of the proposed platform is analysed and has been proved to be resistant to tracking, replay, key disclosure, and desynchronization attacks. The performance of the proposed platform is also evaluated and has been proven to be supported by low-power loT devices.
In recent years, the zero-knowledge proof and zero-knowledge succinct non-interactive argument of knowledge (zk-SNARK) have drawn significant attention as privacy-enhancing technologies in various ...domains, especially the cryptocurrency industry and verifiable computations. A post-quantum designated verifier type zero-knowledge succinct non-interactive argument of knowledge (zk-SNARK) for Boolean circuits was proposed by Gennaro et al. in ACM CCS '18. However, this scheme does not include arithmetic circuits. Furthermore, it is difficult to use it in various applications. Their paper described the construction of a post-quantum designated verifier zk-SNARK for arithmetic circuits from quadratic arithmetic programs (QAPs) as an open problem. Recently, Nitulescu proposed a post-quantum designated verifier zk-SNARK for arithmetic circuits using square arithmetic programs (SAPs), which are the special cases of QAPs.In this paper, we give another answer to this problem and propose a post-quantum designated verifier zk-SNARK scheme for arithmetic circuits using QAPs. Our proposal, which employs QAPs, the zero-knowledge proof comprises three learning with errors (LWE) ciphertexts. We implemented our proposed scheme and the other known schemes using the libsnark library. Our experimental results show that our scheme can generate a zero-knowledge proof, which is known as the bottleneck of zk-SNARK, for an arithmetic circuit that comprises 2 16 gates in a processing time of only 50 s, which is approximately three times faster than that of the post-quantum zk-SNARKs by Gennaro et al. or two times faster than the one by Nitulescu.
Internet of Things (IoT) devices are being deployed in huge numbers around the world, and often present serious vulnerabilities. Accordingly, delivering regular software updates is critical to secure ...IoT devices. Manufactures face two predominant challenges in providing software updates to IoT devices: 1) scalability of the current client-server model and 2) integrity of the distributed updates - exacerbated due to the devices' computing power and lightweight cryptographic primitives. Motivated by these limitations, we propose CrowdPatching, a blockchain-based decentralized protocol, allowing manufacturers to delegate the delivery of software updates to self-interested distributors in exchange for cryptocurrency. Manufacturers announce updates by deploying a smart contract (SC), which in turn will issue cryptocurrency payments to any distributor who provides an unforgeable proof-of-delivery. The latter is provided by IoT devices authorizing the SC to issue payment to a distributor when the required conditions are met. These conditions include the requirement for a distributor to generate a zero-knowledge proof, generated with a novel proving system called zk-SNARKs. Compared with related work, CrowdPatching protocol offers three main advantages. First, the number of distributors can scale indefinitely by enabling the addition of new distributors at any time after the initial distribution by manufacturers (i.e., redistribution among the distributor network). The latter is not possible in existing protocols and is not account for. Secondly, we leverage the recent common integration of gateway or Hub in IoT deployments in our protocol to make CrowdPatching feasible even for the more constraint IoT devices. Thirdly, the trustworthiness of distributors is considered in our protocol, rewarding the honest distributors' engagements. We provide both informal and formal security analysis of CrowdPatching using Tamarin Prover.
PDF
