Identity-based mutual authentication and key agreement (ID-MAKA) between a mobile user and cloud service provider is necessary for accessing any cloud services. In recent years, there are a large number of ID-MAKA schemes had been proposed on mobile cloud computing services to make authentication and accessing process more usability, security, and scalability. In this paper, we propose a new ID-MAKA scheme for mobile cloud computing, which firstly achieves remote biometric-based authentication(remote servers authenticate user's biometrics), single sign-on (a single credential and single registration for accessing multiple servers) and center-less authentication(the registration center does not participate in the access procedure) in one scheme. In order to realize this target, we design a ZK-token based on ECC and cryptographic hash function, and then artfully employ it to introduce the fuzzy extractor technology and zero-knowledge technology into our scheme. Therefore, the user can access multiple cloud computing servers by registering only once in the registration center, and cloud computing servers can complete the biometric-based remote authentication and key agreement for the user without the registration center participating. In this way, our scheme greatly improves usability, scalability, and security compared to other existing solutions. We give a formal security proof for our scheme by using Real-Or-Random(RoR) model and Burrows-Abadi-Needham (BAN) logic to show that the present scheme is secure and security analysis for other known attacks. Finally, according to the experiment result, our scheme has lower computation and communication cost compared with most existing related schemes.
Inspired by the work of Ghadafi and Groth (ASIACRYPT 2017) on a certain type of computational hardness assumptions in cyclic groups (which they call ``target assumptions''), we initiate an analogous work on another type of hardness assumptions, namely the ``knowledge-of-exponent'' assumptions (KEAs). Originally introduced by Damgard to construct practical encryption schemes secure against chosen ciphertext attacks, KEAs have subsequently been used primarily to construct succinct non-interactive arguments of knowledge (SNARKs), and proved to be inherent to such constructions. Since SNARKs (and their zero-knowledge variant, zk-SNARKs) are already used in practice in such systems as the Zcash digital currency, it can be expected that the use of KEAs will increase in the future, which makes it important to have a good understanding of those assumptions. Using a proof technique first introduced by Bellare and Palacio (but acknowledged by them as being due to Halevi), we first investigate the internal structure of the q-power knowledge-of-exponent (q-PKE) family of assumptions introduced by Groth, which is thus far the most general variant of KEAs. We then introduce a generalisation of the q-PKE family, and show that it can be simplified.
Among the zero-knowledge succinct non-interactive arguments of knowledge (zk-SNARK), the simulation-extractable zk-SNARK (SE-SNARK) introduces a security notion of non-malleability. The existing pairing-based zk-SNARKs designed from linear encoding are known to be vulnerable to algebraic manipulation of the proof. The latest SE-SNARKs check the proof consistency by increasing the proof size and the verification cost. In particular, the number of pairings increases almost doubles due to further verification. In this article, we propose two novel SE-SNARK constructions with a single verification. The consistency check is subsumed in a single verification through employing a hash function. The proof size and verification time of the proposed SE-SNARK schemes are minimal in that it is the same as the state-of-the-art zk-SNARK without non-malleability. The proof in our SE-SNARK constructions comprises only three group elements (type III) in the QAP-based scheme and two group elements (type I) in the SAP-based scheme. The verification time in both requires only 3 pairings. The soundness of the proposed schemes is proven under the hash-algebraic knowledge (HAK) assumption and the (linear) collision-resistant hash assumption.
Daniel Kales, Sebastian Ramacher, Christian Rechberger, Roman Walch · 5 authors
Post-quantum cryptography has received increased attention in recent years, in particular, due to the standardization effort by NIST. One of the second-round candidates in the NIST post-quantum standardization project is Picnic, a post-quantum secure signature scheme based on efficient zero-knowledge proofs of knowledge. In this work, we present the first FPGA implementation of Picnic. We show how to efficiently calculate LowMC, the block cipher used as a one-way function in Picnic, in hardware despite the large number of constants needed during computation. We then combine our LowMC implementation and efficient instantiations of Keccak to build the full Picnic algorithm. Additionally, we conform to recently proposed hardware interfaces for post-quantum schemes to enable easier comparisons with other designs. We provide evaluations of our Picnic implementation for both, the standalone design and a version wrapped with a PCIe interface, and compare them to the state-of-the-art software implementations of Picnic and similar hardware designs. Concretely, signing messages on our FPGA takes 0.25 ms for the L1 security level and 1.24 ms for the L5 security level, beating existing optimized software implementations by a factor of 4.
The Holy Grail of a decentralised stablecoin is achieved on rigorous mathematical frameworks, obtaining multiple advantageous proofs: stability, convergence, truthfulness, faithfulness, and malicious-security. These properties could only be attained by the novel and interdisciplinary combination of previously unrelated fields: model predictive control, deep learning, alternating direction method of multipliers (consensus-ADMM), mechanism design, secure multi-party computation, and zero-knowledge proofs. For the first time, this paper proves: - the feasibility of decentralising the central bank while securely preserving its independence in a decentralised computation setting - the benefits for price stability of combining mechanism design, provable security, and control theory, unlike the heuristics of previous stablecoins - the implementation of complex monetary policies on a stablecoin, equivalent to the ones used by central banks and beyond the current fixed rules of cryptocurrencies that hinder their price stability - methods to circumvent the impossibilities of Guaranteed Output Delivery (G.O.D.) and fairness: standing on truthfulness and faithfulness, we reach G.O.D. and fairness under the assumption of rational parties As a corollary, a decentralised artificial intelligence is able to conduct the monetary policy of a stablecoin, minimising human intervention.
We propose a cryptographic protocol with zero-knowledge proof (ZKP) on elliptic curves (EC) using public keys and random messages, allowing to establish the truth of a statement not conveying any additional information about the statement itself. The cryptographic protocols based on zero-knowledge proof allow identification, key exchange and other cryptographic operations to be performed without leakage of sensitive information during the information exchange. The implementation of the cryptographic protocol of the zero-knowledge proof on the basis of the mathematical apparatus of elliptic curves allows to significantly reduce the size of the protocol parameters and increase its cryptographic strength (computational complexity of the breaking). The security of cryptosystems involving elliptic curves is based on the difficulty of solving the elliptic curve discrete logarithm problem. We determine the completeness and correctness of the protocol and give an example of the calculation is given. The cryptographic protocol was modeled in the High-Level Protocol Specification Language, the model validation and verification of the protocol were also performed. The software verification of the cryptographic protocol was performed using the software modules On the Fly Model Checker and Constraint Logic based Attack Searcher. In order to validate the cryptographic protocol resistance to intruder attacks, we used the Security Protocol Animator package for Automated Validation of Internet Security Protocols and Applications. The security of the proposed cryptographic protocol ZKP EC is based on the difficulty of solving the elliptic curve discrete logarithm problem). The recommended elliptical curves according to DSTU 4145-2002 may be used to implement such cryptographic protocol.
We define a new query measure we call quantum distinguishing complexity, denoted QD(f) for a Boolean function f. Unlike a quantum query algorithm, which must output a state close to |0> on a 0-input and a state close to |1> on a 1-input, a "quantum distinguishing algorithm" can output any state, as long as the output states for any 0-input and 1-input are distinguishable. \nUsing this measure, we establish a new relationship in query complexity: For all total functions f, Q_0(f)=O~(Q(f)^5), where Q_0(f) and Q(f) denote the zero-error and bounded-error quantum query complexity of f respectively, improving on the previously known sixth power relationship. \nWe also define a query measure based on quantum statistical zero-knowledge proofs, QSZK(f), which is at most Q(f). We show that QD(f) in fact lower bounds QSZK(f) and not just Q(f). QD(f) also upper bounds the (positive-weights) adversary bound, which yields the following relationships for all f: Q(f) >= QSZK(f) >= QD(f) = Omega(Adv(f)). This sheds some light on why the adversary bound proves suboptimal bounds for problems like Collision and Set Equality, which have low QSZK complexity. \nLastly, we show implications for lifting theorems in communication complexity. We show that a general lifting theorem for either zero-error quantum query complexity or for QSZK would imply a general lifting theorem for bounded-error quantum query complexity.
While ‘classical’ human identity has kept philosophers busy since millennia, ‘Digital Identity’ seems primarily machine related. Telephone numbers, E-Mail inboxes, or Internet Protocol (IP)-addresses are irrelevant to define us as human beings at first glance. However, with the omnipresence of digital space the digital aspects of identity gain importance. In this submission, we aim to put recent developments in context and provide a categorization to frame the landscape as developments proceed rapidly. First, we present selected philosophical perspectives on identity. Secondly, we explore how the legal landscape is approaching identity from a traditional dogmatic perspective both in national and international law. After blending the insights from those sections together in a third step, we will go on to describe and discuss current developments that are driven by the emergence of new tools such as ‘Distributed Ledger Technology’ and ‘Zero Knowledge Proof’. One of our main findings is that the management of digital identity is transforming from a purpose driven necessity towards a self-standing activity that becomes a resource for many digital applications. In other words, whereas traditionally identity is addressed in a predominantly sectoral fashion whenever necessary, new technologies transform digital identity management into a basic infrastructural service, sometimes even a commodity. This coincides with a trend to take the ‘control’ over identity away from governmental institutions and corporate actors to ‘self-sovereign individuals’, who have now the opportunity to manage their digital self autonomously. To make our conceptual statements more relevant, we present several already existing use cases in the public and private sector. Subsequently, we discuss potential risks that should be mitigated in order to create a desirable relationship between the individual, public institutions, and the private sector in a world where self-sovereign identity management has become the norm. We will illustrate these issues along the discussion around privacy, as well as the development of backup mechanisms for digital identities. Despite the undeniable potential for the management of identity, we suggest that particularly at this point in time there is a clear need to make detailed (non-technological) governance decisions impacting the general design and implementation of self-sovereign identity systems.
Jan 1, 2019·Proceedings of the 16th International Joint Conference on e-Business and Telecommunications - Volume 2: SECRYPT, 325-332, 2019, Prague, Czech Republic
Martin Schanzenbach, Thomas Kilian, Julian Schütte, Christian Banse
In this paper we present ZKlaims: a system that allows users to present attribute-based credentials in a privacy-preserving way. We achieve a zero-knowledge property on the basis of Succinct Non-interactive Arguments of Knowledge (SNARKs). ZKlaims allow users to prove statements on credentials issued by trusted third parties. The credential contents are never revealed to the verifier as part of the proving process. Further, ZKlaims can be presented non-interactively, mitigating the need for interactive proofs between the user and the verifier. This allows ZKlaims to be exchanged via fully decentralized services and storages such as traditional peer-to-peer networks based on distributed hash tables (DHTs) or even blockchains. To show this, we include a performance evaluation of ZKlaims and show how it can be integrated in decentralized identity provider services.
Mary Maller, Sean Bowe, Markulf Kohlweiss, Sarah Meiklejohn
Ever since their introduction, zero-knowledge proofs have become an important tool for addressing privacy and scalability concerns in a variety of applications. In many systems each client downloads and verifies every new proof, and so proofs must be small and cheap to verify. The most practical schemes require either a trusted setup, as in (pre-processing) zk-SNARKs, or verification complexity that scales linearly with the complexity of the relation, as in Bulletproofs. The structured reference strings required by most zkSNARK schemes can be constructed with multi-party computation protocols, but the resulting parameters are specific to an individual relation. Groth et al. discovered a zk-SNARK protocol with a universal structured reference string that is also updatable, but the string scales quadratically in the size of the supported relations.<br/> <br/>Here we describe a zero-knowledge SNARK, Sonic, which supports a universal and continually updatable structured reference string that scales linearly in size. We also describe a generally useful technique in which untrusted “helpers” can compute advice that allows batches of proofs to be verified more efficiently. Sonic proofs are constant size, and in the “helped” batch verification context the marginal cost of verification is comparable with the most efficient SNARKs in the literature<br/>
The Fiat-Shamir (FS) transform is a well known and widely used technique to convert any constant-round public-coin honest-verifier zero-knowledge (HVZK) proof or argument system \(\mathsf {HVZK}=(\mathcal {P},\mathcal {V})\) in a non-interactive zero-knowledge (NIZK) argument system
Zero-Knowledge Proof-of-Identity from trusted public certificates (e.g., national identity cards and/or ePassports; eSIM) is introduced here to permissionless blockchains in order to remove the inefficiencies of Sybil-resistant mechanisms such as Proof-of-Work (i.e., high energy and environmental costs) and Proof-of-Stake (i.e., capital hoarding and lower transaction volume). The proposed solution effectively limits the number of mining nodes a single individual would be able to run while keeping membership open to everyone, circumventing the impossibility of full decentralization and the blockchain scalability trilemma when instantiated on a blockchain with a consensus protocol based on the cryptographic random selection of nodes. Resistance to collusion is also considered. Solving one of the most pressing problems in blockchains, a zk-PoI cryptocurrency is proved to have the following advantageous properties: - an incentive-compatible protocol for the issuing of cryptocurrency rewards based on a unique Nash equilibrium - strict domination of mining over all other PoW/PoS cryptocurrencies, thus the zk-PoI cryptocurrency becoming the preferred choice by miners is proved to be a Nash equilibrium and the Evolutionarily Stable Strategy - PoW/PoS cryptocurrencies are condemned to pay the Price of Crypto-Anarchy, redeemed by the optimal efficiency of zk-PoI as it implements the social optimum - the circulation of a zk-PoI cryptocurrency Pareto dominates other PoW/PoS cryptocurrencies - the network effects arising from the social networks inherent to national identity cards and ePassports dominate PoW/PoS cryptocurrencies - the lower costs of its infrastructure imply the existence of a unique equilibrium where it dominates other forms of payment
Mathematics is not universal.Traditional (normal) mathematics accepts both deductive and empirical proofs like science.Colonial education replaced it with formal mathematics, the unique feature of which is not the use of reasoning but exclusion of the empirical.The coloniser never critically compared normal and formal mathematics, and tries to block such a comparison today.In Western dogma (of the church theology of reason) deduction is infallible.In fact, deduction is fallible.(1) An invalid deductive proof may be mistaken as valid.Doubts about validity can only be settled inductively.In practice, doubts are settled by invoking authority.Hence, deductive proofs are always more fallible than empirical proofs.(2) The postulates of formal math cannot be empirically checked; they are metaphysics (a metaphysics of infinity is needed even for the formal math of 1+1=2).Thus, far from being eternal truths, formal mathematical theorems may not even be approximately valid knowledge.(3) Formal math dogmatically assumes two-valued logic (on the superstition that logic binds God).But logic is neither culturally universal (e.g.Buddhist logic) nor empirically certain (quantum logic).Therefore, the theorems of formal math (even if valid) are not even truths relative to postulates.Hence, colonial/formal math is inferior and should be rejected.This does not affect the practical value of math -what 'works'which all comes from normal math which we should, accordingly, teach.I describe two actual decolonised math courses being taught: decolonised geometry in school, and decolonised calculus in the university.Decolonised (string) geometry that is indigenous to Africa and India, is superior to the geometry currently taught in terms of conceptual clarity (points, angle, distance), ease of learning, and practical applications.Decolonised calculus teaches calculus as normal math, the way it originated in India as a numerical technique to solve differential equations, together with non-Archimedean arithmetic (instead of formal 'real' numbers) and zeroism (instead of limits) used to sum infinite series.Europeans stole calculus from India, and falsely attributed it to Newton and Leibniz, who failed to understand how to sum infinite series due to the Western superstition (since Plato) that mathematics is eternal truth, and hence exact.Eventually, they introduced a metaphysics of infinity allied to church dogmas of eternityset theory, formal real numbers, and limitsas taught in university today.This metaphysics is irrelevant for any practical application of calculus, such as sending a rocket to the moon, but makes calculus very difficult.Decolonised calculus is easy, requires almost no background, and results in better science.It enables students to solve harder problems not covered in usual calculus courses.However, it excludes the ability to slip politically convenient dogmas into science through the metaphysics of formal math, and is, hence, resisted by the coloniser today.