Blockchain Papers

Xianrui Qin, Cailing Cai, Tsz Hon Yuen

No abstract is available for this record.

Jung Hee Cheon, Dongwoo Kim, Keewoo Lee

We propose a multi-party computation (MPC) protocol over \(\mathbb {Z}_{2^k}\) secure against actively corrupted majority from somewhat homomorphic encryption. The main technical contributions are: (i) a new efficient packing method for \(\mathbb {Z}_{2^k}\)-messages in lattice-based somewhat homomorphic encryption schemes, (ii) a simpler reshare protocol for level-dependent packings, (iii) a more efficient zero-knowledge proof of plaintext knowledge on cyclotomic rings \({\mathbb Z}[X]/\varPhi _M(X)\) with M being a prime. Integrating them, our protocol shows from 2.2x upto 4.8x improvements in amortized communication costs compared to the previous best results. Our techniques not only improve the efficiency of MPC over \(\mathbb {Z}_{2^k}\) considerably, but also provide a toolkit that can be leveraged when designing other cryptographic primitives over \(\mathbb {Z}_{2^k}\).

Suthee Ruangwises

Sudoku is a famous logic puzzle where the player has to fill a number between 1 and 9 into each empty cell of a $9 \times 9$ grid such that every number appears exactly once in each row, each column, and each $3 \times 3$ block. In 2020, Sasaki et al. developed a physical card-based protocol of zero-knowledge proof (ZKP) for Sudoku, which enables a prover to convince a verifier that he/she knows a solution of the puzzle without revealing it. Their protocol uses 90 cards, but requires nine identical copies of some cards, which cannot be found in a standard deck of playing cards (consisting of 52 different cards and two jokers). Hence, nine identical standard decks are required to perform that protocol, making the protocol not very practical. In this paper, we propose a new ZKP protocol for Sudoku that can be performed using only two standard decks of playing cards, regardless of whether the two decks are identical or different. In general, we also develop the first ZKP protocol for a generalized $n \times n$ Sudoku that can be performed using a deck of all different cards.

Christoph Dobraunig, Lorenzo Grassi, Anna Guinet, Daniël Kuijsters

Motivated by new applications such as secure Multi-Party Computation (MPC), Fully Homomorphic Encryption (FHE), and Zero-Knowledge proofs (ZK), the need for symmetric encryption schemes that minimize the number of field multiplications in their natural algorithmic description is apparent. This development has brought forward many dedicated symmetric encryption schemes that minimize the number of multiplications in \( \mathbb {F}_{2^n} \) or \( \mathbb {F}_{p} \), with p being prime. These novel schemes have lead to new cryptanalytic insights that have broken many of said schemes. Interestingly, to the best of our knowledge, all of the newly proposed schemes that minimize the number of multiplications use those multiplications exclusively in S-boxes based on a power mapping that is typically \(x^3\) or \(x^{-1}\). Furthermore, most of those schemes rely on complex and resource-intensive linear layers to achieve a low multiplication count. In this paper, we present Ciminion, an encryption scheme minimizing the number of field multiplications in large binary or prime fields, while using a very lightweight linear layer. In contrast to other schemes that aim to minimize field multiplications in \( \mathbb {F}_{2^n} \) or \( \mathbb {F}_{p} \), Ciminion relies on the Toffoli gate to improve the non-linear diffusion of the overall design. In addition, we have tailored the primitive for the use in a Farfalle-like construction in order to minimize the number of rounds of the used primitive, and hence, the number of field multiplications as far as possible.

Ida Tucker

One of the current challenges in cryptographic research is the development of advanced cryptographic primitives ensuring a high level of confidence. In this thesis, we focus on their design, while proving their security under well-studied algorithmic assumptions.My work grounds itself on the linearity of homomorphic encryption, which allows to perform linear operations on encrypted data. Precisely, I built upon the linearly homomorphic encryption scheme introduced by Castagnos and Laguillaumie at CT-RSA'15. Their scheme possesses the unusual property of having a prime order plaintext space, whose size can essentially be tailored to ones' needs. Aiming at a modular approach, I designed from their work technical tools (projective hash functions, zero-knowledge proofs of knowledge) which provide a rich framework lending itself to many applications.This framework first allowed me to build functional encryption schemes; this highly expressive primitive allows a fine grained access to the information contained in e.g., an encrypted database. Then, in a different vein, but from these same tools, I designed threshold digital signatures, allowing a secret key to be shared among multiple users, so that the latter must collaborate in order to produce valid signatures. Such signatures can be used, among other applications, to secure crypto-currency wallets. Significant efficiency gains, namely in terms of bandwidth, result from the instantiation of these constructions from class groups. This work is at the forefront of the revival these mathematical objects have seen in cryptography over the last few years.

Abdelrahaman Aly, Tomer Ashur, Eli Ben‐Sasson, Siemen Dhooghe · 5 authors

While traditional symmetric algorithms like AES and SHA-3 are optimized for efficient hardware and software implementations, a range of emerging applications using advanced cryptographic protocols such as multi-party computation and zero knowledge proofs require optimization with respect to a different metric: arithmetic complexity. In this paper we study the design of secure cryptographic algorithms optimized to minimize this metric. We begin by identifying the differences in the design space between such arithmetization-oriented ciphers and traditional ones, with particular emphasis on the available tools, efficiency metrics, and relevant cryptanalysis. This discussion highlights a crucial point—the considerations for designing arithmetization-oriented ciphers are oftentimes different from the considerations arising in the design of software- and hardware-oriented ciphers. The natural next step is to identify sound principles to securely navigate this new terrain, and to materialize these principles into concrete designs. To this end, we present the Marvellous design strategy which provides a generic way to easily instantiate secure and efficient algorithms for this emerging domain. We then show two examples for families following this approach. These families — Vision and Rescue — are benchmarked with respect to three use cases: the ZK-STARK proof system, proof systems based on Rank-One Constraint Satisfaction (R1CS), and Multi-Party Computation (MPC). These benchmarks show that our algorithms achieve a highly compact algebraic description, and thus benefit the advanced cryptographic protocols that employ them.

Ethan Heilman, Neha Narula, Garrett Tanzer, James Peter Thomas. Lovejoy · 7 authors

We present attacks on the cryptography formerly used in the IOTA blockchain, including under certain conditions the ability to forge signatures. We developed practical attacks on IOTA’s cryptographic hash function Curl-P-27, allowing us to quickly generate short colliding messages. These collisions work even for messages of the same length. Exploiting these weaknesses in Curl-P-27, we broke the EUCMA security of the former IOTA Signature Scheme (ISS). Finally, we show that in a chosen-message setting we could forge signatures and multi-signatures of valid spending transactions (called bundles in IOTA).

Ward Beullens, Tim Beyne, Aleksei Udovenko, Giuseppe Vitto

The Legendre PRF relies on the conjectured pseudorandomness properties of the Legendre symbol with a hidden shift. Originally proposed as a PRG by Damgård at CRYPTO 1988, it was recently suggested as an efficient PRF for multiparty computation purposes by Grassi et al. at CCS 2016. Moreover, the Legendre PRF is being considered for usage in the Ethereum 2.0 blockchain. This paper improves previous attacks on the Legendre PRF and its higher-degree variant due to Khovratovich by reducing the time complexity from O(< (p log p/M) to O(p log2 p/M2) Legendre symbol evaluations when M ≤ 4√ p log2 p queries are available. The practical relevance of our improved attack is demonstrated by breaking three concrete instances of the PRF proposed by the Ethereum foundation. Furthermore, we generalize our attack in a nontrivial way to the higher-degree variant of the Legendre PRF and we point out a large class of weak keys for this construction. Lastly, we provide the first security analysis of two additional generalizations of the Legendre PRF originally proposed by Damgård in the PRG setting, namely the Jacobi PRF and the power residue PRF.

PKC 2020 Online, Kiayias, Aggelos, Kohlweiss, Markulf, Wallden, Petros · 5 authors

No abstract is available for this record.

Ward Beullens, Cyprien Delpech de Saint Guilhem

No abstract is available for this record.

Emanuele Bellini, Philippe Gaborit, Alexandros Hasikos, Víctor Mateu

The advent of quantum computers is a threat to most currently deployed cryptographic primitives. Among these, zero-knowledge proofs play an important role, due to their numerous applications. The primitives and protocols presented in this work base their security on the difficulty of solving the Rank Syndrome Decoding (RSD) problem. This problem is believed to be hard even in the quantum model. We first present a perfectly binding commitment scheme. Using this scheme, we are able to build an interactive zero-knowledge proof to prove: the knowledge of a valid opening of a committed value, and that the valid openings of three committed values satisfy a given linear relation, and, more generally, any bitwise relation. With the above protocols it becomes possible to prove the relation of two committed values for an arbitrary circuit, with quasi-linear communication complexity and a soundness error of 2/3. To our knowledge, this is the first quantum resistant zero-knowledge protocol for arbitrary circuits based on the RSD problem. An important contribution of this work is the selection of a set of parameters, and an a full implementation, both for our proposal in the rank metric and for the original LPN based one by Jain et al. in the Hamming metric, from which we took the inspiration. Beside demonstrating the practicality of both constructions, we provide evidence of the convenience of rank metric, by reporting performance benchmarks and a detailed comparison.

Alexandr Kuznetsov, Kyryl Shekhanin, Andrii Kolhatin, Diana Kovalchuk · 6 authors

The main cryptographic primitives in blockchain networks are hashing functions that are designed to form short and unpredictable digests for the message entered. In blockchain networks, hashing is used to build linked block lists, which provide safe and secure storage of important information in a distributed repository. The peculiarity of the hash search problem in blockchain networks allows applying the maximum parallelization of calculations, what good are multithreaded graphics processors (GPUs). In this paper, we explore the performance of GOST 34.311, STRIBOG, KECCAK, SHA2, RIPEMD160, Blake2b, and Whirlpool cryptographic hashing algorithms. HashCat software and various GPUs were used for comparative analysis of efficiency. GPUs were used: Geforce 740M 2GB; Geforce GTX1050ti 4GB; Rx580 Aorus 4GB; Rx580 Sapphire Pulse 8GB; Sapphire Vega 56 8GB.

Stefan Kölbl, Elmar Tischhauser, Patrick Derbez, Andrey Bogdanov

No abstract is available for this record.

Jack Grigg, George Tankersley, Henry de Valence, Isis Lovecruft · 5 authors

This memo specifies a prime-order group, ristretto255, suitable for implementing complex cryptographic protocols such as zero-knowledge proofs. The ristretto255 group can be implemented using Curve25519, allowing existing Curve25519 implementations to be reused and extended to provide a prime-order group.

Omar A. Dawood, Othman I. Hammadi, Falath M. Mohammed

This paper proposes a new symmetric secret-key cipher for construction of block cipher model. This new approach is considered as a smart step that can be applied to the long process research of modern designing methods used in developing earlier symmetric algorithms. The present cipher can encrypt block lengths of 128-bit by employing Substitution-Permutation Network (SPN) structure. The present cipher uses three options of strong ciphering-key along with variable lengths of 192-bit for 12 rounds, 128-bit for 10 rounds and long ciphering key of 256-bit for 14 rounds similar to standard ciphers. The proposed algorithm has been designed to trust applications that are based on Bitcoin and crypto-currencies. The current algorithm intended to encrypt addresses of Bitcoin wallet that work quite similar to the e-mail address. The bitcoin wallet includes sensitive information like private secret keys and derived password that are highly confidential. The Advance Encryption Standard (AES) is employed to encrypt most of the bitcoin wallet database. The proposed cipher can act as a good substitute for the standard cipher that allows trusting the Bitcoin wallet database with high security and with a much more complex scheme. The key goal of the submitted algorithm is to build a new enhanced modern cipher with a secure and efficient applicable algorithm that can be used for crypto currencies applications employing a wide trail design strategy.

Eli Ben‐Sasson, Lior Goldberg, Swastik Kopparty, Shubhangi Saraf

Motivated by the quest for scalable and succinct zero knowledge arguments, we revisit worst-case-to-average-case reductions for linear spaces, raised by [Rothblum, Vadhan, Wigderson, STOC 2013]. The previous state of the art by [Ben-Sasson, Kopparty, Saraf, CCC 2018] showed that if some member of an affine space U is δ-far in relative Hamming distance from a linear code V - this is the worst-case assumption - then most elements of U are almost-δ-far from V - this is the average case. However, this result was known to hold only below the "double Johnson" function of the relative distance δ_V of the code V, i.e., only when δ < 1-(1-δ_V)^(1/4). First, we increase the soundness-bound to the "one-and-a-half Johnson" function of δ_V and show that the average distance of U from V is nearly δ for any worst-case distance δ smaller than 1-(1-δ_V)^(1/3). This bound is tight, which is somewhat surprising because the one-and-a-half Johnson function is unfamiliar in the literature on error correcting codes. To improve soundness further for Reed Solomon codes we sample outside the box. We suggest a new protocol in which the verifier samples a single point z outside the box D on which codewords are evaluated, and asks the prover for the value at z of the interpolating polynomial of a random element of U. Intuitively, the answer provided by the prover "forces" it to choose one codeword from a list of "pretenders" that are close to U. We call this technique Domain Extending for Eliminating Pretenders (DEEP). The DEEP method improves the soundness of the worst-case-to-average-case reduction for RS codes up their list decoding radius. This radius is bounded from below by the Johnson bound, implying average distance is approximately δ for all δ < 1-(1-δ_V)^(1/2). Under a plausible conjecture about the list decoding radius of Reed-Solomon codes, average distance from V is approximately δ for all δ. The DEEP technique can be generalized to all linear codes, giving improved reductions for capacity-achieving list-decodable codes. Finally, we use the DEEP technique to devise two new protocols: - An Interactive Oracle Proof of Proximity (IOPP) for RS codes, called DEEP-FRI. The soundness of the protocol improves upon that of the FRI protocol of [Ben-Sasson et al., ICALP 2018] while retaining linear arithmetic proving complexity and logarithmic verifier arithmetic complexity. - An Interactive Oracle Proof (IOP) for the Algebraic Linking IOP (ALI) protocol used to construct zero knowledge scalable transparent arguments of knowledge (ZK-STARKs) in [Ben-Sasson et al., eprint 2018]. The new protocol, called DEEP-ALI, improves soundness of this crucial step from a small constant < 1/8 to a constant arbitrarily close to 1.

Lake Bu, Rashmi Agrawal, Hai Cheng, Michel A. Kinsy

The development and implementation of post-quantum cryptosystems have become a pressing issue in the design of secure computing systems, as general quantum computers have become more feasible in the last two years. In this work, we introduce a set of hardware post-quantum cryptographic primitives (PCPs) consisting of four frequently used security components, i.e., public-key cryptosystem (PKC), key exchange (KEX), oblivious transfer (OT), and zero-knowledge proof (ZKP). In addition, we design a high speed polynomial multiplier to accelerate these primitives. These primitives will aid researchers and designers in constructing quantum-proof secure computing systems in the post-quantum era.

Nir Bitansky, Akshay Degwekar

No abstract is available for this record.

Khoa Nguyen, Khai Hanh Tang, Huaxiong Wang, Neng Zeng

No abstract is available for this record.

Behzad Abdolmaleki, Hamidreza Khoshakhlagh, Daniel Slamanig

Hash proof systems or smooth projective hash functions (SPHFs) have been proposed by Cramer and Shoup (Eurocrypt’02) and can be seen as special type of zero-knowledge proof system for a language. While initially used to build efficient chosen-ciphertext secure public-key encryption, they found numerous applications in several other contexts. In this paper, we revisit the notion of SPHFs and introduce a new feature (a third mode of hashing) that allows to compute the hash value of an SPHF without having access to neither the witness nor the hashing key, but some additional auxiliary information. We call this new type publicly computable SPHFs (PC-SPHFs) and present a formal framework along with concrete instantiations from a large class of SPHFs.

Ruping Shen, Hong Xiang, Xin Zhang, Bin Cai · 5 authors

No abstract is available for this record.

Ward Beullens, Jean‐Charles Faugère, Eliane Koussa, Gilles Macario-Rat · 6 authors

No abstract is available for this record.

Itai Dinur, Daniel Kales, Angela Promitzer, Sebastian Ramacher · 5 authors

No abstract is available for this record.

M. Albrecht, Carlos Cid, Lorenzo Grassi, Dmitry Khovratovich · 7 authors

No abstract is available for this record.