Blockchain Papers

Léo Robert, Daiki Miyahara, Pascal Lafourcade, Takaaki Mizuki

No abstract is available for this record.

Rabimba Karanjai, Sangwon Shin, Xiong, and Wujie, Xinxin Fan · 11 authors

Cryptographic schemes like Fully Homomorphic Encryption (FHE) and Zero-Knowledge Proofs (ZKPs), while offering powerful privacy-preserving capabilities, are often hindered by their computational complexity. Polynomial multiplication, a core operation in these schemes, is a major performance bottleneck. While algorithmic advancements and specialized hardware like GPUs and FPGAs have shown promise in accelerating these computations, the recent surge in AI accelerators (TPUs/NPUs) presents a new opportunity. This paper explores the potential of leveraging TPUs/NPUs to accelerate polynomial multiplication, thereby enhancing the performance of FHE and ZKP schemes. We present techniques to adapt polynomial multiplication to these AI-centric architectures and provide a preliminary evaluation of their effectiveness. We also discuss current limitations and outline future directions for further performance improvements, paving the way for wider adoption of advanced cryptographic tools.

Amalan Joseph Antony, Kunwar Singh

No abstract is available for this record.

Jianqiang Ni, Jianhui Zhang, Gaoli Wang, Rui Li · 5 authors

Modern cryptographic protocols such as zero-knowledge proofs and secure multi-party computation have increased the demand for a novel category of symmetric primitives. These primitives are not optimized for traditional platforms such as servers, microcontrollers, and desktop computers but rather for their ability to be implemented in arithmetic circuits. To enable efficient arithmetic operations, they define operations over larger finite fields and use low-degree invertible functions to construct their non-linear layers. Grendel is an arithmetization-oriented permutation that leverages the Legendre Symbol to enhance the growth of algebraic degrees in its non-linear layer. In this paper, we present a preimage attack on the sponge hash function instantiated with the full rounds of the Grendel permutation using algebraic methods. We introduce a technique that allows us to eliminate two full rounds of substitution permutation networks (SPN) in the sponge hash function with minimal or no additional cost. This method can be combined with univariate root-finding techniques and Gröbner basis attacks to break the number of rounds claimed by the designers. By utilizing this strategy, our attack achieves an improvement of two additional rounds compared to the previous state-of-the-art attack. While not breaking its security margin, it allows us to further understand the design and analysis of such cryptographic primitives.

Lorenzo Grassi

Motivated by new applications such as secure Multi-Party Computation (MPC), Fully Homomorphic Encryption (FHE), and Zero-Knowledge proofs (ZK), many MPC-, FHE- and ZK-friendly symmetric-key primitives that minimize the< number of multiplications over Fp for a large prime p have been recently proposed in the literature. These symmetric primitives are usually defined via invertible functions, including (i) Feistel and Lai-Massey schemes and (ii) SPN constructions instantiated with invertible non-linear S-Boxes. However, the “invertibility” property is actually never required in any of the mentioned applications.In this paper, we discuss the possibility to set up MPC-/FHE-/ZK-friendly symmetric primitives instantiated with non-invertible bounded surjective functions. In contrast to one-to-one functions, each output of a l-bounded surjective function admits at most l pre-images. The simplest example is the square map x → x2 over Fp for a prime p ≥ 3, which is (obviously) 2-bounded surjective. When working over Fnp for n ≥ 2, we set up bounded surjective functions by re-considering the recent results proposed by Grassi, Onofri, Pedicini and Sozzi at FSE/ToSC 2022 as starting points. Given a quadratic local map F : Fmp → Fp for m ∈ {1, 2, 3}, they proved that the shift-invariant non-linear function over Fnp defined as SF (x0, x1, . . . , xn−1) = y0∥y1∥ . . . ∥yn−1 where yi := F(xi, xi+1) is never invertible for any n ≥ 2 · m − 1. Here, we prove that • the quadratic function F : Fmp → Fp for m ∈ {1, 2} that minimizes the probability of having a collision for SF over Fnp is of the form F(x0, x1) = x20 + x1 (or equivalent);• the function SF over Fnp defined as before via F(x0, x1) = x20 +x1 (or equivalent) is 2n-bounded surjective.As concrete applications, we propose modified versions of the MPC-friendly schemes MiMC, HadesMiMC, and (partially of) Hydra, and of the FHE-friendly schemes Masta, Pasta, and Rubato. By instantiating them with the bounded surjective quadratic functions proposed in this paper, we are able to improve the security and/or the performances in the target applications/protocols.

Yongcheng Song, Jiang Zhang, Xinyi Huang, Wei Wu · 5 authors

Abstract The MinRank problem is an NP-complete problem that is prevalent in multivariate cryptography and its goal is to find a non-zero linear combination of given a series of matrices over a ring such that the obtained matrix has a small rank. At Asiacrypt 2001, two Zero-Knowledge Proofs of Knowledge (ZKPoK) for the MinRank problem are proposed, and we call them MRZK and MRZK$^{\dagger }$, respectively. The latter is an improved version of the proof size of the former. However, the efficiency of MRZK$^{\dagger }$ has been open and not analyzed. While the MRZK protocol is secure, it must be repeated many times due to the soundness error $2/3$, which leads to the large proof size. For 128-bit security, the MRZK protocol is executed at least 219 iterations and the proof size is about 32 KB. In this paper, we first show that the efficiency of MRZK$^{\dagger }$ is impractical due to unreasonable parameter size. However, when the parameter size is tuned and the efficiency is improved, an imposter can be efficiently constructed. Then, to alleviate the large proof size of MRZK, inspired by the technique designing ZKPoK (Eurocrypt 2020), we propose a sigma protocol with helper to prove the solution to the MinRank problem. Finally, we transform the sigma protocol with helper into a standard ZKPoK (MRZK$^{\sharp }$) by removing the helper. The MRZK$^{\sharp }$ protocol can achieve any small soundness error and enjoy the proof size of about 15 KB (53% improvement over MRZK).

Dong Fang, Guifang Huang, Mengfan Wang, Lei Hu

Abstract Bootle et al. in CRYPTO 2019 proposed a zero knowledge proof for an $\mathrm{ISIS}_{m,n,q,\beta }$ instance $A\vec{s} = \vec{u} \bmod q$ with $\|\vec{s}\|_{\infty }\leq \beta $ (BLS scheme). It was implemented by transforming the instance into the form $A^{\prime }\vec{s}^{\prime } =\vec{u}\bmod q$, where the coefficients of $\vec{s}^{\prime}$ are in $\{0,1,2\}$, and proved the latter in an exact way. With the concrete parameters $m=1024,n=2048,\beta =1,q\approx 2^{32}$, their proof is of length 384.03KB. In this paper, we decrease the proof size of BLS scheme by two techniques. The first one takes effect on some special parameters. For these parameters, using the binary basic set instead of the ternary one results in a shorter proof. The second one deals with the repetition of the lower half in BLS scheme. Observing that what the lower half proves is of form $\mathbf{B}\vec{\mathbf{r}}=\vec{\mathbf{t}}$ with a short vector $\vec{\mathbf{r}}$ of polynomials, a variant of parallel repetition can be used to shorten the proof size. Combining these two techniques together, the proof size of the above-mentioned instance can be reduced to 220.01KB, only 57.3$\%$ of BLS scheme.

Arnab Roy, Matthias Johann Steiner, Stefano Trevisani

In this paper we propose the (keyed) permutation Arion and the hash function ArionHash over $\mathbb{F}_p$ for odd and particularly large primes. The design of Arion is based on the newly introduced Generalized Triangular Dynamical System (GTDS), which provides a new algebraic framework for constructing (keyed) permutation using polynomials over a finite field. At round level Arion is the first design which is instantiated using the new GTDS. We provide extensive security analysis of our construction including algebraic cryptanalysis (e.g. interpolation and Gröbner basis attacks) that are particularly decisive in assessing the security of permutations and hash functions over $\mathbb{F}_p$. From an application perspective, ArionHash aims for efficient implementation in zkSNARK protocols and Zero-Knowledge proof systems. For this purpose, we exploit that CCZ-equivalence of graphs can lead to a more efficient implementation of Arithmetization-Oriented primitives. We compare the efficiency of ArionHash in R1CS and Plonk settings with other hash functions such as Poseidon, Anemoi and Griffin. For demonstrating the practical efficiency of ArionHash we implemented it with the zkSNARK libraries libsnark and Dusk Network Plonk. Our result shows that ArionHash is significantly faster than Poseidon - a hash function designed for zero-knowledge proof systems. We also found that an aggressive version of ArionHash is considerably faster than Anemoi and Griffin in a practical zkSNARK setting.

Adel Alahmadi, Selda Çalkavur, Patrick Solé, Abdul Nadim Khan · 6 authors

Blockchain is a method of recording information that makes it not feasible for the system to be replaced, attacked, or manipulated. A blockchain is equipped with a notebook that copies and processes the various procedures across the network of computers participating in the blockchain. Digital signature algorithm is one of the cryptographic protocols used by the blockchain. In this work, we introduce a new digital signature scheme based on error correcting codes. In the scheme constructed on a [n, k, d]− code over 𝔽q, which is d ≥ 2t + 1, and the size of the signature length is n − k. The signature verification is based on the bounded distance decoding of the code. Since the verification space is 𝔽qn, the proposed scheme has an improved performance in terms of working in a wider space.

Vaishnavi Nagaraja, Muhammad Rezal Kamel Ariffin, Terry Shue Chien Lau, Nurul Nur Hanisah Adenan · 7 authors

The identification protocol is a type of zero-knowledge proof. One party (the prover) needs to prove his identity to another party (the verifier) without revealing the secret key to the verifier. One can apply the Fiat–Shamir transformation to convert an identification scheme into a signature scheme which can be used for achieving security purposes and cryptographic purposes, especially for authentication. In this paper, we recall an identification protocol, namely the RankID scheme, and show that the scheme is incorrect and insecure. Then, we proposed a more natural approach to construct the rank version of the AGS identification protocol and show that our construction overcomes the security flaws in the RankID scheme. Our proposal achieves better results when comparing the public key size, secret key size, and signature size with the existing identification schemes, such as Rank RVDC and Rank CVE schemes. Our proposal also achieves 90%, 50%, and 96% reduction for the signature size, secret key size, and public key size when compared to the Rank CVE signature scheme.

Yongcheng Song, Jiang Zhang, Xinyi Huang, Wei Wu · 5 authors

No abstract is available for this record.

Leonardo Tejaya, Desi Arisandi, Janson Hendryli

Cryptocurrency is in great demand as an investment medium to gain financial benefits. A common problem that is often faced is how to predict the movement of the value of electronic money in the future. Investors/traders usually only see price movements and buy/sell Cryptocurrency assets intuitively, so mistakes often occur in making transactions. To anticipate and minimize this, you can use an algorithm that can help predict Cryptocurrency price movements. Extreme Learning Machine (ELM) is a development method of a simple feedforward neural network using one hidden layer or commonly known as Single Hidden Layer Feedforward Neural NetworksTesting is done by doing several trials for each percentage value, namely 60%, 65%, 70%, 75%, 80%. Tests were carried out using the binary sigmoid activation function, the number of hidden neurons was 20 and the weight range was [-1,1]. The best prediction results using MAPE are generated on Bitcoin data with the smallest error value of 2.8590% Keywords: Cryptocurrency; Investation; Extreme Learning Machine ; Prediction  Abstrak Cryptocurrency banyak diminati untuk menjadi media investasi dalam meraih keuntungan finansial. Masalah umum yang sering dihadapi adalah bagaimana meramalkan pergerakan nilai dari uang elektronik pada masa mendatan. Investor/ trader biasanya hanya melihat pergerakan harga dan melakukan jual/beli aset Cryptocurrency secara intuitif, sehingga sering terjadi salah dalam melakukan transaksi. Untuk mengantisipasi dan meminimalisir hal tersebut maka dapat menggunakan sebuah algoritme yang dapat membantu dalam meramalkan pergerakan harga Cryptocurrency . Extreme Learning Machine (ELM) merupakan metode pengembangan dari jaringan syaraf tiruan feedforward sederhana dengan menggunakan satu hidden layer atau biasa dikenal dengan Single Hidden Layer Feedforward Neural Networks . Pengujian dilakukan dengan melakukan beberapa kali percobaan untuk setiap nilai persentase yaitu 60%, 65%, 70%, 75%, 80%. Pengujian dilakukan menggunakan fungsi aktivasi sigmoid biner, jumlah hidden neuron 20 serta rentang bobot [-1,1]. Hasil prediksi terbaik menggunakan MAPE dihasilkan pada data Bitcoin dengan nilai kesalahan terkecil yaitu 2.8590% Kata Kunci: Cryptocurrency; Investasi; Extreme Learning Machine ; Prediksi

Ginevra Giordani, Lorenzo Grassi, Silvia Onofri, Marco Pedicini

No abstract is available for this record.

Xiaohui Hu, Huiwen Jia, Jingang Liu, Zhi‐Qi Zhao

Identity-based cryptography (IBC) can be applied to scenarios that involve a large number of public keys in each execution. In this paper, we propose an efficient identity-based ring signature scheme on lattices with signature size logarithmic to the cardinality of the ring. To this end, we first construct an efficient identity-based ring identification scheme by combining preimage sampling algorithms and a zero-knowledge proof system for a tree-based accumulator. Then we apply the Fiat-Shamir transformation and obtain a secure identity-based ring signature scheme. We prove its security in the random oracle model under the small integer solution assumption.

Clémence Bouvier, Pierre Briaud, Pyrros Chaidos, Léo Perrin · 7 authors

No abstract is available for this record.

Tjerand Silde

No abstract is available for this record.

Carlos Aguilar-Melchor, Nicolas Gama, James Howe, Andreas Hülsing · 6 authors

No abstract is available for this record.

Andrea Basso, Giulio Codogni, Deirdre Connolly, Luca De Feo · 10 authors

No abstract is available for this record.

Lorenzo Grassi, Yonglin Hao, Christian Rechberger, Markus Schofnegger · 6 authors

No abstract is available for this record.

Amalan Joseph Antony, Kunwar P. Singh

Interactive zero-knowledge arguments for some fundamental linear algebraic operations have been formulated. Using those proofs for operations involving vectors or matrices requires certain reductions and additional communication rounds. In this paper, we explore the possibility of using various principles of discrete mathematics to formulate a method for a prover to securely prove to the verifier that he knows the sum of all the elements of a matrix, while both the sum and the original matrix remain unknown to the verifier.

Adda Akram Bendoukha, Oana Stan, Renaud Sirdey, Nicolas Quero · 5 authors

No abstract is available for this record.

Clémence Bouvier, Anne Canteaut, Léo Perrin

No abstract is available for this record.

Gizem Kara, Oğuz Yayla

A number of arithmetization-oriented ciphers emerge for use in advanced cryptographic protocols such as secure multi-party computation (MPC), fully homomorphic en-cryption (FHE) and zero-knowledge proofs (ZK) in recent years. The standard block ciphers like AES and the hash functions SHA2/SHA3 are proved to be efficient in software and hardware but not optimal to use in this field, for this reason, new kind of cryptographic primitives were proposed recently. However, unlike traditional ones, there is no standard approach to design and analyze such block ciphers and the hash functions, therefore their security analysis needs to be done carefully. In 2018, StarkWare launched a public STARK-Friendly Hash (SFH) Challenge to select an efficient and secure hash function to be used within ZK-STARKs, transparent and post-quantum secure proof systems. The block cipher JARVIS is one of the first ciphers designed for STARK applications but, shortly after its publication, the cipher has been shown vulnerable to Gröbner basis attack. This paper aims to describe a Gröbner basis attack on new block ciphers, MiMC, GMiMCerfand the variants of JARVIS. We present the complexity of Gröbner basis attack on JARVIS-like ciphers. Then we give results from our experiments for the attack on reduced-round MiMC and a structure we found in the Gröbner basis attack for GMiMCerf•

Thibauld Feneuil, Antoine Joux, Matthieu Rivain

No abstract is available for this record.