Modern cryptography relies heavily on the principles of algebraic structures to ensure the security and integrity of data. This paper explores the fundamental algebraic structures that underpin contemporary cryptographic systems, including groups, rings, fields, and lattices. We provide a detailed examination of how these structures are employed in various cryptographic algorithms and protocols, such as public-key cryptography, digital signatures, and hash functions. an overview of basic algebraic concepts and their properties, followed by an in-depth analysis of their applications in cryptographic schemes. For instance, the use of elliptic curve groups in Elliptic Curve Cryptography (ECC) offers enhanced security with smaller key sizes compared to traditional systems like RSA. Similarly, lattice-based cryptography presents promising solutions for post-quantum security, leveraging the hardness of lattice problems to resist attacks by quantum computers. the role of algebraic structures in the development of advanced cryptographic techniques, such as homomorphic encryption, which allows computations on encrypted data without decryption, and zero-knowledge proofs, which enable the verification of information without revealing the information itself. Through these examples, we illustrate the critical importance of algebraic structures in achieving robust and efficient cryptographic systems.
As cryptographic technologies evolve, the need for specialized hash functions to operate efficiently over different computational environments becomes necessary. Traditional symmetric algorithms like AES and SHA-3 have been optimized for traditional hardware and software implementations, which are designed over binary fields. However, protocols like zero-knowledge proofs require hash functions that are optimised over large prime fields. This thesis addresses the growing demand for Arithmetization-Oriented (AO) cryptographic hash functions for zero-knowledge applications. The performance and efficiency of many zero-knowledge applications often depends on the efficiency of the hash function used. In response to this need, this work explores a selection of these hash functions and implements them within two zero-knowledge proving systems: Dusk Network?s Plonk and Polygon?s Plonky2, with a focus on assessing the different performance tradeoffs that these hash functions offer within these sytems.
Xi Lin, Heyang Cao, Feng-Hao Liu, Zhedong Wang · 5 authors
Abstract Zero-knowledge succinct non-interactive arguments of knowledge (zk-SNARKs) are cryptographic protocols that offer efficient and privacy-preserving means of verifying NP language relations and have drawn considerable attention for their appealing applications, e.g., verifiable computation and anonymous payment protocol. Compared with the pre-quantum case, the practicability of this primitive in the post-quantum setting is still unsatisfactory, especially for the space complexity. To tackle this issue, this work seeks to enhance the efficiency and compactness of lattice-based zk-SNARKs, including proof length and common reference string (CRS) length. In this paper, we develop the framework of square span program-based SNARKs and design new zk-SNARKs over cyclotomic rings. Compared with previous works, our construction is without parallel repetition and achieves shorter proof and CRS lengths than previous lattice-based zk-SNARK schemes. Particularly, the proof length of our scheme is around $$23.3\%$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>23.3</mml:mn> <mml:mo>%</mml:mo> </mml:mrow> </mml:math> smaller than the recent shortest lattice-based zk-SNARKs by Ishai et al. (in: Proceedings of the 2021 ACM SIGSAC conference on computer and communications security, pp 212â234, 2021), and the CRS length is $$3.6\times$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>3.6</mml:mn> <mml:mo>Ă</mml:mo> </mml:mrow> </mml:math> smaller. Our constructions follow the framework of Gennaro et al. (in: Proceedings of the 2018 ACM SIGSAC conference on computer and communications security, pp 556â573, 2018), and adapt it to the ring setting by slightly modifying the knowledge assumptions. We develop concretely small constructions by using module-switching and key-switching procedures in a novel way.
Jonathan Ku, Junyao Zhang, Haoxuan Shan, Saichand Samudrala · 9 authors
Elliptic curve cryptography (ECC) is widely used in security applications such as public key cryptography (PKC) and zero-knowledge proofs (ZKP). ECC is composed of modular arithmetic, where modular multiplication takes most of the processing time. Computational complexity and memory constraints of ECC limit the performance. Therefore, hardware acceleration on ECC is an active field of research. Processing-in-memory (PIM) is a promising approach to tackle this problem. In this work, we design ModSRAM, the first 8T SRAM PIM architecture to compute large-number modular multiplication efficiently. In addition, we propose R4CSA-LUT, a new algorithm that reduces the cycles for an interleaved algorithm and eliminates carry propagation for addition based on look-up tables (LUT). ModSRAM is co-designed with R4CSA-LUT to support modular multiplication and data reuse in memory with 52% cycle reduction compared to prior works with only 32% area overhead.
As the practical applications of fully homomorphic encryption (FHE), secure multiâparty computation (MPC) and zeroâknowledge (ZK) proof continue to increase, so does the need to design and analyze new symmetricâkey primitives that can adapt to these privacyâpreserving protocols. These designs typically have low multiplicative complexity and depth with the parameter domain adapted to their application protocols, aiming to minimize the cost associated with the number of nonlinear operations or the multiplicative depth of their representation as circuits. In this paper, we propose two differential fault attacks against a oneâway function RAIN used for Rainier (CCS 2022), a signature scheme based on the MPCâinâtheâhead approach and an FHEâfriendly cipher HERA used for the RtF framework (Eurocrypt 2022), respectively. We show that our attacks can recover the keys for both ciphers by only injecting a fault into the internal state and requiring only one normal and one faulty ciphertext blocks. Thus, we can use only the practical complexity of 2 26.6 /2 28.8 /2 30.4 bit operations to break the fullâround RAIN with 128/192/256âbit keys. For fullâround HERA with 80/128âbit key, our attack is practical with complexity the complexity of 2 20 encryptions with about 2 16 memory.
The increased internet usage after the pandemic led the UN Forum to improve cybersecurity measures, with zero-knowledge proofs (ZKP) being a viable solution for securing confidential information. ZKP protocols can be demonstrated through the binary puzzle, an NP-complete logic puzzle with four specific constraints. The key contribution of this paper is its successful implementation of the genetic algorithm as a new method to solve the binary puzzle. The optimized fitness function determined the solution at an average of 1.33-2.33 generations for populations ranging from 100 to 500. Its quadratic property calculated the solution faster than the ordinary linear fitness function.
Lennart Braun, Guilhem Castagnos, Ivan DamgÄrd, Fabien Laguillaumie · 7 authors
We present distributed key generation and decryption protocols for an additively homomorphic cryptosystem based on class groups, improving on a similar system proposed by Braun, DamgĂ„rd, and Orlandi at CRYPTO â23. Our key generation is similarly constant round but achieves lower communication complexity than the previous work. This improvement is in part the result of relaxing the reconstruction property required of the underlying integer verifiable secret sharing scheme. This eliminates the reliance on potentially costly proofs of knowledge in unknown order groups. We present a new method to batch zero-knowledge proofs in unknown order groups which strengthens these improvements. We also present a protocol which is proven secure against adaptive adversaries in the single inconsistent player (SIP) model. Our protocols are secure in the universal composability (UC) framework and provide guaranteed output delivery. We demonstrate the relative efficiency of our techniques by presenting the running times and communication costs associated with our implementation of the statically secure protocol and provide a direct comparison with alternate state of the art constructions.
Motivated by progress in the field of zero-knowledge proofs, so-called Arithmetization-Oriented (AO) symmetric primitives have started to appear in the literature, such as MiMC, Poseidon or Rescue. Due to the design constraints implied by this setting, these algorithms are defined using simple operations over large (possibly prime) fields. In particular, many rely on simple low-degree monomials for their non-linear layers, essentially using x ⊠x3 as an S-box.In this paper, we show that the structure of the material injected in each round (be it subkeys in a block cipher or round constants in a public permutation) could allow a specific pattern, whereby a well-defined affine space is mapped to another by the round function, and then to another, etc. Such chains of one-dimensional subspaces always exist over 2 rounds, and they can be extended to an arbitrary number of rounds, for any linear layer, provided that the round-constants are well chosen.As a consequence, for several ciphers like Rescue, or a variant of AES with a monomial Sbox, there exist some round-key sequences for which the cipher has an abnormally high differential uniformity, exceeding the size of the Sbox alphabet.Well-known security arguments, in particular based on the wide-trail strategy, have been reused in the AO setting by many designers. Unfortunately, our results show that such a traditional study may not be sufficient to guarantee security. To illustrate this, we present two new primitives (the tweakable block cipher Snare and the permutation-based hash function Stir) that are built using state-of-the-art security arguments, but which are actually deeply flawed. Indeed, the key schedule of Snare ensures the presence of a subspace chain that significantly simplifies an algebraic attack against it, and the round constants of Stir force the presence of a subspace chain aligned with the rate and capacity of the permutation. This in turns implies the existence of many easy-to-find solutions to the so-called CICO problem.
Open access
Cryptographic Implementations and Security
Physical Unclonable Functions (PUFs) and Hardware Security
Fukang Liu, Mohammad Mahzoun, Morten Ăygarden, Willi Meier
Designing novel symmetric-key primitives for advanced protocols like secure multiparty computation (MPC), fully homomorphic encryption (FHE) and zero-knowledge proof systems (ZK), has been an important research topic in recent years. Many such existing primitives adopt quite different design strategies from conventional block ciphers. Notable features include that many of these ciphers are defined over a large finite field, and that a power map is commonly used to construct the nonlinear component due to its efficiency in these applications as well as its strong resistance against the differential and linear cryptanalysis. In this paper, we target the MPC-friendly ciphers AIM and RAIN used for the post-quantum signature schemes AIMer (CCS 2023 and NIST PQC Round 1 Additional Signatures) and Rainier (CCS 2022), respectively. Specifically, we can find equivalent representations of 2-round RAIN and full-round AIM, respectively, which make them vulnerable to either the polynomial method, or the crossbred algorithm, or the fast exhaustive search attack. Consequently, we can break 2-round RAIN with the 128/192/256-bit key in only 2111/2170/2225 bit operations. For full-round AIM with the 128/192/256-bit key, we could break them in 2136.2/2200.7/2265 bit operations, which are equivalent to about 2115/2178/2241 calls of the underlying primitives. In particular, our analysis indicates that AIM does not reach the required security levels by the NIST competition.
With the increasing interest for advanced protocols for Multi Party Computation, Fully-Homomorphic Encryption or Zero Knowledge proofs, a need for cryptographic algorithms with new constraints has emerged. These algorithms, called Arithmetization-Oriented ciphers, seek to minimize the number of field multiplications in large finite fields F2n or Fp. Among them, Ciminion is an encryption algorithm proposed by Dobraunig et al. in Eurocrypt 2021. In this paper, we show a new univariate modelization on a variant of Ciminion proposed by the designers. This instance restricts the attacker to at most 2 s/2 data, where s is the security level. Because the designers chose to reduce the number of rounds in that specific attacker model, we are able to attack the cipher for large security levels. We also propose some slight modifications of Ciminion that would overcome this vulnerability.
The rise of modern cryptographic protocols such as Zero-Knowledge proofs and secure Multi-party Computation has led to an increased demand for a new class of symmetric primitives. Unlike traditional platforms such as servers, microcontrollers, and desktop computers, these primitives are designed to be implemented in arithmetical circuits. In terms of security evaluation, arithmetization-oriented primitives are more complex compared to traditional symmetric cryptographic primitives. The arithmetization-oriented permutation Grendel employs the Legendre Symbol to increase the growth of algebraic degrees in its nonlinear layer. To analyze the security of Grendel thoroughly, it is crucial to investigate its resilience against algebraic attacks. This paper presents a preimage attack on the sponge hash function instantiated with the complete rounds of the Grendel permutation, employing algebraic methods. A technique is introduced that enables the elimination of two complete rounds of substitution permutation networks (SPN) in the sponge hash function without significant 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 employing this strategy, our attack achieves a gain of two additional rounds compared to the previous state-of-the-art attack. With no compromise to its security margin, this approach deepens our understanding of the design and analysis of such cryptographic primitives.
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.
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.
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.
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.
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.
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