Title    name Lastest   |   Most hits   년도선택 최근 50건20102009200820072006200520042003200220012000     KAIST Math Colloquium (Second Semester,2010) Introduction to Random Matrix Theory Lee, Jioon (KAIST) 2010-10-28   Since introduced by Wigner, random matrix theory has become a powerful tool in mathematical phyics. The subject now also plays important roles in various fileds such as combinatorics, probability theory, statistical physics, number theory, nuclear physics, game theory, wireless communication, etc. In this talk, I will explain some important results on random matrices such as Wigner semi-circle law and Dyson sine kernel. Some applications will also be introduced.   Differential Geometry Seminar The Geography Problems of 4-Manifolds, Part II Park, Jongil (Seoul National University) 2010-10-28     Basic Notions Seminar The Geography Problems of 4-Manifolds, Part I Park, Jongil (Seoul National University) 2010-10-28   One of the fundamental problems in 4-manifolds is to classify simply connected smooth (symplectic, complex) 4-manifolds. The classical invariants of a simply connected 4-manifold X are encoded by its intersection form Q_X, a unimodular symmetric bilinear pairing on H_2(X:Z). M. Freedman showed that a simply connected closed 4-manifold is determined up to homeomorphism by Q_X. But the situation in the smooth (symplectic, complex) category is strikingly different. Hence it is an important question to know which unimodular, symmetric, bilinear integral forms are realized as the intersection form of a simply connected smooth (symplectic, complex) 4-manifold, and which simply connected smooth (symplectic, complex) 4-manifolds admit more than one smooth (symplectic, complex) structure. We call these geography problems of 4-manifolds. Gauge theory - Donaldson theory and Seiberg-Witten theory - has been very successful in the geography problems. For example, S. Donaldson proved that the intersection form of a simply connected, definite, smooth 4-manifold is diagonalizable, and it has been known that most known simply connected irreducible smooth 4-manifolds with b_2^+ odd > 1admit infinitely many distinct smooth structures. Recently, there has also been a big progress in the case of b_2^+ = 1. In this talks I’d like to review recent known results on the geography problems of 4-manifolds, in particular in the case of b_2^+ = 1, in three levels - smooth, symplectic and complex category.   ASARC Seminar Results on geometric flow Pak Tung Ho (Sogang University) 2010-10-26   I will talk about several results on geometric flow. In particular, I will talk about prescribed (Gaussian) curvature flow, CR Yamabe flow, and Q-curvature flow.   KAIST Discrete Math Seminar On the free arrangements and truncated affine Weyl arrangements Masahiko Yoshinaga (Kyoto University) 2010-10-26   Freeness of a hyperplane arrangement is defined algebraically using module of derivations. I will discuss freeness of certain truncated affine Weyl arrangements, called the extended Catalan/Shi arrangements. I will also talk some enumerative corollaries.   KAIST Discrete Math Seminar Approximation algorithms for finding maximum stable matchings Shuichi Miyazaki (Kyoto University) 2010-10-15   The stable marriage problem is a classical matching problem. An input consists of the set of men, the set of women, and each person’s preference list that orders the members of the opposite sex according to the preference. The problem asks to find a stable matching, that is, a matching that contains no (man, woman) pair, each of which prefers the other to his/her current partner in the matching. One of the practical extensions is to allow participants to use ties in preference lists and to exclude unacceptable persons from lists. In this variant, finding a stable matching of maximum size is NP-hard. In this talk, we give some of the approximability results on this problem.   KAIST Math Colloquium (Second Semester,2010) Pairing 계산의 효율성 및 암호에의 응용 Lee, Hyangsook (Ewha Womans University) 2010-10-14   We will survey how to improve computational efficiency in various pairing computations.   Differential Geometry Seminar Sub-conformal and almost CR geometry Joo, Jaecheon (POSTECH) 2010-10-13   If we consider strongly-pseudo convex CR manifolds with integrable CR structure, the transformation formula of the pseudo-Hermitian scalar curvatures satisfies a very special non-linear sub-elliptic PDE, which is called the CR Yamabe equation. In 1995, R. Schoen made use of this equation for the characterization of the Heisenberg group under the non-proper action of CR automorphism group. In contrast with integrable case, the transformation formula of the pseudo-Hermitian scalar curvatures is much more complecated than the CR Yamabe equation, if the CR structure is not integrable and this complexity makes it difficult to follow the analysis of integrable case. In this talk, I will introduce a sub-class of contact sub-Riemannian manifolds for which sub-conformal transformation formula of a twisted sub-Riemannian scalar curvature becomes the sub-conformal Yamabe equation. Using the sub-conformal Yamabe equation, we will also discuss about the characterization 5 and 7-dimenisional non-integrable strongly pseudo-convex almost CR manifolds under the non-proper action of CR automorphisms by Schoen's argument.   Basic Notions Seminar An invitation to Kahler-Einstein metrics and Monge-Ampere equations Philippe Eyssidieux (University of Grenoble) 2010-10-08     Differential Geometry Seminar Degenerate Monge-Ampere equations and their applications Philippe Eyssidieux (University of Grenoble) 2010-10-08     Face the world with mathematical mind 하이브리드: 철학, 미학, 윤리학 Hong, Seongwook (Seoul National University) 2010-10-08   최근 우리 사회의 화두 중 하나는 '통섭'이다. 우리를 가두고 있었던 울타리를 넘나들며 새로운 이웃과 만나 서로가 가진 생각을 섞는다는 의미에서 통섭 현상은 바람직하며, 대학 구성원들이 진지하게 생각해 볼 가치가 있다. 그러나 통섭의 시대일수록   KAIST Math Colloquium (Second Semester,2010) Weil-étale cohomology and special values of zeta-functions Thomas Geisser (U. Southern California / Nagoya University) 2010-10-07   The zeta-function of a variety defined over the integers encoded the number of solutions with coefficients in all finite fields. Surprisingly, the value of this zeta function is related to other interesting invariants of the variety. A good example is the analytic class number formula, which related the value of the Dedekind zeta-function of a number field to the class number and other invariants. We will discuss generalizations of this to varieties over finite fields.   ASARC Seminar Finite generation questions for motivic cohomology Thomas Geisser (U. Southern California / Nagoya University) 2010-10-05     The Mathematics of Aperiodic Order On Fibonacci electrons and the stability of soft quasicrystals Ron Lifshitz (Tel Aviv University) 2010-10-01   I would like to take advantage of the informal nature of this workshop to describe three (not necessarily related) results of ongoing research on quasicrystals in my group, which may be of interest to mathematicians. The rst is the observation of log-periodic oscillations in quantities characterizing the quantum dynamics of Fibonacci electrons, such as the probability of an electron to remain in its initial position as a function of time. The second is a conjecture suggesting that the addition of weak disorder, to an otherwise perfect quasiperiodic potential, may provide the necessary conditions for the existence of a generalized Bloch theorem for quasicrystals. The third result is our successful explanation of the thermodynamic stability of quasicrystals, composed of soft isotropic particles. We have demonstrated that, with some help from entropy, very simple (even purely-repulsive) isotropic pair-potentials can lead to the formation of stable dodecagonal quasicrystals.   The Mathematics of Aperiodic Order Aperiodic order and quantum mechanics David Damanik (Rice University) 2010-10-01    We review recent developments in the spectral theory of Schrodinger operators with potentials exhibiting aperiodic order. We will discuss in detail the shape of the spectrum, especially the presence of gaps and their structure.   MiniWorkshop on holomorphic symplectic geometry Classification and construction of general singular fibers of proper Lagrangian fibration. Keiji Oguiso (Osaka University) 2010-09-30     MiniWorkshop on holomorphic symplectic geometry An explicit study of non-locallytree locus of O'Grady's example Yasunari Nagai (University of Tokyo) 2010-09-30     MiniWorkshop on holomorphic symplectic geometry Global Torelli theorem for hyperkaehler manifolds Misha Verbitsky (University of Glasgow) 2010-09-30     MiniWorkshop on holomorphic symplectic geometry Lagrangian fibrations Dimitri Markushevich (University de Lille) 2010-09-30     The Mathematics of Aperiodic Order Rauzy fractals associated with a sequence of substitutions Pierre Arnoux (University d' Aix-Marseilles) 2010-09-30   In several contexts, it would be interesting to describe a Rauzy fractal associated, not with a substitution, but with an innite sequence of substitutions. We explain how this can be realized in a specic case, when the substitutions have the same matrix of the irreducible Pisot type. The generalization of this contruction poses dicult questions.   The Mathematics of Aperiodic Order Toward S-adic Rauzy fractals Valerie Berthe (CNRS) 2010-09-30    Rauzy fractals are compact sets that are associated with substitutive dynamical systems with Pisot type in order to produce a geometric and spectral representation of the underlying symbolic dynamical system. In particular, discrete spectrum property can be stated in terms of tiling properties for the Rauzy fractals. The aim of this lecture is to discuss a possible generalization of this situation to more general symbolic dynamical systems, namely symbolic systems generated by iterating a nite number of substitutions according to a given sequence. Such systems (called S-adic) arise for instance when applying a multidimensional continued fraction algorithm.   The Mathematics of Aperiodic Order Tilings associated with shift radix systems Wolfgang Steiner (CNRS) 2010-09-30    Shift radix systems form a collection of dynamical systems depending on a parameter which varies in the d-dimensional real vector space. They generalize well-known numeration systems such as beta-expansions, expansions with respect to rational bases, and canonical number systems. In this talk, we discuss collections of fractal tiles dened by shift radix systems. For certain classes of parameters, they provide natural families of tiles for betaexpansions with (non-unit) Pisot numbers as well as for canonical number systems with (non-monic) expanding polynomials. In the unit and monic case respectively, they coincide with the well-known Rauzy fractals or fundamental domains of canonical number systems. The case of non-monic expanding polynomials is intimately related to the self-ane tiles with p-adic factors discussed in Jorg Thuswaldner's talk. Under some algebraic conditions on the parameter, the tiles provide multiple (weak) tilings and in many cases, e.g. for the dense family of all rational parameters, even (weak) tilings of the d-dimensional real vector space. Here, we mean by weak tiling that the tiles are compact, cover the space, and the interiors of distinct tiles do not intersect. The obtained weak tilings can have a complicated structure: They may consist of tiles having innitely many dierent shapes, the tiles need not be self-ane (or graph directed self-ane), and we do not know whether the boundary of the tiles has zero measure.   The Mathematics of Aperiodic Order Number systems and tilings with p-adic factors Joerg Thuswaldner (University of Leoben) 2010-09-30    Many results are known about tilings induced by integral self-similar   The Mathematics of Aperiodic Order Discrete planes, two dimensional placement rules and connectivity of Rauzy fractals Anne Siegel (CNRS) 2010-09-30    Rauzy fractals - or central tiles - can be considered as geometrical representations of selfsimilar processes. Their topological properties are related to several questions in number theory, ergodic theory or quasi-crystals. Most of methods allowing studying the topological properties of fractals are connected to an ad-hoc description of the boundary of the tiles. Unfortunately, this description of the graph boundary is not uniform and prevents one to study the properties of families of fractals. In this talk, we investigate the connections between Rauzy fractals and discrete geometry, especially polygonal tilings induced by discrete plane. We will explain how these polygonal tilings can be generated thanks to placement rules inspired by a duality process. As an example of application, we will prove Rauzy fractal connectivity for the full family of Arnoux-Rauzy substitutions. This is a common work with Valerie Berthe and Timo Jollivet.   The Mathematics of Aperiodic Order Relative Cohomology for Tiling Spaces Lorenzo Sadun (University of Texas) 2010-09-30      MiniWorkshop on holomorphic symplectic geometry Slodowy slices, Poisson deformations and symplectic hypersurfaces. Manfred Lehn (Universität Mainz) 2010-09-29     MiniWorkshop on holomorphic symplectic geometry Universal Poisson deformations and birational geometry Yukihiko Namikawa (Nagoya University) 2010-09-29     MiniWorkshop on holomorphic symplectic geometry Minimal singularities in nilpotent orbits and a conjecture of Lusztig Baohua Fu (Chinese Academy of Sciences) 2010-09-29     MiniWorkshop on holomorphic symplectic geometry Symplectic resolutions and canonical bases Dmitry Kaledin (Steklov Mathematical Institute) 2010-09-29     The Mathematics of Aperiodic Order Words, decomposition rules and invariants Jun Morita (University of Tsukuba) 2010-09-29    For bi-innite words, we introduce some algebraic structure using Kellendonk product, which allows us to discuss their standard modules and decomposition rules. We also obtain several deformations of the dimension map. Using this, we dene certain formal power series as word invariants.   The Mathematics of Aperiodic Order Some comments on a hexagonal monotile Uwe Grimm (The Open University) 2010-09-28      The Mathematics of Aperiodic Order Fusion tilings Natalie Priebe Frank (Vassar College) 2010-09-28   We introduce a class of tilings of Euclidean space that generalizes self-similar tilings. Larger and larger patches of tiles are constructed according to fusion rules that play a similar role to the substitution rules of symbolic dynamics. The construction is extremely general, but conditions can be chosen that allow us to investigate the measure theory and topology. We will discuss which standard results for self-similar tilings hold and if time permits, sketch the proofs.   The Mathematics of Aperiodic Order Topological invariants of aperiodic tilings Franz Gahler (University of Bielefeld) 2010-09-28   An overview is given on dierent ways to construct a space of aperiodic tilings as an inverse limit of a sequence of simpler spaces, and how this can be used to compute topological invariants like Cech cohomology. For two-dimensional canonical projection tilings it is then analysed to what extent the dierent MLD classes of such tiling spaces can be distinguished by their cohomology.   The Mathematics of Aperiodic Order Arithmetics of self-similarities of Finitely Generated Uniformly Discrete Jean-Louis Verger-Gaugry (CNRS) 2010-09-28      The Mathematics of Aperiodic Order Aperiodic structures and notions of order and disorder Shelomo I. Ben-Abraham (Ben-Gurion University) 2010-09-27   Articial aperiodic structures have recently been the subject of extensive and intensive research, resulting in layered quasiregular heterostructures, as well as photonic and phononic metamaterials with possible applications such as optical and acoustic bandpasslters or photonic waveguides. Our main interests are centered on rather fundamental questions concerning determinism, or the old problem of order vs. disorder. We seek to establish possible quantications of such concepts, to develop basic notions of complexity and entropy, and beyond. Our specic objects of study are multidimensional generalizations of the standard substitution sequences. Here we present and discuss some two-dimensional instances of the Prouhet-Thue-Morse and paperfolding systems. We compute their rectangle complexities and nd them to be at most polynomial, which means that the corresponding entropy basically vanishes. We also point out that the perfectly deterministic Champernowne sequence has entropy log 2. Thus the notion of entropy cannot serve as an unqualied measure of disorder, and there still remain many unanswered questions.   The Mathematics of Aperiodic Order Wannier transform for aperiodic solids: preliminary results Jean Bellissard (Georgia Institute of Technology) 2010-09-27   The talk will present some preliminary results on a work in progress concerning the possible extension of the Bloch theory to aperiodic Schrodinger operators on $L^2$($R^d$). The operator giving the potential energy in this specic case will be seen as a sum of short range atomic potentials with atoms located on a Delone set Ll ⊂ $R^d$, which is aperiodic, repetitive with nite local complexity. The main properties of such sets will be summarized, examples will be given, and their associated tilings will be described. The Penrose, the octagonal tilings and the icosahedral phase of several quasicrystals are important examples. The Anderson-Putnam complex and the Lagarias group will be dened. This will lead to a denition of the Wannier transform that is shown to be a unitary map onto a Hilbert space analog to the space of Bloch functions used in Solid State Physics. The Schrodinger operator will be shown to have a Bloch like representation and its domain will be characterized. Comments will be made about the potential applications of such method of analysis depending upon how far this work has progressed.   KAIST Discrete Math Seminar List coloring for geometric hypergraphs Shakhar Smorodinsky (Ben-Gurion University) 2010-09-17   Given a hypergraph H = (V,E), a coloring of its vertices is said to be conflict-free if for every hyperedge S ∈ E there is at least one vertex whose color is distinct from the colors of all other vertices in S. The study of this notion is motivated by frequency assignment problems in wireless networks. We introduce and study the list-coloring (or choice) version of this notion. Joint work with Panagiotis Cheilaris   KAIST Math Colloquium (Second Semester,2010) Conflict-Free colorings Shakhar Smorodinsky (Ben-Gurion University) 2010-09-16   Given a hypergraph H = (V,E), a coloring of its vertices is said to be conflict-free if for every hyperedge S ∈ E there is at least one vertex whose color is distinct from the colors of all other vertices in S. When all hyperedges in H have cardinality two (i.e., when H is a simple graph), this coloring coincides with the classical graph coloring. The study of this coloring is motivated by frequency assignment problems in wireless networks and several other applications. We will survey this notion and introduce some fascinating open problems.   ASARC Seminar A Quantum Kirwan Map and Symplectic Vortices Fabian Ziltener (KIAS) 2010-09-15   Given a Hamiltonian Lie group action on a symplectic manifold, I will explain the construction of a quantum deformation of the Kirwan map. It is defined by counting solutions of the symplectic vortex equations, which are a gauge theoretical deformation of the Cauchy-Riemann equations. Based on this map, I will formulate a quantum abelianization conjecture (joint work with Chris Woodward).   ASARC Seminar Estimates of the topological entropy from below for continuous self-maps on some compact manifolds Waclaw Marzantowicz (UAM Poznan) 2010-09-10   We confirm that Entropy Conjecture holds for every continuous self-map of a compact K( π, 1) manifold with the fund. gr. π virtually nilpotent, e.g. for every continuous map of an infra-nilmanifold. In fact, a lower estimate of the topological entropy by the logarithm of the spectral radius of exterior power of an assoc. ”linearization matrix” with integer entries. This & estimates of Mahler measure of polynom., give some absolute lower bounds for the entropy.   KAIST Math Colloquium (Second Semester,2010) Brauer-Manin obstruction and integral points Jean-Louis Colliot-Thelene (Universite Paris-Sud) 2010-09-09   Manin showed how the Brauer group of schemes together with class field theory(reciprocity laws) accounts for many counterexamples to the Hasse principle(local-global principle) and to weak approximation for rational points of projective varieties. Only recently did one start to investigate an analogous approach for integral points of affine varieties. Here the relevant approximation property is strong approximation,a generalization of the chinese remainder theorem. I shall recall what is known or conjectured for rational points.I will then go on to describe what has been achieved for integral points :unconditional results for many classes of homogeneous spaces of linear algebraic groups, with a connexion to the classical study of integral quadratic forms(F. Xu and the speaker, D. Harari, M. Borovoi, C. Demarche) ; computations and conjectures for curves (D. Harari and F. Voloch) ; computations for certain cubic surfaces (O. Wittenberg and the speaker). I will in particular discuss the classical problem of representation of an integer as sum of three cubes of integers.   KAIST Math Colloquium (Second Semester,2010) Solitons in nonlinear dispersive equations Kwon, Soonsik (KAIST) 2010-09-02   Solitons are nonlinear solutions that maintain its shape and travel at a constant speed. They widely arise in focusing nonlinear dispersive equations. They are occurred as a balance of nonlinear reinforcing effects and dispersive effects in the medium. In this talk, I will briefly review long-standing history of solitons and discuss past and current issues around soliton solutions. It will include a brief explanation to the inverse scattering method, the orbital (asymptotic) stability, and then an introduction to the 'soliton resolution conjecture'.   ASARC Seminar Recent progress on algebraic cycles Masanori Asakura (Hokkaido University) 2010-08-31   It is an important conjecture that the Chow group of a smooth projective variety over a number field is a finitely generated Z-module, and no one knows how to solve it so far. On the other hand people considered two modified questions which are more accessible. One is whether the Chow group modulo n is finite or not, and the other is whether the torsion part is finite or not.   2010 International Workshop on Mathematical Cryptology HCI Security: 1. Human Knowledge-Based Authentication Kwon, Taekyoung (Sejong University) 2010-08-28   사용자 인증을 위한 편리한 방법으로서 사용자의 지식에 기반한 인증 기법이 널리 사용되고 있다. 하지만 이것은 사용자 인터페이스를 통한 입력이 필요하며, 특히 입력 시점에 shoulder-surfing 공격을 통해서 사용자의 입력값 또는 비밀값이 쉽게 유출될 수 있는 위험이 있다. 이와 같은 문제를 해결하기 위해서 그동안 많은 기법이 제안되었지만 HCI를 고려한 안전성과 사용성 측면에서 폭넓은 사용이 어렵다. 이러한 주제를 바탕으로 HCI 보안의 어려움과 중요성에 대해서 알아본다.   2010 International Workshop on Mathematical Cryptology Traffic measurement with virtual vector and anomaly detection Yoon, MyungKeun (Kookmin University) 2010-08-28   고속 네트워크 환경에서 정확한 트래픽 측정은 중요하지만 어려운 문제이며, 작은 SRAM내에 상주할 수 있는 컴팩트한 자료구조 설계가 핵심기술 중 하나이다. 정확한 측정결과는 네트워크 보안에 직접 응용될 수 있는데 heavy hitter와 heavy distinct hitter를 탐지하는 경우가 이에 해당한다. Heavy hitter란 측정기간 동안 비정상적으로 많이 등장하는 트래픽을 말하며, heavy distinct hitter란 비정상적으로 많은 서로 다른 목적지로 접근을 시도하는 출발지를 의미한다. 우리가 제안했던 가상벡터 자료구조는 heavy distinct hitter를 탐지하는데 있어서 기존 알고리즘보다 빠르면서도 메모리 사용량을 줄이는 장점을 가진다. 최근에는 가상벡터가 heavy hitter 탐지에도 매우 효과적으로 사용될 수 있음이 확인되었으며 이번 워크숍을 통해 관련된 연구내용을 소개한다.   2010 International Workshop on Mathematical Cryptology Order Preserving Symmetric Encryption Lee, Younho (Yeungnam University) 2010-08-28   SIGMOD 04에서 Agrawal에 제안했던 순서 보존 대칭 암호 (Order Preserving Symmetric Encryption: OPE)에 대하여 현대 암호학적 측면에서의 연구를 시작한다. 첫번째로 순서 보존 대칭 암호에서는 표준 보안 모델의 하나인 선택적 평문 공격 (IND-CPA) 에 대한 구별 불가능성을 이룰 수 없음을 증명한다. 이를 대신하여, 우리는 의사 난수 함수 (PRF)에 기반한 보안 모델을 제안한다. 본 모델에서는 순서 보존 제한 조건하에서 "가능한 한 가장 무작위로(as-random-as-possible)" 라는 개념을 근거로 한다. 우리는 효율적인 OPE 방법을 설계하고, 제안 방법이 블럭암호의 의사난수성에 기반하여 제안 보안 모델에서 안전함을 증명한다. 제안 구현 방법은 순서 보존 난수 함수와 초기하 분포 (hypergeometric distribution) 와의 관계를 바탕으로한다. 즉, 효율적인 초기하 분포 추출(sampling) 알고리즘을 black-box 로 이용한다.   2010 International Workshop on Mathematical Cryptology Pairing-based Non-interactive Zero-Knowledge Proofs Jens Groth (University College London) 2010-08-28    Non-interactive zero-knowledge proofs enable a prover to convince a verifier of the truth of a statement without revealing any other information. They are useful in contexts where verifiability and privacy are needed at the same time and have many applications, for instance in the context of anonymous signatures. Pairing-based cryptography has provided new insights in the area of non-interactive zero-knowledge proofs. We will see how pairing-based non-interactive proofs can be constructed in a simple fashion and how to obtain perfect and everlasting privacy. We will also see how pairing-based techniques have improved the efficiency of non-interactive zero-knowledge proofs and made them useful in practical application.   2010 International Workshop on Mathematical Cryptology Sharing Sensitive Information with Privacy Gene Tsudik (University of California) 2010-08-28    Modern society is increasingly dependent on, and fearful of, the availability of electronic information. There are numerous realistic scenarios where sensitive data must be (sometimes reluctantly or suspiciously) shared between two or more entities without mutual trust. As often happens, the research community has foreseen the need for mechanisms to enable limited (privacy-preserving) sharing of sensitive information and a number of effective (if not always efficient) solutions have been proposed. Among them, Private Set Intersection techniques are particularly appealing whenever two parties wish to compute an intersection of their respective sets of items without revealing to each other any other information. This talk motivates the need for Private Set Intersection (PSI) techniques with various features and privacy properties and illustrates several concrete Private Set Intersection protocols that offer appreciably better efficiency than prior work. We show how to integrate these protocols into a real database system supporting privacy-preserving querying. We also demonstrate their practicality via experimental results obtained from a prototype implementation and discuss a number of systems issues encountered in developing a toolkit that provides various flavors of PSI.   2010 International Workshop on Mathematical Cryptology Effcient Verifiably Encrypted Signatures Without Random Oracles Lee, Juhee (Ewha Womans University) 2010-08-28   A verifiably encrypted signature can convince the verifier that a given ciphertext is the encryption of the signature on a given message, but only the party whose key was used to encrypt it can recover the signature. Recently, Yang et al. proposed a verifiably encrypted signature scheme and claimed that their scheme was secure without random oracle model. Although their verifiably encrypted signature scheme is more efficient and provably secure in standard model, their security proof of opacity is awed. To overcome this weakness, we revisited this scheme and as a result, our verifiably encrypted signature scheme is more efficient and provably secure in the standard model under the q-SDH assumption.   2010 International Workshop on Mathematical Cryptology Practical and Robust Multi-Party Private Set Intersection Seo, Jaehong (Seoul National University) 2010-08-28   One challenge in privacy-preserving multiparty set operations is to design a protocol with linear complexities for communication and computation. This paper describes a new approach that enables to gain quasi-linear complexities in the input size. We outline technical alternatives to represent user’s dataset using polynomial and to carry out polynomial arithmetics, and show how they help improving practical efficiency, especially, in polynomial arithmetics and zero-knowledge proof. The complexities of our protocols are O(n2k) transmission overhead and O((n+log k)2k+(n+(log k)2)k ) computation overhead for k size dataset, n players, and plaintext domain size of an encryption. Based on these building blocks, we construct a multiparty set intersection (MPSI) protocol and then prove that our construction is secure in the malicious model. Our protocol is robust even when corrupted players leave during the process of the protocol.

Information Center for Mathematical Sciences KAIST 335 Gwahangno (373-1 Guseong-dong), Yuseong-gu, Daejeon 305-701, Republic of Korea TEL +82-42-869-8195~6, FAX +82-42-869-5722, e-mail : mathnet@mathnet.or.kr Copyright (c) 2009 by ICMS. All Rights Reserved