Blockchain Papers

Yashvanth Kondi, Abhi Shelat

No abstract is available for this record.

Zvika Brakerski, Sanjam Garg, Rotem Tsabary

We present a novel tree-based technique that can convert any designated-prover NIZK proof system (DP-NIZK) which maintains zero-knowledge only for single statement, into one that allows to prove an unlimited number of statements in ZK, while maintaining all parameters succinct. Our transformation requires leveled fully-homomorphic encryption. We note that single-statement DP-NIZK can be constructed from any one-way function. We also observe a two-way derivation between DP-NIZK and attribute-based signatures (ABS), and as a result derive now constructions of ABS and homomorphic signatures (HS).

Shuichi Katsumata, Ryo Nishimaki, Shota Yamada, Takashi Yamakawa

No abstract is available for this record.

Jun Zhou, Kim‐Kwang Raymond Choo, Zhenfu Cao, Xiaolei Dong

Outsourced pattern matching delegates the task of finding all positions pattern$P$appears in text$T$to the cloud from resource-constrained devices. Unfortunately, it has brought a series of security and privacy issues. Most of the state-of-the-art either disclosed text/pattern privacy or exploited the computationally-intensive techniques of public key fully homomorphic encryption (FHE), commitment schemes and zero knowledge proof to achieve both text/pattern privacy and verifiability. To address these issues, as a building block, an efficient privacy preserving verifiable outsourced discrete fourier transform protocol OVFT is first devised based on any one-way trapdoor permutation (OWTP). Based on OVFT, we propose an efficient secure verifiable outsourced polynomial multiplication protocol OPVML which is further exploited in designing our final protocol PVOPM for verifiable privacy-preserving outsourced pattern matching. Without exploiting public key FHE, the proposed PVOPM achieves both verifiability and text/pattern privacy against the collusion between the cloud and malicious receiver/sender, by generating authentication proofs of constant size and executing constant times of any one-way trapdoor permutation, independent to both the text size$n$and the pattern size$m$. Finally, formal security proof under universal composable (UC) model and extensive evaluations demonstrate the efficiency and practicability of our proposed PVOPM.

Masayuki Abe, Charanjit S. Jutla, Miyako Ohkubo, Arnab Roy

We construct the first (almost) tightly-secure unbounded-simulation-sound quasi-adaptive non-interactive zero-knowledge arguments (USS-QA-NIZK) for linear-subspace languages with compact (number of group elements independent of the security parameter) common reference string (CRS) and compact proofs under standard assumptions in bilinear-pairings groups. In particular, under the SXDH assumption, the USS-QA-NIZK proof size is only seventeen group elements with a factor \(O(\log {Q})\) loss in security reduction to SXDH. The USS-QA-NIZK primitive has many applications, including structure-preserving signatures (SPS), CCA2-secure publicly-verifiable public-key encryption (PKE), which in turn have applications to CCA-anonymous group signatures, blind signatures and unbounded simulation-sound Groth-Sahai NIZK proofs. We show that the almost tight security of our USS-QA-NIZK translates into constructions of all of the above applications with (almost) tight-security to standard assumptions such as SXDH and, more generally, \(\mathcal{D}_k\)-MDDH. Thus, we get the first publicly-verifiable (almost) tightly-secure multi-user/multi-challenge CCA2-secure PKE with practical efficiency under standard bilinear assumptions. Our (almost) tight SPS construction is also improved in the signature size over previously known constructions.

Seongseop Kim, David J. Wu

Non-interactive zero-knowledge (NIZK) proofs are fundamental to modern cryptography. Numerous NIZK constructions are known in both the random oracle and the common reference string (CRS) models. In the CRS model, there exist constructions from several classes of cryptographic assumptions such as trapdoor permutations, pairings, and indistinguishability obfuscation. However, at the time of the initial publication of this work, we did not have constructions of NIZKs from standard lattice assumptions. In this work, we take an initial step toward constructing multi-theorem NIZKs for general $$\mathsf {NP}$$ languages from standard lattice assumptions by considering a relaxation to the preprocessing model and a new model we call the designated-prover model. In the preprocessing model, a setup algorithm generates secret proving and verification keys for the prover and the verifier, respectively. In the designated-prover model, the proving key is secret, but the verification key is public. In both settings, the proving key is used to construct proofs and the verification key is used to check proofs. Finally, in the multi-theorem setting, both the proving and verification keys should be reusable for an unbounded number of theorems without compromising soundness or zero-knowledge. Previous constructions of NIZKs in the preprocessing model that rely on weaker assumptions like one-way functions or oblivious transfer are only secure in a single-theorem setting. Thus, constructing multi-theorem NIZKs in these relaxed models does not seem to be inherently easier than constructing them in the CRS model. In this work, we first construct a multi-theorem preprocessing NIZK argument from context-hiding homomorphic signatures. In fact, the construction is a designated-prover NIZK. We also show that using homomorphic commitments, we can get statistically sound proofs in the preprocessing and designated-prover models. Together with lattice-based instantiations of homomorphic signatures and commitments, we obtain the first multi-theorem NIZKs in the preprocessing and designated-prover models from standard lattice assumptions. Finally, we show how to generalize our construction to obtain a universally composable NIZK (UC-NIZK) in the preprocessing model from standard lattice assumptions. Our UC-NIZK relies on a simple preprocessing protocol based on a new primitive we call blind homomorphic signatures.

Michele Ciampi, Giuseppe Persiano, Luisa Siniscalchi, Ivan Visconti

The Fiat-Shamir (FS) transform is a popular technique for obtaining practical zero-knowledge argument systems. The FS transform uses a hash function to generate, without any further over-head, non-interactive zero-knowledge (NIZK) argument systems from public-coin honest-verifier zero-knowledge (public-coin HVZK) proof systems. In the proof of zero knowledge, the hash function is modeled as a programmable random oracle (PRO). In TCC 2015, Lindell embarked on the challenging task of obtaining a similar transform with improved heuristic security. Lindell showed that, for several interesting and practical languages, there exists an efficient transform in the non-programmable random oracle (NPRO) model that also uses a common reference string (CRS). A major contribution of Lindell’s transform is that zero knowledge is proved without random oracles and this is an important step towards achieving efficient NIZK arguments in the CRS model without random oracles. In this work, we analyze the efficiency and generality of Lindell’s transform and notice a significant gap when compared with the FS transform. We then propose a new transform that aims at filling this gap. Indeed our transform is almost as efficient as the FS transform and can be applied to a broad class of public-coin HVZK proof systems. Our transform requires a CRS and an NPRO in the proof of soundness, similarly to Lindell’s transform. 1

Markus Rückert, Michael Schneider, Dominique Schröder

Verifiably encrypted signature schemes (VES) allow a signer to encrypt his or her signature under the public key of a trusted third party, while maintaining public signature verifiability. With our work, we propose two generic constructions based on Merkle authentication trees that do not require non-interactive zero-knowledge proofs (NIZKs) for maintaining verifiability. Both are stateful and secure in the standard model. Furthermore, we extend the specification for VES, bringing it closer to real-world needs. We also argue that statefulness can be a feature in common business scenarios. Our constructions rely on the assumption that CPA (even slightly weaker) secure encryption, maskable CMA secure signatures, and collision resistant hash functions exist. Maskable means that a signature can be hidden in a verifiable way using a secret masking value. Unmasking the signature is hard without knowing the secret masking value. We show that our constructions can be instantiated with a broad range of efficient signature and encryption schemes, including two lattice-based primitives. Thus, VES schemes can be based on the hardness of worstcase lattice problems, making them secure against subexponential and quantum-computer attacks. Among others, we provide the first efficient pairing-free instantiation in the standard model.

Markus Rückert

No abstract is available for this record.

Chunming Tang, Dingyi Pei, Xiao Feng Wang, Zhuojun Liu

A delegateable signature scheme(DSS)which was first introduced by Barak is mainly based on the non-interactive zero-knowledge proof(NIZK)for preventing the signing verifier from telling which witness(i.e.,restricted subset)is being used. However,the scheme is not significantly efficient due to the difficulty of constructing NIZK.We first show that a non-interactive witness indistinguishable(NIWI)proof sys- tem and a non-interactive witness hiding(NIWH)proof system are easier and more efficient proof models than NIZK in some cases.Furthermore,the witnesses em- ployed in these two protocols(NIWI and NIWT)cannot also be distinguished by the verifiers.Combined with theΣ-protocol,we then construct NIWI and NIWH proofs for any NP statement under the existence of one-way functions and show that each proof is different from those under the existence of trapdoor permutations.Finally,based on our NIWI and NIWH proofs,we construct delegateable signature schemes under the existence of one-way functions,which are more efficient than Barak's scheme under the existence of trapdoor permutations.

Craig Gentry, Dávid Molnár, Zulfikar Ramzan

Abstract. Most prior designated confirmer signature schemes either prove security in the random oracle model (ROM) or use general zeroknowledge proofs for NP statements (making them impractical). By slightly modifying the definition of designated confirmer signatures, Goldwasser and Waisbard presented an approach in which the Confirm and ConfirmedSign protocols could be implemented without appealing to general zero-knowledge proofs for NP statements (their Disavow protocol still requires them). The Goldwasser-Waisbard approach could be instantiated using Cramer-Shoup, GMR, or Gennaro-Halevi-Rabin signatures. In this paper, we provide an alternate generic transformation to convert any signature scheme into a designated confirmer signature scheme, without adding random oracles. Our key technique involves the use of a signature on a commitment and a separate encryption of the random string used for commitment. By adding this “layer of indirection, ” the underlying protocols in our schemes admit efficient instantiations (i.e., we can avoid appealing to general zero-knowledge proofs for NP statements) and furthermore the performance of these protocols is not tied to the choice of underlying signature scheme. We illustrate this using the Camenisch-Shoup variation on Paillier’s cryptosystem and Pedersen commitments. The confirm protocol in our resulting scheme requires 10 modular exponentiations (compared to 320 for Goldwasser-Waisbard) and our disavow protocol requires 41 modular exponentiations (compared to using a general zero-knowledge proof for Goldwasser-Waisbard). Previous schemes use the encryption of a signature paradigm, and thus run into problems when trying to implement the confirm and disavow protocols efficiently. 1