Fixed-Base Comb with Window-Non-Adjacent Form (NAF) Method for Scalar Multiplication

Hwajeong Seo, Hyunjin Kim, Taehwan Park, Yeoncheol Lee, Zhe Liu, Howon Kim

TL;DR

This paper introduces a novel fixed-base scalar multiplication method for elliptic curve cryptography (ECC) that significantly increases the frequency of zero occurrences in pre-computation tables. By combining this with existing methods, they achieve a "fine-tuned" approach that allows for flexible trade-offs between speed and memory usage, making ECC more efficient for resource-constrained devices.

What Problem Does This Paper Address?

Elliptic Curve Cryptography (ECC) is a popular choice for public-key cryptography due to its strong security with relatively short key sizes. However, a core operation in ECC, scalar multiplication (multiplying a secret scalar k by a point P on an elliptic curve), is computationally expensive. This is particularly challenging for embedded systems with limited processing power and memory. Researchers have developed various methods to speed up scalar multiplication, often by using pre-computation tables. These tables store intermediate results, reducing the number of expensive operations. However, existing methods often face a trade-off: larger tables can improve speed but consume more memory, while smaller tables save memory but are slower. This paper aims to address this by proposing a new pre-computation method that generates more "zero occurrences" in the table, which can lead to fewer additions and thus faster computation, while also offering a way to finely tune the table size and speed for specific applications.

Methods

The paper's core contribution is a new pre-computation method for fixed-base scalar multiplication that leverages the width-w Non-Adjacent Form (w-NAF) representation. The key innovation lies in identifying a characteristic of w-NAF that allows for the construction of pre-computation tables with a significantly higher ratio of zero occurrences compared to previous methods.

Here's a breakdown of the methods:

  • w-NAF Representation: This is a standard technique for representing scalars in ECC to reduce the number of non-zero digits, thereby reducing the number of additions.
  • Pre-computation Tables: The paper builds upon existing ideas of using look-up tables to store pre-computed points.
  • Proposed Zero Occurrence Characteristic: The authors identify a specific property of w-NAF that, when exploited, leads to tables with more zeros. This is achieved by carefully grouping elements in the look-up table based on their interrelationships within a window.
  • Hybrid Model: Recognizing that their proposed method might require large tables, the authors combine it with existing methods (specifically, Mohamed et al.'s approach) to create a "hybrid" model. This allows for a fine-tuned trade-off between table size and computational speed. Different versions of this hybrid model are presented, varying the combination and structure of the tables.
  • Size-Optimized Model: In addition to the speed-optimized model, they also propose a size-optimized version that prioritizes reducing memory footprint while maintaining a good balance of zero occurrences.

Datasets

Not discussed in the paper. The evaluation relies on random number generation for testing.

Key Insights and Ideas

  • The "Zero Occurrence" Advantage: The most significant insight is the discovery and exploitation of a characteristic in w-NAF that allows for the creation of pre-computation tables with a much higher frequency of zero entries. This is crucial because zero entries in the table directly translate to fewer addition operations during scalar multiplication.
  • Fine-Tuning for Embedded Systems: The paper emphasizes that a one-size-fits-all approach to ECC optimization isn't ideal for diverse embedded systems. Their hybrid and size-optimized models offer a flexible way to tailor the pre-computation table to specific memory and performance constraints.
  • Interrelationship of w-NAF Digits: The authors highlight that within a given window size in w-NAF, certain digits have a strong interrelationship. Understanding and grouping these related digits is key to achieving higher zero occurrence rates.
  • Trade-off Management: The paper effectively demonstrates how to manage the inherent trade-off between table size and computation speed. By combining different table structures and optimization strategies, they can achieve a more precise balance than previous methods.

Key Results

  • Increased Zero Occurrences: The proposed method demonstrates a significantly higher percentage of zero occurrences in pre-computation tables compared to existing methods, as shown in Table 5. For example, in the 4NAF case, their "SP" (speed-optimized) model achieves 53.33% zero occurrences, outperforming others.
  • Performance Enhancement: The paper claims a speed performance enhancement of 12.7% compared to traditional NAFw methods for unknown points (Appendix B).
  • Flexible Table Sizes: The hybrid model allows for a range of table sizes, from as small as 3.2 KB to larger sizes, offering users the ability to choose based on their needs. For instance, in Table 10, for 4NAF, their hybrid models (V3 and V4) achieve table sizes of 12.8 KB, while Mohamed et al.'s method (which is not explicitly detailed in this table but implied to be smaller) is compared.
  • Competitive Performance: While their speed-optimized model might have larger tables, it generally shows competitive or superior performance in terms of speed compared to other methods, especially when considering the number of operations.

Limitations and Future Work

  • Large Table Size for Speed Optimization: The speed-optimized version of their method can result in a large pre-computation table, which might still be a constraint for extremely memory-limited devices.
  • Hybrid Model Complexity: While the hybrid model offers fine-tuning, the management and selection of different combinations might add complexity.
  • Future Work: The paper suggests that this approach can be applied to other combinations of table structures for finely-tuned models, implying further exploration of hybrid strategies. They also highlight the applicability of their method to unknown points, which is a crucial aspect for practical ECC implementations.

Summary updated

Abstract

Elliptic curve cryptography (ECC) is one of the most promising public-key techniques in terms of short key size and various crypto protocols. For this reason, many studies on the implementation of ECC on resource-constrained devices within a practical execution time have been conducted. To this end, we must focus on scalar multiplication, which is the most expensive operation in ECC. A number of studies have proposed pre-computation and advanced scalar multiplication using a non-adjacent form (NAF) representation, and more sophisticated approaches have employed a width-w NAF representation and a modified pre-computation table. In this paper, we propose a new pre-computation method in which zero occurrences are much more frequent than in previous methods. This method can be applied to ordinary group scalar multiplication, but it requires large pre-computation table, so we combined the previous method with ours for practical purposes. This novel structure establishes a new feature that adjusts speed performance and table size finely, so we can customize the pre-computation table for our own purposes. Finally, we can establish a customized look-up table for embedded microprocessors.
BibTeX
@inproceedings{seo2013fixed,
  author = {Hwajeong Seo and Hyunjin Kim and Taehwan Park and Yeoncheol Lee and Zhe Liu and Howon Kim},
  title = {{Fixed-Base Comb with Window-Non-Adjacent Form (NAF) Method for Scalar Multiplication}},
  booktitle = {Sensors},
  year = {2013},
  url = {https://openreview.net/forum?id=9KbBD9JHlleu},
}
Figure