Geri Dön

Hardware implementation of the post-quantum cryptography algorithm falcon

Kuantum sonrası kriptografi algoritması falcon'un donanım gerçeklemesi

PDF İndir

  1. Tez No: 963455
  2. Yazar: YASİN YILMAZ
  3. Danışmanlar: PROF. DR. SIDDIKA BERNA ÖRS YALÇIN
  4. Tez Türü: Yüksek Lisans
  5. Konular: Elektrik ve Elektronik Mühendisliği, Electrical and Electronics Engineering
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2025
  8. Dil: İngilizce
  9. Üniversite: İstanbul Teknik Üniversitesi
  10. Enstitü: Lisansüstü Eğitim Enstitüsü
  11. Ana Bilim Dalı: Elektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Elektronik Mühendisliği Bilim Dalı
  13. Sayfa Sayısı: 87

Özet

Kuantum bilgisayarların ortaya çıkışı, klasik kriptografik sistemler için ciddi bir tehdit oluşturmaktadır. RSA ve ECC gibi yaygın açık anahtarlı şemaların dayandığı matematiksel problemlerin kuantum algoritmaları ile çözülebilmesi, bu sistemleri güvensiz hâle getirmektedir. Bu doğrultuda, NIST (National Institute of Standards and Technology), 2016 yılında kuantuma dayanıklı Kuantum Sonrası Kriptografi (PQC) algoritmalarının belirlenmesi ve standardizasyonu amacıyla uluslararası açık bir çağrı başlatmış ve çok aşamalı bir değerlendirme süreci yürütmüştür. Bu süreçte dijital imzalama yapısı olarak seçilen algoritmalardan biri olan FALCON (Fast-Fourier Lattice-based Compact Signatures over NTRU), kafes tabanlı bir dijital imza algoritmasıdır. Algoritmanın güvenliği, LWE (Learning With Errors) ve SIS (Short Integer Solution) gibi kafes problemlerinin zorluğuna dayanır. FALCON, Gentry-Peikert-Vaikuntanathan (GPV) çerçevesini temel almakta, yani kafeslerden kısa vektörler örnekleyerek imza üretimini gerçekleştirmektedir. Bu süreçte“trapdoor”adı verilen özel matematiksel yapılar kullanılmakta, böylece imza üretiminde etkinlik ve güvenlik birlikte sağlanmaktadır. FALCON'un verimliliğinin merkezinde Fast Fourier Sampling algoritması yer alır. Bu yöntem, Babai tarafından ortaya konan en yakın düzlem (nearest-plane) algoritmasının bir türevi olup, kafeslerdeki en yakın vektör problemini çözmeye yönelik tasarlanmıştır. Bu yöntem, klasik kafes tabanlı imza algoritmalarına kıyasla hem hız hem de imza boyutu açısından önemli avantajlar sunmaktadır. Bu çalışmada, FALCON algoritmasının ayrıntılı biçimde analiz edilip donanım hızlandırıcılarla optimize edilebilecek kısımların belirlenmesi ve ardından özel bir System-on-Chip (SoC) mimarisi içinde RISC-V işlemcisi ve DMA (Direct Memory Access) birimiyle birlikte gerçekleştirmektir. Böylelikle, hem imza üretimi hem de doğrulama süreçlerinde önemli performans kazanımları sağlanması hedeflenmektedir. İlk adım olarak FALCON'un yazarları tarafından yayınlanan referans C kodu incelenmiş, bir profilleme aracı kullanılarak alt fonksiyonların harcadıkları süreler ölçülmüş ve darboğazlar tespit edilmiştir. Bu analizler, algoritmanın işlem yapısını anlamaya, darboğazları belirlemeye ve donanım hızlandırmasına en uygun noktaları seçmeye imkan vermiştir. Elde edilen bulgular, özellikle kayan nokta işlemlerinin (floating-point operations) toplam sürenin büyük çoğunluğunu oluşturduğunu göstermiştir. FPGA üzerinde gerçeklenen RISC-V çekirdeği üzerinde uyarlanan C kodları çalıştırılmış ve belirli büyük alt fonksiyonların aldığı süreler ölçülüp temel oluşturmak üzere kaydedilmiştir. Bu sonuçlar, donanım hızlandırıcılarının sağlayacağı performans kazanımlarını kıyaslamak için temel bir karşılaştırma noktası oluşturmuştur. Analizler sonucunda, belirli alt fonksiyonların bütün halinde donanıma taşınmasına karar verilmiştir. Bu yaklaşımda, çok sayıda alt fonksiyonda tekrar kullanılabilecek temel işlem çekirdekleri tasarlamak yerine, belirli fonksiyonların doğrudan hızlandırıcı olarak gerçeklenmesi hedeflenmiştir. Böylelikle yazılım ve donanım arasındaki iletişimden doğan ek yük azaltılmıştır. Her ne kadar bu yöntem daha yüksek donanım kaynak tüketimine yol açsa da en yüksek hızın elde edilmesini mümkün kılmıştır. Profil sonuçları ve FPGA üzerinde yapılan temel ölçümler, hangi alt fonksiyonların donanım hızlandırıcıları olarak tasarlanacağını belirlemede kullanılmıştır. İmza üretimi tarafında FFT (Fast Fourier Transform) uzayındaki polinom işlemleri ve Fsat Foirer Sampling metodunu gerçeklendiği ffSampling fonksiyonu öne çıkarken, doğrulama tarafında en çok zaman alan işlem NTT (Number Theoretic Transform) ile gerçekleştirilen polinom çarpımı olmuştur. Bu fonksiyonlar için özel hızlandırıcı çekirdekler tasarlanması planlanmıştır. İmza üretiminde kullanılan polinom işlemleri FFT alanında gerçekleştiğinden elemanlar karmaşık sayılar olarak temsil edilmektedir ve yoğun biçimde kayan nokta hesaplamaları gerektirmektedir. Bu nedenle, çekirdeklerin ana işlem birinlerini oluşturmak için Xilinx tarafından sağlanan yapılandırılabilir floating-point IP çekirdekleri kullanılmıştır. Belirli işlemler için programlanmış IP çekirdekleri doğru şekillerde birleştirilerek her fonksiyon ve alt fonksiyonları için işlem birimleri oluşturulmuştur. Bu işlem birimleri kontrolcü, dahili bellekler ve FIFO'lar (First-in-First-Out) gibi kontrol komponentleri ile birleştirilerek hızlandırıcı çekirdekler tasarlanmıştır. Doğrulama tarafında ise NTT ve ters NTT çekirdekleri, FFT ve ters FFT'nin tam sayı modüler aritmetik uyarlamaları olarak tasarlanmıştır. Bu çekirdeklerde toplama, çıkarma ve çarpma işlemleri mod q uzayında gerçekleştirilmektedir, bu nedenle modüler indirgeme işlemleri de devreye eklenmiştir. Her bir çekirdek ayrı ayrı tasarlanmış, test vektörleriyle doğrulanmış ve maksimum saat frekansları ölçülmüştür. Çekirdekler ereken optimizasyonlar uygulanarak en yüksek performansı sağlayan hallerine getirilmiştir. Tüm çekirdekler hazırlandıktan sonra, tasarlanan hızlandırıcılar özel DMA birimi aracılığıyla RISC-V işlemciye bağlanmış ve blok RAM ile desteklenerek bir SoC mimarisi oluşturulmuştur. Yazılım tarafı C diliyle geliştirilmiş, hızlandırıcı çekirdeklerin doğru konfigürasyon ve giriş veri akışıyla beslenmesi için sürücü kodları yazılmıştır. Çekirdeklerden alınan sonuçlar yine sürücüler aracılığıyla bellek alanlarına yönlendirilmiştir. Tasarlanan sistem, Zynq-7000 FPGA üzerinde test edilmiş ve kaynak tüketimi, alan ve hız açısından değerlendirilmiştir. Elde edilen sistem referans RISC-V implementasyonuna kıyasla imza üretiminde yaklaşık 375 kat, doğrulama kısmında ise 70 kat hızlanma sağlamıştır. Literatürdeki benzer çalışmalarla kıyaslandığında da hız ve alan açısından kayda değer bir noktaya yerleşebilmektedir. Bu sonuçlar, önerilen tasarım metodolojisinin etkinliğini ve FALCON için güçlü bir çözüm sunduğunu ortaya koymaktadır. Mevcut tasarımın ilk sürümü, daha ileri optimizasyonlara imkan tanımaktadır. Özellikle bazı alt fonksiyonların paralelleştirilmesi, özel kayan nokta devrelerinin tasarlanması ve alan verimliliğinin artırılması gelecek çalışmalarda hedeflenmektedir. Böylelikle, hız, alan ve güç tüketimi arasında daha dengeli bir tasarım elde edilebilecektir. Çalışma sonucunda, PQC algoritmaları temellerini ve özellikle FALCON algoritması derinlemesine öğrenilmiştir. Çeşitli tasarım metodolojisi ve teknikleri incelenmiş ve uygulanmış, karşılaşılan problemlerin çözülmesiyle bu alanda da kazanımlar sağlanmıştır. Tasarlanan hızlandırıcı çekirdekler, algoritmanın performansını büyük ölçüde artırmıştır. Gelecekte yapılacak iyileştirmeler ile FALCON'un donanım tabanlı uygulanabilirliği daha da güçlenecek ve PQC standartlarının pratik uygulamaları için önemli katkılar sunacaktır.

Özet (Çeviri)

The emergence of quantum computing poses a significant threat to classical cryptographic systems, as it undermines the hardness assumptions on which widely used public-key schemes such as RSA and ECC are based. In response to this evolving threat landscape, the National Institute of Standards and Technology (NIST) launched a multi-year, open international process in 2016 to identify and standardize post-quantum cryptographic (PQC) algorithms that are secure against quantum adversaries. This initiative has involved extensive evaluation of submissions based on their security, efficiency, and suitability for practical deployment. Among the algorithms submitted and assessed throughout NIST's multi-round selection process, FALCON (Fast Fourier Lattice-based Compact Signatures over NTRU) emerged as one of the selected candidates for digital signature standardization. FALCON is a lattice-based digital signature scheme, and leverages several techniques and methods for efficient polynomial arithmetic, offering significant performance improvements over conventional lattice-based schemes. The novel Fast Fourier Sampling method, that is developed by the creators of FALCON, is a central component of this efficiency. This method is employed alongside various other algorithms, including the Fast Fourier Transform (FFT) and floating-point arithmetic, to compose the complete algorithm in three parts: key generation, signature generation and verification. This study aims to analyze FALCON in detail and identify key components for hardware acceleration. The goal is to design accelerator cores to enhance the speed of the major algorithmic parts, and to form a System-on-Chip (SoC) that includes the accelerator cores, a RISC-V processor, and a special Direct Memory Access (DMA) module, to improve the overall efficiency of the signature generation and verification processes. The initial phase involved a comprehensive analysis of the FALCON algorithm, utilizing reference documentation and the official C implementation. A C profiler was used to measure the execution time distribution across various sub-functions. This profiling revealed the computational structure of the algorithm, identified performance bottlenecks, and highlighted operations most suitable for acceleration. To enable hardware-software integration, the reference C code was modified for compatibility with a RISC-V environment. And to establish a baseline, compiled codes for the signature generation and verification of FALCON was employed on a actual FPGA implementation of a RISC-V core, VexRiscv, and the clock cycles required by each major sub-function were measured. Following this analysis, a design methodology was adopted that focuses on implementing selected components of the algorithm in their entirety. Rather than developing generalized cores for basic operations—intended for reuse across multiple sub-functions—this approach targets the direct hardware realization of specific, high-impact sub-functions as dedicated accelerator cores. This methodology significantly reduces the communication overhead between the software and hardware domains, which is often a bottleneck in hybrid implementations. Although this approach may incur higher resource consumption, it enables maximum performance by minimizing latency and maximizing data locality, thereby achieving the highest possible execution speed. Results from both profiling and baseline implementation were used in the selection process of the parts that will be realized on accelerator cores, following the explained design methodology. The design process began with a detailed examination of the selected functions. Following the functional analysis, a dedicated hardware circuit for the selected sub-functions was developed. In the signature generation process, the majority of operations involve floating-point arithmetic, as the polynomials being processed reside in the FFT domain, where their elements are represented as floating-point complex numbers. Consequently, the accelerator cores for signature generation were designed using configurable floating-point IP cores provided by Xilinx, complemented by data flow control components such as internal memory blocks and First-In First-Out (FIFO) buffers. On the other hand, the most time consuming part of the algorithm was determined to be polynomial multiplication for the verification part, where the Number Theoretic Transform (NTT) method is used in the reference implementation. Therefore, accelerator cores that carry out NTT and Inverse-NTT operations were constructed for improving the overall performance of the part. Each core was then individually implemented and verified using test vectors generated from the reference C code, covering both the signature generation and verification components. The maximum achievable clock frequency for each circuit was measured, and necessary optimizations and modifications were applied to obtain the highest-performing versions of the cores. With all of the components ready, the SoC was formed using the designed accelerators connected to the special DMA, together with the VexRiscv processor and a block RAM for data and instructions. The software responsible for managing the algorithmic flow and controlling the accelerator cores was developed in the C programming language. Core control is handled through dedicated driver code, which provides the accelerators with appropriate configuration parameters and input data sourced from memory via the DMA. Similarly, the drivers manage the transfer of computed outputs from the cores back to designated memory locations. The system then was implemented on a Zynq-7000 FPGA, after the designed accelerator cores were prepared as IPs to be used in a block design. Implemented system was evaluated for its execution time and resource usage. Performance was prioritized over other considerations initially. Nonetheless, the design serves as both a proof of concept and a viable FPGA-based implementation. The results demonstrate that the proposed implementation achieves an approximate 375× and 70× speed-up for the signature generation and verification, respectively, over the baseline RISC-V implementation. And compared to the related work, results from the system are remarkable, making the design methodology a viable solution for implementing FALCON. The current implementation represents a first iteration of the system design. Simulation and performance analysis have revealed opportunities for further optimization for a number of accelerators, including parallelization and the design of custom floating-point units to improve area efficiency. Future work will aim to refine the design to balance speed, area, and power consumption. This study not only provided a deep understanding of FALCON, particularly the signature generation and verification, but also highlighted the critical points for the both parts. The proposed hardware accelerators demonstrates a substantial improvement in execution speed. While this work prioritizes speed, future research may focus on achieving a more balanced trade-off between performance and hardware resource utilization.

Benzer Tezler

  1. Tez No

    864196

    Hardware design of K2RED modular multiplication algorithm used in number theoretic transform for post quantum cryptography and homomorphic encryption

    Post kuantum kriptografi ve homomorfik şifreleme için sayı teorik dönüşümünde kullanılan K2RED modüler çarpma algoritmasının donanım tasarımı

    FURKAN CAN

    Yüksek Lisans

    İngilizce

    İngilizce

    2024

    Bilim ve Teknolojiİstanbul Teknik Üniversitesi

    Elektronik ve Haberleşme Mühendisliği Ana Bilim Dalı

    PROF. DR. SIDDIKA BERNA ÖRS YALÇIN

  2. Tez No

    680357

    Efficient hardware implementations for lattice-based cryptography primitives

    Kafes-tabanlı kriptografi öğeleri için verimli donanım uygulamaları

    AHMET CAN MERT

    Doktora

    İngilizce

    İngilizce

    2021

    Elektrik ve Elektronik MühendisliğiSabancı Üniversitesi

    Elektronik Mühendisliği Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ ERDİNÇ ÖZTÜRK

  3. Tez No

    941590

    A novel key management framework for secure and scalable decentralized identity systems

    Güvenli ve ölçeklenebilir dağıtık kimlik sistemleri için yeni bir anahtar yönetim mimarisi

    MERT YILDIZ

    Yüksek Lisans

    İngilizce

    İngilizce

    2025

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. ŞERİF BAHTİYAR

  4. Tez No

    760471

    Accelerating lattice-based cryptosystems

    Lattice-tabanlı kripto-sistemler hızlandırıcısı

    KEMAL DERYA

    Yüksek Lisans

    İngilizce

    İngilizce

    2022

    Elektrik ve Elektronik MühendisliğiSabancı Üniversitesi

    Elektronik Mühendisliği Ana Bilim Dalı

    PROF. DR. ERKAY SAVAŞ

  5. Tez No

    352355

    İkinci nesil sayısal video yayını (DVB-S2) ileri hata kodlama birimi tasarımı ve gerçeklemesi

    Design and implementation of forward error correction unit for second generation digital video broadcasting (DVB-S2)

    ŞAKİR BALTA

    Yüksek Lisans

    Türkçe

    Türkçe

    2013

    Elektrik ve Elektronik Mühendisliğiİstanbul Teknik Üniversitesi

    Elektronik ve Haberleşme Mühendisliği Ana Bilim Dalı

    DOÇ. DR. MESUT KARTAL

Geri Dön