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.
Feroz Ahmad Ahmad, Prashant Kumar, Gulshan Shrivastava, Med Salim Bouhlel
ON 12 JANUARY 2009 a pseudonymous entity signed a transaction that instructed a distributed network to transfer a small amount of digital currency to Hal Finney, one ofthe key figures of the cypherpunk movement. After a few minutes, the transaction was recorded on a distributed public ledger, permanently updating the balance ofbothparties. This transactionâ the first Bitcoin transactionâmarked the beginning of a new era of decentralized payment systems, ushering in a variety of financial Services that do not depend on any centralized clearinghouse or other financial middleman. Bitcoin is regarded by many as a powerful technological innovation that could disrupt many sectors, in the realm of finance and beyond. But the underlying technology on which the network operates, the Bitcoin blockchain can do much more than that. Just as the internet did in the early-1990s, blockchain technology carries with it a whole new range of promises concerning how decentralization can support and promote individual freedoms and autonomy. Blockchain proponents believe that Bitcoin and other cryptocurrency platforms will revolutionize mechanisms of value exchange in the same way that the internet transformed information sharing, by providing a platform for people to exchange digital resources, in a secure and decentralized manner without the need to rely on any intermediary or trusted authority. But this revolutionary potential also carries with it serious implications for censorship, intellectual property, and the regulated flow of information. A blockchain is a decentralized database of transactions maintained by a distributed network of computers, which all contribute to the verification and the validation of transactions. Once accepted, these transactions are recorded inside a âblockâ of transactions, which incorporates a reference to previous blocks. This creates a long chain of blocksâa âblockchainââthat stores the history of all transactions in a chronological order. Every block contains information about a particular set of transactions, a reference to the preceding block in the blockchain, and the answer to a complex mathematical puzzle that is used to validate the data associated with that block. A copy of the blockchain is stored on every computer in the network, making it virtually impossible for anyone unilaterally to modify the data stored on this decentralized database: if anyone tries to modify any transaction the fraud will be immediately detected by all other network participants.
Open access
43 source records
Blockchain Technology Applications and Security
Advanced Steganography and Watermarking Techniques
In this paper, we describe our analysis of a recently proposed electric vehicle charing protocol. The protocol builds on complicated cryptographic primitives such as commitment, zero-knowledge proofs, BBS+ signature and etc. Moreover, interesting properties such as secrecy, authentication, anonymity, and location privacy are claimed on this protocol. It thus presents a challenge for formal verification, as existing tools for security protocol analysis lack support for all the required features. In our analysis, we employ and combine the strength of two state-of-the-art symbolic verifiers, Tamarin and Prove if, to check all important properties of the protocol.
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.
Many algorithms admit very efficient batch versions that compute simultaneously the output of the algorithms on a set of inputs. Batch algorithms are widely used in cryptography, especially in the setting of pairing-based computations, where they deliver significant speed-ups. Auto Batch is an automated tool that computes highly optimized batch verification algorithms for pairing-based signature schemes. Thanks to finely tuned heuristics, Auto Batch is able to rediscover efficient batch verifiers for several signature schemes of interest, and in some cases to output batch verifiers that outperform the best known verifiers from the literature. However, Auto Batch only provides weak guarantees (in the form of a LaTeX proof) of the correctness of the batch algorithms it outputs. In this paper, we verify the correctness and security of these algorithms using the Easy Crypt framework. To achieve this goal, we define a domain-specific language to describe verification algorithms based on pairings and provide an efficient algorithm for checking (approximate) observational equivalence between expressions of this language. By translating the output of Auto Batch to this language and applying our verification procedure, we obtain machine-checked correctness proofs of the batch verifiers. Moreover, we formalize notions of security for batch verifiers and we provide a generic proof in Easy Crypt that batch verifiers satisfy a security property called screening, provided they are correct and the original signature is unforgeable against chosen-message attacks. We apply our techniques to several well-known pairing-based signature schemes from the literature, and to Groth-Sahai zero-knowledge proofs.
Quantum zero-knowledge proofs and quantum proofs of knowledge are inherently\ndifficult to analyze because their security analysis uses rewinding. Certain\ncases of quantum rewinding are handled by the results by Watrous (SIAM J\nComput, 2009) and Unruh (Eurocrypt 2012), yet in general the problem remains\nelusive. We show that this is not only due to a lack of proof techniques:\nrelative to an oracle, we show that classically secure proofs and proofs of\nknowledge are insecure in the quantum setting.\n More specifically, sigma-protocols, the Fiat-Shamir construction, and\nFischlin's proof system are quantum insecure under assumptions that are\nsufficient for classical security. Additionally, we show that for similar\nreasons, computationally binding commitments provide almost no security\nguarantees in a quantum setting.\n To show these results, we develop the "pick-one trick", a general technique\nthat allows an adversary to find one value satisfying a given predicate, but\nnot two.\n
We introduce a novel concept of dual-system simulation-sound non-interactive zero-knowledge (NIZK) proofs. Dual-system NIZK proof system can be seen as a two-tier proof system. As op-posed to the usual notion of zero-knowledge proofs, dual-system defines an intermediate partial-simulation world, where the proof simulator may have access to additional auxiliary information about the potential language member, for example a membership bit, and simulation of proofs is only guaranteed if the membership bit is correct. Further, dual-system NIZK proofs allow a quasi-adaptive setting where the CRS can be generated based on language parameters. This allows for the further possibility that the partial-world CRS simulator may have access to fur-ther trapdoors related to the language parameters. We show that for important hard languages like the Diffie-Hellman language, such dual-system proof systems can be given which allow unbounded partial simulation soundness, and which further allow transition between partial simulation world and single-theorem full simulation world even when proofs are sought on non-members. The construction is surprisingly simple, involving only two additional group elements in asymmetric bilinear pairing groups.
Payman Mohassel, Seyed Saeed Sadeghian, Nigel P. Smart
Abstract. We propose the first general framework for designing actively secure private function eval-uation (PFE), not based on universal circuits. Our framework is naturally divided into pre-processing and online stages and can be instantiated using any generic actively secure multiparty computation (MPC) protocol. Our framework helps address the main open questions about efficiency of actively secure PFE. On the theoretical side, our framework yields the first actively secure PFE with linear complexity in the circuit size. On the practical side, we obtain the first actively secure PFE for arithmetic circuits with O(g · log g) complexity where g is the circuit size. The best previous construction (of practical interest) is based on an arithmetic universal circuit and has complexity O(g5). We also introduce the first linear Zero-Knowledge proof of correctness of âextended permutation â of ciphertexts (a generalization of ZK proof of correct shuffles) which maybe of independent interest.
Kai-Min Chung, Daniel Dadush, Feng-Hao Liu, Chris Peikert
The smoothing parameter $η_Δ(\mathcal{L})$ of a Euclidean lattice $\mathcal{L}$, introduced by Micciancio and Regev (FOCS'04; SICOMP'07), is (informally) the smallest amount of Gaussian noise that "smooths out" the discrete structure of $\mathcal{L}$ (up to error $Δ$). It plays a central role in the best known worst-case/average-case reductions for lattice problems, a wealth of lattice-based cryptographic constructions, and (implicitly) the tightest known transference theorems for fundamental lattice quantities. In this work we initiate a study of the complexity of approximating the smoothing parameter to within a factor $γ$, denoted $γ$-${\rm GapSPP}$. We show that (for $Δ= 1/{\rm poly}(n)$): $(2+o(1))$-${\rm GapSPP} \in {\rm AM}$, via a Gaussian analogue of the classic Goldreich-Goldwasser protocol (STOC'98); $(1+o(1))$-${\rm GapSPP} \in {\rm coAM}$, via a careful application of the Goldwasser-Sipser (STOC'86) set size lower bound protocol to thin spherical shells; $(2+o(1))$-${\rm GapSPP} \in {\rm SZK} \subseteq {\rm AM} \cap {\rm coAM}$ (where ${\rm SZK}$ is the class of problems having statistical zero-knowledge proofs), by constructing a suitable instance-dependent commitment scheme (for a slightly worse $o(1)$-term); $(1+o(1))$-${\rm GapSPP}$ can be solved in deterministic $2^{O(n)} {\rm polylog}(1/Δ)$ time and $2^{O(n)}$ space. As an application, we demonstrate a tighter worst-case to average-case reduction for basing cryptography on the worst-case hardness of the ${\rm GapSPP}$ problem, with $\tilde{O}(\sqrt{n})$ smaller approximation factor than the ${\rm GapSVP}$ problem. Central to our results are two novel, and nearly tight, characterizations of the magnitude of discrete Gaussian sums.
This thesis proposes several protocols for achieving secure com- putation under concurrent and physical attacks. Secure computation allows many parties to compute a joint function of their inputs, while keeping the privacy of their input preserved. It is required that the pri- vacy one party's input is preserved even if other parties participating in the protocol collude or deviate from the protocol. In this thesis we focus on concurrent and physical attacks, where adversarial parties try to break the privacy of honest parties by ex- ploiting the network connection or physical weaknesses of the honest parties' machine. In the rst part of the thesis we discuss how to construct proto- cols that are Universally Composable (UC for short) based on physical setup assumptions. We explore the use of Physically Uncloneable Func- tions (PUFs) as setup assumption for achieving UC-secure computa- tions. PUF are physical noisy source of randomness. The use of PUFs in the UC-framework has been proposed already in [14]. However, this work assumes that all PUFs in the system are trusted. This means that, each party has to trust the PUFs generated by the other parties. In this thesis we focus on reducing the trust involved in the use of such PUFs and we introduce the Malicious PUFs model in which only PUFs generated by honest parties are assumed to be trusted. Thus the secu- rity of each party relies on its own PUF only and holds regardless of the goodness of the PUFs generated/used by the adversary. We are able to show that, under this more realistic assumption, one can achieve UC- secure computation, under computational assumptions. Moreover, we show how to achieve unconditional UC-secure commitments with (ma- licious) PUFs and with stateless tamper-proof hardware tokens. We discuss our contribution on this matter in Part I. These results are contained in papers [80] and [28]. In the second part of the thesis we focus on the concurrent setting, and we investigate on protocols achieving round optimality and black- box access to a cryptographic primitive. We study two fundamental functionalities: commitment scheme and zero knowledge, and we focus on some of the round-optimal constructions and lower bounds con- cerning both functionalities. We nd that such constructions present subtle issues. Hence, we provide new protocols that actually achieve the security guarantee promised by previous results. Concerning physical attacks, we consider adversaries able to re- set the machine of the honest party. In a reset attack a machine is forced to run a protocol several times using the same randomness. In this thesis we provide the rst construction of a witness indistinguish- able argument system that is simultaneous resettable and argument of knowledge. We discuss about this contribution in Part III, which is the content of the paper. [edited by Author]
Open access
Cryptography and Data Security
Physical Unclonable Functions (PUFs) and Hardware Security
The main aim of cryptography is to provide the frameworks and solutions for information security. The fundamental weapons to protect information are interactions and private randomness. Since the breakthrough result, zero-knowledge proof system, by Goldwasser, Micali, and Rackoff in mid 80s, the cryptography community has endeavored to propose the new notions of information security and the relative solutions which more closely reflect the modern computing environment. Concurrent security first introduced by Dwork, Naor, and Sahai was suggested to capture the information security in the modern internet environment. That is, the adversary may interact with a honest parties in many concurrent executions of a protocol where the messages are scheduled in any adversarial way.Resettable security was first introduced by Canetti, Goldreich, Goldwasser, and Micali, which models the security issues in which parties have a limited source of private randomness. In other words, an adversary might interact with honest parties in many executions of a protocol while the honest parties are only allowed to use the polynomially bounded number of (hard-wired) randomness.An important question is: "How much efficient protocol can we construct to achieve the above security in terms of round complexity?" Unfortunately, it has been showed that the best possible round complexity for such protocols is poly-logarithmic in the security parameter based on black-box simulation without help of external set-up assumptions. Thus, the question is now to minimize the round complexity of protocols with a minimal set-up assumption.In this thesis, we positively answer the above question with help of set-up assumptions. Specifically, we consider two set-up assumptions, the Bare Public Key (BPK) model and the Cross-Domain (CD) model. The BPK model was first introduced by Canetti, Goldreich, Goldwasser, and Micali. In the BPK model, each party is required to register their public keys before the start of interacting with each other. The CD model is a newly proposed model in this work. In the CD model, we have domains which models key certification authorities in the real world and each party belongs to one of the domains.In the BPK model, we show a constructions of constant-round simultaneously resettable zero-knowledge argument of knowledge with a standard cryptographic assumptions. As a main building block for this result, we show a construction of constant-round simultaneously resettable witness-indistinguishable argument of knowledge.In the CD model, we show a construction of constant-round concurrently secure multi-party computation protocol with the fixed number of domains. On the other hand, we prove that if the number of domains is not fixed, such a constant-round protocol does not exist.
Abstract. Consider a joint distribution (X,A) on a set X Ă{0, 1}â. We show that for any family F of distinguishers f: X Ă {0, 1}â â {0, 1}, there exists a simulator h: X â {0, 1}â such that 1. no function in F can distinguish (X,A) from (X,h(X)) with advantage Ç«, 2. h is only O(23âÇ«â2) times less efficient than the functions in F. For the most interesting settings of the parameters (in particular, the cryptographic case where X has superlogarithmic min-entropy, Ç«> 0 is negligible and F consists of circuits of polynomial size), we can make the simulator h deterministic. As an illustrative application of this theorem, we give a new security proof for the leakage-resilient stream-cipher from Eurocryptâ09. Our proof is simpler and quantitatively much better than the original proof using the dense model theorem, giving meaningful security guarantees if instantiated with a standard blockcipher like AES. Subsequent to this work, Chung, Lui and Pass gave an interactive variant of our main theorem, and used it to investigate weak notions of Zero-Knowledge. Vadhan and Zheng give a more constructive version of our theorem using their new uniform min-max theorem. 1
We consider a class of two-party function evaluation protocols in which the parties are allowed to<br/>use ideal functionalities as well as a set of powerful primitives, namely commitments, homomorphic<br/>encryption, and certain zero-knowledge proofs. We illustrate that with these it is possible to capture<br/>protocols for oblivious transfer, coin- ipping, and generation of multiplication-triple.<br/>We show how any protocol in our class can be compiled to a symbolic representation expressed<br/>as a process in an abstract process calculus, and prove a general computational soundness theorem<br/>implying that if the protocol realises a given ideal functionality in the symbolic setting, then the<br/>original version also realises the ideal functionality in the standard computational UC setting. In<br/>other words, the theorem allows us to transfer a proof in the abstract symbolic setting to a proof in<br/>the standard UC model.<br/>Finally, we show that the symbolic interpretation is simple enough in a number of cases for the<br/>symbolic proof to be partly automated using ProVerif
Henry Corrigan-Gibbs, Wendy Mu, Dan Boneh, Bryan Ford
The security of any cryptosystem relies on the secrecy of the system's secret keys. Yet, recent experimental work demonstrates that tens of thousands of devices on the Internet use RSA and DSA secrets drawn from a small pool of candidate values. As a result, an adversary can derive the device's secret keys without breaking the underlying cryptosystem. We introduce a new threat model, under which there is a systemic solution to such randomness flaws. In our model, when a device generates a cryptographic key, it incorporates some random values from an "entropy authority" into its cryptographic secrets and then proves to the authority, using zero-knowledge-proof techniques, that it performed this operation correctly. By presenting an entropy-authority-signed public key certificate to a third party (like a certificate authority or SSH client), the device can demonstrate that its public key incorporates randomness from the authority and is therefore drawn from a large pool of candidate values. Where possible, our protocol protects against eavesdroppers, entropy authority misbehavior, and devices attempting to discredit the entropy authority. To demonstrate the practicality of our protocol, we have implemented and evaluated its performance on a commodity wireless home router. When running on a home router, our protocol incurs a $1.7\times$ slowdown over conventional RSA key generation and it incurs a $3.6\times$ slowdown over conventional EC-DSA key generation.
Authentication is a process by which an entity, which could be a person or intended computer, establishes its identity to another entity. In private and public computer networks including the Internet, authentication is commonly done through the use of logon passwords. Knowledge of the password is assumed to guarantee that the user is authentic. Internet business and many other transactions require a more stringent authentication process. The aim of this paper is to propose two authentication schemes based on general non-commutative rings. The key idea of the schemes is that for a given non-commutative ring; one can build polynomials on additive structure and takes them as underlying work structure. By doing so, one can implement authentication schemes, one of them being zero-knowledge interactive proofs of knowledge, on multiplicative structure of the ring. The security of the schemes is based on the intractability of the polynomial symmetrical decomposition problem over the given non-commutative ring.
Developers building cryptography into security-sensitive applications face a daunting task. Not only must they understand the security guarantees delivered by the constructions they choose, they must also implement and combine them correctly and efficiently. Cryptographic compilers free developers from this task by turning high-level specifications of security goals into efficient implementations. Yet, trusting such tools is hard as they rely on complex mathematical machinery and claim security properties that are subtle and difficult to verify. In this paper we present ZKCrypt, an optimizing cryptographic compiler achieving an unprecedented level of assurance without sacrificing practicality for a comprehensive class of cryptographic protocols, known as Zero-Knowledge Proofs of Knowledge. The pipeline of ZKCrypt integrates purpose-built verified compilers and verifying compilers producing formal proofs in the CertiCrypt framework. By combining the guarantees delivered by each stage, ZKCrypt provides assurance that the output implementation securely realizes the abstract proof goal given as input. We report on the main characteristics of ZKCrypt, highlight new definitions and concepts at its foundations, and illustrate its applicability through a representative example of an anonymous credential system
In this paper, through introducing the Williams public-key cryptosystem in detail, the analysis of the characteristics of the system, and the combination with zero knowledge proof, we set up a zero-knowledge proof scheme based on Williams public-key cryptosystem. The scheme will enrich the theory of cryptography, and particularly zero-knowledge proof theory.
CertiCrypt is a framework that enables the machine-checked construction and verification of cryptographic proofs in the Coq proof assistant. CertiCrypt instruments the code-based game-based approach to cryptographic proofs, and builds upon many areas, including probability and complexity theory, algebra, semantics of programming languages, and program optimizations. In this thesis, we illustrate the application of CertiCrypt on two examples: the Hashed ElGamal encryption scheme and zero-knowledge protocols. Like previous case studies in CertiCrypt, these examples demonstrate the feasibility of formalizing complex cryptographic proofs. However, using CertiCrypt requires a high level of expertise in Coq, and is time consuming. In order to ease the adoption of formal proofs by the cryptographic community, we develop a semi-automated tool, called EasyCrypt, for elaborating security proofs of cryptographic systems from proof sketches. Proof sketches are checked automatically using SMT solvers and automated theorem provers, and then compiled into verifiable proofs in the CertiCrypt framework. We illustrate the application of EasyCrypt with two examples: the Hashed ElGamal encryption system, and the Cramer-Shoup encryption system. Finally, we extend the language of CertiCrypt with a formalization of polytime functions.
When initializing cryptographic systems or running cryptographic protocols, the randomness of critical parameters, like keys or key components, is one of the most crucial aspects. But, randomly chosen parameters come with the intrinsic chance of duplicates, which finally may cause cryptographic systems including RSA, ElGamal and Zero-Knowledge proofs to become insecure. When concerning digital identifiers, we need uniqueness in order to correctly identify a specific action or object. Unfortunately we also need randomness here. Without randomness, actions become linkable to each other or to their initiatorâs digital identity. So ideally the employed (cryptographic) parameters should fulfill two potentially conflicting requirements simultaneously: randomness and uniqueness. This article proposes an efficient mechanism to provide both attributes at the same time without highly constraining the first one and never violating the second one. After defining five requirements on random number generators and discussing related work, we will describe the core concept of the generation mechanism. Subsequently we will prove the postulated properties (security, randomness, uniqueness, efficiency and privacy protection) and present some application scenarios including system-wide unique parameters, cryptographic keys and components, identifiers and digital pseudonyms.