보고서 정보
주관연구기관 |
서울대학교 Seoul National University |
보고서유형 | 최종보고서 |
발행국가 | 대한민국 |
언어 |
한국어
|
발행년월 | 2015-06 |
과제시작연도 |
2014 |
주관부처 |
미래창조과학부 Ministry of Science, ICT and Future Planning |
등록번호 |
TRKO201600009220 |
과제고유번호 |
1711010643 |
사업명 |
리더연구자지원 |
DB 구축일자 |
2016-10-01
|
키워드 |
페어링 역연산.이산대수.인수분해.변형 이산대수.페어링 암호.암호학적 난제.클라우드 컴퓨팅.공격 복잡도.계산 알고리즘.pairing inversion.discrete logarithm.integer factorization.variant DL.pairing cryptography.cryptographic hard problem.cloud computing.attack complexity.computational algorithm.
|
DOI |
https://doi.org/10.23000/TRKO201600009220 |
초록
▼
연구의 목적 및 내용
• 연구 목적
- 페어링 기반 변형 이산 대수 문제의 해결
- 이산대수 기반 암호의 안전성과 변형 이산대수 문제의 복잡도 및 상관관계 규명
- 부분정보를 이용한 인수분해 문제 해결
• 연구 내용
본 연구에서는 암호알고리즘에 기반하는 여러 가지 암호학적 난제를 분석하고 난제를 해결하는 알고리즘을 개발을 목표로 한다.
첫 번째는 소수체에서의 다변수 다항식 표현을 이용한 페어링 역연산 문제를 연구하고자 한다. Miller 함수를 다항식으로 표현하였듯이 페어링을 계산하는 다
연구의 목적 및 내용
• 연구 목적
- 페어링 기반 변형 이산 대수 문제의 해결
- 이산대수 기반 암호의 안전성과 변형 이산대수 문제의 복잡도 및 상관관계 규명
- 부분정보를 이용한 인수분해 문제 해결
• 연구 내용
본 연구에서는 암호알고리즘에 기반하는 여러 가지 암호학적 난제를 분석하고 난제를 해결하는 알고리즘을 개발을 목표로 한다.
첫 번째는 소수체에서의 다변수 다항식 표현을 이용한 페어링 역연산 문제를 연구하고자 한다. Miller 함수를 다항식으로 표현하였듯이 페어링을 계산하는 다변수 다항식을 찾아 이를 페어링 역연산 연구에 이용한다.
두 번째는 부분 정보가 주어진 경우 인수분해 문제의 안전성 분석에 관한 연구이다. 부채널 공격의 등장은 인수분해 문제의 안전성이 키 사이즈 제한, 소수의 일부 정보와 같은 비밀키에 관한 부분 정보가 주어진 상황에서 새롭게 검토되어야 함을 의미한다. 따라서 부분 정보를 이용한 인수분해 알고리즘을 개발하고 이를 통해 인수분해 기반 암호 시스템들의 안전성을 분석하고자 한다.
세 번째는 강한 이산대수 문제 해결 알고리즘의 일반화 및 적용에 대해 연구한다. 강한 이산대수 문제에 대한 공격 알고리즘에 대한 분석과 이를 바탕으로 프라이버시를 보장하는 등의 응용 암호 알고리즘 개발을 병행하려 한다.
연구결과
1. 페어링 연산에서의 마지막 지수승 단계 경량화
기존에 알려진 Miller 알고리즘을 개선하는 방법에 착안하여 마지막 지수승 계산량이 줄어드는 방안을 마련하였다. 페어링 연산에서 마지막 지수승을 계산하는 방법 중 최선의 방법으로 알려진 기존 방법을 분석해본 결과, 대부분의 페어링 친화 타원곡선의 족들에 대하여 제곱 계산량이 우리의 방법과 동일하게 나타나는데, 기존의 결과에서는 이러한 현상에 대한 이론적인 분석이 이루어지지 않았다. 하지만 본 연구진의 결과에 의하면 이러한 현상이 이론적으로 항상 가능한 것임을 보일 수 있다.
2. 부분정보를 이용한 인수분해
DL암호 시스템에서 비밀키의 에러치가 10% 일 때, 비밀키를 복구하는 계산량이 전수조사를 이용하면 271.58의 계산량이 들지만, 특정 알고리즘을 사용하면 243.24정도의 계산량으로 줄어들며, 더욱이, 단방향성의 에러를 가지면 236.38까지 줄어든다는 사실을 발견하였다. 이 연구결과를 RSA에도 적용시킬 수 있었으며 위와 유사한 결과를 얻을 수 있었다.
3. 변형 이산대수 연구
본 연구진은 랜덤 오라클에 의존하지 않고, 결정적 선형 가정에 기반한 라운드 최적화 blind signature 스킴을 제시하였다. 이는 기존결과에 비해 짧은 서명 크기를 가지며 안전성 분석에 대하여 보다 더 합리적인 결과를 얻어냈다.
연구결과의 활용계획
- 학문적, 과학기술적 측면: 계산수론 및 알고리즘 이론 연구 확대, 독자적 공개키 암호해독 기법 확보, 새로운 공개키 암호 원천 기술 선행 개발, 학제간 학문의 발전 유도
- 경제, 사회적 측면: 신뢰성 있는 다양한 IT 모델 및 비즈니스 활성화, 안전한 차세대 e-Government/Business 제공에 의한 사회 전반적 편리성 향상
- 국가적 측면: 암호 기초 분야의 전문 연구인력 양성, 사이버 방어력 강화, 차세대 암호기술 선행 확보에 따른 국가 경쟁력 및 위상 향상
Abstract
▼
Purpose&contents
• Purpose
- Solving variant of discrete logarithm problem based on pairing
- Investigation of complexity and correlation of security of cryptography based on discrete logarithm and variant of discrete logarithm problem
- Solving integer factorization using auxiliary info
Purpose&contents
• Purpose
- Solving variant of discrete logarithm problem based on pairing
- Investigation of complexity and correlation of security of cryptography based on discrete logarithm and variant of discrete logarithm problem
- Solving integer factorization using auxiliary information
• Contents
We will analyze various cryptographic hard problems and develop algorithms solving hard problems.
Firstly, we will research on pairing inversion problem using multi-variable polynomial representation on field with positive characteristic. We will find multi-variable polynomial represents pairing inversion like representation of Miller function by polynomial, and use it to investigate pairing inversion.
Secondly, we will research on security analysis of integer factorization using auxiliary information.
For the sake of advent of side-channel attack, we need to reexamine security of integer factorization under new circumstance in which auxiliary information such as key size restriction, partial information of prime number is given. So we will develop integer factorization algorithm using auxiliary information and through this, we will investigate security of cryptosystems based on integer factorization problem.
Lastly, we will research on generalization and application of the problem solving algorithm for strong discrete logarithm problem . We will investigate attack algorithm for strong discrete logarithm problem, and based on this, we will develop cryptographic algorithm for various application e.g. privacy protection.
Result
1. Weight lightening of final exponentiation step in pairing calculation
We developed method for reduce cost of final exponentiation step based on the known method used to improve Miller algorithm. We investigated the method used to calculate final exponential step which is known as the best, and found that cost of exponentiation in most families of pairing-friendly elliptic curve is same as our method, and that in the existing investigation, there is no theoretic analysis for the cost reduction. However, according to our result, the reduction is always possible.
2. Integer factorization using auxiliary information
If the error rate of secret key is 10% on DL cryptography,brutal force attack costs 271.58 operation. However, we established that if we use specific algorithm, the cost decreases to 243.24 and furthermore, if it has unidirectional error the cost decreases to 236.38. We could apply this result on RSA and obtained similar result.
3. Research on variant of discrete logarithm
We proposed round-optimal blind signature scheme based on deterministic linear assumption,without relying on random oracle. Our scheme has shorter signature size and obtained more reasonable result from security investigation.
Expected Contribution
- Academic, scientific contributions: promoting computational number theory and algorithmic theory, obtaining independent decryption technique, development of core technology for novel public key cryptography, promoting development of interdisciplinary study.
- Economic, social contribution: Construction of novel crypto-systems for cloud computing environment, invigorating trustful IT model and business model, enhancing society-wide facilities for next generation e-Government and e-buisiness
- National contribution: cultivating research manpower on fundamental field of cryptography,enforcement of cyber defense, enhancement of status and competitiveness by procuring next generation cryptography technology.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.