Blockchain Papers

Eli Ben‐Sasson, Alessandro Chiesa, Nicholas Spooner

No abstract is available for this record.

Benoît Libert, San Ling, Khoa Nguyen, Huaxiong Wang

Abstract An accumulator is a function that hashes a set of inputs into a short, constant-size string while preserving the ability to efficiently prove the inclusion of a specific input element in the hashed set. It has proved useful in the design of numerous privacy-enhancing protocols, in order to handle revocation or simply prove set membership. In the lattice setting, currently known instantiations of the primitive are based on Merkle trees, which do not interact well with zero-knowledge proofs. In order to efficiently prove the membership of some element in a zero-knowledge manner, the prover has to demonstrate knowledge of a hash chain without revealing it, which is not known to be efficiently possible under well-studied hardness assumptions. In this paper, we provide an efficient method of proving such statements using involved extensions of Stern’s protocol. Under the Small Integer Solution assumption, we provide zero-knowledge arguments showing possession of a hash chain. As an application, we describe new lattice-based group and ring signatures in the random oracle model. In particular, we obtain: (i) the first lattice-based ring signatures with logarithmic size in the cardinality of the ring and (ii) the first lattice-based group signature that does not require any GPV trapdoor and thus allows for a much more efficient choice of parameters.

Samuel Ranellucci, Alain Tapp, Rasmus Winther Zakarias

No abstract is available for this record.

Xavier Bultel, Jannik Dreier, Jean‐Guillaume Dumas, Pascal Lafourcade

Akari, Takuzu, Kakuro and KenKen are logic games similar to Sudoku. In Akari, a labyrinth on a grid has to be lit by placing lanterns, respecting various constraints. In Takuzu a grid has to be filled with 0's and 1's, while respecting certain constraints. In Kakuro a grid has to be filled with numbers such that the sums per row and column match given values; similarly in KenKen a grid has to be filled with numbers such that in given areas the product, sum, difference or quotient equals a given value. We give physical algorithms to realize zero-knowledge proofs for these games which allow a player to show that he knows a solution without revealing it. These interactive proofs can be realized with simple office material as they only rely on cards and envelopes. Moreover, we formalize our algorithms and prove their security.

Jonathan Bootle, Andrea Cerulli, Pyrros Chaidos, Jens Groth

No abstract is available for this record.

Melissa Chase, Chaya Ganesh, Payman Mohassel

Practical anonymous credential systems are generally built around sigma-protocol ZK proofs. This requires that credentials be based on specially formed signatures. Here we ask whether we can instead use a standard say, RSA, or ECDSA signature that includes formatting and hashing messages, as a credential, and still provide privacy. Existing techniques do not provide efficient solutions for proving knowledge of such a signature: On the one hand, ZK proofs based on garbled circuits Jawurek et al. 2013 give efficient proofs for checking formatting of messages and evaluating hash functions. On the other hand they are expensive for checking algebraic relations such as RSA or discrete-log, which can be done efficiently with sigma protocols. We design new constructions obtaining the best of both worlds: combining the efficiency of the garbled circuit approach for non-algebraic statements and that of sigma protocols for algebraic ones. We then discuss how to use these as building-blocks to construct privacy-preserving credential systems based on standard RSA and ECDSA signatures. Other applications of our techniques include anonymous credentials with more complex policies, the ability to efficiently switch between commitments and signatures in different groups, and secure two-party computation on committed/signed inputs.

Broadbent Anne, Zhengfeng Ji, Song Fang, Watrous John

Prior work has established that all problems in NP admit classical zero-knowledge proof systems, and under reasonable hardness assumptions for quantum computations, these proof systems can be made secure against quantum attacks. We prove a result representing a further quantum generalization of this fact, which is that every problem in the complexity class QMA has a quantum zero-knowledge proof system. More specifically, assuming the existence of an unconditionally binding and quantum computationally concealing commitment scheme, we prove that every problem in the complexity class QMA has a quantum interactive proof system that is zero-knowledge with respect to efficient quantum computations. Our QMA proof system is sound against arbitrary quantum provers, but only requires an honest prover to perform polynomial-time quantum computations, provided that it holds a quantum witness for a given instance of the QMA problem under consideration. The proof system relies on a new variant of the QMA-complete local Hamiltonian problem in which the local terms are described by Clifford operations and standard basis measurements. We believe that the QMA-completeness of this problem may have other uses in quantum complexity.

Benny Applebaum, Pavel Raykov

No abstract is available for this record.

Eli Ben‐Sasson, Alessandro Chiesa, Ariel Gabizon, Madars Virza

The seminal result that every language having an interactive proof also has a zero-knowledge interactive proof assumes the existence of one-way functions. Ostrovsky and Wigderson (ISTCS 1993) proved that this assumption is necessary: if one-way functions do not exist, then only languages in BPP have zero-knowledge interactive proofs. Ben-Or et al. (STOC 1988) proved that, nevertheless, every language having a multi-prover interactive proof also has a zero-knowledge multi-prover interactive proof, unconditionally. Their work led to, among many other things, a line of work studying zero knowledge without intractability assumptions. In this line of work, Kilian, Petrank, and Tardos (STOC 1997) defined and constructed zero-knowledge probabilistically checkable proofs (PCPs). While PCPs with quasilinear-size proof length, but without zero knowledge, are known, no such result is known for zero knowledge PCPs. In this work, we show how to construct “2-round” PCPs that are zero knowledge and of length ~ O(K) where K is the number of queries made by a malicious polynomial time verifier. Previous solutions required PCPs of length at leastK 6 to maintain zero knowledge. In this model, which we call duplex PCP (DPCP), the verifier first receives an oracle string from the prover, then replies with a message, and then receives another oracle string from the prover; a malicious verifier can make up toK queries in total to both oracles. Deviating from previous works, our constructions do not invoke the PCP Theorem as a blackbox but instead rely on certain algebraic properties of a specific family of PCPs. We show that if the PCP has a certain linear algebraic structure — which many central constructions can be shown to possess, including [BFLS91,ALMSS98,BS08] — we can add the zero knowledge property at virtually no cost (up to additive lower order terms) while introducing only minor modifications in the algorithms of the prover and verifier. We believe that our linear-algebraic characterization of PCPs may be of independent interest, as it gives a simplified way to view previous well-studied PCP constructions.

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.

Alexandre Marques Albano da Silveira

SILVEIRA, Alexandre Marques Albano da. Prova de conhecimento nulo baseada em isomorfismo de subgrafos. 2016. 71 f. - Dissertação - Universidade Federal do Ceará, Programa de Pós-Graduação em Engenharia Elétrica e da Computação, Sobral, 2016.

Aaron Louis Rosenberg

This anthology represents a valuable contribution to scholarly explorations of stylistics and its viability as a tool to be used in the elucidation of the literary and socio-cultural aspects inherent in African literatures and oral forms of expression. As is made clear in the introduction by Russell West-Pavlov and J. K. S. Makokha, the collection attempts to cover as much of the topic in geographic, generic, and theoretical terms as possible, limited only by the responses received to their call for papers. Unfortunately, there were no scholars working on literature from the Maghreb or Egypt who responded to this summons and thus the volume is concerned only with Sub-Saharan Africa. Certainly, given the transformations going on in this part of the world over the past few years, it would have been valuable for those of us studying African literatures to have the opportunity to study the literature emerging from here.This blind spot notwithstanding, the book and its contributors strive to provide a broad range of case studies, which can give the reader both a broad understanding of the field of literary stylistics at the same time as they may focus in on those specific works and theoretical perspectives that may be of interest to them. Thus we have studies of a conventional if not canonical nature such as the analysis of metaphor in Chinua Achebe's Things Fall Apart by Adeyemi Daramola which, though covering fairly familiar ground for the majority of literary scholars, manages to position the analysis of metaphor in a more specifically and exacting linguistic trajectory drawing on the work of Lakoff and Johnson, Halliday and Ortony, among others.Speaking from my own personal perspective, what I found to be most valuable in the volume are the ways in which various authors have chosen to approach their subject matter. Firstly, there are various articles which make a concentrated effort to present and profoundly analyze African literary and verbal art in its original language whether that be a Europhone language with its particular authorial inflections such as English, French, or Portuguese, an indigenous African language such as Swahili or Igbo, or a language such as Mauritian Kreol with its combination of French and non-French elements in the same language as is the case in the essay by Shawkat M. Toorawa. Although the sometimes lengthy transcriptions and translations of these passages in the texts might be thought to be a bit tedious to those who do not understand the original language, taking a leaf from the intellectual tree of the great scholar Okot p'Bitek, who stated that “[i]t is important to stress that these are my own translations, and I believe that there can be other versions. It is for this reason that the vernacular had to be included, to give other translators and scholars the opportunity to criticise my translation and also to attempt their own” (Okot p'Bitek Preface. In Horn of My Love. London: Heinemann Educational Books, 1974. x.), I feel that such presentations in the original are important and useful. This is, of course, particularly relevant in a collected work where questions of a linguistic nature are paramount, such as is the case here. Judging from Mikhail Gromov's essay on Modern tenzi and mashairi poetic forms in Kenya and Tanzania, I can safely say that the presence of the original texts for a Swahili speaker such as myself was manifestly enriching to his analysis and clarified various points under discussion. The only text that left me more than a bit disappointed in this respect is Michael Wainaina's intervention dealing with Gikuyu popular music in which he has chosen to render the translations of the song texts in English translation only, without providing the transcription of the works in their original Kikuyu. Given the tonal nature and orthographic complexity of Kikuyu (there have actually over time been various methods of rendering the Gikuyu language in print) I sympathize with the scholar's choice to streamline the excerpts provided but do nonetheless feel that transcriptions in the original would have made it easier to zero in on the various forms of discourse, which he underlines in the opening section of the study. To take a contrasting example as my model, Iwu Ikwubuzo's contribution on Igbo riddles in the volume does take on the added complexity of these riddles in their original and thus makes a profound technical study of the linguistic aspects of these artistic works in miniature possible alongside the more contextual elements brought into play in the analysis. While I still found Wainaina's essay compelling and useful, I suspect that it would be more so if he had been moved to include these songs in their Kikuyu form.Having mentioned Wainaina's work on Gikuyu popular songs, I feel obliged to recognize and give praise where praise is due to the sheer breadth of the collection in terms of its generic scope stretching from novels through poetry, popular song, and on into riddles. As a scholar who has maintained a concerted effort in my work to trace similarities across these generic boundaries, I was heartened to see the successful attempts made here to carry out detailed and meaningful studies of so many distinct yet clearly related forms of expression.The only problem that I encountered reading the text, and this only sporadically, is an apparent lack of attention in some cases to proofreading before the final proofs were submitted. While direct spelling errors were rare (and would in any case most likely been identified by a standard word-processing program) there was a tendency in numerous cases for authors to employ awkward turns of phrase or verbs in tenses that did not apply to the contexts in which they were being deployed. While I understand and am sensitive to the pressures of academic work and the extreme limitations which are often put on our time, I do feel that, given the nature of this volume as in large part a linguistic study of literary stylistics, greater attention should have been applied, both from the authors themselves and the editors in charge in order to ensure that the language used in these articles was more carefully crafted and accessible to its readers.In any case, the volume's positive attributes far outweigh any such difficulties and provide the attentive reader with a broad and profound introduction to the state of the field of African literature studies in terms of literary stylistics. Throughout the essays and taken as a whole the authors do an excellent job of communicating the importance of narrative techniques in building a greater knowledge of various genres and these works’ importance in transmitting cultural knowledge in African communities as well as between such communities and the increasingly globalized contexts through which they move.

Anchal Doegar, M. Sivasankar

In this paper we propose a digital signature scheme using a two-layer multivariate polynomial system. This scheme works like a zero-knowledge proof scheme. The algorithm can be implemented in two modes, parallel mode and series mode. As Multivariate Polynomial Cryptography (MPC) is a viable choice in the post quantum era, various algorithms based on MPC are gaining importance. The proposed scheme points to a potential direction for digital signature schemes in the presence of quantum computers.

Seetha Ranganathan, R. Saravanan

&lt;p&gt;The password which is a more secure and valuable data should be highly protected from eavesdropper. This paper presents how password required for authentication of members of group communication is securely delivered by the source or initiator of the group. The password delivery uses zero knowledge proof and sent to the group member in an encrypted format using cipher block mode encryption. The password delivered is a One Time Password which can be used for certain amount of time in order to ensure a highly secure communication environment among the group.&lt;/p&gt;

Jürgen Angst, Guillaume Poly

We investigate the mean number of real zeros over an interval $[a,b]$ of a random trigonometric polynomial of the form $\sum_{k=1}^n a_k \cos(kt)+b_k \sin(kt)$ where the coefficients are i.i.d. random variables. Under mild assumptions on the law of the entries, we prove that this mean number is asymptotically equivalent to $\frac{n(b-a)}{π\sqrt{3}}$ as $n$ goes to infinity, as in the known case of standard Gaussian coefficients. Our principal requirement is a new Cramer type condition on the characteristic function of the entries which does not only hold for all continuous distributions but also for discrete ones in a generic sense. To our knowledge, this constitutes the first universality result concerning the mean number of zeros of random trigonometric polynomials. Besides, this is also the first time that one makes use of the celebrated Kac-Rice formula not only for continuous random variables as it was the case so far, but also for discrete ones. Beyond the proof of a non asymptotic version of Kac-Rice formula, our strategy consists in using suitable small ball estimates and Edgeworth expansions for the Kolmogorov metric under our new weak Cramer condition, which both constitute important byproducts of our approach.

Juan-Hong Tian, Jian-Zhong Zhang, Yan-Ping Li

No abstract is available for this record.

John A. Replogle

Abstract. Modern flow metering technology frequently emphasizes the exploitation of ultrasonics, communications, and other electronic-based systems. Yet, there are thousands of irrigation measurement locations that are poorly served by existing devices. Even the more sophisticated developments are limited, for indeed, neither one-size nor one-method fits all. Discussed are hydraulic principles and flow measurement methodologies that are economical, convenient, and accurate. Some are common knowledge and some not-so-common, but all contribute to managing our water-resources. Some improvements in older techniques are often supported by improvements in communications and computer software. Improved broader understanding of hydraulics contributes to convenient flume and weir zero registration, stilling well design modifications, and accurate sediment-sampler design methods. The sampler concepts can also be applied to sprinkler-nozzle testing and to rain-gage accuracy. Additionally, weed-proofing of propeller meters and cone meters without weed screening is discussed.

Jesús Ildefonso Díaz Díaz, A. Arjona

In the last 30 years several mathematical studies have been devoted to the viscoelastic-gravitational coupling in stationary and transient regimes either for static case or for hyperbolic case. However, to the best of our knowledge there is a lack of mathematical study of the stabilization as $t$ goes to infinity of a viscoelastic-gravitational models crustal deformations of multilayered Earth. Here we prove that, under some additional conditions on the data, the difference of the viscoelastic and elastic solutions converges to zero, as $t$ goes to infinity, in a suitable functional space. The proof of that uses a reformulation of the hyperbolic/elliptic system in terms of a nonlocal hyperbolic system.

Huafei Zhu, Shuoping Wang, Peipei Tang

In this paper, a new notion which we call verifiably anonymous data collection protocol is introduced and formalized in the client-server model where each respondent uses a web interface to communicate with a server operated by the data miner. A construction leveraging a combination of semantically secure double trap-door encryption and OR zero-knowledge proof system is proposed and analyzed, where data sent from a respondent Alice is first encrypted using her personal partial key; Alice then proves to the data miner that the resulted ciphertext is valid and is sent by one of respondents dynamically formed by the respondent without getting the consent or assistance of the other respondents. A rigorous proof of the soundness and the zero-knowledge property of our data collection protocol in the presence of malicious adversary is presented.

Irwan Irwan, Armein Z. R. Langi, Emir Husni

Mobile agent brings new concept on programming, especially on distributed computing paradigm. It attracts great interest because of its mobility, autonomy and persistence. But it also brings security issues i.e. insecure networks, malicious agents, malicious hosts and malicious users. One most difficult issues is protecting mobile agent from malicious host because mobile agent execute its code on host so that host can do many things to manipulate data, code and control flow of mobile agent. This paper proposes mobile-agent's self-reliant host security examination so that mobile agent is able to identify malicious host. In this proposed scheme, every hosts must have signature in blinded form in order to ensure unauthorized host cannot use this signature. This signature serves to distinguish malicious hosts with trusted host. When mobile agent arrives at new host, it will check validation of host's signature. Mobile agent also gives challenge to host, and host has to give a valid response. If host cannot give valid signature and response, mobile agent will identify this host as malicious host and return to its previous host. Zero knowledge proof of knowledge is used on challenge-response phase so that private keys cannot be revealed.

Peter Corcoran, Claudia Costache

The potential synergies between consumer handheld devices, particularly smartphones and biometric technologies is outlines. The practicalities and challenges for three such technologies - fingerprint, iris and palmprint - are presented. The use of biometrics for personal authentication is discussed, including the use of zero knowledge proof techniques to ensure that the biometric data does not leave the phone. The scope for data theft and breach through spoofing of the original biometric are discussed. Finally the potential impact of this technology synergy on personal privacy is considered.

Mohsen Toorani

Abstract This paper considers security analysis of the YAK, a public key‐based authenticated key agreement protocol. The YAK protocol is a variant of the two‐pass HMQV protocol but uses zero‐knowledge proofs for proving knowledge of ephemeral values. In this paper, we show that the YAK protocol lacks joint key control and perfect forward secrecy attributes and is vulnerable to some attacks including unknown key‐share and key‐replication attacks. This invalidates the semantic security of the protocol in several security models. There are also other considerations regarding the impersonation and small subgroup attacks. Copyright © 2015 John Wiley &amp; Sons, Ltd.

Marcos Portnoi, Chien-Chung Shen

We introduce LOCATHE (Location-Enhanced Authenticated Key Exchange), a generic protocol that pools location, user attributes, access policy and desired services into a multi-factor authentication, allowing two peers to establish a secure, encrypted session and perform mutual authentication with pre-shared keys, passwords and other authentication factors. LOCATHE contributes to: (1) forward secrecy through ephemeral session keys; (2) security through zero-knowledge password proofs (ZKPP), such that no passwords can be learned from the exchange; (3) the ability to use not only location, but also multiple authentication factors from a user to a service; (4) providing a two-tiered privacy authentication scheme, in which a user may be authenticated either based on her attributes (hiding her unique identification), or with a full individual authentication; (5) employing the expressiveness and flexibility of Decentralized or Multi-Authority Ciphertext-Policy Attribute-Based Encryption, allowing multiple service providers to control their respective key generation and attributes.

Liang-Ao Zhang, Xingming Sun, Zhihua Xia, Qiuju Ji

Attribute-Based Encryption (ABE) is a promising cryptographic primitive to implement access control for secure data storage in the cloud. Since the data owner may frequently change the access policies defined in the ciphertext, it is significant to provide the capacity for dynamic policy updating. However the cloud should also authenticate the owner because the adversary may modify the access policies of the files in the cloud to prevent the legal users from accessing them. In this paper, we focus on the owner's authentication in the ABE systems and propose a novel scheme which enables access control with authenticated dynamic policy updating in the cloud. We adapt the Pedersen commitment and Zero Knowledge Proof of Knowledge (ZKPK) to realize the anonymous authentication of the owner's policy updating key without increasing any secret information to the owner side. The analysis shows that our scheme is authentic and efficient as well as adaptive to different types of access policies.