Blockchain Papers

Ramiro Martínez, Paz Morillo

No abstract is available for this record.

Yanhua Zhang, Yifeng Yin, Ximeng Liu, Qikun Zhang · 5 authors

No abstract is available for this record.

Vincenzo Iovino, Ivan Visconti

The Fiat-Shamir (FS) transform is a well known and widely used technique to convert any constant-round public-coin honest-verifier zero-knowledge (HVZK) proof or argument system \(\mathsf {HVZK}=(\mathcal {P},\mathcal {V})\) in a non-interactive zero-knowledge (NIZK) argument system

S. M. Ratseev, M. A. Rostov

, , , , 432017, ,

Wei Ou, Mingwei Deng, Entao Luo

No abstract is available for this record.

Yanhua Zhang, Yupu Hu, Qikun Zhang, Huiwen Jia

No abstract is available for this record.

Matteo Campanelli, Dario Fiore, Anaïs Querol

We study the problem of building non-interactive proof systems modularly by linking small specialized SNARKs in a lightweight manner. Our motivation is both theoretical and practical. On the theoretical side, modular SNARK designs would be flexible and reusable. Also, previous works (e.g., Geppetto) consider They have been successfully employed in previous works.(cite prev papers ). These approaches, however, tend to be ad-hoc and to reinventing the wheel. We propose to fill this gap. In practice, specialized SNARKs have the potential to be more efficient than general-purpose schemes, on which most existing works have focused. If a computation naturally presents different components (e.g. one arithmetic circuit and one boolean circuit), a general-purpose scheme would homogenize them to a single representation with a subsequent cost in performance. Through a modular approach one could instead exploit the nuances of a computation and choose the best gadget for each component. Our contribution is LegoSNARK, a toolbox (or framework) for commit-and-prove zkSNARKs (CP-SNARKs) that includes: 1) General composition tools: build new CP-SNARKs from proof gadgets for basic relationssimply. Formalize notion of cc-SNARK. 2) A lifting tool: a compiler to add commit-and-prove capabilities to a broad class of existing zkSNARKsefficiently. This makes them interoperable (linkable) within the same computation. For example, one QAP-based scheme can be used prove one component; another GKR-based scheme can be used to prove another. 3) A collection of succinct proof gadgets for a variety of relations. Additionally, through our framework and gadgets, we are able to obtain new succinct proof systems. Notably: -- LegoGro16, a commit-and-prove version of Groth16 zkSNARK, that operates over data committed with a classical Pedersen vector commitment, and that achieves a 5000× speedup in proving time. -- LegoUAC, a pairing-based SNARK for arithmetic circuits that has a universal, circuit-independent, CRS, and proving time linear in the number of circuit gates (vs. the recent scheme of Groth et al. (CRYPTO'18) with quadratic CRS and quasilinear proving time). -- LegoMM, a CP-SNARK for matrix multiplication that achieves optimal proving complexity.

David Cerezo Sánchez

Zero-Knowledge Proof-of-Identity from trusted public certificates (e.g., national identity cards and/or ePassports; eSIM) is introduced here to permissionless blockchains in order to remove the inefficiencies of Sybil-resistant mechanisms such as Proof-of-Work (i.e., high energy and environmental costs) and Proof-of-Stake (i.e., capital hoarding and lower transaction volume). The proposed solution effectively limits the number of mining nodes a single individual would be able to run while keeping membership open to everyone, circumventing the impossibility of full decentralization and the blockchain scalability trilemma when instantiated on a blockchain with a consensus protocol based on the cryptographic random selection of nodes. Resistance to collusion is also considered. Solving one of the most pressing problems in blockchains, a zk-PoI cryptocurrency is proved to have the following advantageous properties: - an incentive-compatible protocol for the issuing of cryptocurrency rewards based on a unique Nash equilibrium - strict domination of mining over all other PoW/PoS cryptocurrencies, thus the zk-PoI cryptocurrency becoming the preferred choice by miners is proved to be a Nash equilibrium and the Evolutionarily Stable Strategy - PoW/PoS cryptocurrencies are condemned to pay the Price of Crypto-Anarchy, redeemed by the optimal efficiency of zk-PoI as it implements the social optimum - the circulation of a zk-PoI cryptocurrency Pareto dominates other PoW/PoS cryptocurrencies - the network effects arising from the social networks inherent to national identity cards and ePassports dominate PoW/PoS cryptocurrencies - the lower costs of its infrastructure imply the existence of a unique equilibrium where it dominates other forms of payment

Tiacheng Xie, Jiaheng Zhang, Yupeng Zhang, Charalampos Papamanthou · 5 authors

No abstract is available for this record.

Thomas Haines, Clémentine Gritti

No abstract is available for this record.

Michael Backes, Lucjan Hanzlik, Amir Herzberg, Aniket Kate · 5 authors

No abstract is available for this record.

Elette Boyle, Niv Gilboa, Yuval Ishai, Ariel Nof

Secure multiparty computation enables a set of parties to securely carry out a joint computation on their private inputs without revealing anything but the output. A particularly motivated setting is that of three parties with a single corruption (hereafter denoted 3PC). This 3PC setting is particularly appealing for two main reasons: (1) it admits more efficient MPC protocols than in other standard settings; (2) it allows in principle to achieve full security (and fairness). Highly efficient protocols exist within this setting with security against a semi-honest</> adversary; however, a significant gap remains between these and protocols with stronger security against a malicious</> adversary. In this paper, we narrow this gap within concretely efficient protocols. More explicitly, we have the following contributions: Concretely Efficient Malicious 3PC. We present an optimized 3PC protocol for arithmetic circuits over rings with (amortized) communication of 1 ring element per multiplication gate per party, matching the best semi-honest protocols. The protocol applies also to Boolean circuits, significantly improving over previous protocols even for small circuits. Our protocol builds on recent techniques of Boneh et al. (Crypto 2019) for sublinear zero-knowledge proofs on distributed data, together with an efficient semi-honest protocol based on replicated secret sharing (Araki et al., CCS 2016). We present a concrete analysis of communication and computation costs, including several optimizations. For example, for 40-bit statistical security, and Boolean circuit with a million (nonlinear) gates, the overhead on top of the semi-honest protocol can involve less than 0.5KB of communication for the entire circuit,</> while the computational overhead is dominated by roughly 30 multiplications per gate in the field F247. In addition, we implemented and benchmarked the protocol for varied circuit sizes. Full Security. We augment the 3PC protocol to further provide full security</> (with guaranteed output delivery) while maintaining amortized 1 ring element communication per party per multiplication gate, and with hardly any impact on concrete efficiency. This is contrasted with the best previous 3PC protocols from the literature, which allow a corrupt party to mount a denial-of-service attack without being detected.

Lorenzo Grassi, Dmitry Khovratovich, Christian Rechberger, Arnab Roy · 5 authors

No abstract is available for this record.

Jonathan Bootle, Vadim Lyubashevsky, Gregor Seiler

A key component of many lattice-based protocols is a zero-knowledge proof of knowledge of a vector \(\vec {s}\) with small coefficients satisfying \(A\vec {s}=\vec {u}\bmod \,q\). While there exist fairly efficient proofs for a relaxed version of this equation which prove the knowledge of \(\vec {s}'\) and c satisfying \(A\vec {s}'=\vec {u}c\) where \(\Vert \vec {s}'\Vert \gg \Vert \vec {s}\Vert \) and c is some small element in the ring over which the proof is performed, the proofs for the exact version of the equation are considerably less practical. The best such proof technique is an adaptation of Stern’s protocol (Crypto ’93), for proving knowledge of nearby codewords, to larger moduli. The scheme is a \(\varSigma \)-protocol, each of whose iterations has soundness error \(2{/}3\), and thus requires over 200 repetitions to obtain soundness error of \(2^{-128}\), which is the main culprit behind the large size of the proofs produced.

Jean‐Guillaume Dumas, Pascal Lafourcade, Daiki Miyahara, Takaaki Mizuki · 6 authors

No abstract is available for this record.

Muhammed F. Esgin, Ron Steinfeld, Joseph K. Liu, Dongxi Liu

We devise new techniques for design and analysis of efficient lattice-based zero-knowledge proofs (ZKP). First, we introduce one-shot proof techniques for non-linear polynomial relations of degree \(k\ge 2\), where the protocol achieves a negligible soundness error in a single execution, and thus performs significantly better in both computation and communication compared to prior protocols requiring multiple repetitions. Such proofs with degree \(k\ge 2\) have been crucial ingredients for important privacy-preserving protocols in the discrete logarithm setting, such as Bulletproofs (IEEE S&P ’18) and arithmetic circuit arguments (EUROCRYPT ’16). In contrast, one-shot proofs in lattice-based cryptography have previously only been shown for the linear case (\(k=1\)) and a very specific quadratic case (\(k=2\)), which are obtained as a special case of our technique.

Dan Boneh, Elette Boyle, Henry Corrigan-Gibbs, Niv Gilboa · 5 authors

We introduce and study the notion of fully linear probabilistically checkable proof systems. In such a proof system, the verifier can make a small number of linear queries that apply jointly to the input and a proof vector.

Jestine Paul, Quanqing Xu, Shao Fei, Bharadwaj Veeravalli · 5 authors

No abstract is available for this record.

Xixun Yu, Zheng Yan, Rui Zhang

No abstract is available for this record.

Hui Tian, Fulin Nan, Chin‐Chen Chang, Yongfeng Huang · 6 authors

No abstract is available for this record.

Yusheng Wei, Zongli Lin

In this paper, we propose a delay independent control scheme that regulates to zero the state and the control input of a linear input delayed system whose open loop poles are at the origin. Two main features of our control scheme are its non-distributed nature in the sense that only the current state is used in the feedback, and its delay independence in the sense that no knowledge of the delay is required. The main ingredients of our control scheme and the regulation proof include a design of the delay independent truncated predictor feedback law with a time-varying feedback parameter, a Lyapunov function based adaptation of the time-varying parameter, a mechanism for switching between two update laws of the time-varying parameter, and the partial differential equation based analysis for delayed systems.

CK Raju

Mathematics is not universal.Traditional (normal) mathematics accepts both deductive and empirical proofs like science.Colonial education replaced it with formal mathematics, the unique feature of which is not the use of reasoning but exclusion of the empirical.The coloniser never critically compared normal and formal mathematics, and tries to block such a comparison today.In Western dogma (of the church theology of reason) deduction is infallible.In fact, deduction is fallible.(1) An invalid deductive proof may be mistaken as valid.Doubts about validity can only be settled inductively.In practice, doubts are settled by invoking authority.Hence, deductive proofs are always more fallible than empirical proofs.(2) The postulates of formal math cannot be empirically checked; they are metaphysics (a metaphysics of infinity is needed even for the formal math of 1+1=2).Thus, far from being eternal truths, formal mathematical theorems may not even be approximately valid knowledge.(3) Formal math dogmatically assumes two-valued logic (on the superstition that logic binds God).But logic is neither culturally universal (e.g.Buddhist logic) nor empirically certain (quantum logic).Therefore, the theorems of formal math (even if valid) are not even truths relative to postulates.Hence, colonial/formal math is inferior and should be rejected.This does not affect the practical value of math -what 'works'which all comes from normal math which we should, accordingly, teach.I describe two actual decolonised math courses being taught: decolonised geometry in school, and decolonised calculus in the university.Decolonised (string) geometry that is indigenous to Africa and India, is superior to the geometry currently taught in terms of conceptual clarity (points, angle, distance), ease of learning, and practical applications.Decolonised calculus teaches calculus as normal math, the way it originated in India as a numerical technique to solve differential equations, together with non-Archimedean arithmetic (instead of formal 'real' numbers) and zeroism (instead of limits) used to sum infinite series.Europeans stole calculus from India, and falsely attributed it to Newton and Leibniz, who failed to understand how to sum infinite series due to the Western superstition (since Plato) that mathematics is eternal truth, and hence exact.Eventually, they introduced a metaphysics of infinity allied to church dogmas of eternityset theory, formal real numbers, and limitsas taught in university today.This metaphysics is irrelevant for any practical application of calculus, such as sending a rocket to the moon, but makes calculus very difficult.Decolonised calculus is easy, requires almost no background, and results in better science.It enables students to solve harder problems not covered in usual calculus courses.However, it excludes the ability to slip politically convenient dogmas into science through the metaphysics of formal math, and is, hence, resisted by the coloniser today.

Wu Chen, Shaohua Tang, Xingfu Yan

The great convenience of electronic voting can improve the attendance and thus promote the process of democratization. However, the appearance of quantum computer severely threatens the security of those traditional electronic voting schemes. The efficiency of the current post-quantum electronic voting scheme is relatively low, some of them are unable to verify the validity of the ballots which results in a stronger security assumption. In this paper, we propose an efficient LWE-based verifiable electronic voting system whose security is based on the LWE assumption. To protect the user privacy, we tally homomorphically and verify the validity of ballot ciphertext through some interactions between two verification servers. In addition, a zero-knowledge proof can be utilized to verify the correctness of tally results. Finally, we analyze the properties and implement our system, the experimental results show the effectiveness of our system.

Terry Chien‐Jen Yang

Elections conducted on paper consume a lot of resources and contribute to the destruction of forests, which leads to climate deterioration. Moreover, such election process can make it difficult for some people to vote and it often leads to doubts in the validity of counting, in people submitting multiple votes, in ineligible people voting. In several well-known previous examples, doubts in the validity of paper elections lead to the need of recounting and even court battles to decide the validity of the outcome. Having a way to vote online could be an easier and more reliable solution. However, secure and verifiable methods of online voting need to be developed to achieve this.<br><br>Recent online voting experiences in countries such as the United States, India and Brazil demonstrated that further research is needed to improve security guarantees for future elections, to ensure the confidentiality of votes and enable the verification of their integrity and validity. Electronic voting, to be successful, requires a more transparent and secure approach, than the approach that is offered by current electronic voting protocols. Advanced security methods are necessary to introduce effective online voting in the whole world.<br><br>Currently, most online voting systems are centralized, which means that they involve central tallying authorities to take responsibility for verifying, tallying and publishing the final outcome of the election. These previous systems always assume that their central authorities are honest. Otherwise, the published final outcome cannot be trusted. The aim of our new research is to propose and investigate a decentralized ranked choice online voting systems, which never rely on any third party (such as tallying authorities), thereby significantly increasing the confidence and trust of the voters.<br><br>The thesis presents several publicly verifiable online voting systems and indicates the processing steps and stages in the development of a publicity verifiable online voting system from centralized to semi-decentralized, to fully decentralized. By using Homomorphic cryptosystem, proof of zero knowledge and Blockchain technology, the proposed system in this thesis can achieve the following: (1) Flexible voting mechanism: voters can easily rank all candidates; (2) Publicity verifiable: the whole election procedure is transparent and verifiable by voters; (3) Self-tallying: the final outcome of the election can be computed by any individual voter; and (4) Fully decentralized: no tallying authority (or any other trusted third party) involved at all.<br><br>The proposed systems presented in this thesis include protocols developed on Blockchain technology. The technology that is used as the basis for a secure online voting system is ``smart contract over Blockchain', which offers a factor of the integrity of votes and has not been deeply studied in Blockchain technologies to date. The proposed voting protocols ensure confidentiality and preserve the voters' privacy while keeping the election procedures transparent and secure. The underlying Blockchain protocol has not been modified in any way, the voting scheme proposed merely offers an alternative use case of the protocol at hand, which could be presented as the basis for voting systems using Blockchain with further development of the underlying Blockchain protocols.<br><br>