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 encryption-decryption 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.
Xavier Bultel, Jannik Dreier, Pascal Lafourcade, Malika More
At the main cryptography conference, CRYPTO, in 1989, Quisquater and colleagues published a paper showing how to explain the complex notion of zero-knowledge proof in a simpler way that children can understand. In the same line of work, this article presents simple and intuitive explanations of various modern security concepts and technologies, including symmetric encryption, public key encryption, homomorphic encryption, intruder models (CPA, CCA1, CCA2), and security properties (OW, IND, NM). The explanations given in this article may also serve in demystifying such complex security notions for non-expert adults.
The class TFNP is the search analog of NP with the additional guarantee that any instance has a solution. TFNP has attracted extensive attention due to its natural syntactic subclasses that capture the computational complexity of important search problems from algorithmic game theory, combinatorial optimization and computational topology. Thus, one of the main research objectives in the context of TFNP is to search for efficient algorithms for its subclasses, and at the same time proving hardness results where efficient algorithms cannot exist. Currently, no problem in TFNP is known to be hard under assumptions such as NP hardness, the existence of one-way functions, or even public-key cryptography. The only known hardness results are based on less general assumptions such as the existence of collision-resistant hash functions, one-way permutations less established cryptographic primitives (e.g. program obfuscation or functional encryption). Several works explained this status by showing various barriers to proving hardness of TFNP. In particular, it has been shown that hardness of TFNP hardness cannot be based on worst-case NP hardness, unless NP=coNP. Therefore, we ask the following question: What is the weakest assumption sufficient for showing hardness in TFNP? In this work, we answer this question and show that hard-on-average TFNP problems can be based on the weak assumption that there exists a hard-on-average language in NP. In particular, this includes the assumption of the existence of one-way functions. In terms of techniques, we show an interesting interplay between problems in TFNP, derandomization techniques, and zero-knowledge proofs.
Blockchain technology has the potential to disrupt how cryptography is done. In this work, we propose to view blockchains as an “enabler”, much like indistinguishability obfuscation [5, 23, 46] or one-way functions, for building a variety of cryptographic systems. Our contributions in this work are as follows:
1.
A Framework for Proof-of-Stake based Blockchains: We provide an abstract framework for formally analyzing and defining useful security properties for Proof-of-Stake (POS) based blockchain protocols. Interestingly, for some of our applications, POS based protocols are more suitable. We believe our framework and assumptions would be useful in building applications on top of POS based blockchain protocols even in the future.
2.
Blockchains as an Alternative to Trusted Setup Assumptions in Cryptography: A trusted setup, such as a common reference string (CRS) has been used to realize numerous systems in cryptography. The paragon example of a primitive requiring trusted setup is a non-interactive zero-knowledge (NIZK) system. We show that already existing blockchains systems including Bitcoin, Ethereum etc. can be used as a foundation (instead of a CRS) to realize NIZK systems. The novel aspect of our work is that it allows for utilizing an already existing (and widely trusted) setup rather than proposing a new one. Our construction does not require any additional functionality from the miners over the already existing ones, nor do we need to modify the underlying blockchain protocol. If an adversary can violate the security of our NIZK, it could potentially also take over billions of dollars worth of coins in the Bitcoin, Ethereum or any such cryptocurrency!
We believe that such a “trusted setup” represents significant progress over using CRS published by a central trusted party. Indeed, NIZKs could further serve as a foundation for a variety of other cryptographic applications such as round efficient secure computation [33, 36].
3.
One-time programs and pay-per use programs: Goldwasser et al. [29] introduced the notion of one time program and presented a construction using tamper-proof hardware. As noted by Goldwasser et al. [29], clearly a one-time program cannot be solely software based, as software can always be copied and run again. While there have been a number of follow up works [4, 6, 30], there are indeed no known constructions of one-time programs which do not rely on self destructing tamper-proof hardware (even if one uses trusted setup or random oracles). Somewhat surprisingly, we show that it is possible to base one-time programs on POS based blockchain systems without relying on trusted hardware. Our ideas do not seem to translate over to Proof-of-Work (POW) based blockchains.
We also introduce the notion of pay-per-use programs which is simply a contract between two parties — service provider and customer. A service provider supplies a program such that if the customer transfers a specific amount of coins to the provider, it can evaluate the program on any input of its choice once, even if the provider is offline. This is naturally useful in a subscription based model where your payment is based on your usage.
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.
Riccardo Longo, Federico Pintore, Giancarlo Rinaldo, Massimiliano Sala
In recent years certification authorities (CAs) have been the target of multiple attacks due to their sensitive role in internet security. In fact, with access to malicious certificates it is possible to mount effective large-scale man-in-the-middle attacks that may become very vicious, especially if the incident is not properly handled. Many attacks, such as the 2011 ones against DigiNotar and Comodo, also show strong hints of state sponsorship; thus, CAs have to be considered primary targets in a scenario of (possibly state-sponsored) large-scale cyber attacks. Therefore, there is a need for a PKI protocol which is more resilient and without single points of failure, such as the CAs. The BIX protocol is a blockchain-based protocol that allows distribution of certificates linking a subject with their public key, hence providing a service similar to that of a PKI but without the need for a CA. In this paper, we analyse the security of the BIX protocol in a formal way. First, we identify formal security assumptions which are well-suited to this protocol. Second, we present some attack scenarios against the BIX protocol. Third, we provide formal security proofs that these attacks are not feasible under our previously established assumptions.
One of today’s main challenge related to cloud storage is to maintain the functionalities and the efficiency of customers’ and service providers’ usual environments while protecting the confidentiality of sensitive data. Deduplication is one of those functionalities: it enables cloud storage providers to save a lot of memory by storing only once a file uploaded several times. However, classical encryption schemes block deduplication. One needs to use a “message-locked encryption” scheme (MLE), which allows the detection of duplicates and the storage of only one encrypted file on the server, which can be decrypted by any owner of the file. However, in most existing scheme, a user can bypass this deduplication protocol. In this article, we provide servers verifiability for MLE schemes: the servers can verify that the ciphertexts are well-formed. This property forces a customer to prove that she complied to the deduplication protocol, thus preventing her to deviate from the prescribed functionality of MLE. Then, we provide an MLE scheme satisfying this new security property. To achieve the deduplication consistency, our construction primarily relies on zero-knowledge proofs. Unlike Abadi et al.’s MLE, we instantiate those proofs, so<br> that we obtain a more efficient scheme, secure in the random oracle model.
Smooth (or universal) projective hash functions were first introduced by Cramer and Shoup, at Eurocrypt'02, as a tool to construct efficient encryption schemes, indistinguishable under chosen-ciphertext attacks. Since then, they have found many other applications, including password-authenticated key exchange, oblivious transfer, blind signatures, and zero-knowledge arguments. They can be seen as implicit proofs of membership for certain languages. An important question is to characterize which languages they can handle.In this thesis, we make a step forward towards this goal, by introducing diverse modules. A diverse module is a representation of a language, as a submodule of a larger module, where a module is essentially a vector space over a ring. Any diverse module directly yields a smooth projective hash function for the corresponding language, and almost all the known smooth projective hash functions are constructed this way.Diverse modules are also valuable in their own right. Thanks to their algebraic structural properties, we show that they can be easily combined to provide new applications related to zero-knowledge notions, such as implicit zero-knowledge arguments (a lightweight alternative to non-interactive zero-knowledge arguments), and very efficient one-time simulation-sound (quasi-adaptive) non-interactive zero-knowledge arguments for linear languages over cyclic groups.
Francisco Martín-Fernández, Pino Caballero‐Gil, Cándido Caballero‐Gil
This paper describes the design and analysis of a new scheme for the authenticated exchange of confidential information in insecure environments within the Internet of Things, which allows a receiver of a message to authenticate the sender and compute a secret key shared with it. The proposal is based on the concept of a non-interactive zero-knowledge proof, so that in a single communication, relevant data may be inferred to verify the legitimacy of the sender. Besides, the new scheme uses the idea under the Diffie-Hellman protocol for the establishment of a shared secret key. The proposal has been fully developed for platforms built on the Android Open Source Project, so it can be used in any device or sensor with this operating system. This work provides a performance study of the implementation and a comparison between its promising results and others obtained with similar schemes.
Proof-of-work is a central concept in modern cryptocurrencies and denial-ofservice protection tools, but the requirement for fast verification so far has made it an easy prey for GPU-, ASIC-, and botnet-equipped users. The attempts to rely on memory-intensive computations in order to remedy the disparity between architectures have resulted in slow or broken schemes. In this paper we solve this open problem and show how to construct an asymmetric proof-of-work (PoW) based on a computationally-hard problem, which requires a great deal of memory to generate a proof (called a ”memory-hardness” feature) but is instant to verify. Our primary proposal, Equihash, is a PoW based on the generalized birthday problem and enhanced Wagner’s algorithm for it. We introduce the new technique of algorithm binding to prevent cost amortization and demonstrate that possible parallel implementations are constrained by memory bandwidth. Our scheme has tunable and steep time-space tradeoffs, which impose large computational penalties if less memory is used. Our solution is practical and ready to deploy: a reference implementation of a proof-of-work requiring 700 MB of RAM runs in 15 seconds on a 2.1 GHz CPU, increases the computations by a factor of 1000 if memory is halved, and presents a proof of just 120 bytes long.
Abstract The Naor–Yung paradigm [63] allows to generically boost security under chosen-plaintext attacks (CPA) to security against chosen-ciphertext attacks (CCA) for public-key encryption (PKE) schemes. The main idea is to encrypt the plaintext twice (under independent public keys), and to append a non-interactive zero-knowledge (NIZK) proof that the two ciphertexts indeed encrypt the same message. Later work by Camenisch, Chandran, and Shoup [32] and Naor and Segev [ 28 , 30 ] established that the very same technique can also be used in the settings of key-dependent message (KDM) and key-leakage attacks (respectively). In this paper we study the conditions under which the two ciphertexts in the Naor–Yung construction can share the same random coins. We find that this is possible, provided that the underlying PKE scheme meets an additional simple property. The motivation for re-using the same random coins is that this allows to design much more efficient NIZK proofs. We showcase such an improvement in the random oracle model, under standard complexity assumptions including Decisional Diffie–Hellman, Quadratic Residuosity, and Subset Sum. The length of the resulting ciphertexts is reduced by 50%, yielding truly efficient PKE schemes achieving CCA security under KDM and key-leakage attacks. As an additional contribution, we design the first PKE scheme whose CPA security under KDM attacks can be directly reduced to (low-density instances of) the Subset Sum assumption. Our PKE scheme supports key-dependent messages computed via any affine function of the secret key.
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.
We revisit the question of constructing public-key encryption and signature schemes with security in the presence of bounded leakage and tampering memory attacks. For signatures we obtain the first construction in the standard model; for public-key encryption we obtain the first construction free of pairing (avoiding non-interactive zero-knowledge proofs). Our constructions are based on generic building blocks, and, as we show, also admit efficient instantiations under fairly standard number-theoretic assumptions.
Tema ovog rada su kriptovalute. Budući da većina ljudi nije pravodobno upoznata s ovom temom, ovaj rad prikazuje i opisuje kriptovalute te način na koji se upotrjebljuju u svakodnevnom životu. Kriptovalute (eng. cryptocurrency) digitalne su valute dizajnirane kao sredstvo razmjene. Poznate su po tome što su državne agencije i banke isključene iz procesa razmjene. Kriptovalute omogućuju jednostavnu, jeftinu i brzu transakciju na području cijeloga svijeta. Trenutno najisplativije kriptovalute su Bitcoin i Ethereum, a u radu je opisana njihova korisnost, prednosti i mane. Budući da se Bitcoinu predviđa uspješna budućnost i sve je prisutniji i prihvatljiviji na tržištu, u radu su navedeni primjeri iz Hrvatske koji to potvrđuju. Sve veći broj poduzetnika odlučuje se za uvođenje kriptovaluta. U primjerima je obuhvaćen širok spektar djelatnosti, od frizerskih usluga, preko raznih tvrtki koji se bave prodajom računalne opreme, ugostiteljskih usluga preko mogućnosti brzog i lakog podizana gotovine na kripto bankomatima pa sve do plaćanja komunalnih usluga, pa čak i humanitarno djelovanje. Mnogi smatraju da su kriptovalute samo sinonim za prijevare i pranje novca, no programeri tvrde da su kriptovalute samo jedna vrsta tehnologije, alat koji sam po sebi ne može biti ni dobar ni loš, ovisno o tome za što se koristi. Autor ovoga rada proveo je istraživanje o tome kako se može besplatno započeti trgovanje kriptovalutama te je anketom ispitao stavove ispitanika o implementaciji kriptovaluta u društvu.
M. Albrecht, Pooya Farshim, Shuai Han, Dennis Hofheinz · 6 authors
Abstract We provide constructions of multilinear groups equipped with natural hard problems from indistinguishability obfuscation, homomorphic encryption, and NIZKs. This complements known results on the constructions of indistinguishability obfuscators from multilinear maps in the reverse direction. We provide two distinct, but closely related constructions and show that multilinear analogues of the $${\text {DDH}} $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mtext>DDH</mml:mtext></mml:math> assumption hold for them. Our first construction is symmetric and comes with a $$\kappa $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>κ</mml:mi></mml:math> -linear map $$\mathbf{e }: {{\mathbb {G}}}^\kappa \longrightarrow {\mathbb {G}}_T$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>e</mml:mi><mml:mo>:</mml:mo><mml:msup><mml:mrow><mml:mi>G</mml:mi></mml:mrow><mml:mi>κ</mml:mi></mml:msup><mml:mo>⟶</mml:mo><mml:msub><mml:mi>G</mml:mi><mml:mi>T</mml:mi></mml:msub></mml:mrow></mml:math> for prime-order groups $${\mathbb {G}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>G</mml:mi></mml:math> and $${\mathbb {G}}_T$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>G</mml:mi><mml:mi>T</mml:mi></mml:msub></mml:math> . To establish the hardness of the $$\kappa $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>κ</mml:mi></mml:math> -linear $${\text {DDH}} $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mtext>DDH</mml:mtext></mml:math> problem, we rely on the existence of a base group for which the $$\kappa $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>κ</mml:mi></mml:math> -strong $${\text {DDH}} $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mtext>DDH</mml:mtext></mml:math> assumption holds. Our second construction is for the asymmetric setting, where $$\mathbf{e }: {\mathbb {G}}_1 \times \cdots \times {\mathbb {G}}_{\kappa } \longrightarrow {\mathbb {G}}_T$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>e</mml:mi><mml:mo>:</mml:mo><mml:msub><mml:mi>G</mml:mi><mml:mn>1</mml:mn></mml:msub><mml:mo>×</mml:mo><mml:mo>⋯</mml:mo><mml:mo>×</mml:mo><mml:msub><mml:mi>G</mml:mi><mml:mi>κ</mml:mi></mml:msub><mml:mo>⟶</mml:mo><mml:msub><mml:mi>G</mml:mi><mml:mi>T</mml:mi></mml:msub></mml:mrow></mml:math> for a collection of $$\kappa +1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>κ</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math> prime-order groups $${\mathbb {G}}_i$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>G</mml:mi><mml:mi>i</mml:mi></mml:msub></mml:math> and $${\mathbb {G}}_T$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>G</mml:mi><mml:mi>T</mml:mi></mml:msub></mml:math> , and relies only on the 1-strong $${\text {DDH}} $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mtext>DDH</mml:mtext></mml:math> assumption in its base group. In both constructions, the linearity $$\kappa $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>κ</mml:mi></mml:math> can be set to any arbitrary but a priori fixed polynomial value in the security parameter. We rely on a number of powerful tools in our constructions: probabilistic indistinguishability obfuscation, dual-mode NIZK proof systems (with perfect soundness, witness-indistinguishability, and zero knowledge), and additively homomorphic encryption for the group $$\mathbb {Z}_N^{+}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msubsup><mml:mi>Z</mml:mi><mml:mi>N</mml:mi><mml:mo>+</mml:mo></mml:msubsup></mml:math> . At a high level, we enable “bootstrapping” multilinear assumptions from their simpler counterparts in standard cryptographic groups and show the equivalence of PIO and multilinear maps under the existence of the aforementioned primitives.
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.