Public-Key Encryption and Functional Encryption from LWR

이주희 서울대학교 대학원 2019 국내박사

2016년 미국 National Institute of Standards and Technology (NIST)에 의해 양자내성 암호 표준화 공모가 시작된 이래로 RSA 암호, 타원곡선 암호 등을 대체할 수 있는 실용적인 양자내성 암호에 대한 필요성이 대두되어, 양자내성 암호 스킴의 효율적인 인스턴스화를 위해 다양한 기법들과 방법론들이 제안되어 왔다. 본 논문에서는 공개키 암호, 동형 암호, 함수 암호 설계를 위한 LWE 기반 설계 방식으로 가장 범용적으로 사용되는 Dual-Regev 방식의 암호화 과정에서 랜덤 가우시안 오류를 더하는 대신 하위 비트를 소거하는 식으로 오류를 주입함으로 서 LWR의 어려움에 기반하여 안전성을 확보하는 방식을 제안하였다. 또한, 해당 LWR 기반 Dual-Regev 암호화 방식을 사용하는 공개키 암호와 신원 기반 암호, 속성 기반 암호 스킴에 대한 안전성을 수학적으로 증명하였다. 마지막으로 LWR 문제에 대한 구체적인 공격 방법들을 연구하고 각 스킴들의 복호화 실패 확률을 분석하여 공개키 암호와 신원 기반 암호, 속성 기반 암호에 대해 LWR 기반의 Dual-Regev 암호화 방식을 사용하는 효율적인 인스턴스화를 제안하였다. Post-quantum cryptography has gained a growing attention from the cryptography community at this moment due to the recent development of quantum computer and standardization project launched by the National Institute of Standards and Technology (NIST) in the United States. The dual-Regev encryption based on the Learning with Errors (LWE) problem has been widely employed in many constructions for post-quantum cryptography such as public-key encryption, fully homomorphic encryption, functional encryption, etc. In this thesis, we propose an efficient post-quantum public-key encryption scheme with its variants and functional encryption schemes such as identity-based encryption and attribute-based encryption schemes based on Learning with Rounding (LWR) problem, all of which share the essence of the LWE-based dual-Regev encryption. Our approach accelerates encryption speeds by replacing the Gaussian sampling phase with efficient rounding process, and reduces the ciphertext sizes. To achieve these results, we investigate the concrete hardness of the LWR problem to assess the security of proposed schemes. We also analyze the respective conditions on which these schemes correctly work, and propose efficient instantiation with adequate quantum security.

Efficient Instantiation of LWE-based Public-Key Encryption and Commitment Schemes

김진수 서울대학교 대학원 2018 국내박사

The Learning with Errors (LWE) problem has been used as a underlying problem of a variety of cryptographic schemes. It makes possible constructing advanced solutions like fully homomorphic encryption, multi linear map as well as basic primitives like key-exchange, public-key encryption, signature. Recently, developments in quantum computing have triggered interest in constructing practical cryptographic schemes. In this thesis, we propose efficient post-quantum public-key encryption and commitment schemes based on a variant LWE, named as spLWE. We also suggest related zero-knowledge proofs and LWE-based threshold cryptosystems as an application of the proposed schemes. In order to achieve these results, it is essential investigating the hardness about the variant LWE problem, spLWE. We describe its theoretical, and concrete hardness from a careful analysis.

Tight security for cryptographic schemes in the multi-instance settings

이영경 Graduate School of Cybersecurity, Korea University 2021 국내박사

This thesis presents tight security results in independent cryptographic schemes public-key encryption (PKE) and identity-based signature (IBS). The security of PKE schemes in multi-user settings is aimed at capturing real-world scenarios in which an adversary could attack multiple users and multiple ciphertexts of its choice. However, the fact that a real-world adversary can also mount key-exposure attacks requires us to consider a more realistic notion of security in multi-user settings. An IBS scheme can be generically constructed from an ordinary signature scheme. But it was unclear that a generic construction leads to a tightly secure IBS scheme, no matter what tightly secure signature scheme be used as a building block. The summary of tight security results of this thesis is presented as follows: • This thesis defines the security notion of PKE in a multi-user setting with corruptions, where an adversary is able to issue corruption (i.e., private key) queries. Then, this thesis proposes the first practical and tightly secure PKE scheme in the multi-user setting with corruptions. • This thesis shows that the recent work by Seo, Abdalla, Lee, and Park (Information Sciences, July 2019) has a flaw in the security analysis of CCA conversion methods and presents revised security proofs. • This thesis demonstrates that the generic construction of IBS can achieve tightness if the underlying signature scheme is tightly secure in the multiuser setting with corruption. In addition, this thesis extends the tightness result of IBS to the multi-instance setting, where an adversary can corrupt multiple key generation centers and obtain related master secret keys.

Cryptographic Algorithms for Quantum Computations

한민기 서울대학교 대학원 2022 국내박사

The advent of a quantum mechanical computer presents a clear threat to existing cryptography. On the other hand, the quantum computer also suggests the possibility of a new cryptographic protocol through the properties of quantum mechanics. These two perspectives, respectively, gave rise to a new field called post-quantum cryptography as a countermeasure against quantum attacks and quantum cryptography as a new cryptographic technology using quantum mechanics, which are the subject of this thesis. In this thesis, we reconsider the security of the current post-quantum cryptography through a new quantum attack, model, and security proof. We present the fine-grained quantum security of hash functions as cryptographic primitives against preprocessing adversaries. We also bring recent quantum information theoretic research into cryptography, creating new quantum public key encryption and quantum commitment. Along the way, we resolve various open problems such as limitations of quantum algorithms with preprocessing computation, oracle separation problems in quantum complexity theory, and public key encryption using group action. 양자역학을 이용한 컴퓨터의 등장은 쇼어의 알고리즘 등을 통해 기존 암호학에 명백한 위협을 제시하며, 양자역학의 성질을 통한 새로운 암호프로토콜의 가능성 또한 제시한다. 이러한 두 가지 관점은 각각 이 학위 논문의 주제가 되는 양자공격에 대한 대응책으로써의 대양자암호와 양자역학을 이용한 암호기술인 양자암호라고 불리는 새로운 분야를 발생시켰다. 이 학위 논문에서는 현재 대양자암호의 안전성을 새로운 양자암호 공격 알고리즘과 모델, 안전성 증명을 통해 재고한다. 특히 암호학적 해쉬함수의 일방향함수, 암호학적 의사난수생성기로서의 대양자 암호 안전성의 구체적인 평가를 제시한다. 또한 최근 양자역학의 연구를 양자암호에 도입함으로써 새로운 양자 공개키암호와 양자 커밋먼트 등의 새로운 발견을 제시한다. 이 과정에서 전처리 계산을 포함한 양자알고리즘의 한계, 양자 복잡계들의 오라클분리 문제, 군의 작용을 이용한 공개키 암호 등의 여러 열린문제들의 해결을 제시한다.

등가조인을 지원하는 공개키 암호의 안전성 분석 및 개선

이우진 전북대학교 일반대학원 2020 국내석사

Recently, Wang and Pang proposed the PKDE (public key encryption for relational databases with controlled equijoin) scheme. Their scheme allows to perform equijoin operations on encrypted data in different relational databases and it was claimed to achieve the indistinguishability against adaptively chosen ciphertext attacks (IND-CCA2) before equijoin operations. In this thesis, we first analyze the security of the PKDE scheme by presenting an adaptively chosen ciphertext attack to the PKDE scheme before equijoin operations. More precisely, our attack algorithm performs as follows. When the adversary receives the challenge ciphertext from the challenger, the adversary makes a new ciphertext by modifying the challenge ciphertext in the IND-CCA2 security game. Then, the adversary requests a decryption query on that ciphertext to thechallenger. Once the adversary receives the answer from the challenger, the adversary can distinguish which value is encrypted by using that answer. The adversary always wins the IND-CCA2 security game and thus the PKDE scheme does not satisfy the IND-CCA2 security before equijoin operations. Next, we modify the PKDE scheme so that it achieves the IND-CCA2 security as well as provides the functionality that the original PKDE scheme offers. In addition, the modified scheme reduces the ciphertext generation time and ciphertext size by 12.5% and 20%, respectively. 최근 Wang과 Pang은 암호화된 Wang Pang 데이터베이스 상의 정보에 대해서 등가조인 연산을 지원하는 PKDE 암호를 제안했다. 그들은 PKDE 암호가 등가조인 연산 이전에 대해서 능동적 선택 암호문 공격에 대한 비구별성 (IND-CCA2)을 만족한다고 주장했다. 본 논문에서는 PKDE 암호의 등가조인 연산 이전에 대한 능동적 선택 암호문 공격을 제시한다. IND-CCA2 안전성 게임에서 공격자가 챌린저로부터 챌린지 암호문을 받았을 때, 공격자는 이 암호문의 일부를 변형하여 새로운 암호문을 만들고, 챌린저에게 새로운 암호문의 복호화를 요청한다. 공격자는 새로운 암호문의 복호화된 결과로 챌린지 암호문이 어떤 평문으로 암호화 되었는지를 구별할 수 있게 된다. 이 안전성 게임에서 항상 공격자가 승리하기 때문에 PKDE 암호는 등가조인 연산 이전에 대해서 IND-CCA2 안전성을 만족하지 못한다. PKDE 암호를 암호화된 데이터베이스 상의 정보에 대하여 등가조인을 할 수 있고, 등가조인 이전에 대해서 IND-CCA2 안전성을 만족시킬 수 있도록 개선한다. 개선된 암호는 기존의 암호에 비해서 암호문을 만들 때 필요한 암호문 계산 시간이 12.5%가 줄어들고, 암호문의 길이도 20%가 줄어든다.

Stronger Security for Practical Encryption Schemes

Zaheri Darkahi, Mohammad ProQuest Dissertations & Theses Georgetown Univers 2020 해외박사(DDOD)

인터넷 電子商去來 基盤技術의 特許法的 保護에 관한 硏究

강명균 延世大學校 法務大學院 2001 국내석사

(A) study on the advanced verifier-based Three Party Encrypted Key Exchange protocol

김현택 Graduate School, Yonsei University 2005 국내석사

Password-based authentication protocol begins Encrypted Key Exchange(EKE) proposed by Bellovin and Merritt in 1992. After this protocol, many password-based protocols are published. Three-party encrypted key exchange (3PEKE) protocol, such as STW-3PEKE, LSH-3PEKE and LSSH-3PEKE, is proposed. In the 3PEKE, all clients share a password with a trusted server only and server mediates between two communication parties to allow their mutual authentication. The password-based protocols is divided into plaintext-based protocol and verifier-based protocol. The verifier-based protocol is proposed to protect the user password stored in server.In this thesis, we propose the advanced verifier-based Three-Party Encrypted Key Exchange protocol that is the more secure than the most secure of the previous 3PEKE protocols. Then, we analyze the security and efficiency of the proposed protocol. 패스워드 기반 인증 프로토콜은 1992년 Bellovin과 Merritt에 의해서 제안된 Encrypted Key Exchange(EKE)를 그 시작으로 한다. 이후 많은 패스워드 기반 인증 프로토콜들이 제안되었다. EKE는 두 통신개체 사이에서 상호 검증 및 세션키 교환이 이루어진다. Three-Party 키 교환 프로토콜은 두 통신개체 외에 제3의 개체인 신뢰할 수 있는 서버를 두어 통신 개체간의 상호 인증 및 세션키 교환을 하는 방법이다. 이제까지 STW-3PEKE, LSH-3PEKE, LSSH-3PEKE 등이 제안되었다. 그러나 STW-3PEKE는 Undetectable Password Guessing Attack에 취약하고, LSH-3PEKE는 서버의 공개키를 사용하였으며, LSSH-3PEKE는 Known Key Attack에 취약한 것으로 알려져 있다. 유무선 통합망에서 사용하기 위하여 사용자 인증 및 키 교환 프로토콜은 무선 환경의 특수성을 고려하여야 한다.따라서 본 논문에서는 공개키를 기반으로 시스템에 부하를 많이 주는 메시지 단계를 줄였으나 기존의 3PEKE 프로토콜과 유사한 보안 성능을 가지는 향상된 Three-Party 키교환 프로토콜을 제안한다.

Fully Secure Ciphertext-Policy Attribute-Based Encryption Scheme Supporting Access Policy with Negated Attribute : 무효 속성의 접근 정책을 지원하는 안전한 CP-ABE(암호문 정책 속성 기반 암호화) 기술

Sadikin, Rifki 경북대학교 대학원 2014 국내박사

이 논문은 CP-ABE(Ciphertext-policy attribute-based encryption) 의 새로 운방식을제안하고있다.제안하는CP-ABE는큰속성우주와비단조부울함수 접근정책을 지원하며, 완전한 보안 정책 하에서 증명하였다. 완벽 보안 CP-ABE 는 선택적 보안 보다 강력한 보안 개념이다 지금까지는 완벽 보안 CP-ABE가 가 장 강력한 보안 정의였지만, 제안하는 CP-ABE는 공공 매개 변수 의 크기가 불변 의이기 때문에 큰 우주 건설 을 지원한다. 비 단조 부울 함수 접근 정책을 지원하 기 때문에, 제안하는 CP-ABE 방식은 사용자가 접근 정책으로서 conjunction과 threshold gate 중에서 negation gate를 선택할 수 있게 한다. 제안하는 CP-ABE 방식은 Lagrange interpolation을 이용한 접근정책으로 large universe construction과 비 단조 부울함수를 지원한다. 비 단조 부울 함 수의 접근정책을 지원하기 위해서, 3개의 논리 게이트를 지원하는 generalized secret sharing scheme 을 이용했다 negated attribute 를 표현하기 위하 여 negation gate 를 기반으로 하는라 그랑제 보간 다항식을 결합된AND, OR 그리고threshold combine 이 3개의 논리게이트 예이다. 우리가 제안하는 CP-ABE 방식이 완벽하게 안전하다는 것을 증명하기 위해 dual encryption technique을 사용했다. Dual encryption system 에서, 암호문이나 비밀키의 semifunctional version을 소개하였다. Semifunctional version은 일반적인 counterpart에서 적절하게 동작하도록 설계되었으며, semifunctional 암호문과 semifunctional 비밀키 사이에서의 복호는 제외한다. 우리가 증명한 것은 정상 적인인 indistinguishable game 이 final indistinguishable game 과 구분이 되 지 않을 때를 보여준다. 이 때 indistinguishable game 은challenge ciphertext 가 normal 이고 모든 secret key 가 normal secret key 인 방식이고, final indistinguishable game 은challenge ciphertext가 랜덤수의 semifunctional 이 고, 모든 secret key 가 semifunctional secret key 인 방식이다. 이 전의 방식과 비교 제안하는 CP-ABE 는 3가지 특징이 있다. Large attribute universe 를 지원하고, 비 단조 부울함수 접근 정책을 지원한다. 그 리고완벽하게 안전한방식이다. 더구나,선택된 bilinear group에서 측정하였을 때, 우리가 제안한 CP-ABE 방식은 attribute set 의 크기가 thousands 임에도 불구하고 4개의 알고리즘의 동작 시간 측면에서 unit of seconds가 걸렸다.

Energy-efficient secure routing protocol and WSN management framework in mobile ad hoc and sensor networks

최종오 Graduate School, Yonsei University 2007 국내박사

In recent years, wireless ad hoc and sensor networks have received increased attention in the research community. For the most part, this may be attributed to their highly appealing promise: mobile wireless networking autonomously without the need for an existing infrastructure.Due to its wireless, mobility attributes and capability to relay signal for peer to peer communication, Mobile ad hoc network has raised several challenging problems on routing protocol design, power consumption and topological self-organization. Such problem neither exists nor is a concern in traditional wired networks. Mobile Ad hoc network in its limited temporal and spatial extent, exhibiting asymmetric characteristics, imposes additional routing protocol design requirement.This dissertation proposes three contention resolution schemes in Mobile ad Hoc and sensor networks. : (1) An Efficient Scheme for Detecting Malicious Nodes in MANET and (2) The Residual Battery Capacity and Signal Strength Based on Power-Aware Routing Protocol in MANET and (3) WSNs Management Architecture using Policy-Based Network Management and Hierarchical Clustering Algorithm.First, this dissertation proposes a scheme capable of effectively detecting a malicious node that normally operates during determination of a route over MANET but modifies or drops data during data transmission or reports wrong information regarding a normal node, using a report message and a report table that list reporter nodes and suspect nodes. In the existing Schemes, a malicious node that provides wrong information can be easily identified but cannot be removed from a network. To solve this problem, the proposed scheme determines a suspect node as a malicious node when more than k lists of reporter nodes and suspect nodes are recorded in the report table in case where k malicious nodes are over the network. The proposed scheme is applicable to both Dynamic Source Routing(DSR) and Ad hoc On-Demand Distance Vector (AODV) routing. In particular, the proposed scheme is easy to be applied to and effective in the DSR that adopts source routing. Accordingly, this dissertation proves through a simulation that the AODV routing using the proposed scheme is superior to the existing AODV. In the simulation, the NS-2 simulator was used to compare them in terms of their average loss rates and transmission rates while varying the number of malicious nodes over the network and the mobility of malicious nodes. The simulation showed that as time goes by, the performance of the AODV routing protocol using the proposed scheme becomes far greater than that of the conventional AODV routing protocol.Second, This dissertation proposes the Residual Battery and Signal Strength Based Power-aware Routing Protocol in MANET(RBSSPR) that minimizes whole energy consumption through consideration of both residual battery capacity and signal strengths and also increases the lifetime of network through applying a threshold to a residual battery capacity.Finally, This dissertation proposes a self-management architecture for wireless sensor networks called SNMA(Sensor Network Management Architecture). In WSNs, a large number of sensor nodes are deployed over a large area and long distances and multi hop communication is required between nodes. So managing numerous wireless sensor nodes directly is very complex and is not efficient. The management of WSNs must be autonomic with a minimum of human interference, and robust to changes in network states. To do this, Proposed SNMA architecture is based on hierarchical management architecture and on the Policy Based Network Management(PBNM) paradigm. SNMA can reduce the costs of managing sensor nodes and of the communication among them using hierarchical clustering architecture. SNMA can also provide administrators with a solution to simplify and automate the management of WSNs using PBNM paradigm. 인터넷 및 무선이동 통신망은 급속한 성장에 반해 기반구조의 확충에 막대한 재원이 소요되고, 새로운 서비스 수용에 한계점을 보일 수밖에 없다. 이러한 변화의 공백을 채우기 위하여 이동성 및 네트워크 구성이 용이한 Mobile Ad Hoc Networks(MANET) 기술과 Sensor Network 기술이 주목받고 있다. 이러한 기술들은 모바일 환경에서 가장 소비자에 근접한 위치에서 이루어지며, 또한 4세대 이동통신 시스템에서 핵심적인 기술로 인정받고 있다. 본 논문에서는 MANET에서 2가지 측면에서 연구와 센서 네트워크에서 한 가지 측면에서 연구되었으며 세부 내용은 다음과 같다.첫째, 본 논문에서는 기존 MANET에서 연구는 모든 노드들이 정상적인 노드로 간주된 라우팅 프로토콜에 주목 되어 왔으나, 실제 MANET에서 각 노드들이 악의적인 노드들이 존재하고 있다는 것이다. 또한 기존에 제시되었던 악의적인 노드를 식별하는 방안들은 거짓 신고하는 악의적인 노드가 있을 때에는 이를 적절히 식별하고 제거하지 못하는 문제점이 있었다. 이러한 문제점들을 해결하기 위하여 본 논문에서는 MANET에서 신고자 목록(report list)과 혐의자 목록(suspect list) 으로 구성되는 신고 메시지와 신고 테이블을 이용하여 경로 설정단계(idle stage)에서는 정상적으로 동작하지만 데이터 전달(data forwarding) 과정에서는 데이터를 버리거나 내용을 변경시키는 행위, 또는 다른 노드를 거짓으로 신고하는 등의 악의적인 노드들을 식별하는 효율적인 방안을 제안한다. 이러한 제안된 방안은 네트워크 내에 k개의 악의적인 노드가 있다고 가정할 경우 신고 테이블에 신고자 및 혐의자 목록이 k개 이상 기록되면 비로소 악의적인 노드라고 식별하도록 함으로써 악의적인 노드의 거짓 신고에도 효율적으로 대응하도록 하였다. 제안하는 방안은 DSR과 AODV에 모두 적용 가능하며 소스 라우팅 방식인 DSR에서 더욱 쉽게 적용하고 효율적으로 사용할 수 있다. 따라서 이 논문에서는 NS-2 시뮬레이터를 이용하여 좀더 복잡한 AODV에서 악의적인 노드의 수, 이동성 등이 변화함에 따라 평균 분실률(loss rate) 및 전송량 비교를 통해 제안하는 방안이 순수 AODV 방식보다 훨씬 많은 성능 향상을 나타내고 있다는 것과 시간이 지날수록 더욱 많은 성능 차이가 난다는 것을 제시하였다.둘째, 본 논문에서는 배터리 잔량과 신호세기를 동시에 고려하여 네트워크 전체의 에너지 소모를 최소화 하고 배터리 잔량에 대한 임계치를 부여함으로써 각 이동 노드의 균형된 에너지 소모를 통해 네트워크 수명을 좀 더 오래 지속시키기 위한 프로토콜인 RBSSPR(Residual Battery and Signal Strength Based Power-aware Routing Protocol in Mobile Ad-hoc Network)을 제안한다.MANET 라우팅 프로토콜은 Table-Driven 방식, On-Demand 방식으로 분류할 수 있다. Table-Driven 방식에서 네트워크 내 각 노드들은 자신을 중심으로 도착 가능한 모든 노드들의 라우팅 정보를 라우팅 테이블에 항상 유지한다. 즉 하나 이상의 테이블에 네트워크 토폴로지에 대한 정보를 저장하고 갱신해야 하므로 노드들의 이동이 빈번히 발생할 경우, 다른 노드들의 라우팅 테이블 갱신을 위한 라우팅 정보가 브로드캐스트 되기 때문에 제어 패킷으로 인한 오버헤드가 크다. 반면에 On-Demand 방식은 송신자가 필요한 경우에만 경로를 설정하므로 제어 패킷 오버헤드를 감소시킬 수 있다. 그러나 이와 같은 프로토콜들은 거리를 나타내는 홉 수만을 메트릭으로 사용하기 때문에 End-to-End 사이의 거리는 가까울 수 있으나 비효율적인 에너지 소모에 의한 네트워크 수명 단축과 같은 단점을 가지고 있다. 이러한 단점을 보완하기 위해 MTPR, MCBR, BECT 등과 같은 파워를 고려한 프로토콜들이 제안되었다. 하지만 이와 같은 프로토콜들은 에너지 소모를 감소시키거나 또는 에너지 소모의 균형을 이루는 어느 한 측면만을 고려했다. 따라서 에너지 소모 측면만을 고려할 경우 전체 네트워크의 에너지 소모는 감소시킬 수 있었으나 네트워크에 존재하는 각 노드들의 균형적인 에너지 소모는 불가하였다. 다른 한편으로 균형적인 에너지 소모 측면만을 고려할 경우 네트워크에 참여하는 모든 노드들이 균형된 에너지 소모를 하나 전체 네트워크의 에너지 소모량은 크게 감소하지 않는 결과를 가져왔다. 따라서 이와 같은 단점을 보완할 새로운 프로토콜이 필요하다.마지막으로 이 논문은 기존 연구되어온 센서 네트워크 클러스터링 알고리즘(LEACH,LEACH-C)들은 관리적인 측면을 고려하지 않아서 관리적 측면을 고려한 새로운 알고리즘의 필요성과 매우 빈번한 클러스터링 과정을 통하여 클러스터링 재구성에 대한 센서노드들의 에너지와 통신비용이 증가하였다. 이러한 문제점을 해결하기위하여 SNMA(Sensor Network Management Architecture) 라 불리우는 무선센서 네트워크를 위한 self-management 구조를 제안한다. 또한 무선센서 네트워크에서, 많은 센서노드들은 많은 지역, 긴 거리, 노드들 간의 멀티 홉에 적용되고 있다. 그래서 수많은 센서 노드들의 직접적으로 관리하는 것이 매우 복잡하고, 비효율적이다. 이것을 해결하기 위해서 이 논문에서 제안하는 SNMA 구조는 계층적 관리구조와 Policy-Based Network Management(PBNM)에 기반하고 있다. SNMA는 센서노드들을 관리하고, 계층적인 클러스터링 구조를 이용하는 비용을 줄일 수 있다. 또한 PBNM을 이용하는 관리를 자동화하고 단순화하기 위한 솔루션을 가진 administrator 이다.