Bitcoin is a "crypto currency", a decentralized electronic payment scheme based on cryptography which has recently gained excessive popularity. Scientific research on bitcoin is less abundant. A paper at Financial Cryptography 2012 conference explains that it is a system which "uses no fancy cryptography", and is "by no means perfect". It depends on a well-known cryptographic standard SHA-256. In this paper we revisit the cryptographic process which allows one to make money by producing bitcoins. We reformulate this problem as a Constrained Input Small Output (CISO) hashing problem and reduce the problem to a pure block cipher problem. We estimate the speed of this process and we show that the cost of this process is less than it seems and it depends on a certain cryptographic constant which we estimated to be at most 1.86. These optimizations enable bitcoin miners to save tens of millions of dollars per year in electricity bills. Miners who set up mining operations face many economic incertitudes such as high volatility. In this paper we point out that there are fundamental incertitudes which depend very strongly on the bitcoin specification. The energy efficiency of bitcoin miners have already been improved by a factor of about 10,000, and we claim that further improvements are inevitable. Better technology is bound to be invented, would it be quantum miners. More importantly, the specification is likely to change. A major change have been proposed in May 2013 at Bitcoin conference in San Diego by Dan Kaminsky. However, any sort of change could be flatly rejected by the community which have heavily invested in mining with the current technology. Another question is the reward halving scheme in bitcoin. The current bitcoin specification mandates a strong 4-year cyclic property. We find this property totally unreasonable and harmful and explain why and how it needs to be changed.
We present a constant-round concurrent zero-knowledge protocol for NP. Our protocol relies on the existence of families of collision-resistant hash functions, and a new, but in our eyes, natural complexity-theoretic assumption: the existence of P-certificates-that is, "succinct" non-interactive proofs/arguments for P. As far as we know, our results yield the first constant-round concurrent zero-knowledge protocol for NP with an explicit zero-knowledge simulator based on any assumption.
Recently, smart devices for various services have been developed using converged telecommunications, and the markets for near field communication mobile services is expected to grow rapidly. In particular, the realization of mobile NFC payment services is expected to go commercial, and it is widely attracting attention both on a domestic and global level. However, this realization would increase privacy infringement, as personal information is extensively used in the NFC technology. One example of such privacy infringement would be the case of the Google wallet service. In this paper, we propose an zero-knowledge proof scheme and ring signature based on NTRU for protecting user information in NFC mobile payment systems without directly using private financial information of the user.
Bitcoin is a digital currency that unlike traditional currencies does not rely on a centralized authority. Instead Bitcoin relies on a network of volunteers that collectively implement a replicated ledger and verify transactions. In this paper we analyze how Bitcoin uses a multi-hop broadcast to propagate transactions and blocks through the network to update the ledger replicas. We then use the gathered information to verify the conjecture that the propagation delay in the network is the primary cause for blockchain forks. Blockchain forks should be avoided as they are symptomatic for inconsistencies among the replicas in the network. We then show what can be achieved by pushing the current protocol to its limit with unilateral changes to the client's behavior.
Consider a practical scenario: an untrusted gate-way is required to verify all the incoming information en-crypted via an encryption scheme, while the sender does not want to reveal any information about the plaintext and the privileged user to the gateway. That is, the gateway distributes the information to a predefined group of users and only the privileged user can open the message. To solve this problem, we need an access control mechanism to allow certain specification of the access control policies while protecting the users' privacy. With this scenario in mind, we propose the notion of verifiable and anonymous encryption where a verification function is added to the ciphertext, which captures the security requirements of the confidentiality of the plaintext and the anonymity of the privileged user. We present two specific constructions of our framework under the setting of asymmetric bilinear pairings in this paper. Our first scheme is proven confidential and anonymous under a weaker security model in the random oracle model, and our second one is built on the basis of a zero knowledge proof of knowledge under a strong security game.
Cayrel.et.al at SAC 2010 proposed a zero-knowledge identification scheme based on syndrome decoding of q-ary codes. It is a 5-pass scheme with soundness error q/2(q-1). We propose an alternative to this scheme by generalizing (binary) Stern zero-knowledge identification from CRYPTO 1993 directly to q-ary setting. Our proposal is a 3-pass scheme with soundness error 2/3. We show that it is superior to Cayrel et al scheme in terms of communication cost for the case q = {3, 4}. A possible application for q-ary code-based identification schemes with small q is a proof of plaintext knowledge for code-based public key encryption.
The privacy of users has rapidly become one of the most pervasive and stringent requirements in distributed computing. Designing and implementing privacy-preserving distributed systems, however, is challenging since these systems also have to fulfill seemingly conflicting security properties and system requirements: e.g., authorization and accountability require some form of user authentication and session management necessarily involves some form of user tracking. In this work, we present a solution based on declarative design. The core component of our framework is a logic-based declarative API for data processing that exports methods to conveniently specify the system architecture and the intended security properties, and conceals the cryptographic realization. Invisible to the programmer, the implementation of this API relies on a powerful combination of digital signatures, non-interactive zero-knowledge proofs of knowledge, pseudonyms, and reputation lists. We formally proved that the cryptographic implementation enforces the security properties expressed in the declarative specification. The systems produced by our framework enjoy interoperability and open-endedness: they can easily be extended to offer new services and cryptographic data can be shared and processed by different services, without requiring any extra bootstrapping phase or interaction among parties. We implemented the API in Java and conducted an experimental evaluation to demonstrate the practicality of our approach.
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.
A collection of questions about Bitcoin and its hypothetical relatives Bitguilder and Bitpenny is formulated. These questions concern technical issues about protocols, security issues, issues about the formalizations of informational monies in various contexts, and issues about forms of use and misuse. Some questions are formulated in the more general setting of informational monies and near-monies. We also formulate questions about legal, psychological, and ethical aspects of informational money. Finally we formulate a number of questions concerning the economical merits of and outlooks for Bitcoin.
With the advent of the information age, the network security is particularly important. The secure multiparty computation is a very important branch of cryptography. It is a hotspot in the field of information security. It expanded the scope of the traditional distributed computing and information security, provided a new computing model for the network collaborative computing. First we introduced several key technologies of secure multiparty computation: secret sharing and verifiable secret sharing, homomorphic public key cryptosystem, mix network, zero knowledge proof, oblivious transfer, millionaire protocol. Second we discussed the applications of secure multiparty computation in electronic voting, electronic auctions, threshold signature, database queries, data mining, mechanical engineering and other fields.
In this paper, we present novel constructions of chosen-ciphertext secure (CCA secure) key encapsulation mechanism (KEM) from chosen-plaintext secure (CPA secure) KEM in the standard model. It is already known that CCA secure public key encryption (PKE) can be generically constructed from CPA secure PKE and ((simulation-sound) non-interactive zero-knowledge proof) via the Naor-Yung or Dolev-Dwork-Naor transforms. Thus, one can also immediately construct CCA secure PKE from CPA secure KEM by converting CPA secure KEM into CPA secure PKE and transforming it to be CCA secure PKE. However, such a construction seems redundant since in general PKE is less efficient than KEM and it would be more efficient if we can directly construct CCA secure KEM from CPA secure KEM without intermediating CPA secure PKE. In this work, we propose new variants of the Naor-Yung and Dolev-Dwork-Naor transforms that directly convert CPA secure KEM into CCA secure KEM, and show that our proposed schemes are more efficient than the above straightforward constructions. For example, when instantiating from the decision linear assumption, ciphertext size of our Naor-Yung variant consists of 34 group elements while that of the straightforward construction consists of 47 group elements. Furthermore, we also propose another variant of the Dolev-Dwork-Naor transform from multiple KEM and show that a KEM which is obtained from Wee's extractable hash proof system can also be considered as an efficient construction of multiple KEM.
In a recent paper at Asiacrypt'2012, Jain et al point out that Veron code-based identification scheme is not perfect zero-knowledge. In particular, this creates a gap in security arguments of proof of plaintext knowledge (PPK) and verifiable encryption for the McEliece public key encryption (PKE) proposed by Morozov and Takagi at ACISP'2012. We fix the latter result by showing that PPK for the code-based Niederreiter and McEliece PKE's can be constructed using Stern zero-knowledge identification scheme, which is unaffected by the above mentioned problem. Since code-based verifiable encryption uses PPK as a main ingredient, our proposal presents a fix for the McEliece verifiable encryption as well. In addition, we present the Niederreiter verifiable encryption.
Ian Miers, Christina Garman, Matthew Green, Aviel D. Rubin
Bitcoin is the first e-cash system to see widespread adoption. While Bitcoin offers the potential for new types of financial interaction, it has significant limitations regarding privacy. Specifically, because the Bitcoin transaction log is completely public, users' privacy is protected only through the use of pseudonyms. In this paper we propose Zerocoin, a cryptographic extension to Bitcoin that augments the protocol to allow for fully anonymous currency transactions. Our system uses standard cryptographic assumptions and does not introduce new trusted parties or otherwise change the security model of Bitcoin. We detail Zerocoin's cryptographic construction, its integration into Bitcoin, and examine its performance both in terms of computation and impact on the Bitcoin protocol.
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
Blind signature-based electronic voting is the simplest paradigm for implementing remote voting platforms due to the fact that it does not employ complicated zero-knowledge proofs. Unfortunately, the existence of a trusted entity (the "Authentication Server") that, in case of corruption, would be able to cast indistinguishable fake votes reduces the acceptance of the paradigm in non fully trusted environments. Trust on the system can be increased by splitting this entity into of a set of parties that are unlikely to collaborate in a dishonest manner. Nevertheless, this technique increases the risk of failure of some of them causing a service interruption during the voting period. Better fault tolerance is provided by proposals which permit to anticipate the interaction with the distributed authentication server before the voting period begins, so that, in case of failure, there is a broad time margin for system restoration. Previous proposals following this approach have been proven to be cryptographically weak or just provide individual verifiability. In this paper, a system that employs blind certificates is presented. Unlike previous proposals, it provides universal verifiability and permits to detect double voting without putting voters' privacy at risk.
Single-prover interactive proofs can recognize PSPACE; if certain complexity assumptions are made, they can do so in zero-knowledge. Generalizing to multiple non-communicating provers extends this class to NEXP, and at the same time removes the complexity assumption needed for zero-knowledge. \n \nHowever, it was recently discovered that the non-communication condition might be insufficient to guarantee soundness. The provers can form joint randomness through non-local computation without communicating. This could break protocols that rely on the statistical independence of the provers. \n \nIn this work, we analyze multi-prover interactive proofs under the constraint of statistical isolation which prohibits non-local computation. We show that there exists perfect zero-knowledge proofs for NEXP under statistical isolation.
์ต๊ทผ ์ค๋งํธ ๊ธฐ๊ธฐ๋ ๊ฒฐ์ , ํ ์ธ์ฟ ํฐ ๋ฑ ๊ฐ์ข ๊ธฐ๋ฅ์ ์ ๊ณตํ๋ ์๋จ์ผ๋ก ์งํ๋๋ฉด์ ํต์ ๊ณผ ๊ธ์ต์ด ์ตํฉ๋ ๋ชจ๋ฐ์ผ NFC ์๋น์ค์ ์์ฅ์ด ๊ธ์ฑ์ฅํ ๊ฒ์ผ๋ก ์ ๋ง๋๊ณ ์๋ค. ํนํ ๋ชจ๋ฐ์ผ NFC ๊ฒฐ์ ์๋น์ค ์์ฅ์ ํ์ฑํ๊ฐ ์์๋จ์ ๋ฐ๋ผ ๋ชจ๋ฐ์ผ NFC ๊ฒฐ์ ์๋น์ค๋ ๊ตญ๋ด ์ธ์ ์ผ๋ก ๋๋ฆฌ ์ฃผ๋ชฉ๋ฐ๊ณ ์๋ค. ํ์ง๋ง ์ด์ ๋ฐ๋ฅธ NFC ๊ธฐ์ ํ์ฉ ์ฆ๊ฐ๋ก ๊ฐ์ธ์ ๋ณด ์ด์ฉ์ด ๋๋ฉด์ ์นจํด์์ ๋ํ ์ฆ๊ฐํ๊ณ ์๋ค. ์ต๊ทผ ํ๊ตญ์ธํฐ๋ท์งํฅ์์์ ๋ฐํํ "NFC ๊ฐ์ธ์ ๋ณด๋ณดํธ ๋์ฑ ์ต์ข ๋ณด๊ณ ์"์ ๋ฐ๋ฅด๋ฉด ๊ฐ์ธ์ ๋ณด ์ํธํ๋ฅผ ๋ถ๋ถ์ ์ผ๋ก ๋ฏธ์ง์ํ๊ฑฐ๋ ๋ถํ์ํ ๊ฐ์ธ์ ๋ณด์ ๊ณผ๋ํ ์์ง ๋ฐ ์ ์ฅ ๋ฑ์ด ๋ฌธ์ ์ ์ผ๋ก ์ ๊ธฐ๋์์ผ๋ฉฐ Google์ฌ์ Google Wallet ์๋น์ค์ ๊ฐ์ธ์ ๋ณด ์ ์ถ ์ฌ๊ณ ๋ํ ์ด๋ฌํ ๋ฌธ์ ์ ์ ๋ท๋ฐ์นจํ๋ ๊ทผ๊ฑฐ๊ฐ ๋๊ณ ์๋ค. ๋ณธ ๋ ผ๋ฌธ์์๋ ๊ธฐ์กด์ ์๋น์ค๋๊ณ ์๋ NFC ๋ชจ๋ฐ์ผ ๊ฒฐ์ ์๋น์ค ์์์ ๊ฒฐ์ ์ ๋ณด์ ์ด๋ ๊ฒฝ๋ก ๋ณ ๊ฒฐ์ ๊ธฐ์ ์ ์ํ์ ๋ถ์ํ๊ณ OTA(Over the Air) ์์์ ์์ ํ ์ ๋ณด๊ตํ์ ์ํ NTRU ๊ธฐ๋ฐ ์ํธ์ธ์ฆ ๊ธฐ๋ฒ๊ณผ ์ฌ์ฉ์์ ์ํ ๊ฐ์ ๊ฒฐ์ ๋จ๊ณ์์ ๊ฒฐ์ ์ ๋ณด๋ฅผ ์ง์ ์ ์ผ๋ก ์ฌ์ฉํ์ง ์๊ณ ๊ฒฐ์ ์๋ฅผ ์ฆ๋ช ํ ์ ์๋ NTRU๊ธฐ๋ฐ ์์ง์ ์ฆ๋ช ๊ธฐ๋ฒ์ ๋ํด ์ ์ํ๋ค. Recently, smart devices for various services have been developed using converged telecommunications, and the markets for near field communication (NFC) mobile services is expected to grow rapidly. In particular, the realization of mobile NFC payment services is expected to go commercial, and it is widely attracting attention both on a domestic and global level. However, this realization would increase privacy infringement, as personal information is extensively used in the NFC technology. One example of such privacy infringement would be the case of the Google wallet service. In this paper, we propose an mutual authentication scheme based on NTRU for secure channel in OTA and an zero-knowledge proof scheme NTRU based on for protecting user information in NFC mobile payment systems without directly using private financial information of the user.
Jannik Dreier, Guillaume Dumas, Hugo Jonker, Pascal Lafourcade
An electronic auction protocol will only be used by those who trust that it operates correctly. Therefore, e-auction protocols must be verifiable: seller, buyer and losing bidders must all be able to determine that the result was correct. We pose that the importance of verifiability for e-auctions necessitates a formal analysis. Consequently, in the first part of the talk, we identify notions of verifiability for each stakeholder. We formalize these and then use the developed framework to study the verifiability of several examples. We provide an analysis of the protocol by Sako in the applied pi-calculus with help of ProVerif, finding it to be correct. Additionally we identify issues with the protocols due to Curtis et al. and Brandt. In the second part, we will analyze the protocol by Brandt in more detail. We show first that this protocol โ when using malleable interactive zero-knowledge proofs โ is vulnerable to attacks by dishonest bidders. Such bidders can manipulate the publicly available data in a way that allows the seller to deduce all participantsโ bids. Additionally we discuss attacks on non-repudiation, fairness and the privacy of individual bidders exploiting authentication problems.
Demonstrable data retention (DDR) is a technique which certain the integrity of data in storage outsourcing. In this paper we propose an efficient DDR protocol that prevent attacker in gaining information from multiple cloud storage node. Our technique is for distributed cloud storage and support the scalability of services and data migration. This technique Cooperative store and maintain the clientโs data on multi cloud storage. To insure the security of our technique we use zero-knowledge proof system, which satisfies zero-knowledge properties, knowledge soundness and completeness. We present a Cooperative DDR (CDDR) protocol based on hash index hierarchy and homomorphic verification response. In order to optimize the performance of our technique we use a novel technique for selecting optimal parameter values to reduce the storage overhead and computation costs of client for service providers. Keyword: Demonstrable Data Retention, homomorphic, zero knowledge, storage outsourcing, multiple cloud, Cooperative, data Retention.