This article presents a comprehensive framework for implementing privacy-preserving credit card reward systems using Secure Multi-Party Computation (SMPC) technologies. Traditional reward architectures require extensive sharing of sensitive transaction data across multiple entities, creating significant privacy risks, security vulnerabilities, and regulatory compliance challenges. It leverages cryptographic advances to enable card issuers, payment networks, and merchant partners to collaborate on reward calculations,fraud detection, and personalized offers without revealing sensitive transaction details to one another. The article explores the evolution of privacy-preserving technologies in financial systems, comparing Fully Homomorphic Encryption, Zero-Knowledge Proofs, and SMPC approaches. A detailed case study of a travel rewards program implementation demonstrates how this framework ensures data remains protected throughout the entire process while maintaining the performance characteristics necessary for production deployment. The system provides comprehensive privacy protection, enhances fraud detection capabilities through secure collaboration, and facilitates compliance with evolving privacy regulations.Performance evaluations confirm the practical viability of the article, with minimal latency impact, strong scalability characteristics, and robust security guarantees. It contributes to the growing field of privacy-enhancing technologies for financial services and offers a viable solution to balance analytical utility with privacy protection in consumer-facing applications.
Elvira Albert, Samir Genaim, Daniel Kirchner, Enrique Martin-Martin
Program optimization is a key factor for green software. In the context of the Ethereum blockchain, optimization is particularly relevant because there is a fee to pay for each EVM (Ethereum Virtual Machine) instruction executed and also there exist bytecode-size limitations for deploying the software on the blockchain. Still, optimization of EVM code is not as widely spread as one could imagine. This is at least partly due to the lack of trust in the correctness of the tools, as security is even more relevant than efficiency in the blockchain context in which bugs may cause huge economical losses. This article develops a formal verification framework using Coq to ensure the security of EVM optimizations performed on jump-free sequences of EVM bytecode. By means of Coq’s theorem proving capabilities, we are able to automatically verify/certify that an optimized jump-free sequence of EVM opcodes is semantically equivalent to a given original one. We also present an extension to our framework that can handle inter-block optimizations that propagate global information across blocks. We have applied our tool to successfully prove the security of peephole optimizations performed by the standard Solidity compiler, and also to existing EVM superoptimization tools (namely GASOL and Superstack) in which we have found bugs that have been reported and fixed.
Recently, the practical applications of advanced cryptographic protocols, such as Multi-Party Computation (MPC), Fully Homomorphic Encryption (FHE), and Zero Knowledge Proofs (ZKP), have spurred the development of a series of new symmetric encryption primitives. These novel symmetric encryption primitives, referred to as Arithmetization-Oriented (AO) ciphers, aim to minimize the number of field multiplications in large finite fields, including 𝔽2n or 𝔽p. In order to evaluate the algebraic degrees of AO ciphers over 𝔽2n, the general monomial prediction technique was proposed by Cui et al. at ASIACRYPT 2022. However, when using their searching tool to evaluate the algebraic degrees of AO ciphers with complex affine layers, the efficiency is low, preventing solutions within a predetermined timeframe. In this study, we extend the propagation rules of monomials for field-based operations and present an automatic searching tool based on Mixed Integer Linear Programming (MILP) and Boolean Satisfiability (SAT) Problem for evaluating the upper bound of the algebraic degrees. Moreover, to accurately calculate the algebraic degrees of monomials in the SAT model, we improve the sequence encoding method, enabling it to accurately determine whether the monomials of degree d exist in the output. We apply our new searching tool to various AO ciphers, including Chaghri, MiMC, and Ciminion. For Chaghri, we compare our results with the Coefficient Grouping technique proposed by Liu et al. at EUROCRYPT 2023, and our results yield tighter upper bounds compared to Liu et al.’s findings. Additionally, we evaluate the algebraic degrees of Chaghri and MiMC with arbitrary complex affine layers and obtain tighter bounds compared to the results from Liu et al. at CRYPTO 2023. Regarding Ciminion, we have observed that starting from the 4-th round, the upper bound on the algebraic degrees for each round actually 1 degree lower than the previous bound. Our searching tool enables a more precise evaluation of the algebraic degrees of AO ciphers, contributing to a deeper understanding of the design and analysis of such primitives.
Classical symmetric cryptography interprets ciphers and hash functions as bit-based functions, that is, as functions between binary vector spaces. However, in the past decade, research and adoption of cryptographic protocols with advanced privacy-enhancing features, such as Fully Homomorphic Encryption, Multi-Party Computation and Zero-Knowledge proof systems, have accelerated. These privacy-enhancing protocols often have a novel feature: Their mathematical model is native over a prime field, whose characteristic p is significantly larger than 2. Applications of the aforementioned protocols often require a symmetric cipher for data encryption or a hash function for data compression. For efficiency reasons, two novel criteria must be satisfied: - A primitive should be native over a prime field, so it is modeled as function between vector spaces of characteristic p. - It should be possible to evaluate or represent a primitive with a low number of multiplications. Primitives satisfying these criteria are often summarized under the term Arithmetization-Oriented. To satisfy the second criterion, Arithmetization-Oriented primitives are often constructed by iterating relatively low-degree polynomials. However, this choice comes at a cost: Such primitive can also be modeled as a low-degree polynomial system for key or preimage recovery. Analyzing the complexity of polynomial system solving-based attacks poses a major problem in the design of Arithmetization-Oriented primitives. In practice, cryptodesigners often applied generic complexity bounds for cryptanalysis without proving the underlying assumptions. The aim of this manuscript is the development of tools for complexity estimations based on provable properties of a cryptographic polynomial system. We also apply our tools to the analysis of Arithmetization-Oriented Substitution-Permutation Network and Feistel ciphers. For early Arithmetization-Oriented primitives, our analysis reveals a large complexity gap between initial cryptanalysis and the capabilities of state-of-the-art polynomial system solving techniques.
At a time when post-quantum cryptography is more and more present in the cryptographic landscape, it is of great interest to find new hard problems on which we can rely. Here, we present a new problem, the vector space factorization problem, and use it to build a signature scheme. The idea of factorizing subspaces of a finite field is used in rank metric codes, most notably in the decoding of LRPCs. In this context, one of the subspaces is known to factorize. Factorizing without the knowledge of both subspaces appears in the signature scheme Murave, in which the rank support basis decomposition problem is introduced from a coding theory in rank metric point of view. In Bro's thesis, the SquareSpace problem is introduced, where one wants to find the 'square root' of a subspace. We generalize here this problem into the vector space factorization problem, which is the same as the rank support basis decomposition problem introduced in Murave, the difference being we do not look at it from a coding theory point of view, but really from a vector subspace one. We use it here to build a zero-knowledge proof of knowledge. The scheme uses the MPCitH paradigm, and especially the TCitH framework, which is an efficient way to build ZK proofs. We study the difficulty of solving the vector space factorization problem by detailing the combinatorial attacks on the problem, analyzing their complexity, and describing an algebraic model to solve the problem. We then explain the MPC protocol used to build the signature scheme. Finally, this construction allows us to obtain sizes of signature of 8.9 to 10.9 kB for the first security level defined by NIST, which is reasonable as MPC-in-the-Head signatures typically range from 2.5 kB for an MQ instance to 14 kB for lattice-based instances.
Zero-knowledge proof (ZKP) is an attractive cryptographic paradigm that allows a party to prove the correctness of a given statement without revealing any additional information. It offers both computation integrity and privacy, witnessing many celebrated deployments, such as computation outsourcing and cryptocurrencies. Recent general-purpose ZKP schemes, e.g., zero-knowledge succinct non-interactive argument of knowledge (zk-SNARK), suffer from time-consuming proof generation, which is mainly bottlenecked by the large-scale number theoretic transformation (NTT) and multi-scalar point multiplication (MSM). To boost its wide application, great interest has been shown in expediting the proof generation on various platforms like GPU, FPGA and ASIC.So far as we know, current works on the hardware designs for ZKP employ two separated data-paths for NTT and MSM, overlooking the potential of resource reusage. In this work, we particularly explore the feasibility and profit of implementing both NTT and MSM with a unified and high-performance hardware architecture. For the crucial operator design, we propose a dual-precision, load-balanced and fully-pipelined Montgomery multiplier (LBFP MM) by introducing the new mixed-radix technique and improving the prior quotient-decoupled strategy. Collectively, we also integrate orthogonal ideas to further enhance the performance of LBFP MM, including the customized constant multiplication, truncated LSB/MSB multiplication/addition and Karatsuba technique. On top of that, we present the unified, scalable and highperformance hardware architecture that conducts both NTT and MSM in a versatile pipelined execution mechanism, intensively sharing the common computation and memory resource. The proposed accelerator manages to overlap the on-chip memory computation with off-chip memory access, considerably reducing the overall cycle counts for NTT and MSM.We showcase the implementation of modular multiplier and overall architecture on the BLS12-381 elliptic curve for zk-SNARK. Extensive experiments are carried out under TSMC 28nm synthesis and similar simulation set, which demonstrate impressive improvements: (1) the proposed LBFP MM obtains 1.8x speed-up and 1.3x less area cost versus the state-of-the-art design; (2) the unified accelerator achieves 12.1x and 5.8x acceleration for NTT and MSM while also consumes 4.3x lower overall on-chip area overhead, when compared to the most related and advanced work PipeZK.
Abstract We propose a generic compiler that can convert any zero-knowledge (ZK) proof for SIMD circuits to general circuits efficiently, and an extension that can preserve the space complexity of the proof systems. Our compiler can immediately produce new results improving upon state of the art. By plugging in our compiler to Antman, an interactive sublinear-communication protocol, we improve the overall communication complexity for general circuits from $$\mathcal {O}(C^{3/4})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>C</mml:mi> <mml:mrow> <mml:mn>3</mml:mn> <mml:mo>/</mml:mo> <mml:mn>4</mml:mn> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> to $$\mathcal {O}(C^{1/2})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>C</mml:mi> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . Our implementation shows that for a circuit of size $$2^{27}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mn>2</mml:mn> <mml:mn>27</mml:mn> </mml:msup> </mml:math> , it achieves up to $$83.6\times $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>83.6</mml:mn> <mml:mo>×</mml:mo> </mml:mrow> </mml:math> improvement on communication compared to the state-of-the-art implementation. Its end-to-end running time is at least $$70\%$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>70</mml:mn> <mml:mo>%</mml:mo> </mml:mrow> </mml:math> faster in a 10Mbps network. Using the recent results on compressed $$\varSigma $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>Σ</mml:mi> </mml:math> -protocol theory, we obtain a discrete-log-based constant-round zero-knowledge argument with $$\mathcal {O}(C^{1/2})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>C</mml:mi> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> communication and common random string length, improving over the state of the art that has linear-size common random string and requires heavier computation. We improve the communication of a designated n -verifier zero-knowledge proof from $$\mathcal {O}(nC/B+n^2B^2)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mi>C</mml:mi> <mml:mo>/</mml:mo> <mml:mi>B</mml:mi> <mml:mo>+</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:msup> <mml:mi>B</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> to $$\mathcal {O}(nC/B+n^2)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mi>C</mml:mi> <mml:mo>/</mml:mo> <mml:mi>B</mml:mi> <mml:mo>+</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . To demonstrate the scalability of our compilers, we were able to extract a commit-and-prove SIMD ZK from Ligero and cast it in our framework. We also give one instantiation derived from LegoSNARK, demonstrating that the idea of CP-SNARK also fits in our methodology.
Public Key Encryption with Keyword Search (PEKS) is a widely adopted cryptographic scheme for retrieving encrypted data outsourced to cloud servers based on keywords. However, PEKS is susceptible to both offline and online Keyword Guessing Attacks (KGA). In this paper, We use Auxiliary Server to perform blind signing of user keywords to resist offline KGA and limit online KGA, then we introduce Password-Authenticated Encryption (PHE) as a means of authenticating users performing keyword searches. By leveraging passwords for identity verification and encryption key management, the keyword ciphertexts stored on the Storage Server undergo a secondary encryption process, ensuring that unauthorized users are unable to perform legitimate searches. Current password-based searchable encryption schemes are predominantly symmetric, often resulting in a more complex encryption workflow. Additionally, to address the computational overhead associated with exponentiation and zero-knowledge proofs in PHE-based schemes, we harness the capabilities of Intel SGX, a trusted execution environment. By offloading sensitive computational tasks related to password verification to SGX, we eliminate the need for costly exponentiation and zero-knowledge proofs, thereby enhancing the scheme's performance. This approach also achieves cross-period anonymity and addresses the issue of potential malicious auxiliary servers correlating user requests, as highlighted in Lai et al scheme. Consequently, the novel Server-aided Keyword Search with Password-hardened Encryption (SAKSPHE) we propose provides robust defense against offline KGA, restricts the feasibility of online KGA, and enables password-based user authentication alongside additional encryption of keyword ciphertexts for secure storage.
This paper investigates the use of threshold signature schemes in isogeny-based cryptosystems. By leveraging the distinct features of isogeny graphs, we propose a protocol that offers high security and practical efficiency, making it ideal for distributed ledger technologies and secure multi-party computations. Our scheme is resistant to quantum attacks and maintains minimal computational and communication overheads. We present an extensive analysis of the security and performance of our protocol, emphasizing its relevance to real-world cryptographic systems. MSC 2020: 94A60, 11G07, 68M07.
Current technological developments have digital money or cryptocurrency which is currently being used as an investment by the world community. here are views about cryptocurrencies, there is a profitable opportunity by involving cryptocurrencies into the economy and monetary system. The aim of this research is to form a cryptocurrency price dynamics model, analyze the stability of the equilibrium point and interpret the results of the model simulation. This type of research is basic or theoretical research. The method used is a descriptive method. This dynamic model takes the form of a system of differential equations consisting of five equations. In the analysis of the dynamic model, it was found that one equilibrium point was unstable because it did not meet the requirements. Based on the analysis of the simulation results that have been carried out, it shows that cryptocurrency prices deviate from fundamental values with the encouragement of liquidity prices resulting in cryptocurrency prices deviating from the equilibrium point
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.
Changxu Liu, Hao Zhou, Patrick Dai, Li Shang · 5 authors
Multi-Scalar Multiplication (MSM) is a computationally intensive task that operates on elliptic curves based on GF(P) . It is commonly used in zero-knowledge proof (ZKP), where it accounts for a significant portion of the computation time required for proof generation. In this article, we present PriorMSM, an efficient acceleration architecture for MSM. We propose a Priority-Based Scheduling Mechanism (PBSM) based on a multi-FIFO and multi-bank architecture to accelerate the implementation of MSM. By increasing the pairing success rate of internal points, PBSM reduces the number of bubbles in the pipeline of point addition (PADD), consequently improving the data throughput of the pipeline. We also introduce an advanced parallel bucket aggregation algorithm, leveraging PADD’s fully pipelined characteristics to significantly accelerate the implementation of bucket aggregation. We perform a sensitivity analysis on the crucial parameter of window size in MSM. The results indicate that the window size of the MSM significantly impacts its latency. Area-Time Product (ATP) metric is introduced to guide the selection of the optimal window size, balancing the performance and cost for practical applications of subsequent MSM implementations. PriorMSM is evaluated using the TSMC 28 nm process. It achieves a maximum speedup of 10.9× compared to the previous custom hardware implementations and a maximum speedup of 3.9× compared to the GPU implementations.
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.
Multi-Scalar Multiplication (MSM) is a fundamental cryptographic primitive, which plays a crucial role in Zero-knowledge proof systems. In this paper, we optimize the single MSM Process Element (PE) utilizing buckets with fewer conflicts, enhanced by Greedy-based scheduling, to achieve higher efficiency. The evaluation results show our optimized single MSM PE achieving a speedup of over two times on average, peaking at 3.63 times compared to previous works. Furthermore, we introduce Gypsophila, a scalable and bandwidth-optimized architecture for implementing multiple MSM PEs. Leveraging the characteristics of the bucket method, we optimize the data flow by balancing the throughput of bucket classification, bucket aggregation, and result aggregation in MSM. Simultaneously, multiple PEs with different data access patterns share a universal point input channel and post-processing unit, which improves the module utilization and mitigates the bandwidth pressure. Gypsophila with 16 PEs, accomplishes 16 MSM tasks in a mere 1.01% additional time, showcasing an approximate 7.8% reduction in area, with only about 116 of the bandwidth requirement, compared with 16 PEs without input channel and post-process unit sharing.
Hao Zhou, Changxu Liu, Lan Yang, Li Shang · 5 authors
Recently, there has been increased emphasis on privacy-preserving computation technologies, such as homomorphic encryption (HE) and zero-knowledge proof (ZKP). Modular multiplication is a critical component for both HE and ZKP. Variable bit-width is a must for many applications of privacy-preserving computation, due to variable bit-width requirements for different cryptography schemes. However, the majority of modular multipliers that support variable bit-width configurations exhibit relatively low throughput. This work presents a fully pipelined Montgomery modular multiplier with variable bit-width support. Truncated multipliers are introduced to reduce the resources of modular multipliers in our approach. In order to meet different bit-width requirements, the proposed modular multiplier can be dynamically reconfigured. The proposed design can support widely used bit-width configurations, specifically, 384-bit, 256-bit, and 128-bit. 256-bit and 128-bit modes support parallel computation of 2 and 6 sets of operands, respectively. Compared with existing variable bit-width modular multipliers, the proposed reconfigurable modular multiplier significantly improves the throughputs with even lower resources.