분류
2024년 2월
작성일
2023.10.13
수정일
2024.01.24
작성자
라라사티 하라스타 타티마
조회수
221

Design and Optimization of Quantum Arithmetic Circuits for Binary Elliptic Curve Discrete Logarithms

Title:

 

Design and Optimization of Quantum Arithmetic Circuits for Binary Elliptic Curve Discrete Logarithms

 


Summary:

Works on quantum cryptanalysis have increased significantly in the past decades, particularly after Shor's algorithm rose to prominence due to its potential applicability in breaking legacy public-key cryptosystems, namely Rivest-Shamir-Adleman (RSA) and Elliptic Curve Cryptography (ECC). However, the variant of the algorithm for cracking ECC has been less extensively investigated compared to its counterpart for RSA, despite the verdict that elliptic curve-based cryptosystems are likely to be crackable earlier due to their shorter key length. 

In this dissertation, we focus on exploring Shor's algorithm for solving elliptic curve discrete logarithms, the variant that forms the foundation of cracking ECC. Notably, we present the design, optimization, and resource analyses of quantum arithmetic circuits involved in the subroutines for binary elliptic curves. In detail, our contributions encompass three key aspects. Firstly, we presented a comprehensive literature review of Shor's algorithm for elliptic curve discrete logarithms, serving as an introduction to the topic before delving into our quantum arithmetic proposals. 

Secondly, we propose a depth-optimized variant of the quantum inversion circuit, modifying the existing Fermat Little Theorem (FLT)-based inversion by translating its Itoh-Tsujii's quantum algorithm version to suit a lower-depth design, which results in a smaller number of CNOT gates and a slightly reduced T depth, hence contributing to a reduced overall depth and gate count than previous work. We also propose employing Gidney's relative-phase Toffoli gate (i.e., GRT gate) for the decomposition of our circuit, achieving a significantly lower T depth while further reducing the overall depth. This approach complements the more prevalent width-optimized strategies commonly proposed in the existing literature. 

Thirdly, we present concrete designs of quantum point-doubling circuits, which, to the best of our knowledge, have never been found in the literature. In particular, we propose three different constructions to suit diverse design considerations: depth-optimized, ancilla-optimized, and balanced implementation, which show the need for one additional n-sized register compared to point addition for each round, along with their resource analyses in both Toffoli-level and T-level circuit decomposition. In addition, we also present the design of our integration between point doubling and point addition circuits, which can serve as a reference for obtaining a more complete resource estimation of Shor's algorithm for binary elliptic curve discrete logarithms.

Keywords Optimization, quantum circuit design, resource analysis, binary field inversion, elliptic curve point doubling, elliptic curve cryptography (ECC), Shor's algorithm


 

학위연월
2024년 2월
지도교수
김호원
키워드
Optimization, quantum circuit design, resource analysis, binary field inversion, elliptic curve point doubling, elliptic curve cryptography (ECC), Shor's algorithm
소개 웹페이지
https://sites.google.com/view/harashta/phd-summary
첨부파일
첨부파일이(가) 없습니다.
다음글
복잡도 다양성을 고려한 C 프로그램의 시험 용이성 예측 모형 구축 방법
최현재 2023-10-16 13:41:33.783
이전글
Improving 6TiSCH Network Formation and Transmission using Q-Learning
파와즈 자키 자키얄 2023-10-10 13:43:26.357
RSS 2.0 132
게시물 검색
박사학위논문
번호 제목 작성자 작성일 첨부파일 조회수
132 확산 모델 기반 필기 이미지 생성에 관한 연구 홍동진 2025.04.10 0 24
131 연합 학습 기반 전기차 충전 인프라 최적 운영 및 전력망 안정을 위한 유연성 자원 활용 연 류준우 2025.04.09 0 23
130 Design and Analysis of Quantum Circuits for Inform 와다니 리니 위스누 2025.04.08 0 39
129 Towards computation - communication efficient and 응우옌 민 두옹 2025.04.08 0 29
128 Quantum Convolutional Neural Networks for Classifi 노대일 2025.04.08 0 35
127 Service Management for Reliable Distributed 6G IoT 응우옌 쑤언 둥 2025.04.08 0 31
126 Large Language Model for Penetration Testing Domai 데리 프라타마 2025.04.07 0 39
125 Discovery and Authentication of Marker Genes Using 프라타마 리안 다니스 아디 2025.04.07 0 51
124 산업 환경의 IEEE 802.15.4 TSCH 기반 네트워크에서 트래픽 처리량 향상을 위한 이희준 2025.04.07 0 53
123 Uncertainty-Based Hybrid Deep Learning Approach fo 멘가라 악셀 기드온 2024.12.10 0 87
122 Effective Deep Learning Primitives Design for Bina 황선진 2024.10.14 0 94
121 Toward Immersive Multiview Video Streaming through 탄중 디온 2024.10.14 0 61
120 A Low-cost Deep Learning Model for Real-time Low L 등 제강 2024.10.10 0 99
119 Enhancing Nested Entity Recognition Using Nested R 양홍진 2024.10.09 0 84
118 다양한 도메인과 데이터 형식에 강건한 사전학습 언어모델 기반의 표 질의응답 방법 조상현 2024.10.09 0 83
117 Trust Guard Extension for Enhanced Security Featur 김해용 2024.05.04 0 109
116 Task-Specific Differential Private Data Publish Me 신진명 2024.04.09 0 132
115 Advanced Defense Framework against Physical Advers 김용수 2024.04.08 0 162
114 한글 메신저 채팅의 크로스 텍스팅 탐지를 위한 저자 검증 모형 이다영 2024.04.05 0 127
113 상태 기반 테스트 시나리오 보강 방법 이선열 2023.10.17 0 206