Blockchain Papers

Marcos Villagra, Tomoyuki Yamakaki

No abstract is available for this record.

Kai-Min Chung, Huijia Lin, Rafael Pass

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.

Sung-Wook Park, Im-Yeong Lee

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.

Guomin Yang, Chik How Tan, Yi Mu, Willy Susilo · 5 authors

No abstract is available for this record.

M Snyder, Jason Dunn, Eddie Gonzalez

Made In Space, Inc. participated in four weeks of microgravity testing with NASA’s Flight Opportunities Program during the Fall of 2011 and Summer of 2013. The company tested the effects of microgravity on custom built and commercially available extrusion additive manufacturing machines, more commonly known as 3D printers. The testing took place on board a modified Boeing 727 aircraft flown by the Zero-G corporation, in conjunction with NASA’s Reduced Gravity Office and Flight Opportunities Program. The company has utilized the knowledge gained through this campaign on the project that will deliver the first 3D printer to the International Space Station (ISS). 3D printing in space is an enabling technology that is crucial to the exploration of space beyond the low Earth orbit environment. In order for 3D printing to finally be realized as a permanent fixture in space exploration, the behavior must be fully understood in microgravity. Various 3D printers were flown and tested, as well as multiple individual sub-components. With some modification to the key systems, Made In Space was able to demonstrate that additive manufacturing with extrusion-based machines functions similarly in microgravity as it does on the ground, allowing for a full proof of concept. The microgravity flights enabled the Technology Readiness Level (TRL) of the technology to be elevated to a TRL-6.

Zongyang Zhang, Zhenfu Cao, Haojin Zhu

No abstract is available for this record.

Huixin Wu, Feng Wang, Mo Duo

No abstract is available for this record.

Xiyu Pang, Cheng Wang, Yuhong Zhang

On the basis of analyzing the shortcomings of traditional authentication mechanism synthetically, the paper presents a new kind of P2P identity authentication model. In the new P2P Identity authentication model, it authenticates the identity of nodes by using a new Zero-Knowledge proof identification scheme which combines the advantage of RSA. Besides, during the process of validating nodes ’ identity, CA (Center Authentication) doesn’t need to participate in. At last, Simulation results show that the new P2P identity authentication method can improve the safety of network effectively.

Hui Cui, Yi Mu, Man Ho Au

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.

Rong Hu, Kirill Morozov, Tsuyoshi Takagi

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.

Hubert Lacoin, François Simenhaus, Fabio Lucio Toninelli

Let be a bounded, smooth enough domain of ℝ 2 . For L > 0 consider the continuous‐time, zero‐temperature heat bath stochastic dynamics for the nearest‐neighbor Ising model on (ℤ/ L ) 2 (the square lattice with lattice spacing 1/ L ) with initial condition such that σ x =−1 if x ∊ and σ x = + 1 otherwise. We prove the following classical conjecture due to H. Spohn: In the diffusive limit where time is rescaled by L 2 and L → ∞, the boundary of the droplet of “‐” spins follows a deterministic anisotropic curve‐shortening flow such that the normal velocity is given by the local curvature times an explicit function of the local slope. Locally, in a suitable reference frame, the evolution of the droplet boundary follows the one‐dimensional heat equation. To our knowledge, this is the first proof of mean‐curvature‐type droplet shrinking for a lattice model with genuine microscopic dynamics. An important ingredient is in our forthcoming work, where the case of convex was solved. The other crucial point in the proof is obtaining precise regularity estimates on the deterministic curve‐shortening flow. This builds on geometric and analytic ideas of Grayson, Gage and Hamilton, Gage and Li, Chou and Zhu, and others.© 2015 Wiley Periodicals, Inc.

Yang Liu, Yuan Cao, Marcos Curty, Sheng‐Kai Liao · 16 authors

Bit commitment is a fundamental cryptographic task that guarantees a secure commitment between two mutually mistrustful parties and is a building block for many cryptographic primitives, including coin tossing, zero-knowledge proofs, oblivious transfer and secure two-party computation. Unconditionally secure bit commitment was thought to be impossible until recent theoretical protocols that combine quantum mechanics and relativity were shown to elude previous impossibility proofs. Here we implement such a bit commitment protocol. In the experiment, the committer performs quantum measurements using two quantum key distribution systems and the results are transmitted via free-space optical communication to two agents separated with more than 20 km. The security of the protocol relies on the properties of quantum information and relativity theory. We show that, in each run of the experiment, a bit is successfully committed with less than 5.68*10^-2 cheating probability. Our result demonstrates unconditionally secure bit commitment and the experimental feasibility of relativistic quantum communication.

Matteo Maffei, Kim Pecina, Manuel Reinert

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.

Patrick Hayden, Kevin R. Milner, Mark M. Wilde

Suppose that a polynomial-time mixed-state quantum circuit, described as a sequence of local unitary interactions followed by a partial trace, generates a quantum state shared between two parties. One might then wonder, does this quantum circuit produce a state that is separable or entangled? Here, we give evidence that it is computationally hard to decide the answer to this question, even if one has access to the power of quantum computation. We begin by exhibiting a two-message quantum interactive proof system that can decide the answer to a promise version of the question. We then prove that the promise problem is hard for the class of promise problems with 'quantum statistical zero knowledge' (QSZK) proof systems by demonstrating a polynomial-time Karp reduction from the QSZK-complete promise problem 'quantum state distinguish ability' to our quantum separability problem. By exploiting Knill's efficient encoding of a matrix description of a state into a description of a circuit to generate the state, we can show that our promise problem is NP-hard with respect to Cook reductions. Thus, the quantum separability problem (as phrased above) constitutes the first nontrivial promise problem decidable by a two-message quantum interactive proof system while being hard for both NP and QSZK. We also consider a variant of the problem, in which a given polynomial-time mixed-state quantum circuit accepts a quantum state as input, and the question is to decide if there is an input to this circuit which makes its output separable across some bipartite cut. We prove that this problem is a complete promise problem for the class QIP of problems decidable by quantum interactive proof systems. Finally, we show that a two-message quantum interactive proof system can also decide a multipartite generalization of the quantum separability problem. © 2013 IEEE.

Neil Savage

Shafi Goldwasser and Silvio Micali laid the foundations for modern cryptography, with contributions including interactive and zero-knowledge proofs.

Xiaoqiang Guo, Shuai Zhang, Ying Li

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.

Lee Klingler, Rainer Steinwandt, Dominique Unruh

No abstract is available for this record.

Takashi Yamakawa, Shota Yamada, Takahiro Matsuda, Goichiro Hanaoka · 5 authors

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.

Rong Hu, Kirill Morozov, Tsuyoshi Takagi

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.

Alessandra Scafuro

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]

Víctor Mateu, Francesc Sebé, Magda Valls

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.

Nan Yang

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.

Sung Wook Park, Im Yeong Lee

최근 스마트 기기는 결제, 할인쿠폰 등 각종 기능을 제공하는 수단으로 진화되면서 통신과 금융이 융합된 모바일 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.