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.
This paper addresses the problem of uploading large quantities of sensitive industrial data to a public distributed network by proposing a new framework. The framework combines the existing technologies of the distributed web and distributed ledger to provide a mechanism of encrypting data and choosing whom to share the data with. The framework is designed to work with existing platforms; the InterPlanetary File System (IPFS) and the Ethereum blockchain platforms are used as examples within this paper, though it is stated that similar platforms are capable of providing the requirements for the framework to operate. The framework uses the concept of the Diffie-Hellman Key Exchange (DHKE), and is implemented in three different mechanisms of the DHKE: one-step Elliptical-Curve Diffie-Hellman Key Exchange (ECDH); two-step ECDH; and Supersingular Isogeny Diffie-Hellman Key Exchange (SIDH). The paper discusses the security of each along with individual advantages and disadvantages, and concludes that the SIDH is the most appropriate implementation for future use due to it being post-quantum secure.
Most cryptocurrency systems or systems based on blockchain technology are currently using the elliptic curves digital signature algorithm (ECDSA) on the secp256k1 curve, which is susceptible to backdoors implemented by the curve creator (secp256k1). The paper proposes a multiple elliptic curves digi-tal signature algorithm (MECDSA), which allows not only for setting the number of elliptic curves according to practical security requirements, but also for editing the parameters of each elliptic curve. The performance analy-sis proves that the scheme is secure and efficient, and can avoid any back-doors implemented by curve creators. We suggest that the systems based on blockchain should operate in two elliptic curves considering the contradic-tion between security and efficiency.
Preuves à divulgation nulle de connaissance efficaces à base de réseaux euclidiens et applications Le chiffrement à base de réseaux euclidiens a connu un grand essor durant les vingt dernières années. Autant grâce à l’apparition de nouvelles primitives telles que le chiffrement complètement homomorphe, que grâce à l’amélioration des primitives existantes, comme le chiffrement á clef publique ou les signatures digitales, qui commencent désormais à rivaliser avec leurs homologues fondés sur la théorie des nombres. Cela dit les preuves à divulgation nulle de connaissance, bien qu’elles représentent un des piliers des protocols de confidentialité, n’ont pas autant progressé, que ce soit au niveau de leur expressivité que de leur efficacité. Cette thèse s’attelle dans un premier temps à améliorer l’état de l’art en matière de preuves à divulgation nulle de connaissance. Nous construisons une preuve d’appartenance à un sous ensemble dont la taille est indépendante de l’ensemble en question. Nous construisons de même une preuve de connaissance amortie qui est plus efficace et plus simple que toutes les constructions qui la précèdent. Notre second propos est d’utiliser ces preuves à divulgation nulle de connaissance pour construire de nouvelles primitives cryptographiques. Nous concevons une signature de groupe dont la taille est indépendante du groupe en question, ainsi qu’un schéma de vote électronique hautement efficace, y compris pour des élections à grand échelle.
Proposed cryptographic protocol with zero-knowledge proof on elliptic curves using one-way hash function, allowing to establish the truth of allegation and does not convey any additional information about the approval. 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 the cryptographic stability (computational complexity of the hacking problem). The security of cryptosystems on elliptic curves is based on the difficulty of solving the elliptic curve discrete logarithm problem. The completeness and correctness of the protocol is determined in the work, an example of calculation is given, the cryptographic protocol is modeled on the High-Level Protocol Specification Language, the model validation and verification of the protocol are performed. Software verification of the cryptographic protocol was performed using the software modules On the Fly Model Checker and Constraint Logic based Attack Searcher. To validation the cryptographic protocol for resistance to intruder attacks was used the Security Protocol Animator package for Automated Validation of Internet Security Protocols and Applications. The security of the proposed cryptographic protocol is based on the difficulty of solving the elliptic curve discrete logarithm problem and the cryptographic stability of the hash function. To implement the cryptographic protocol, you can use the recommended elliptical curves according to DSTU 4145-2000 and the hash function GOST 34.311-95.
We propose building a new PKC in a ring structure, the classification of rings being an open problem. The difficulty of the scheme is based on retrieving the eigenvalues of endomorphism on a finite type module over a non-commutative ring. It is resistant to a chosen cipher text attack. Working in the fraction ring of a non-commutative ring makes our scheme a zero-knowledge proof of knowledge, result indistinguishable, in the Naor-Yung model. Finally, a dramatic improvement in security is obtained through the drawing with uniform probability of the working ring at high frequency.
Card‐based physical access control systems are used by most people on a daily basis, for example, at work, in public transportation, or at hotels. Yet these systems have often very poor cryptographic protection. User identifiers and keys can be easily eavesdropped on and counterfeited. The privacy‐preserving features are almost missing in these systems. To improve this state, we propose a novel cryptographic scheme based on efficient zero‐knowledge proofs and Boneh‐Boyen signatures. The proposed scheme is provably secure and provides the full set of privacy‐enhancing features, that is, the anonymity, untraceability, and unlinkability of users. Furthermore, our scheme supports distributed multidevice authentication with multiple RFID (Radio‐Frequency IDentification) user devices. This feature is particularly important in applications for controlling access to dangerous sites where the presence of protective equipment is checked during each access control session. Besides the full cryptographic specification, we also show the results of our implementation on devices commonly used in access control applications, particularly the smart cards and embedded verification terminals. By avoiding costly operations on user devices, such as bilinear pairings, we were able to achieve times comparable to existing systems (around 500 ms), while providing significantly higher security, privacy protection, and features for RFID multidevice authentication.
Eli Ben‐Sasson, Iddo Bentov, Yinon Horesh, Michael Riabzev
The family of Reed-Solomon (RS) codes plays a prominent role in the construction of quasilinear probabilistically checkable proofs (PCPs) and interactive oracle proofs (IOPs) with perfect zero knowledge and polylogarithmic verifiers. The large concrete computational complexity required to prove membership in RS codes is one of the biggest obstacles to deploying such PCP/IOP systems in practice. To advance on this problem we present a new interactive oracle proof of proximity (IOPP) for RS codes; we call it the Fast RS IOPP (FRI) because (i) it resembles the ubiquitous Fast Fourier Transform (FFT) and (ii) the arithmetic complexity of its prover is strictly linear and that of the verifier is strictly logarithmic (in comparison, FFT arithmetic complexity is quasi-linear but not strictly linear). Prior RS IOPPs and PCPs of proximity (PCPPs) required super-linear proving time even for polynomially large query complexity. For codes of block-length N, the arithmetic complexity of the (interactive) FRI prover is less than 6 * N, while the (interactive) FRI verifier has arithmetic complexity <= 21 * log N, query complexity 2 * log N and constant soundness - words that are delta-far from the code are rejected with probability min{delta * (1-o(1)),delta_0} where delta_0 is a positive constant that depends mainly on the code rate. The particular combination of query complexity and soundness obtained by FRI is better than that of the quasilinear PCPP of [Ben-Sasson and Sudan, SICOMP 2008], even with the tighter soundness analysis of [Ben-Sasson et al., STOC 2013; ECCC 2016]; consequently, FRI is likely to facilitate better concretely efficient zero knowledge proof and argument systems. Previous concretely efficient PCPPs and IOPPs suffered a constant multiplicative factor loss in soundness with each round of "proof composition" and thus used at most O(log log N) rounds. We show that when delta is smaller than the unique decoding radius of the code, FRI suffers only a negligible additive loss in soundness. This observation allows us to increase the number of "proof composition" rounds to Theta(log N) and thereby reduce prover and verifier running time for fixed soundness.
Preuves à divulgation nulle de connaissance pour le calcul sécurisé Dans cette thèse, nous étudions les preuves à divulgation nulle de connaissance, une primitive cryptographique permettant de prouver une assertion en ne révélant rien de plus que sa véracité, et leurs applications au calcul sécurisé. Nous introduisons tout d’abord un nouveau type de preuves à divulgation nulle, appelées arguments implicites à divulgation nulle, intermédiaire entre deux notions existantes, les preuves interactives et les preuves non interactives à divulgation nulle. Cette nouvelle notion permet d’obtenir les mêmes bénéfices en terme d’efficacité que les preuves non-interactives dans le contexte de la construction de protocoles de calcul sécurisé faiblement interactifs, mais peut être instanciée à partir des mêmes hypothèses cryptographiques que les preuves interactives, permettant d’obtenir de meilleures garanties d’efficacité et de sécurité. Dans un second temps, nous revisitons un système de preuves à divulgation nulle de connaissance qui est particulièrement utile dans le cadre de protocoles de calcul sécurisé manipulant des nombres entiers, et nous démontrons que son analyse de sécurité classique peut être améliorée pour faire reposer ce système de preuve sur une hypothèse plus standard et mieux connue. Enfin, nous introduisons une nouvelle méthode de construction de systèmes de preuves à divulgation nulle sur les entiers, qui représente une amélioration par rapport aux méthodes existantes, tout particulièrement dans un modèle de type client-serveur, où un client à faible puissance de calcul participe à un protocole de calcul sécurisé avec un serveur à forte puissance de calcul.
The systematic introduction to zero knowledge proof protocol has important theoretical guidance and practical significance on attracting more scholars involved in research as well as expanding application fields. Zero-knowledge proofs were first conceived in 1985 by Shafi Golwasser, Silvio Micalli and Charles Rackoff in a draft of the knowledge complexity of interactive proof systems. The goal of the present paper is to introduce a new identity based scheme which is a combination of zero-knowledge interactive proof and weil pairing on elliptic curves. The concept of weil pairing was first introduced by Andre Weil in 1940. It plays an important role in the theoretical study of the arithmetic of elliptic curves and Abelian varieties. It has also recently become extremely useful in cryptologic constructions related to these objects.
With the rise of Bitcoin, blockchain which is the core technology of Bitcoin has received increasing attention. Privacy preserving and performance on blockchain are two research points in academia and business, but there are still some unresolved issues in both respects. An aggregate signature scheme is a digital signature that supports making signatures on many different messages generated by many different users. Using aggregate signature, the size of the signature could be shortened by compressing multiple signatures into a single signature. In this paper, a new signature scheme for transactions on blockchain based on the aggregate signature was proposed. It was worth noting that elliptic curve discrete logarithm problem and bilinear maps played major roles in our signature scheme. And the security properties of our signature scheme were proved. In our signature scheme, the amount will be hidden especially in the transactions which contain multiple inputs and outputs. Additionally, the size of the signature on transaction is constant regardless of the number of inputs and outputs that the transaction contains, which can improve the performance of signature. Finally, we gave an application scenario for our signature scheme which aims to achieve the transactions of big data on blockchain.
With the rise of Bitcoin, cryptographic currencies have attracted more and more attention. Subsequently, other cryptographic currencies were gradually created, such as Zcash, Moreno, Dash and so on. In cryptographic currency, privacy preserving and expansion are two key technical points. In terms of privacy preserving, more effective solutions were proposed in Zcach, Moreno, Dash and other cryptographic currencies systems, in which ring signature, zero knowledge proof and other cryptographic techniques played important roles. But these schemes mainly considered protecting the addresses of both sides of the transaction. In terms of expansion, lightning network and other projects also give solutions. But most of these projects will bring other problems. In this paper, a signature scheme based on the aggregate signature and the elliptic curve algorithm is proposed to hide the transaction value of a single sender and receiver in the transactions which contain multiple inputs and outputs. This signature scheme achieves the purpose of privacy preserving from the transaction value. Further, the correctness proof and security analysis are given in this paper. In addition to that, another signature scheme that combines aggregation signature with bilinear ring signature is proposed. This aggregate ring signature scheme gives another attempt to solve the problem of expansion in the cryptographic currency system only using cryptographic technologies. At the same time, the sender's addresses can be hidden. Similarly, we also confirmed the correctness of this signature scheme.
Innovative idea using ring theory is raised to build a new algorithm for zero knowledge (ZK) cryptosystem. In this paper we introduce an algorithm for zero knowledge protocol based on a specific kind of rings named weak Armendariz. On the other hand, the aim of this paper focuses on the category of noncommutative algebraic structures to describe a new algebraic scheme of zero knowledge proof using weak Armendariz rings. As a result, we employ for the first time weak Armendariz rings in the science of cryptographic which regards as a new application of this class of rings. Finally, we present a novel idea combining between abstract algebra and cryptography.
Nicolas T. Courtois, Guangyan Song, Ryan Castellucci
Abstract In this paper, we study and give the first detailed benchmarks on existing implementations of the secp256k1 elliptic curve used by at least hundreds of thousands of users in Bitcoin and other cryptocurrencies. Our implementation improves the state of the art by a factor of 2.5 with a focus on the cases, where side channel attacks are not a concern and a large quantity of RAM is available. As a result, we are able to scan the Bitcoin blockchain for weak keys faster than any previous implementation. We also give some examples of passwords which we have cracked, showing that brain wallets are not secure in practice even for quite complex passwords.
We propose new constructions for inner product encryption – Open image in new window and Open image in new window , both secure under the eXternal Diffie-Hellman assumption (SXDH) in asymmetric pairing groups. The first scheme has constant-size ciphertexts whereas the second one is weakly attribute hiding. Open image in new window is derived from the identity-based encryption scheme of Jutla Roy (Asiacrypt 2013), that was extended from tag-based quasi-adaptive non-interactive zero-knowledge (QA-NIZK) proofs for linear subspaces of vector spaces over bilinear groups. The verifier common reference string (CRS) in these tag-based systems are split into two parts, that are combined during verification. We consider an alternate form of the tag-based QA-NIZK proof with a single verifier CRS that already includes a tag, different from the one defining the language. The verification succeeds as long as the two tags are unequal. Essentially, we embed a two-equation revocation mechanism in the verification. The new QA-NIZK proof system leads to Open image in new window , a constant-sized ciphertext IPE scheme with very short ciphertexts. Both the IPE schemes are obtained by applying the n-equation revocation technique of Attrapadung and Libert (PKC 2010) to the corresponding identity based encryption schemes and proved secure under SXDH assumption. As an application, we show how our schemes can be specialised to obtain the first fully secure identity-based broadcast encryption based on SXDH with a trade-off among the public parameters, ciphertext and key sizes, all of them being sub-linear in the maximum number of recipients of a broadcast.
Kriptovalute su digitalni novac utemeljen na kriptografiji i decentraliziranom sustavu. Postoje samo u elektroničkom obliku kao jedinstveni digitalni novčići ("tokeni"). Iza njih ne stoji autoritet države niti ih je moguće svojevoljno proizvesti. Rad se fokusira na značajkama, postavkama, razvoju i svim međuodnosima važnih ekonomskih faktora koji utječu na kriptovalute. U prvom poglavlju navedena su obilježja kriptovaluta. Drugo poglavlje daje primjere i govori o primjeni kriptovaluta u svakodnevnom životu. U trećem poglavlju je raspravljano o trenutnim i budućim regulacijama najmoćnijih zemalja svijeta (G20) , kao i njihovoj zajedničkoj suradnji u želji za jedinstvenim i standardiziranim pravilima, a sve u svrhu što kvalitetnijeg nadzora nad kriptovalutama kako bi se spriječile malverzacije i zaštitili potrošači. Četvrto poglavlje govori o inicijalnoj ponudi kovanica, a peto poglavlje je namijenjeno sigurnosti kriptovaluta. Cilj istraživanja je utvrditi koliko je studentska populacija upoznata i usmjerena prema novim oblicima digitalnog novca, koje značajke kriptovaluta smatraju pozitivnima, a koje negativnima i u kojoj su mjeri investirali ili su spremni investirati dio svojih ulaganja u kriptovalute i sl. Metode istraživanja korištene u radu su kompilacija na temelju proučavanja postojeće literature o temi rada, prikupljanje i analiza podataka vezanih uz kriptovalute, ponajprije podataka vezanih uz cijene i tržišnu kapitalizaciju, anketiranje studenata Ekonomskog fakulteta u Rijeci i metoda dedukcije putem koje su pokazane sve važne karakteristike i obilježja kriptovaluta. Na temelju provedene ankete u kojoj je sudjelovalo 90 studenata Ekonomskog fakulteta u Rijeci zaključak toga dijela istraživanja je da je mlada populacija dobro upoznata s kriptovalutama i njenim glavnim značajkama, ali i određenim nedostatkom informiranosti o tehnologiji (trećina studenata nije čula za pojam "blockchain") i nedovoljnoj odlučnosti oko investiranja i trgovanja u kriptovalute. Povrh toga, dokazan je i negativan utjecaj hakerskih napada i određenih kriminalnih radnji, kao i nestabilnost tržišne cijene na povjerenje studenata, ali i ukupne populacije vezane uz globalni financijski sustav u kriptovalute. Ishod istraživanja omogućio je da zaključimo kako su kriptovalute trenutno u ranoj fazi razvoja i nisu se dovoljno implementirale za široku primjenu u trgovini roba i usluga ili općenito kao sredstvo razmjene. Faktor koji je uključen u istraživanje kako bi opisao veličinu, odnosno obujam neke kriptovalute je tržišna kapitalizacija u dolarima. Temeljna ideja ovog rada je informirati čitatelja o pozitivnim i negativnim značajkama koje se se vežu uz kriptovalute. Na taj način čitatelji će biti bolje informirani i educirani o potencijalnom riziku ulaganja u kriptovalute, kao i većoj razini zaštite prilikom posjedovanja neke digitalne valute.
The protocols for member expansion in secret sharing schemes are very useful for key management in dynamic topology networks. In order to reduce the computation complexity of the existed protocols for member expansion in secret sharing schemes, a new protocol is proposed based on the problem of elliptic curve discrete logarithm. This paper examines fifteen most recent patens that were awarded in the area of secret sharing. Unlike traditional detailed patent reviews that are focused on applying the simple secret sharing method, the proposed protocol has the following merits: 1) there is no trust center ; 2) only requesting broadcast 2 1 t + times to generate the sub-secret for the new participant and the new participant can verify the truth of the sub-secret; 3) the old participants can verify the new sub-secret by the noninteractive zero-knowledge proof protocol; 4) In the sub-secret generation stage, not only sub-secrets of old participants but also the sub-secret of new participant is secure. Compared to the existed protocols, the proposed protocol has lower computational complexity and less communications. Therefore, the proposed protocol has higher performance and is suitable for resource-constrained terminals of dynamic networks.
ECDSA has become a popular choice as lightweight alternative to RSA and classic DL based signature algorithms in recent years. As standardized, the signature produced by ECDSA for a pair of a message and a key is not deterministic. This work shows how this non-deterministic choice can be exploited by an attacker to leak private information through the signature without any side channels, an attack first discovered by Young and Yung for classic DL-based cryptosystems in 1997, and how this attack affects the application of ECDSA in the Bitcoin protocol.