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.
For any pair $(X,Z)$ of correlated random variables we can think of $Z$ as a randomized function of $X$. Provided that $Z$ is short, one can make this function computationally efficient by allowing it to be only approximately correct. In folklore this problem is known as \emph{simulating auxiliary inputs}. This idea of simulating auxiliary information turns out to be a powerful tool in computer science, finding applications in complexity theory, cryptography, pseudorandomness and zero-knowledge. In this paper we revisit this problem, achieving the following results: \begin{enumerate}[(a)] We discuss and compare efficiency of known results, finding the flaw in the best known bound claimed in the TCC'14 paper "How to Fake Auxiliary Inputs". We present a novel boosting algorithm for constructing the simulator. Our technique essentially fixes the flaw. This boosting proof is of independent interest, as it shows how to handle "negative mass" issues when constructing probability measures in descent algorithms. Our bounds are much better than bounds known so far. To make the simulator $(s,ε)$-indistinguishable we need the complexity $O\left(s\cdot 2^{5\ell}ε^{-2}\right)$ in time/circuit size, which is better by a factor $ε^{-2}$ compared to previous bounds. In particular, with our technique we (finally) get meaningful provable security for the EUROCRYPT'09 leakage-resilient stream cipher instantiated with a standard 256-bit block cipher, like $\mathsf{AES256}$.
Cryptography relies on Mathematics in all its aspects, beginning from the constructions relying on various mathematical theories, continuing with security evaluation of cryptographic systems, and proving their security, and finally ending in implementation.Recently, new security threats are posed by the emerging quantum computing technology.Specifically, quantum algorithms can break some public-key encryption schemes such as RSA and Elgamal, which are widely used for protection of computer systems and networks.This issue demands us to develop a new generation of cryptographic systems, which will serve as secure alternatives to the currently used ones.Such the new systems are referred to as the post-quantum cryptography.One promising direction in post-quantum cryptography is the systems whose security is based on hardness of mathematical problems arising in the context of coding theory.In particular, the problem of decoding random linear codes has been studied for over 30 years, and still no polynomial-time solution has been proposed, even when using quantum algorithms.In this thesis, we focus on this area, which is called the code-based cryptography.The first code-based public-key encryption (PKE) scheme was introduced by R.J. McEliece in 1978.Since then, various code-based public-key encryption, digital signature and identification schemes were introduced, but currently, one of the main challenges is to introduce more advanced cryptographic functionalities based on coding.In this thesis, first, we give a brief introduction about post-quantum cryptography and codebased cryptography, and then we provide the background information about the cryptographic primitives, which we will study, as well as the relevant notions and results from coding theory and cryptography.Next, we introduce our contributions as follows.Firstly, we study zero-knowledge (ZK) identification schemes based q-ary linear codes.We show that when q < 5, a straightforward generalization of Stern's ZK identification scheme (1993) is more efficient in terms of both communication and computation, as compared to the ZK identification scheme by Cayrel, Vron and El Yousfi Alaoui (2010), which is specifically designed for q-ary codes.Secondly, we introduce the first proof of plaintext knowledge (PPK) for the McEliece PKE and the Niederreiter PKE.These protocols allow the encryptor to prove the knowledge of the plaintext contained in a given ciphertext to any party, who does not hold the secret key for decryption.We also provide a performance evaluation for the proposed schemes.
In this thesis we present our contribution in the field of post-quantum cryptography. We introduce a new notion of weakly Random-Self-Reducible public-key cryptosystem and show how it can be used to implement secure Oblivious Transfer. We also show that two recent (Post-quantum) cryptosystems can be considered as weakly Random-Self-Reducible. We introduce a new problem called Isometric Lattice Problem and reduce graph isomorphism and linear code equivalence to this problem. We also show that this problem has a perfect zero-knowledge interactive proof with respect to a malicious verifier; this is the only hard problem in lattices that is known to have this property.
Abstract. LowMC is a collection of block cipher families introduced at Eurocrypt 2015 by Albrecht et al. Its design is optimized for instanti-ations of multi-party computation, fully homomorphic encryption, and zero-knowledge proofs. A unique feature of LowMC is that its internal affine layers are chosen at random, and thus each block cipher family contains a huge number of instances. The Eurocrypt paper proposed two specific block cipher families of LowMC, having 80-bit and 128-bit keys. In this paper, we mount interpolation attacks (algebraic attacks intro-duced by Jakobsen and Knudsen) on LowMC, and show that a practically significant fraction of 2−38 of its 80-bit key instances could be broken 223 times faster than exhaustive search. Moreover, essentially all instances that are claimed to provide 128-bit security could be broken about 1000 times faster. In order to obtain these results, we had to develop novel techniques and optimize the original interpolation attack in new ways. While some of our new techniques exploit specific internal properties of LowMC, others are more generic and could be applied, in principle, to any block cipher.
In this paper we present a new primitive for a key exchange protocol based on multivariate non-commutative polynomial rings, analogous to the classic Diffie-Hellman method. Our technique extends the proposed scheme of Boucher et al. from 2010. Their method was broken by Dubois and Kammerer in 2011, who exploited the Euclidean domain structure of the chosen ring. However, our proposal is immune against such attacks, without losing the advantages of non-commutative polynomial rings as outlined by Boucher et al. Moreover, our extension is not restricted to any particular ring, but is designed to allow users to readily choose from a large class of rings when applying the protocol. Our primitive can also be applied to other cryptographic paradigms. In particular, we develop a three-pass protocol, a public key cryptosystem, a digital signature scheme and a zero-knowledge proof protocol.
One of important issues of information security in the interaction of users is the use of methods and tools, allowing one party to make sure of the authenticity of another party. The proof of knowledge protocols which have the additional property of zero-knowledge are applied to solve this problem. The protocols based on asymmetric encryption have received wide acceptance, such as the Fiat-Shamir, Schnorr, Okamoto, Guillou-Quisquater, Brickell-McCurley, Feige-Fiat-Shamir protocols. Cryptographic strength of these protocols is defined by discrete logarithms in a finite prime field, as well as an increase in the number of accreditation cycles. As a result of the development of methods and tools of cryptanalysis and rapid development of technologies and power of computing systems, there is a need to increase the sizes of system-wide parameters of the protocol, leading to increased resource intensity and performance complexity of basic operations in the fields.Cryptographic zero-knowledge protocols on elliptic curves are proposed in the paper. The strength of cryptosystems on elliptic curves is based on the difficulty of solving the discrete logarithm problem in the group of elliptic curve points, and is more difficult than the discrete logarithm problem in the finite field. The completeness and soundness of protocols were determined, computation examples were given. The tools of the Strength Protocol Animator package were applied to verify the protocols for resistance to enemy attacks. Consequently, the use of cryptographic protocols on elliptic curves will significantly reduce the sizes of protocol parameters and increase the cryptographic strength
In this paper we present a new 5-pass identification scheme with asymptotic\ncheating probability 1/2 based on the syndrome decoding problem. Our protocol\nis related to the Stern identification scheme but has a reduced communication\ncost compared to previous code-based zero-knowledge schemes, moreover our\nscheme permits to obtain a very low size of public key and secret key. The\ncontribution of this paper is twofold, first we propose a variation on the\nStern authentication scheme which permits to decrease asymptotically the\ncheating probability to 1/2 rather than 2/3 (and very close to 1/2 in practice)\nbut with less communication. Our solution is based on deriving new challenges\nfrom the secret key through cyclic shifts of the initial public key syndrome; a\nnew proof of soundness for this case is given Secondly we propose a new way to\ndeal with hashed commitments in zero-knowledge schemes based on Stern's scheme,\nso that in terms of communication, on the average, only one hash value is sent\nrather than two or three. Overall our new scheme has the good features of\nhaving a zero-knowledge security proof based on well known hard problem of\ncoding theory, a small size of secret and public key (a few hundred bits), a\nsmall calculation complexity, for an overall communication cost of 19kb for\nauthentication (for a $2^{16}$ security) and a signature of size of 93kb\n(11.5kB) (for security $2^{80}$), an improvement of 40% compared to previous\nschemes based on coding theory.\n
In this paper we present a new 5-pass identification scheme with asymptotic cheating probability 1/2 based on the syndrome decoding problem. Our protocol is related to the Stern identification scheme but has a reduced communication cost compared to previous code-based zero-knowledge schemes, moreover our scheme permits to obtain a very low size of public key and secret key. The contribution of this paper is twofold, first we propose a variation on the Stern authentication scheme which permits to decrease asymptotically the cheating probability to 1/2 rather than 2/3 (and very close to 1/2 in practice) but with less communication. Our solution is based on deriving new challenges from the secret key through cyclic shifts of the initial public key syndrome; a new proof of soundness for this case is given Secondly we propose a new way to deal with hashed commitments in zero-knowledge schemes based on Stern's scheme, so that in terms of communication, on the average, only one hash value is sent rather than two or three. Overall our new scheme has the good features of having a zero-knowledge security proof based on well known hard problem of coding theory, a small size of secret and public key (a few hundred bits), a small calculation complexity, for an overall communication cost of 19kb for authentication (for a $2^{16}$ security) and a signature of size of 93kb (11.5kB) (for security $2^{80}$), an improvement of 40% compared to previous schemes based on coding theory.
Zeev Dvir, Dan Gutfreund, Guy N. Rothblum, Salil Vadhan
Abstract: We investigate the complexity of the following computational problem: Polynomial Entropy Approximation (PEA): Given a low-degree polynomial mapping p: Fn → Fm, where F is a finite field, approximate the output entropy H(p(Un)), where Un is the uniform distribution on Fn and H may be any of several entropy measures. We show: • Approximating the Shannon entropy of degree 3 polynomials p: Fn 2 → Fm 2 over F2 to within an additive constant (or even n.9) is complete for SZKPL, the class of problems having statistical zero-knowledge proofs where the honest verifier and its simulator are computable in logarithmic space. (SZKPL contains most of the natural problems known to be in the full class SZKP.) • For prime fields F = F2 and homogeneous quadratic polynomials p: Fn → Fm, there is a probabilistic polynomial-time algorithm that distinguishes the case that p(Un) has entropy smaller than k from the case that p(Un) has min-entropy (or even Renyi entropy) greater than (2 + o(1))k. • For degree d polynomials p: Fn 2 → Fm 2, there is a polynomial-time algorithm that distinguishes the case that p(Un) has max-entropy smaller than k (where the max-entropy of a random variable is the logarithm of its support size) from the case that p(Un) has max-entropy at least (1 + o(1)) · kd (for fixed d and large k).
We present new candidates for quantum-resistant public-key cryptosystems based on the conjectured difficulty of finding isogenies between supersingular elliptic curves. The main technical idea in our scheme is that we transmit the images of torsion bases under the isogeny in order to allow the parties to construct a shared commutative square despite the noncommutativity of the endomorphism ring. Our work is motivated by the recent development of a subexponential-time quantum algorithm for constructing isogenies between ordinary elliptic curves. In the supersingular case, by contrast, the fastest known quantum attack remains exponential, since the noncommutativity of the endomorphism ring means that the approach used in the ordinary case does not apply. We give a precise formulation of the necessary computational assumptions along with a discussion of their validity, and prove the security of our protocols under these assumptions. In addition, we present implementation results showing that our protocols are multiple orders of magnitude faster than previous isogeny-based cryptosystems over ordinary curves. This paper is an extended version of [19]. We add a new zero-knowledge identification scheme, and detailed security proofs for the protocols. We also present a new, asymptotically faster, algorithm for key generation, a thorough study of its optimization, and new experimental data.
We use an idea of linear representations of the symmetric group to reduce the number of communication rounds in the verification protocol, proposed in Crypto 2005 by Peng et al., of a shuffling. We assume Paillier encryption scheme with which we can apply some known zero-knowledge proofs following the same line of approaches of Peng et al. Incidence matrices of 1-subsets and 2-subsets of a finite set is intensively used for the implementation, and the idea of <TEX>$\lambda$</TEX>-designs is employed for the improvement of the computational complexity.
Recent studies argue that traditional voting systems do not encourage increased voter participation due to constraints in time, location, accuracy, and, accessibility. To ensure the rights of a democratic society and to enhance and secure the voting rights of citizens by surpassing all the limitations of the traditional voting system, the development of an electronic voting system is an attractive solution. Research on secure electronic voting systems has been conducted for at least the past two decades. We propose to develop an electronic voting system, called the Rochester Institute of Technology Student Government Election System (SGEES) based on Damgard et al. This voting scheme will use efficient honest-verifier zero-knowledge, which, unlike previous election schemes, are both easy to compute and to verify for both voters and authorities. Our proposed electronic voting system will allow convenient and confident voting while maintaining the accuracy of election results. This project will address the security requirements for electronic voting over the Internet, including privacy, completeness, soundness, receipt-freeness, and universal verifiability. In particular, we will research the feasibility of the voting scheme and protocols by studying three related cryptographical theories: homomorphic encryption, efficient honest-verifier zero-knowledge proofs, and threshold decryption cryptosystem.
Theoretical computer science has found fertile ground in many areas of mathematics. The approach has been to consider classical problems through the prism of computational complexity, where the number of basic computational steps taken to solve a problem is the crucial qualitative parameter. This new approach has led to a sequence of advances, in setting and solving new mathematical challenges as well as in harnessing discrete mathematics to the task of solving real-world problems. In this talk, I will survey the development of modern cryptography -- the mathematics behind secret communications and protocols -- in this light. I will describe the complexity theoretic foundations underlying the cryptographic tasks of encryption, pseudo-randomness number generators and functions, zero knowledge interactive proofs, and multi-party secure protocols. I will attempt to highlight the paradigms and proof techniques which unify these foundations, and which have made their way into the mainstream of complexity theory.
In this tutorial, selected topics of cryptology and of computational complexity theory are presented. We give a brief overview of the history and the foundations of classical cryptography, and then move on to modern public-key cryptography. Particular attention is paid to cryptographic protocols and the problem of constructing the key components of such protocols such as one-way functions. A function is one-way if it is easy to compute, but hard to invert. We discuss the notion of one-way functions both in a cryptographic and in a complexity-theoretic setting. We also consider interactive proof systems and present some interesting zero-knowledge protocols. In a zero-knowledge protocol one party can convince the other party of knowing some secret information without disclosing any bit of this information. Motivated by these protocols, we survey some complexity-theoretic results on interactive proof systems and related complexity classes.
Let n be a large composite number. Without factoring n, the computation of a 2 t (mod n)given a, t with gcd(a# n) = 1 and t!n can be done in t squarings modulo n.For t n (e.g., n?2 1024 and t!2 100 ), no lower complexity than t squarings is known to fulfill this task. Rivest et al suggested to use such constructions as good candidates for realising timed-release crypto problems. We argue the necessity for a zero-knowledge proof of the correctness of such constructions and propose the first practically efficient protocol for a realisation. Our protocol proves, in log 2 t standard crypto operations, the correctness of (a e ) 2 t (mod n) with respect to a e where e is an RSA encryption exponent. With such a proof, a Timed-release Encryption of a message M can be given as a 2 t M (mod n) with the assertion that the correct decryption of the RSA ciphertext M e (mod n) can be obtained by performing t squarings modulo n starting from a. Timed-release RSA signatures can be constructed analogously. Keywords Timed-release cryptography, Time-lock puzzles, Non-parallelisability, Efficient zero-knowledge protocols. 1