In crowdsourcing systems, requesters publish tasks, and interested workers provide answers to get rewards. Worker anonymity motivates participation since it protects their privacy. Anonymity with ...unlinkability is an enhanced version of anonymity because it makes it impossible to "link" workers across the tasks they participate in. Another core feature of crowdsourcing systems is worker quality which expresses a worker's trustworthiness and quantifies their historical performance. In this work, we present AVeCQ, the first crowdsourcing system that reconciles these properties, achieving enhanced anonymity and verifiable worker quality updates. AVeCQ relies on a suite of cryptographic tools, such as zero-knowledge proofs, to (i) guarantee workers' privacy, (ii) prove the correctness of worker quality scores and task answers, and (iii) commensurate payments. AVeCQ is developed modularly, where requesters and workers communicate over a platform that supports pseudonymity, information logging, and payments. To compare AVeCQ with the state-ofthe-art, we prototype it over Ethereum. AVeCQ outperforms the state-of-the-art in three popular crowdsourcing tasks (image annotation, average review, and Gallup polls). E.g., for an Average Review task with 5 choices and 128 workers AVeCQ is 40% faster (including computing and verifying necessary proofs, and blockchain transaction processing overheads) with the task's requester consuming 87% fewer gas.
In 1976, Loupekine introduced (via Isaacs) a very general way of constructing new snarks from old snarks by cyclically connecting multipoles constructed by pulling out a path of length 2 from smaller ...snarks. In this paper, we use Zm lifts of voltage graphs formed by a similar construction to produce a variety of snarks which can be drawn with m-fold rotational symmetry for m≥3. In particular, we discuss three infinite families of snarks which can be drawn with Zm rotational symmetry whose smallest element is constructed from 3 snarks with 3-fold rotational symmetry on 28 vertices; one family has the property that the oddness of the family increases with m. We also develop a new infinite family of snarks, of order 12m for each odd m≥3, which can be drawn with m-fold rotational symmetry and which are constructed beginning with a 3-edge-colorable graph, instead of a snark.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
We show that all members of the SemiBlowup, Blowup and the first Loupekine snark families have equitable total chromatic number equal to 4. These results provide evidence of negative answers for the ...questions proposed: by (A. Cavicchioli, T.E. Murgolo, B. Ruini and F. Spaggiari,
Acta Appl. Math.
76
(2003) 56–88.) about the smallest order of a Type 2 snark of girth at least 5; and by (S. Dantas, C.M.H. De Figueiredo, G. Mazzuoccolo, M. Preissmann, V.F. dos Santos and D. Sasaki,
Discret. Appl. Math.
209
(2016) 84–91.) about the existence of Type 1 cubic graph with girth at least 5 and equitable total chromatic number 5. Moreover, we show new infinite families of snarks obtained by the Kochol superpositions that are Type 1.
The resistance of a cubic graph is the smallest number of edges whose removal produces a 3-edge-colourable graph. The flow resistance is the minimum number of zeros in an integer 4-flow on the graph. ...Fiol et al. (2018) made a conjecture that the flow resistance of a bridgeless cubic graph never exceeds its resistance. The conjecture has recently been proved to be false by displaying a family of nontrivial snarks with resistance n and flow resistance 2n (Allie et al., 2022). In this paper, we strengthen the result by showing that the ratio of the flow resistance to the resistance of a snark can be arbitrarily large.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
Chameleon hash functions are collision resistant when only the hashing keys of the functions are known. In particular, without the knowledge of the secret information, the chameleon hash function is ...merely like a regular cryptographic hash function, where it is hard to find collisions. However anyone who has trapdoor keys can efficiently generate pre-images for the chameleon hash function. In some applications, such as redactable blockchains, unfortunately the existing properties do not suffice and we need more features. Actually, it is required that without knowing the trapdoor keys, nobody can compute collisions, even if he can see collisions for arbitrary hash functions. In 2017, Ateniese et al. introduced the notion of chameleon hash functions in the enhanced collision resistant model and proposed a construction in the standard model satifying the features. To date, efficient constructions of this kind of chameleon hash functions remain as an open research problem. In this paper, we answer this problem affirmatively by presenting efficient constructions of the chameleon hash function satisfying the enhanced collision resistance. The contributions of this work are twofold. First, we show the weakness of previous work. Then, we proceed with proposing new schemes with more efficiency. Technically, we present a new chameleon hash function in the basic model and based on simple assumptions. This chameleon hash function is well compatible with Groth-Sahai proof systems and the Cramer-Shoup encryption schemes, and can be used as a stepping stone to construct an efficient chameleon hash function in the enhanced collision resistant model. Moreover, we show our basic chameleon hash can be combined with optimal ZK-SNARKs of Groth and Maller that leads to shorter sizes for chameleon hash function in the enhanced collision resistant model.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
Cloud environments are frequently employed to train Convolutional Neural Networks (CNNs). On the other hand, the training procedure is exposed to potential integrity threats due to the cloud’s lack ...of trustworthiness. Although there are now available methods for zero-knowledge proof-based training integrity verification for small models, the low-proof performance of large-scale CNNs like LeNet-5 and VGG16 makes this task challenging. To solve the training integrity verification of large-scale CNNs, this research suggests a technique called VeriCNN. Particularly, VeriCNN builds proof of integrity for CNN training using zk-SNARK. It adopts the Winograd algorithm to optimize convolution operations and introduces a high-probability matrix multiplication to optimize zero-knowledge proofs. Experimental results demonstrate the effectiveness and practicality of VeriCNN in verifying the training integrity of large-scale models. For instance, VeriCNN can generate a training integrity proof for the LeNet-5 model in just 25 s and for the VGG16 model in 390 s.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
9.
Ligero++: A New Optimized Sublinear IOP Bhadauria, Rishabh; Fang, Zhiyong; Hazay, Carmit ...
Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security,
10/2020
Conference Proceeding
Open access
This paper follows the line of works that design concretely efficient transparent sublinear zero-knowledge Interactive Oracle Proofs (IOP). Arguments obtained via this paradigm have the advantages of ...not relying on public-key cryptography, not requiring a trusted setup, and resistance to known quantum attacks. In the realm of transparent systems, Ligero and Aurora stand out with incomparable advantages where the former has a fast prover algorithm somewhat succinct proofs and the latter has somewhat fast prover and succinct proofs. In this work, we introduce Ligero++ that combines the best features of both approaches to achieve the best of both worlds. We implement our protocol and benchmark the results.
It is becoming important for the client to be able to check whether the AI inference services have been correctly calculated. Since the weight values in a CNN model are assets of service providers, ...the client should be able to check the correctness of the result without them. The Zero-knowledge Succinct Non-interactive Argument of Knowledge (zk-SNARK) allows verifying the result without input and weight values. However, the proving time in zk-SNARK is too slow to be applied to real AI applications. This article proposes a new efficient verifiable convolutional neural network (vCNN) framework that greatly accelerates the proving performance. We introduce a new efficient relation representation for convolution equations, reducing the proving complexity of convolution from O(ln) to O(l+n) compared to existing zero-knowledge succinct non-interactive argument of knowledge (zk-SNARK) approaches, where l and n denote the size of the kernel and the data in CNNs. Experimental results show that the proposed vCNN improves proving performance by 20-fold for a simple MNIST and 18,000-fold for VGG16. The security of the proposed scheme is formally proven.
PDF
