Efficent signature file methods for information retrieval

Yoo, Jae-soo Korea Advanced Institute of Science and Technology 1995 국내박사

Signature of surface bundles over surfaces and mapping class group

이주아 서울대학교 대학원 2017 국내박사

In this thesis, we study the topological constraints on the signature and the Euler characteristic (σ(X); e(X)) for smooth 4-manifolds X (or complex surfaces X) which are surface bundles over surfaces with nonzero signature. The first main result is about the improved upper bounds for the minimal base genus function b(f;n) for a fixed fiber genus f and a fixed signature 4n. In particular, we construct new smooth 4-manifolds with a fixed signature 4 and small Euler characteristic which are surface bundles over surfaces by subtraction of Lefschetz fibrations. They include an example with the smallest Euler characteristic among known examples with non-zero signature. Secondly, we explore possibilities to construct Kodaira fibrations with small signature which are smooth surface bundles over surfaces as ramified coverings of products of two complex curves. To obtain the minimal base genus and the smallest possible signature, we investigate the action of the monodromy of the fibration of pointed curves. Throughout the paper we’ll see that the surface mapping class group plays an important role in both constructions and the control of topological invariants.

Efficient Signature-Based Indexing Schemes for Query Processing in Object-Oriented Database Systems : 객체 지향 데이터베이스에서 질의 처리를 위한 효율적인 시그니쳐 기반의 색인 구조

신학진 전북대학교 대학원 1998 국내박사

객체 지향 데이터베이스 시스템에서 효율적인 질의 처리나 색인 방식의 구현은 객체 지향 데이터베이스 시스템의 성공을 위해서 중요한 문제이다. 특별히 복합 객체(composite objects)는 클래스간에 참조 관계를 가지며, 집단화 계층(aggregation hierarchy)를 형성하기 때문에 질의 처리 시 내포된 객체(nested objects)를 접근하기 위해 매우 큰 순행( traversal)비용을 요구한다. 이와 같은 순행 비용을 최소화하기 위해 다양한 연구가 진행 되었다. 근래에 들어서 소개된 경로 사전 구조는 참조 관계를 나타내는 S-표현(S-expression)을 이용하여 객체간의 순행 시간을 최소로 하고, 다양한 형태의 질의를 효과적으로 처리한다는 장점을 가지고 있다. 하지만 질의 처리 시 데이터베이스를 순차적으로 검색해야 하는 문제점과 경로 사전 역시 순차적 접근을 하는 문제가 있다. 위에서 지적한 복합 객체의 질의 처리 시 요구되는 순연 비용을 최소화하고, 이를 위해 사용하는 경로 사전의 문체를 극복하기 위해서 본 논문에서는 다음과 같이 시그니쳐를 기반한 효과적이고 새로운 색인 구조를 설계한다. 첫째, 경로 사전을 이용하면서 시그니쳐의 중첩(superimpose)방식을 이용한 시그니쳐 파일 기법을 설계한다. 이 시그니쳐를 S-시그니쳐라고 부른다. S-시그니쳐는 경로 사전에 있는 각각의 S-표현식 안에 있는 객체 식별자를 이용하여 객체를 검색한 뒤, 각 객체의 속성 값을 해시(Hash)함수에 대입하여 객체 시그니쳐를 생성한 뒤 이들을 중첩하여 S-시그니쳐를 생성한다. 이와 같은 S-시그니쳐는 경로 사전에 있는 S-표현식과 1:1로 연계하여 참조 공유가 빈번한 상황에서 효과적으로 검색을 수행하고, 특별히 복수개의 질의 조건(predicate)을 가지는 상황에서는 대단히 효과적이다. 둘째, 경로 사전을 이용하면서 시그니쳐의 합성(concatenation)기법을 이용하는 기법을 설계한다. 이 시그니쳐를 우리는 C-시그니쳐라고 부른다. C-시그니쳐에서는 시그니쳐를 이용하여 S-표현식을 필터한 후에도 객체 식별자의 정보를 잃지 않고, S-표현식 안에서 단일 목표 객체 식별자를 필터하는 기능을 가진 구조를 가진다. 이 구조는 임의의 속성에 주어지는 질의 조건을 이용하여 효과적으로 S-표현식을 필터할 수 있고, 필터 된 S-표현을 이용하여 최저의 비용으로 복합 객체 사이를 순행할 수 있도록 한다. 따라서, 복합 객체에 대한 임의의 질의 처리를 효과적으로 수행할 수 있는 접근 기법이며, 이는 복합 객체의 질의 처리에서 필수적인 기술이다. 이상에서 제안한 두 가지 기법과 기존의 관련된 연구들을 구현하여 성능 평가했다. 기존의 접근 기법으로는 경로 색인(path index), 경로 시그니쳐(path signature), 클래스 단위 시그니쳐(class unit signature), 경로 사전(path dictionary), 경로 사전 색인(path dictionary index)을 포함했다. 각각의 접근 기법은 200,000 객체를 포함하는 4개의 클래스와 100,000 객체를 포함하는 6개의 클래스를 가지는 데이터베이스를 대상으로 각각 8가지와 48 가지의 다른 종류의 질의를 주어 성능을 실험했다. 그 결과는 C-시그니쳐가 거의 모든 형태의 검색 질의에서 가장 우수한 성능을 보였다. 또한 여러 개의 질의 조건이 주어질 때, 집단화 계층에서 질의 조건의 위치가 검색 성능에 중요한 변수가 되는 것이 확인 되었고, 이는 질의의 최적화에 중요한 고려 사항이 되겠다. 경로 사전 색인은 질의 조건이 색인 키를 이용하여 진술된 경우에 우수한 검색 성능을 보이고 있다. 끝으로 논문은 이상의 결과 외에 실험 결과를 분석, 비교하여 복합 객체를 포함하는 객체 지향 데이터베이스를 위한 색인 기법의 선택 지침을 제시했다.

Topic Signature와 동시 출현 단어 쌍을 이용한 문서 범주화

배원식 창원대학교 2009 국내석사

We describe a new feature selection method for text categorization system using Topic Signature and co-occurrence words. Co-occurrence word is a pair of words to occur within a window in same documents. We use co-occurred words to classify documents instead of a single word, because we hypothesize that co-occurred words have high ability to classify documents for unique meaning. We use Topic Signature as a feature selection method based log-likelihood ratio. Topic Signature was applied for finding topic words in text summarization. In order to archive a high performance, we use TF-Topic Signature and weight of features to occur in within titles. And we use Naive Bayesian classifier for text classification. We use Reuters-21578 data collection, a standard data collection for evaluating English text categorization system, for evaluating proposed system. We can compare objectively between the proposed system and the previous systems from the data collection. For the result of experiments, we can see that the proposed system give a good performance, when compare the previous systems. The proposed system has some weak point that make many features by using co-occurrence word feature generation. Focus of our future works is to solve the weak points. But we give a good possibility with proposed method, so we expect that our research result is contributed to feature research. 본 논문에서는 Topic Signature와 동시 출현 단어 쌍 자질을 이용한 새로운 문서 범주화 방법에 대하여 기술한다. 동시 출현 단어 쌍은 한 문서에서 일정한 크기의 윈도우 내에 속하는 단어의 쌍으로 정의된다. 본 논문에서는 단어 하나보다 단어의 쌍이 문서의 범주를 판단하는데 더 좋은 자질로 사용될 수 있을 것이라고 가정하였다. 일반적으로 단어 하나는 여러 의미로 사용될 수 있으므로 여러 범주에서 나타날 가능성이 있다. 그러나 단어 쌍은 특별한 의미로 한정되어 특정한 범주에서만 나타날 가능성이 높아지기 때문이다. 자질 추출 방법으로는 Log-likelihood ratio를 기반으로 하는 Topic Signature를 사용한다. Topic Signature는 문서 요약 분야에서 문서의 핵심 단어를 찾기 위해 사용되었던 방법으로, 문서 범주화에서 사용하는 데는 몇 가지 약점을 가지고 있다. 본 논문에서는 이러한 약점을 보완하기 위하여 TF-Topic Signature와 제목에 나타난 자질에 대한 가중치를 부여하는 방법을 사용한다. 그리고 베이지언 분류기(Naive Bayesian Classifier)를 사용하여 문서를 분류한다. 본 논문의 성능 평가에는 Reuters-21578 문서 집합을 사용한다. Reuters-21578 문서 집합은 영어 문서 범주화 시스템 성능 평가의 표준 문서 집합으로 많은 기존 연구에 많이 사용되어 왔다. 따라서 제안 시스템과 기존 시스템을 객관적으로 비교할 수 있다. 실험을 통해 살펴본 결과 기존 시스템과 비교했을 때 좋은 성능을 보였다. 제안 시스템은 동시 출현 단어 쌍 자질을 사용하기 때문에 너무 많은 자질을 생성됨으로 인한 몇 가지 문제점을 안고 있다. 이들 문제점은 향후 연구를 통해 보완해야할 사항이다. 본 논문에서 제안한 방법들은 문서 범주화 시스템에서의 가능성을 충분히 보고 있으므로 앞으로의 연구에도 기여할 수 있을 것이라 기대한다.

Multiple point signature를 이용한 3차원 얼굴인식

이동주 연세대학교 대학원 2007 국내석사

In this dissertation, we propose a distinctive facial feature for a pose invariant 3D face recognition method using Multiple Point Signature. We acquire 3D face models using the different devices and input faces which include different poses. All data must be preprocessed and normalized using EC-SVD. We extract the invariant facial feature point using shape indexes and depth values from the range image. We propose a Multiple Point Signature method for measuring global facial surface information. A Multiple Point Signature represents several one-dimensional signatures. This method may not use error tolerance band to deal with noisy data and a registration technique to matching signatures. In addition, it is invariant to translation and rotation. Derivatives of facial surface are not required. Due to these characteristic, a Multiple Point Signature is fast and efficient to describe global information of facial surface. We use Euclidean distance matching for face recognition. We compared the proposed method with a single point signature method. From the experimental results, we have 94.6% recognition rate for the minimum distance matching, 85.4% by a single point signature. The proposed method shows 9.2% higher recognition rate than the single point signature. 본 논문은 3차원 얼굴 인식 방법에 관한 것으로, 3차원 얼굴 인식에 적합한 전역적 특징을 추출하는 Multiple Point Signature를 이용한 3차원 얼굴 인식 방법을 제안하였다. 3차원 얼굴 데이터의 경우 정규화를 통하여 데이터베이스와 같은 공간상에 놓이도록 하고, 얼굴 포즈 변화를 보정하기 위해 오류 보상 특이치 분해(EC-SVD)방식을 사용한다.3차원 레이저 스캐너로 획득된 3차원 얼굴 데이터는 얼굴의 구조적 정보를 이용하여 데이터 정규화 과정을 수행한다. 이렇게 정규화된 3차원 얼굴 데이터로부터 깊이 정보와 표면곡률지수(shape index)를 이용하여 얼굴의 구조적 정보를 알아내고, Multiple Point Signature를 적용시켜 얼굴의 전역적 특징을 나타내는 특징점 정보를 추출한다. 이 특징점 정보들을 3차원 얼굴 데이터베이스로 구성한다. 구조적 조명 방식의 얼굴 획득 장비에 의한 입력 영상의 경우도 동일한 방식으로 특징점을 추출하게 된다.Multiple Point Signature에 의해 추출된 얼굴의 전역적 특징을 나타내는 특징점들은 여러 개의 1차원 Signature로 표현된다. 여러 개의 Signature로 표현된 각 얼굴 데이터의 특징들을 RBFN의 학습을 거친 후 거리 매칭을 이용하여 얼굴 인식을 수행한다.최종적으로 100명의 데이터베이스에서 총 5가지 포즈 변화에 대한 실험을 통하여 제안한 알고리듬이 기존의 국소적 영역으로 제한되었던 방법의 단점을 극복하였고, 93.8%의 인식률을 나타내었다.

On-line signature verification using local temporal shift estimated by the phase of Gabor filter

이종현 Graduate School, Yonsei University 2002 국내박사

In this dissertation, an on-line signature verification method using temporal shift estimation is presented. Local temporal shifts existing in signatures are estimated by the differences of the phase outputs of Gabor filter applied on signature signals. In the proposed signature verification algorithm, an input signature signal undergoes preprocessing procedures including smoothing, size normalization and skew correction, and then it's feature profile is extracted from the signature signal. A Gabor filter with predetermined center frequency ω is applied on the feature profile, and a phase profile is extracted using the phase output. The feature profile and the phase profile are size normalized and quantized so that a signature code of fixed size is generated. The temporal shifts existing between two signatures are computed from the differences between the two phase profiles, which are divided by the center frequency ω. The information about the temporal shifts is used as offsets for comparing two feature profiles. Two kinds of dissimilarity measures are proposed. Temporal Dissimilarity is a measure reflecting the amount of total temporal disturbance between two signatures. And the difference between the two signature feature profiles are computed at each corresponding point pair and is accumulated into Temporally Arranged Feature Profile Dissimilarity. The decision boundary is represented as a straight line in the dissimilarity space whose two axes are the two dissimilarity measures. The slope and the position of the decision boundary are computed using the distribution of the dissimilarities among the sample signatures involved in the enrollment procedure. Through experiments conducted with 4 kinds of center frequencies of Gabor filter and various feature profiles, the performances and the applicability of the proposed signature verification algorithm are validated. The proposed algorithm shows equal error rates about 3% lower than the conventional approaches. When multiple prototype signatures were selected from 12 training samples, the minimum equal error rate was found to be 2.2%. The proposed algorithm could compare 6563 pairs of signatures and generate 540 signature pairs. And the necessary data size was 512 Bytes long.

SigBox: Automatic Signature Generation Method for Fine-grained Traffic Identification

Yoon, Sung Ho 고려대학교 대학원 2015 국내박사

With the continual appearance of new applications and the frequent update of these applications, the need for automatic signature generation is emphasized. Although several automatic methods have been proposed, there are still limitations to adopt real network environment in terms of automation, robustness, and sophistication. To address this issue, we propose an automatic signature generation method, called SigBox, for fine-grained traffic identification. This system extracts three types of signature such as content, packet, and flow signature using a modified sequence pattern algorithm. The flow signature, final result of this system, consists of a series of packet signatures, and the packet signature consists of a series of content signatures. The content signature means distinguishable and unique substring of packet payload, and consists of a series of characters or hex values. Using the modified sequence pattern algorithm, we can improve system performance in aspect of automation and robustness. Also, the proposed method can generate sophisticated signature for fine-grained traffic identification by using flow-level features beyond ones of packet-level. In order to prove the feasibility of our proposed system, we present experimental results based on ten popular applications after defining three metrics such as redundancy, coverage, and accuracy. Also, we show the quality of signature compared to existing methods.

(A) study on preferences for the attributes of digital signature certificate : choice experiment analysis

강환철 Graduate School, Yonsei University 2023 국내박사

With the enactment of the Digital Signature Act in 1999, accredited certificate were introduced. Accredited certificate serve as a way to identify individuals online and verify their legitimacy as users. This certificate is legally supported under the Electronic Signature Act and have established itself as a reliable authentication method in electronic transactions since the 2000s. It has experienced explosive growth in tandem with the rise of electronic transactions. However, various inconveniences were continuously raised, including the need for program installation, the complexity of the registration process due to annual renewal, and the use of complex passwords. In response to these concerns, the government took action by completely revising the Digital Signature Act in 2020. The revised act aimed to diversify the types of certificates available in the market and eliminate the monopoly of the accredited - ix - certificate. As a result, the accredited certificate system was abolished. As of March 2023, following the abolition of the accredited certificate system, a total of 21 digital signature certification providers emerged in the market, releasing a significant number of certificates. With the introduction of numerous certificates into the market, the government successfully achieved its objective of offering diverse authentication methods to users. There are market questions regarding the fate of existing accredited certificate in the current era of certificate evolution. There is speculation about whether a specific platform company will monopolize the market based on predictions and trends. There is a question in which the market is curious about what is good for a healthy certificate market structure. The best way to address these market questions is to identify consumer choice attributes. This is because consumer choice attributes will be helpful for identifying the market, establishing corporate strategies, and serving as a foundation for government policies. Therefore, in this study, what certificate choice attributes are important to consumers in a time of certificate upheaval. The choice attributes were identified, the relative importance among the choice attributes and the utility value for the level within each attribute were estimated. Identified certificate choice attributes were issuer reliability, program installation, authentication method, and where to use(scope of usage). As a relative importance among the selected attributes, the place of use was the most important, followed by program installation, issuer reliability, and authentication method in order of importance. When forecasting the current certificate market with estimated relative importance, accredited certificate - x - (35.7%), financial certificate (34.9%), and platform company certificate (29.4%) appeared in the order. When forecasting the future certificate market, it was followed by financial certificate (38.3%), platform company certificate (32.2%), and accredited certificate (29.4%). Consumers preferred reliability over convenience in issuer reliability, and bio preference was high value in their 30s. Based on this, we would like to propose policies and market strategies. Policy proposals should separate the current single certificate policy into trusted and convenient certificate. As a proposal for the market, digital signature authentication service providers recommend introducing non-aware facial authentication to increase market share. In details, first of all, the existing preceding papers were investigated to identify the consumer's certificate choice attributes. These papers summarized the factors involved in selecting certificate, which include convenience, security, usefulness, and usage habit. Convenience, as a detailed factor, was investigated by considering program installation, validity period, and ease of use. Security was assessed in terms of the security measures employed during issuance and the location of certificate storage. Usefulness was evaluated by examining where the certificate can be used and their overall usability. Lastly, researchers investigated consumers' usage habits. It was possible to identify the attributes influencing consumers' certificate choices attributes with previouse paper. However, as the limitations of previous papers, determining the relative importance of these attributes was not feasible. Furthermore, most of the previous papers were conducted before the abolition of the accredited certificate, which means they may not fully reflect the market's diversity - xi - following the abolition. To refine the choice attributes identified from the previous papers, a two-round expert Delphi survey was conducted. In the first round, the participants were asked to provide input on any necessary additions, changes, or deletions to the choice attributes. Additionally, the participants rated the importance level of each choice attribute. Based on the findings of the Delphi survey, it was determined that organizing the major categories into "issuance" and "use," representing the life cycle of certificate, would enhance consumer understanding. This reorganization was preferred over the previous categorization of convenience, security, and usefulness. Based on the findings of the first survey, a second expert survey was conducted to finalize the selection of choice attributes. In the second investigation, it was revealed that the majority of certificates have a validity period of 3 years, thereby eliminating any discrimination based on duration. Additionally, the storage location of certificate emerged as a factor that consumers find challenging to recognize or evaluate. Based on these findings, it was recommended to exclude the validity period and storage location as choice attributes. These factors were deemed less relevant to consumer decision-making. Additionally, there was a suggestion to incorporate identity verification level in security at issue time and usage habits as a component of issuer reliability, recognizing the importance of considering consumers' habits in assessing the trustworthiness of certificate issuers. When summarizing the results of the secondary investigation, the selected choice attributes are organized into two categories: the issuer - xii - reliability and program installation in relation to issuance, and the authentication method and where to use in relation to use. The level of issuer reliability is further divided into existing accredited certificate, financial institution, and platform company. The level of program installation was divided into three categories: security program installation, app installation, and no installation. The level of authentication method was categorized into password, PIN/pattern, and bio. As for the level of where to use, it is classified as follows: most uses, e-Government + part of financial institution (including some insurance companies and credit card companies) + part of private institution, and limited to e-Government. An experiment plan was developed using an orthogonal arrangement and PBIBD (Partial Balanced Incomplete Block Design) with the selected four certificate choice attributes, each having three levels. Initially, nine certificate profiles were created using an orthogonal array test. The choice attributes and levels were evenly distributed among the nine certificate profiles through the orthogonal arrangement. To facilitate the experiment with these nine certificate profiles, a set of questions was constructed using PBIBD methodology. To ensure consistency and avoid duplication in the question set, PBIBD was utilized. This construction method ensured that pairs of two certificate profiles were not repeated within the question set and were distributed at least once. The results of the PBIBD analysis indicated that the question set consisted of nine unique questions, with each question containing three certificates. Subsequently, a consumer preference survey was conducted utilizing the nine questions generated from the experimental plan. - xiii - The consumer preference survey was carried out in two stages: a preliminary survey involving 30 participants and a main survey involving 330 participants. The analysis was performed using a conjoint method, incorporating the results from the main investigation. Based on the analysis, the attribute where to use received the highest preference score at 57.7%. It was followed by program installation at 29.8%, issuer reliability at 6.8%, and lastly, authentication method at 5.7%. Firstly, In terms of the reliability of the issuer, the platform company showed a score of -0.17 when compared to the existing accredited certificate, suggesting a preference for the existing accredited certificate in terms of reliability. When considering program installation, app installation received a score of -0.49 when compared to security program installation, indicating a lower preference for app installation. On the other hand, no installation received a score of 0.26, indicating a higher preference for not requiring any installation compared to both security program installation and app installation. In the authentication method, the preference was given to the existing password input instead of using biometric information. However, users in their 30s, who are more open to adopting new technologies, showed a strong preference for biometrics. In terms of application areas, when compared to the sole use of e-government, most scenarios exhibited a preference rating of 1.45. Furthermore, a combination of e-government, select financial institutions (such as certain credit card companies and insurance companies), and specific private institutions displayed a preference rating of 1.17. - xiv - Based on the study's findings, the market was predicted by considering the relative importance of different attributes associated with the certificate and the part-worth of each attribute level. By selecting three representative certificate products available in the market and assigning the same level as current market conditions, the following order was observed in terms of market presence: the existing accredited certificate (35.7%), financial institution certificate (34.9%), and platform company certificate (29.4%). This forecast aligns closely with the actual usage of certificate by the National Tax Service, supporting the accuracy of the results. Additionally, the study found that to increase market share, digital signature authentication service providers should focus on factor: expanding the usage areas. The results indicated that broadening the place of usage could lead to significant market share growth. For instance, the market share of financial institution certificate could potentially increase from 34.9% to 38.3%, while platform certificate could see an increase from 29.4% to 32.2%. However, this is a forecast of the entire population, and it is forecast that financial certificate and platform company certificate will be highly used by young people in the future, and when forecasting only those in their 30s, the market share of financial certificate and platform company certificate was high occupied (financial institution certificate: 46.6%, platform company certificate: 46.6%, accredited certificate: 6.7%). Therefore, in the short term (2-3 years), it is analyzed that it will be very difficult for the platform company's certificate to dominate the market as predicted at the time of the abolition of the accredited certificate, but in the long term, it is expected to occupy the market share 46.6% due to the - xv - influence in their 30s. Based on the study findings, consumers showed a preference for the reliability of existing accredited certificate over the certificate provided by convenient platform companies. Taking this into account, we aim to provide policy and market proposals based on the study results. Firstly, considering that consumers prioritize reliability, it is recommended that policies reflect this characteristic. Consumers place value on both the convenience and reliability of certificate, particularly in non-face-to-face transactions where certificate play a crucial role. However, convenience and reliability often exist as a trade-off, making it challenging to achieve both simultaneously. Hence, a certificate policy that differentiates between convenience and reliability is necessary. Convenient certificate can offer identity verification in a user-friendly manner and are suitable for general services. On the other hand, trusted certificate require stringent identity verification and are ideal for services that demand high reliability, such as money transfers or stock trading. Secondly, digital signature certification service providers need to make choices regarding convenience and reliability during the issuance process. They should aim to maximize consumer convenience by increasing the utilization of biometric information whenever possible. Specifically, the proposal suggests enhancing the use of non-awareness facial authentication method that leverage mobile phone location information and facial recognition technology. This approach seeks to strike a balance between user convenience and security measures. The purpose of this study is to identify the choice attributes that consumers consider when selecting certificates, particularly in a scenario where multiple certificates have emerged in the market following the complete revision of the Digital Signature Act, which led to the - xvi - abolishment of accredited certificate. The study aims to determine the relative importance of these choice attributes and estimate the utility of each level associated with each attribute. Despite the intense competition in the market, the market share of accredited certificate is expected to decline gradually rather than rapidly. This is attributed to the reliability that has been established over the past two decades and the significance of considering the scope of usage, which has been identified as a consumer characteristic in research findings. Furthermore, platform company certificate, initially projected to rapidly dominate the market, are expected to gradually establish their dominance. This certificate will strive to enhance both the issuer reliability and expand their usage across various sectors. This strategic approach will enable platform company certificate to solidify their position in the market over time. This study is to find out what attributes are important to consumers in choosing certificates in the current era of certificate evolution after the full revision of the Electronic Digital Signature Act. In a scenario where the accredited certificate has been abolished and no prior research on consumer characteristics existed, this study utilized consumer surveys to identify consumer characteristics. Based on these findings, policy proposals and strategies were formulated for service providers, taking into account the identified consumer characteristics. The study's significance lies in predicting the market share of representative certificate using the importance of choice attributes obtained from consumers and providing insights into the future market prospects.  Key words : Digital Signature Certificate, Delphi, Conjoint Analysis, Relative Importance, Part-worth

Strong Unforgeable Online/Offline Signature with the Offline Token Security

김기탁 고려대학교 정보경영공학전문대학원 2014 국내박사

The digital signature is one of the most important primitive for the cryptographic purpose such as the integrity and authentication. Researchers in modern cryptography try to design practically efficient and provably secure schemes. To get the reasonable efficiency, the designer tries to reduce the computation, storage requirement, and transmission bandwidth. To provide the security of the scheme, the prover has to set the security model of the scheme. In some special situation that the user has to rapidly response an ask of the user’s signature, it is required to decrease the time and computing costs to sign a message. In other case, the device, such as the smartcard, has a low computational ability. Thus, it is not able to generate a signature if the signature schemes contains some complex computation. In that case, if the parts, which requires the major computing power to sign the message, could be generated at the manufacturing step of the device, it helps to apply the signature algorithm to the low power device. However, the usual signature algorithm may be not possible to pre-compute the computationally intensive part. A special signature is required suitable for this situation. Online/offline signatures can solve the above situations. It contains two phases. In the (first) offline phase, a signer generates the offline token without the message that needs to be signed. In the (second) online phase, the signer uses the offline token to generate the final signature when the message is received. The offline step is relatively slow whereas the online step is fast. In the offline phase, an offline token is generated and stores in the device which performs online/offline signature scheme. To the best of our knowledge, all previous online/offline signature schemes assume that the offline tokens are stored securely. In real applications, however, this assumption does not hold rigidly. For example, smartcards may be used in the application of online/offline signatures, but these devices lack sufficient computational power. Thus, a smartcard performs the offline step when it is used to access a terminal if it has insufficient computational power. Alternatively, the offline tokens may be stored in the smartcard when it is manufactured. A smartcard has secure storage, but maximum storage is only 0.1 megabytes. In the most efficient online/offline signature schemes, the size of an offline token is almost 1,200 bits. Therefore, over 1.4 megabytes of secure storage are required in a smartcard to store 10,000 offline tokens. This means that sufficient offline tokens cannot be stored on a smartcard. To the best of our knowledge, all previous results are forgeable if an offline token is exposed. A smartcard is very small device, which makes it easy to lose or steal. Thus, the previous security model used for online/offline signatures does not reflect the real environments where online/offline signatures are applied. This thesis studies the security of online/offline signatures. A new security model for online/offline signatures, called offline token leakage-resilient model, is proposed. In this model, an attacker has an extra ability, i.e., he/she can issue offline token leakage queries during the study phase, and obtains the offline tokens. By allowing offline token leakage query, this new model reflects the real environment of the smartcard. To show the existence of secure online/offline signature scheme under the proposed model, a generic construction for online/offline signature is also proposed. Finally, the offline token leakage-resilient and strong unforgeable online/offline signature scheme is proposed.

홍채 인식을 위한 1차원 홍채 signature의 분석에 관한 연구

송명섭 연세대학교 대학원 2000 국내석사

본 논문에서는 1차원 홍채 signature에서 나타나는 홍채의 특징을 이용하여 홍채 인식을 수행하고자 할 때, 홍채 signature의 특징을 효과적으로 반영할 수 있는 가공 방법에 대하여 논하였다. 홍채 signature의 주파수 특성을 표현하기 위한 방법으로 퓨리에 변환, Gabor 필터링, 웨이블렛 변환을 제안하였다. 또한 동일인의 홍채 signature들의 일관성, 다른 사람의 홍채 signature들과의 변별력, 그리고 일관성과 변별력을 모두 고려한 우수도(Goodness)를 상관도(correlation)를 이용하여 정의하고, 이를 기준으로 각각의 방법을 비교·분석하였다. 기존의 홍채 인식 시스템은 2차원 영상의 텍스쳐(texture) 정보를 이용하여 홍채 코드를 생성, 인식한다. 이러한 영상을 사용하는 방법은 텍스쳐 정보를 추출하기 위해 사용되는 2차원 Gabor 필터의 설계가 어렵고 계산량이 많다는 단점이 있다. 보다 간단하고 신속한 인식을 위하여 1차원 홍채 signature를 인식에 이용할 수 있다. 홍채 signature의 미세한 변화에 대한 정보는 주파수 성분의 분석을 통해 얻을 수 있고 이를 위해서는 신호를 주파수 분석이 용이한 형태로 바꾸어 줄 필요가 있다. 실험을 통해서 홍채 영역 중 signature를 추출할 위치를 결정하였고, signature의 Gabor 필터링 및 Haar 웨이블렛 변환을 통해 일관성과 변별력이 높은 주파수를 선택하여 이 주파수 성분을 분석하였다. STFT는 신호의 주파수 특성이 어디에서 발생하고 있는지의 정보를 얻어낼 수는 있으나 윈도우의 크기가 고정되어 있기 때문에 효과적인 주파수 분석이 어렵다. 이에 비해 Gabor 필터링과 웨이블렛 변환은 신호의 특정 주파수 성분들이 위치에 따라 어떻게 나타나는지 분석이 가능하며, 분석하고자 주파수 성분에 따라 적절히 공간적 해상도를 조정할 수 있다. Gabor 필터링 및 Haar 웨이블렛 변환된 신호는 홍채 signature에 비해 일관성과 변별력을 높은 것을 확인했다. 이는 Haar 웨이블렛의 기저 함수들이 계단 함수의 형태를 가져 신호의 특성을 잘 반영할 수 있음에 반해 Gabor 필터는 신호의 필터링된 결과에 영향을 주기 때문이다. 따라서 Gabor 필터링보다는 Haar 웨이블렛 변환에 의해 만들어진 신호가 변별력이 높아 홍채 signature를 보다 높은 일관성과 변별력을 가지는 신호로 가공할 수 있는 제안된 가공 방법 중 가장 적절한 것임을 알 수 있었다. To perform iris recognition, the iris is changed to 1-D iris signature. In this paper, methods of efficient iris pattern transformation is discussed. To represent iris signature's frequency characteristics, Fourier transform, Gabor filtering, and wavelet transform are proposed. Considering the consistency between same person's iris and the discrimination between different person's iris, the goodness is defined by using correlation. Based on the goodness, three transform methods are compared and analyzed. To recognize one's iris, former iris recognition system creates iris code using texture information of the 2-D image. To extract texture information, 2-D Gabor filter is used. But the design of the filter is difficult and the computation amount is extremely large. For simpler and faster recognition, 1-D iris signature can be used. The detail informations of the iris signature can be acquired through frequency analysis. The signature should be transformed to make frequency analysis easier. The region to be extracted within the iris region is determined by experiments. By Gabor filtering and Haar wavelet transform, frequency with high consistency and discrimination is selected. The selected frequency is used for the analysis. STFT can obtain the information about where the frequency characteristics actually occur in the signal. But, It is difficult to analyze the frequency characteristics accurately because the size of window is invariable. In contrast, by Gabor filtering and wavelet transform, analysis of specific frequency components according to the position of the signal is possible and we can take appropriate space resolution with frequency variation. It was found out that the Gabor filtering and the wavelet transform has better consistency and discrimination than the iris signature. Because base functions of the Haar wavelet can represent the characteristics well because of their very simple shape like the step functions. So transformed signal by Haar wavelet transform is more discriminative than the signal by the Gabor filtering. As result, Haar wavelet transform was the most appropriate transform, among the proposed transform methods.