Cryptography is traditionally considered as a main information security mechanism, providing several security services such as confidentiality, as well as data and entity authentication. This aspect is clearly relevant to the fundamental human right of privacy, in terms of securing data from eavesdropping and tampering, as well as from masquerading their origin. However, cryptography may also support several other (legal) requirements related to privacy. For example, in order to fulfil the data minimisation principle—i.e., to ensure that the personal data that are being processed are adequate and limited only to what is necessary in relation to the purposes for which they are processed—the use of advanced cryptographic techniques such as secure computations, zero-knowledge proofs or homomorphic encryption may be prerequisite. In practice though, it seems that the organisations performing personal data processing are not fully aware of such solutions, thus adopting techniques that pose risks for the rights of individuals. This paper aims to provide a generic overview of the possible cryptographic applications that suffice to address privacy challenges. In the process, we shall also state our view on the public “debate” on finding ways so as to allow law enforcement agencies to bypass the encryption of communication.
Abstract We use a simplified version of the framework of resource monoids , introduced by Dal Lago and Hofmann, to interpret simply typed λ-calculus with constants zero and successor. We then use this model to prove a simple quantitative result about bounding the size of the normal form of λ-terms. While the bound itself is already known, this is to our knowledge the first semantic proof of this fact. Our use of resource monoids differs from the other instances found in the literature, in that it measures the size of λ-terms rather than time complexity.
Samiksha Kodgire Samiksha, Padma Adane, Ajay Jadhav, Aman R. Agrawal · 5 authors
Transactions over the internet have increased rapidly and so is the need to prove one’s identity and have a secured system to keep records. To overcome identity theft and fraud cases, Self-Sovereign Identity (SSI) was introduced which gives the user complete control over their identity on the internet. Self-Sovereign Identity eliminates the centralized authority and brings Zero-knowledge proof concepts into account to help in easy transactions over the internet. It avoids revealing unnecessary information and correlation attacks. Self-Sovereign Identity, on top of blockchain public ledger features, provides an extra security layer to the system that can be used to monitor the entries in confidential places. This research paper describes a software module, that we have developed, to grant verifiable credentials to users. These credentials, on verification, can grant entry into any security system with which the module is integrated. The module utilizes the facilities provided by Hyperledger Indy and Hyperledger Aries for the creation of verifiable credentials and subsequent verification in a secure manner.
Quantum entangled states have shown distinguished features beyond any classical state. Many methods like quantum state tomography have been presented to verify entanglement. In this work, we aim to identify unknown entanglements with partial information of the state space by developing a nonlinear entanglement witness. The witness consists of a generalized Greenberger-Horne-Zeilinger-like paradox expressed by Pauli observables, and a nonlinear inequality expressed by density matrix elements. First, we verify unknown bipartite entanglements and study the robustness of entanglement witnesses against the white noise. Second, we generalize such a verification to unknown multipartite entangled states, including the Greenberger-Horne-Zeilinger-type states and the cluster states under local channel operations. Third, we give a quantum-information application related to the quantum zero-knowledge proof. Our results provide a useful method in verifying universal quantum computation resources with robustness against white noises. Our work is applicable to detect unknown entanglement without the state tomography.
Marta Bellés-Muñoz, Barry Whitehat, Jordi Baylina, Vanesa Daza · 5 authors
Circuit-based zero-knowledge proofs have arose as a solution to the implementation of privacy in blockchain applications, and to current scalability problems that blockchains suffer from. The most efficient circuit-based zero-knowledge proofs use a pairing-friendly elliptic curve to generate and validate proofs. In particular, the circuits are built connecting wires that carry elements from a large prime field, whose order is determined by the number of elements of the pairing-friendly elliptic curve. In this context, it is important to generate an inner curve using this field, because it allows to create circuits that can verify public-key cryptography primitives, such as digital signatures and encryption schemes. To this purpose, in this article, we present a deterministic algorithm for generating twisted Edwards elliptic curves defined over a given prime field. We also provide an algorithm for checking the resilience of this type of curve against most common security attacks. Additionally, we use our algorithms to generate Baby Jubjub, a curve that can be used to implement elliptic-curve cryptography in circuits that can be validated in the Ethereum blockchain.
Abstract We present a new zero-knowledge succinct argument of knowledge (zkSNARK) scheme for Rank-1 Constraint Satisfaction (RICS), a widely deployed NP-complete language that generalizes arithmetic circuit satisfiability. By instantiating with different commitment schemes, we obtain several zkSNARKs where the verifier’s costs and the proof size range from O (log 2 N ) to <m:math xmlns:m="http://www.w3.org/1998/Math/MathML" display="inline"><m:mrow><m:mi>O</m:mi><m:mrow><m:mo>(</m:mo><m:mrow><m:msqrt><m:mi>N</m:mi></m:msqrt></m:mrow><m:mo>)</m:mo></m:mrow></m:mrow></m:math> O\left( {\sqrt N } \right) depending on the underlying polynomial commitment schemes when applied to an N -gate arithmetic circuit. All these schemes do not require a trusted setup. It is plausibly post-quantum secure when instantiated with a secure collision-resistant hash function. We report on experiments for evaluating the performance of our proposed system. For instance, for verifying a SHA-256 preimage (less than 23k AND gates) in zero-knowledge with 128 bits security, the proof size is less than 150kB and the verification time is less than 11ms, both competitive to existing systems.
5G heterogeneous network (HetNet) is a novel network topology that integrates various kinds of wireless access technologies such as 4G Long-Term Evolution (LTE), Wi-Fi, and so on. Despite greatly improving spectrum efficiency, it poses enormous challenges to spectrum e-auction. Firstly, due to high mobility, bidders may be interested in different spectrums in terms of time or geolocation. Secondly, one’s bidding value should be protected against rival bidders or adversaries to avoid vicious competition as well as privacy leakage. Thirdly, the ubiquitous HetNet requires a trustworthy distributed auction framework rather than a centralized auctioneer-based pattern. Aiming at overcoming these obstacles above, we proposed a blockchain-based combinatorial spectrum e-auction framework. Different from other blockchain-based solutions of using SGX to realize trust processing in the auction phase, we adopt Zether, a privacy-preserving smart contract, as the main building block. Besides, the bidding value is preserved from the beginning to the end, even though the time-consuming Paillier homomorphic encryption and garbled circuits are absent. We provide the auction security by leveraging <a:math xmlns:a="http://www.w3.org/1998/Math/MathML" id="M1"> <a:mi mathvariant="normal">Σ</a:mi> </a:math> -Bullets, a zero-knowledge proof mechanism. Theoretical analysis and extensive evaluation also indicate that our approach is better than the state-of-the-art works in terms of efficiency and effectiveness.
—Algebra is one of the important fields of mathematics. It concerns with the study and manipulation of mathematical symbols. It also concerns with the study of abstractions such as groups, rings, and fields. Due to the development of these abstractions, it is extended to consider other structures, such as vectors, matrices, and polynomials, which are non-numerical objects. Computer algebra is the implementation of algebraic methods as algorithms and computer programs. Recently, many algebraic cryptosystem protocols are based on non-commutative algebraic structures, such as authentication, key exchange, and encryptiondecryption processes are adopted. Cryptography is the science that aimed at sending the information through public channels in such a way that only an authorized recipient can read it. Ring theory is the most attractive category of algebra in the area of cryptography. In this paper, we employ the algebraic structure called skew -Armendariz rings to design a neoteric algorithm for zero knowledge proof. The proposed protocol is established and illustrated through numerical example, and its soundness and completeness are proved
Zero-knowledge succinct arguments of knowledge (zkSNARKs) enable efficient privacy-preserving proofs of membership for general NP languages. Our focus in this work is on post-quantum zkSNARKs, with a focus on minimizing proof size. Currently, there is a 1000x gap in the proof size between the best pre-quantum constructions and the best post-quantum ones. Here, we develop and implement new lattice-based zkSNARKs in the designated-verifier preprocessing model. With our construction, after an initial preprocessing step, a proof for an NP relation of size 2^20 is just over 16 KB. Our proofs are 10.3x shorter than previous post-quantum zkSNARKs for general NP languages. Compared to previous lattice-based zkSNARKs (also in the designated-verifier preprocessing model), we obtain a 42x reduction in proof size and a 60x reduction in the prover's running time, all while achieving a much higher level of soundness. Compared to the shortest pre-quantum zkSNARKs by Groth (Eurocrypt 2016), the proof size in our lattice-based construction is 131x longer, but both the prover and the verifier are faster (by 1.2x and 2.8x, respectively). Our construction follows the general blueprint of Bitansky et al. (TCC 2013) and Boneh et al. (Eurocrypt 2017) of combining a linear probabilistically checkable proof (linear PCP) together with a linear-only vector encryption scheme. We develop a concretely-efficient lattice-based instantiation of this compiler by considering quadratic extension fields of moderate characteristic and using linear-only vector encryption over rank-2 module lattices.
José Bacelar Almeida, Manuel Barbosa, Manuel L. Correia, Karim Eldefrawy · 7 authors
MPC-in-the-Head (MitH) is a general framework that enables constructing efficient zero-knowledge (ZK) protocols for NP relations from secure multiparty computation (MPC) protocols. In this paper we present the first machine-checked implementations of MitH.
A random beacon provides a continuous public source of randomness and its applications range from public lotteries to zero-knowledge proofs. Existing random beacon protocols sacrifice either the fault tolerance or the communication complexity for security, or ease of reconfigurability. This work overcomes the challenges with the existing works through a novel communication efficient combination of state machine replication and (Publicly) Verifiable Secret Sharing (PVSS/VSS).
We propose a new doubly efficient interactive proof protocol for general arithmetic circuits. The protocol generalizes the interactive proof for layered circuits proposed by Goldwasser, Kalai and Rothblum to arbitrary circuits, while preserving the optimal prover complexity that is strictly linear to the size of the circuits. The proof size remains succinct for low depth circuits and the verifier time is sublinear for structured circuits. We then construct a new zero knowledge argument scheme for general arithmetic circuits using our new interactive proof protocol together with polynomial commitments. Our key technique is a new sumcheck equation that reduces a claim about the output of one layer to claims about its input only, instead of claims about all the layers above which inevitably incurs an overhead proportional to the depth of the circuit. We developed efficient algorithms for the prover to run this sumcheck protocol and to combine multiple claims back into one in linear time in the size of the circuit. Not only does our new protocol achieve optimal prover complexity asymptotically, but it is also efficient in practice. Our experiments show that it only takes 0.3 seconds to generate the proof for a circuit with more than 600,000 gates, which is 13 times faster than the original interactive proof protocol on the corresponding layered circuit. The proof size is 208 kilobytes and the verifier time is 66 milliseconds. Our implementation can take general arithmetic circuits directly, without transforming them to layered circuits with a high overhead on the size of the circuit.
Zhiyong Fang, David Darais, Joseph P. Near, Yupeng Zhang
Static program analysis tools can automatically prove many useful properties of programs. However, using static analysis to prove to a third party that a program satisfies a property requires revealing the program's source code. We introduce the concept of zero-knowledge static analysis, in which the prover constructs a zero-knowledge proof about the outcome of the static analysis without revealing the program. We present novel zero-knowledge proof schemes for intra- and inter-procedural abstract interpretation. Our schemes are significantly more efficient than the naive translation of the corresponding static analysis algorithms using existing schemes. We evaluate our approach empirically on real and synthetic programs; with a pairing-based zero knowledge proof scheme as the backend, we are able to prove the control flow analysis on a 2,000-line program in 1,738s. The proof is only 128 bytes and the verification time is 1.4ms. With a transparent zero knowledge proof scheme based on discrete-log, we generate the proof for the tainting analysis on a 12,800-line program in 406 seconds, the proof size is 282 kilobytes, and the verification time is 66 seconds.
Zero-knowledge proof (ZKP) is a fundamental cryptographic primitive that allows a prover to convince a verifier of the validity of a statement without leaking any further information. As an efficient variant of ZKP, noninteractive zero-knowledge proof (NIZKP) adopting the Fiat-Shamir heuristic is essential to a wide spectrum of applications, such as federated learning, blockchain, and social networks. However, the heuristic is typically built upon the random oracle model that makes ideal assumptions about hash functions, which does not hold in reality and thus undermines the security of the protocol. Here, we present a quantum solution to the problem. Instead of resorting to a random oracle model, we implement a quantum randomness service. This service generates random numbers certified by the loophole-free Bell test and delivers them with postquantum cryptography (PQC) authentication. By employing this service, we conceive and implement NIZKP of the three-coloring problem. By bridging together three prominent research themes, quantum nonlocality, PQC, and ZKP, we anticipate this work to inspire more innovative applications that combine quantum information science and the cryptography field.
Carsten Baum, Lennart Braun, Alexander Munch-Hansen, Benoît Razet · 5 authors
Zero-knowledge proofs are highly flexible cryptographic protocols that are an important building block for many secure systems. Typically, these are defined with respect to statements that are formulated as arithmetic operations over a fixed finite field. This inflexibility is a disadvantage when it comes to complex programs, as some fields are more amenable to express certain operations than others. At the same time, there do not seem to be many proofs with a programming model similar to those found in modern computer architectures that perform arithmetic with 32 or 64 bit integers.
Federated machine learning (FL) allows to collectively train models on sensitive data as only the clients' models and not their training data need to be shared. However, despite the attention that research on FL has drawn, the concept still lacks broad adoption in practice. One of the key reasons is the great challenge to implement FL systems that simultaneously achieve fairness, integrity, and privacy preservation for all participating clients. To contribute to solving this issue, our paper suggests a FL system that incorporates blockchain technology, local differential privacy, and zero-knowledge proofs. Our implementation of a proof-of-concept with multiple linear regression illustrates that these state-of-the-art technologies can be combined to a FL system that aligns economic incentives, trust, and confidentiality requirements in a scalable and transparent system.
Aiming at the problems of large ciphertext size and low efficiency in the current secure multi-party computation (SMC) protocol based on fully homomorphic encryption (FHE), the paper proves that the fully homomorphic encryption scheme that supports multi-bit encryption proposed by Chen Li et al. satisfies the key homomorphism. Based on this scheme and threshold decryption, a three-round, interactive, leveled, secure multi-party computation protocol under the Common Random String (CRS) model is designed. The protocol is proved to be safe under the semi-honest model and the semi-malicious model. From the non-interactive zero-knowledge proof, it can be concluded that the protocol is also safe under the malicious model. Its security can be attributed to the Decisional Learning With Errors (DLWE) and a variant of this problem (some-are-errorless LWE). Compared with the existing secure multi-party computation protocol based on fully homomorphic encryption under the CRS model, the ciphertext size of this protocol is smaller, the efficiency is higher, the storage overhead is smaller, and the overall performance is better than the existing protocol.
The continuous development of the mobile computing environment has led to the emergence of fintech to enable convenient financial transactions in this environment. Previously proposed financial identity services mostly adopted centralized servers that are prone to single-point-of-failure problems and performance bottlenecks. Blockchain-based self-sovereign identity (SSI), which emerged to address this problem, is a technology that solves centralized problems and allows decentralized identification. However, the verifiable credential (VC), a unit of SSI data transactions, guarantees unlimited right to erasure for self-sovereignty. This does not suit the specificity of the financial transaction network, which requires the restriction of the right to erasure for credit evaluation. This paper proposes a model for VC generation and revocation verification for credit scoring data. The proposed model includes double zero knowledge - succinct non-interactive argument of knowledge (zk-SNARK) proof in the VC generation process between the holder and the issuer. In addition, cross-revocation verification takes place between the holder and the verifier. As a result, the proposed model builds a trust platform among the holder, issuer, and verifier while maintaining the decentralized SSI attributes and focusing on the VC life cycle. The model also improves the way in which credit evaluation data are processed as VCs by granting opt-in and the special right to erasure.
Igor Mazurok, Yevhen Leonchyk, Oleksandr S. Antonenko, Kyrylo S. Volkov
Nowadays, Decentralized Networks based on Blockchain technology are actively researched. A special place in these researches is occupied by Smart Contracts that are widely used in many areas, such as Decentralized Finance (DeFi), real estate, gambling, electoral process, etc. Nevertheless, the possibility of their widespread adoption is still not a solved problem. This is caused by the fact of their limited flexibility and scalability. In other words, Smart Contracts cannot process a large number of contract calls per second, lack of direct Internet access, inability to operate with a large amount of data, etc. This article is devoted to the development of the Sharding Concept for Decentralized Applications (DApps) that are expressed in form of Smart Contracts written in WebAssembly. The aim of the research is to offer a new Concept of Smart Contract that will increase the scaling due to applying the idea of Sharding that allows avoiding doing the same work by all nodes on the Network and flexibility due to the possibility of interaction with the Internet without special Oracles. During the research, decentralized 0ata storages with the possibility of collective decision-making were developed. The scheme of forming Drives that assumes that each Contract is executed by a set of randomly selected nodes that allows avoiding cahoots and prevents Sybil Attack is offered. Such an approach allowed using Drives as a base layer for Smart Contracts. Moreover, Drives can be used as a standalone solution for decentralized data storing. The features of coordination of results of Contracts execution that greatly expands the possibilities of the Contracts compared to Ethereum Smart Contracts, and, in particular, allow the Contracts to interact with the Internet are described. The Rewards Concept that incentivizes all nodes that honestly execute the Contracts, unlike other systems where only the block producer is rewarded, is developed. It is based on the specially developed Proof of Executiona special algorithm that allows detecting all the nodes that honestly execute the Contracts. In order to make the Proof of Execution more compact, an extension for the existing discrete logarithm zero-knowledge proofs that makes it possible to consistently prove knowledge of dynamically expanding set of values with minimal computational and memory complexity so-called Cumulative Discrete Logarithm Zero-Knowledge Proof is developed. Thus, in this article, the new concept of Smart Contracts Sharding empowered by economic leverages is researched. The main advantages of the proposed approach are the possibility of interaction with the Internet and big data processing. Moreover, the mechanism of incentivizing nodes to honestly execute the Smart Contracts is developed. In addition, the Cumulative Proof that is necessary for the cryptographic strength of the specified mechanism is offered and its correctness is proven. The obtained results can be used to implement Smart Contracts in decentralized systems, in particular, working on the basis of Blockchain technology, especially in the case of demanding high bandwidth and performance.
In this paper, we create a single-use and full syntax zero-knowledge proof system, a.k.a zk-Fabric. Comparing with zk-SNARKS and another variant zero-knowledge proofing system, zkBOO and it's variant zkBOO++. We present multiple new approaches on how to use partitioned garbled circuits to achieve a joint zero-knowledge proof system, with the benefits of less overhead and full syntax verification. zk-Fabric based on partitioned garbled circuits has the advantage of being versatile and single-use, meaning it can be applied to arbitrary circuits with more comprehensive statements, and it can achieve the non-interactivity among all participants. One of the protocols proposed within is used for creating a new kind of partitioned garbled circuits to match the comprehensive Boolean logical expression with multiple variables, we use the term "polythitic syntax" to refer to the context-based multiple variables in a comprehensive statement. We also designed a joint zero knowledge proof protocol that uses partitioned garbled circuits
Jesús García-Rodríguez, Rafael Torres Moreno, Jorge Bernal Bernabé, Antonio Skármeta
Despite the latest efforts to foster the adoption of privacy-enhancing Attribute-Based Credential (p-ABC) systems in electronic services, those systems are not yet broadly adopted. The main reasons behind this are performance efficiency issues, lack of interoperability with standards, and the centralized architectural scheme that relies on a unique Identity Provider (IdP) for credential issuance. To cope with these limitations, this paper describes the first implementation of the Pointcheval–Sanders Multi-Signatures (PS-MS) crypto scheme proposed by Camenisch et al. and its integration in a distributed and privacy-preserving identity management system proposed in OLYMPUS H2020 European research project. Our efficient implementation provides remarkable privacy-preservation features for identity management in online transactions leveraging p-ABC systems, including unforgeability, minimal disclosure of personal data through zero-knowledge proofs, unlinkability in online transactions and fully distributed credential issuance across different IdPs, thereby removing the IdP as a unique point of failure. The performance of the implementation has been exhaustively analyzed and evaluated with different curves, signers and number of attributes, and compared against Identity Mixer, the best known p-ABC system, outperforming significantly the credential issuance and zero-knowledge proving and verification processes (2–4 times less execution time).
Binary Attestation (BA) ist ein Sicherheitsmechanismus, der schon lange zur Sicherstellung der Integrität der auszuführenden Software auf einem Computerssystem verwendet wird. Dies wird durch die Anwendung der Konzepte von Trusted Computing Technologie erreicht. Die Konzepte der Trusted Computing Technologie sind: Trusted Platform Module (TPM), measured/trusted boot und Linux Integrity Measurement Architecture (IMA). Damit die Vertrauenswürdigkeit des Betriebszustandes des Systems überprüft werden kann, wird eine Logdatei erstellt. Diese enthält den Dateinamen und die Hash-Summe der Softwarekomponenten, welche an das TPM gebunden wird. Zu einem späteren Zeitpunkt kann eine entfernte Partei (Verifier) die Evidenz verifizieren, um zu sehen, ob der Betriebszustand des Systems vertrauenswürdig ist. Dies wird als Remote Attestation (RA) bezeichnet.Auf den Systemen im Bereich der Cyber-physische Systeme (z. B.: Energie Netze und Kernkraftwerke) und im Bereich der Verkehrsmittel (z. B.: Züge und Automobil Fahrzeuge) laufen mehrere Anwendungen von verschiedenen Herstellern. Bei bisherigen Ansätzen der BA, werden alle Einträge der Logdatei von allen laufenden Anwendungen aller Hersteller während der RA an die entfernte Partei preisgegeben. Daher gewährleistet die Binary Remote Attestation keine Privatheit. Diese Masterarbeit adressiert die genannte Schwäche von der Binary Remote Attestation indem es eine Privacy-Preserving Remote Attestation Ansatz erstellt. Im Kern der Arbeitsteht die Konzeptionierung eines Ansatzes, welches den Trusted Computing Sektor mit Privacy-Enhancing Technologie verknüpft. Der Ansatz bewahrt die Privatheit, indem alle Logeinträge verschleiert werden. Dabei werden dem Verifier nur die jeweilig zugehörigen Einträge offengelegt. Dadurch kann der Attester dem Verifier durch die Anwendung des Schnorr Non-Interactive Zero-Knowledge Proofs über eine elliptische Kurve (Schnorr-Signatur) beweisen, dass es sich bei den ausgeblendeten Einträgen um die tatsächlich laufende Anwendung auf dem System des Attesters handelt, ohne die anderen Einträge preiszugeben. Dieser Ansatz wird in dieser Arbeit als Proof-of-Concept umgesetzt. Die Leistung und die Privatheit des Proof-of-Concepts wurden in dieser Arbeit analysiert. Hierdruch wird gezeigt, dass die Privatheit gegenüber der entfernten Partei gewährleistet wird, während die Integrität und Authentizität des Betriebszustands des Systems vom Attester sichergestellt wird. Die Gewährleistung der Privatheit geht allerdings mit einem Anstieg der benötigten Ressourcen einher.
Abstract Introduction/Objective My role model when I was a medical technologist intern was a chief pathologist who taught me to speak up when something is unsafe and to serve willingly, do what is right, be fair and excellent in work. His character impacted my whole life and career. Every moment matters; life is precious and something to protect. The patient and their care teams depend upon accurate, safe and high-quality clinical laboratory tests result to achieve positive patient outcomes. Methods/Case Report Clinical Practice Results (if a Case Study enter NA) We can do better. Everybody can be surveyors with greater understanding of pathophysiologic processes in disease, extensive experience working in laboratories and in-depth knowledge about complaince, quality, mistake-proofing care, patient-focused and laboratory management. Diagnostic testing would be the method to screen for disease, confirm disease, and monitor disease in hopes of secondary prevention - to identify latent disease to “catch it early.” The screening tests could be anything from newborn screening for inborn metabolism errors, adult screening tests (like mammograms, pap smears, and colonoscopies), to high-risk population screenings to detect HIV, RPR, and gonorrhea. The disease must have a high prevalence to justify the expense of therapy and should be detectable before symptoms arise. The test must not have many false positives but extremely high sensitivity. The results of these tests could lead to the three different methods of prevention. Primary prevention would reduce the risk of developing cardiovascular disease or stroke. Secondary prevention would detect the disease early to prevent progression of the disease. Tertiary prevention would reduce disabilty and promotion of rehabilitation from the disease like strokes or rehab programs. Conclusion In conclusion, this information provides clinicians with a laboratory test menu guidelines to improve clinical practice. We can all learn well to focus on what really matters. Together, we can make healthcare better, more patient-centered, less costly, and safer.