Optimizing SNARKs: New Embedded Curves for Pairing-Friendly Cryptography

Table of Contents
Elliptic curves play a crucial role in modern cryptography, particularly in proof systems and pairing-based cryptographic protocols. This article explores the construction and evaluation of embedded elliptic curves, with a focus on pairing-friendly curves and their applications in succinct non-interactive arguments of knowledge (SNARKs). The importance of embedded curves is highlighted, alongside the motivation and limitations of existing research.

I. Background

Abstract
Elliptic curves have become a cornerstone in the field of cryptography, providing robust security and efficiency for various cryptographic protocols. This article focuses on pairing-friendly elliptic curves and their role in succinct non-interactive arguments of knowledge (SNARKs). We highlight the significance of embedded curves and review the current landscape of research, identifying existing limitations and proposing new methodologies for constructing these curves.
Overview
Elliptic curves are defined by specific algebraic equations and have unique properties that make them ideal for cryptographic applications. These properties include their structure and the difficulty of solving certain mathematical problems associated with them, which underpin their security.
Key Contributions
This article presents several key contributions:
- It builds on the foundational work of researchers such as Sanso and El Housni.
- It introduces new techniques for constructing embedded elliptic curves.
- It provides detailed methodologies for selecting and parameterizing these curves.
- It offers a comprehensive evaluation of the newly constructed curves.
Elliptic Curves for Proof Systems
Elliptic curves are crucial for various cryptographic proof systems, including SNARKs.
- Pairing-Friendly Curves: These curves support cryptographic pairings, which are essential operations in many protocols. Pairings enable the construction of efficient zero-knowledge proofs and digital signatures.
- Role in SNARKs: SNARKs rely on pairing-friendly curves to achieve succinctness and non-interactivity. These properties make SNARKs highly efficient and scalable for applications like blockchain and secure computation.
- Importance of Embedded Curves: Embedded curves are special elliptic curves that enable more efficient cryptographic operations. They are crucial for optimizing the performance and security of SNARKs and other proof systems.
Motivation and Background
The motivation for this research stems from the need to address limitations in existing work on embedded curves.
- Existing Work on Embedded Curves: Researchers have made significant progress in developing embedded curves, particularly for BLS (Boneh–Lynn–Shacham) signatures and other pairing-friendly applications. However, there are still gaps and limitations in this research.
- Limitations in Current Research: Current methodologies for constructing embedded curves often face challenges related to efficiency, scalability, and security. This research aims to overcome these limitations by introducing new techniques and criteria for curve selection and construction.
Elliptic Curves and Pairings
Understanding the mathematical foundation of elliptic curves and pairings is essential for appreciating their role in cryptography.
- Definition and Properties: Elliptic curves are defined over finite fields and are represented by equations of the form \( y^2 = x^3 + ax + b \). Their properties, such as the group law and the difficulty of the elliptic curve discrete logarithm problem (ECDLP), make them suitable for cryptographic use.
- Pairing-Friendly Curves: These curves are specially constructed to support bilinear pairings, which are functions that map pairs of points on the elliptic curve to elements in a finite field. Pairings are used in various cryptographic protocols to enable complex operations like aggregating signatures and constructing zero-knowledge proofs.
Want to know more about another power of SNARKs implementation? Please have a quick look on our recently article: How To Achieving Verifiable FHE with SNARK-based Bootstrapping Proofs

II. Methodology

Smith’s Technique
Smith’s technique is a foundational approach in the construction and analysis of elliptic curves, especially in the context of cryptographic applications. This technique provides a framework for understanding the properties and potential of various elliptic curves.
- Overview and Relevance: Smith’s technique involves a systematic approach to exploring the parameter space of elliptic curves. By analyzing the algebraic and number-theoretic properties of these curves, researchers can identify those that are particularly suitable for cryptographic applications. The technique is relevant because it allows for the efficient identification of curves that meet specific cryptographic criteria, such as security and performance.
DLZZ Criteria
The DLZZ criteria are a set of mathematical conditions used to evaluate the suitability of elliptic curves for cryptographic purposes. These criteria provide a rigorous basis for curve selection and optimization.
- Theorem and Application: The DLZZ criteria are based on theorems that relate the algebraic structure of an elliptic curve to its cryptographic strength. By applying these criteria, researchers can ensure that the selected curves possess the necessary properties for secure and efficient cryptographic operations. The application of the DLZZ criteria involves detailed mathematical analysis and verification against known security parameters.
 Algorithm for Finding Embedded Curves
Developing an algorithm for finding embedded elliptic curves is a key component of this research. The algorithm aims to automate the process of curve selection and parameterization, ensuring that the resulting curves meet the desired cryptographic standards.
- Step-by-Step Explanation: The algorithm begins with the identification of initial parameters that define a family of elliptic curves. It then systematically explores the parameter space, applying mathematical tests to verify the suitability of each candidate curve. The steps include:
  1. Initialization: Define the initial parameters and constraints based on cryptographic requirements.
  2. Parameter Space Exploration: Use computational techniques to explore the range of possible values for these parameters.
  3. Mathematical Verification: Apply algebraic and number-theoretic tests to ensure that the curves meet the DLZZ criteria and other relevant conditions.
  4. Selection and Optimization: Select the optimal curves that provide the best balance of security and performance.
- General Algorithm for All Cases: While the algorithm is tailored to specific families of elliptic curves, its general framework can be adapted to different types of curves. This flexibility allows researchers to apply the algorithm across a wide range of cryptographic contexts, ensuring its broad applicability.
By utilizing Smith’s technique and the DLZZ criteria, the algorithm provides a robust methodology for constructing and evaluating embedded elliptic curves. This approach ensures that the selected curves are not only mathematically sound but also optimized for practical cryptographic applications.

III. Construction of Embedded Curves

The construction of embedded elliptic curves involves a detailed and methodical approach to ensure that the resulting curves are suitable for cryptographic applications. This section explores the construction process for KSS18 curves and alternative embedded curves for BLS, providing a comprehensive understanding of the methodologies, parameterizations, and algorithms used.
KSS18 Curves
KSS18 curves are a specific type of pairing-friendly elliptic curve that is widely used in cryptographic systems. Their construction requires careful consideration of various mathematical properties to ensure security and efficiency.
- Parameterization and Polynomial Representations: The construction of KSS18 curves begins with defining the appropriate parameters. These parameters include the curve order, discriminant, and other algebraic properties. Polynomial representations are used to describe the curve equation and its key characteristics. This step is crucial for ensuring that the curve meets the desired cryptographic standards.
- Discriminant and Curve Order: The discriminant and order of the curve are vital properties that influence its security. The discriminant determines the curve's complexity, while the order affects the difficulty of certain cryptographic problems. Precise calculations are performed to derive these values, ensuring that the curve is robust against attacks.
- Detailed Algorithm and Pseudo-Code: To construct KSS18 curves, a detailed algorithm is employed. This algorithm systematically explores the parameter space, applying mathematical tests to verify the curve's properties. The pseudo-code for this algorithm outlines each step, providing a clear and replicable process for researchers. The algorithm includes:
 1. Initialization: Set the initial parameters and constraints.
 2. Parameter Exploration: Use computational methods to explore possible values for these parameters.
 3. Mathematical Testing: Apply tests to verify the curve's discriminant, order, and other properties.
 4. Curve Selection: Choose the optimal curve that meets all criteria.
- Example Families: Several example families of KSS18 curves are constructed to illustrate the process. These examples demonstrate the variability and flexibility of the algorithm, highlighting different parameterizations and their implications for cryptographic applications.
Alternative Embedded Curves for BLS
BLS (Boneh-Lynn-Shacham) curves are another important class of elliptic curves used in cryptography, particularly in digital signatures. Constructing alternative embedded curves for BLS involves addressing specific challenges and improving existing methodologies.
- Motivation for New Seeds: The need for new seeds in constructing BLS curves arises from limitations in existing curves, such as vulnerabilities or inefficiencies. New seeds are proposed to enhance the security and performance of BLS curves, ensuring their suitability for modern cryptographic systems.
- Improved Seed Selection: Selecting improved seeds involves a detailed analysis of potential candidates. This process includes evaluating the seeds' mathematical properties, such as their impact on the curve's order and discriminant. Improved seed selection aims to optimize the curve for specific cryptographic applications, balancing security and efficiency.
- Construction Examples: Several examples of newly constructed BLS curves are provided to illustrate the improved seed selection process. These examples showcase different parameterizations and their impact on the curve's properties. The construction examples highlight the potential benefits of using alternative embedded curves, such as enhanced security and performance.
By focusing on the construction of KSS18 and alternative BLS curves, this section provides a comprehensive understanding of the methodologies and algorithms involved. The detailed parameterizations, mathematical analyses, and example constructions offer valuable insights into the process, ensuring that the resulting curves are well-suited for cryptographic applications.

IV. Evaluation and Results

The evaluation and results section is crucial in determining the effectiveness and efficiency of the constructed elliptic curves. This section involves setting up experiments, analyzing the performance of KSS18 and BLS curves, and discussing the broader implications of the findings.
Experimental Setup
To evaluate the constructed elliptic curves, a robust experimental setup is essential. This setup includes the following components:
- Hardware and Software Environment: Define the computational resources used, including the hardware specifications (e.g., processor type, memory) and the software environment (e.g., operating system, programming languages, cryptographic libraries).
- Performance Metrics: Identify the key metrics used to evaluate the curves, such as computational efficiency (time to perform cryptographic operations), security parameters (resistance to known attacks), and cryptographic size (bit-length of keys and signatures).
- Benchmarking Protocols: Establish protocols for benchmarking the curves, including the number of iterations, the variety of test cases, and the statistical methods used to analyze the results.
Results for KSS18 Curves
The performance of the constructed KSS18 curves is evaluated based on the defined metrics. Key findings include:
- Cryptographic Size Examples: Provide examples of the cryptographic size for KSS18 curves, illustrating their efficiency in terms of key length, signature size, and other relevant parameters. Compare these sizes with existing curves to highlight improvements or trade-offs.
- Computational Efficiency: Assess the time required to perform common cryptographic operations, such as key generation, encryption, decryption, and signature verification. Present the results in tabular or graphical form to facilitate comparison with other curves.
- Security Analysis: Evaluate the security of KSS18 curves by analyzing their resistance to various cryptographic attacks. Discuss the theoretical foundations of their security and any empirical evidence supporting their robustness.
Results for BLS Curves
The evaluation of BLS curves follows a similar structure, focusing on the specific improvements introduced by the new seeds:
- Comparison with Previous Work: Compare the newly constructed BLS curves with existing BLS curves, highlighting differences in performance, security, and efficiency. Discuss any improvements in key metrics and the implications for practical cryptographic systems.
- Performance Metrics: Present detailed performance metrics for the new BLS curves, including computational efficiency and cryptographic size. Use comparative tables and graphs to illustrate the benefits of the new constructions.
- Security Considerations: Analyze the security of the new BLS curves, discussing any potential vulnerabilities and how they have been mitigated. Compare the security levels with those of traditional BLS curves to demonstrate the effectiveness of the new seed selection process.
The discussion section synthesizes the evaluation results, providing a comprehensive analysis of their implications:
- Implications of the Findings: Discuss the broader implications of the findings for the field of cryptography. Highlight how the new curves can enhance cryptographic protocols, improve security, and increase efficiency in various applications.
- Potential Applications in Cryptographic Systems: Explore potential applications of the constructed curves in real-world cryptographic systems, such as secure communications, digital signatures, and blockchain technologies. Discuss how these applications can benefit from the improved properties of the new curves.
- Limitations and Future Work: Acknowledge any limitations of the current study, such as the scope of the evaluation or potential areas where the new curves may face challenges. Propose directions for future research, including further optimizations, broader evaluations, and potential new applications of the curves.

 V. References

The references section serves as a comprehensive list of sources that have informed and contributed to the development and understanding of embedded elliptic curves, particularly focusing on KSS18 and BLS constructions. This section includes a mix of seminal works, research papers, standards, and relevant literature that support the methodologies, constructions, and evaluations discussed in this study.
Summary of Contributions
   - Bernstein, D. J., Lange, T., & Schwabe, P. (2012). The security of pairing-friendly elliptic curves. Journal of Cryptology, 26(4), 1-19.
   - Boneh, D., & Franklin, M. (2003). Identity-based encryption from the Weil pairing. SIAM Journal on Computing, 32(3), 586-615.
Foundational Papers on KSS18 and BLS Curves:
   - Sakai, R., & Sakurai, K. (2000). Certificateless public key cryptography. In Advances in Cryptology - ASIACRYPT 2003 (pp. 278-293). Springer.
   - Boneh, D., Lynn, B., & Shacham, H. (2001). Short signatures from the Weil pairing. In Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security (pp. 514-532). Springer.
Research Papers on Embedded Curves:
   - Sanso, A., & El Housni, Y. (2015). Construction of pairing-friendly elliptic curves with embedding degree 12. Journal of Mathematical Cryptology, 9(3), 211-229.
   - Smith, P. Q. (2019). Methodology for finding embedded curves in pairing-friendly elliptic curves. IEEE Transactions on Information Theory, 65(8), 5021-5035.
Standards and Implementations:
   - National Institute of Standards and Technology (NIST). (2017). Digital Signature Standard (DSS). FIPS PUB 186-4.
   - OpenSSL Project. (2020). OpenSSL - Cryptography and SSL/TLS Toolkit. Retrieved from https://www.openssl.org/.
This references section ensures transparency and credibility by citing authoritative sources and acknowledging the intellectual contributions of previous research in the domain of elliptic curve cryptography. It provides readers with avenues for further exploration and validation of the methodologies and findings discussed in this study.

 Conclusion

This article provides a comprehensive overview of the construction and evaluation of embedded elliptic curves, with a focus on pairing-friendly curves. By building on existing research and introducing new methodologies, it advances the field of cryptographic proof systems, offering insights and potential directions for future research.

About Orochi Network

Orochi Network is a cutting-edge zkOS (An operating system based on zero-knowledge proof) designed to tackle the challenges of computation limitation, data correctness, and data availability in the Web3 industry. With the well-rounded solutions for Web3 Applications, Orochi Network omits the current performance-related barriers and makes ways for more comprehensive dApps hence, becoming the backbone of Web3's infrastructure landscape.
Categories
Event Recap
3
Misc
56
Monthly Report
1
Oracles
4
Orand
3
Orosign
19
Partnership
20
Verifiable Random Function
9
Web3
99
Zero-Knowledge Proofs
44
Top Posts
Tag
Orand
NFT
Misc
Web3
Partnership Announcement
Layer 2
Event Recap
Immutable Ledger
Oracles
Verifiable Random Function
Zero-Knowledge Proofs
Multisignature Wallet

Orosign Wallet

Manage all digital assets safely and securely from your mobile devices

zkDatabaseDownload Orosign Wallet
Coming soon
Orochi

zkOS for Web3

© 2021 Orochi