°Ë»ö
/ School of Computational Sciences
Combinatorics, Extremal Graph Theory, Random Structure
-
-

-
³í¹®
NUMBER | C20011 |
AUTHOR | Kim, Jeong Han,Kim, Jiseung |
TITLE | Adventures in crypto dark matter: attacks, fixes and analysis for weak pseudorandom functions |
ARCHIVE | |
FILE | |
JOURNAL | DESIGNS CODES AND CRYPTOGRAPHY, 2022 |
ABSTRACT | A weak pseudorandom function (weak PRF) is one of the most important cryptographic primitives for its efficiency although it has lower security than a standard PRF. Recently, Boneh et al. (in: Theory of cryptography conference, Springer, pp 699-729, 2018) introduced two types of new weak PRF candidates, which are called a basicMod-2/Mod-3 and alternative Mod-2/Mod-3 weak PRF. Both use the mixture of linear computations defined on different small moduli to satisfy conceptual simplicity, low complexity (depth-2 ACC(0)) and MPC friendliness. In fact, the new candidates are conjectured to be exponentially secure against any adversary that allows exponentially many samples, and a basicMod-2/Mod-3 weak PRF is the only candidate that satisfies all the features above. However, none of the direct attacks which focus on basic and alternative Mod-2/Mod-3 weak PRFs use their own structures. In this paper, we investigate weak PRFs from two perspectives; attacks, fixes. We first propose direct attacks for an alternative Mod-2/Mod-3 weak PRF and a basic Mod-2/Mod-3 weak PRF when a circulant matrix is used as a secret key. For an alternative Mod-2/Mod-3 weak PRF, we prove that the adversarys advantage is at least 2(-0.105n), where n is the size of the input space of the weak PRF. Similarly, we show that the advantage of our heuristic attack on the weak PRF with a circulant matrix key is larger than 2(-0.21n), which is contrary to the previous expectation that structured secret key does not affect the security of a weak PRF. Thus, for an optimistic parameter choice n = 2 lambda for the security parameter lambda, parameters should be increased to preserve lambda-bit security when an adversary obtains exponentially many samples. Next, we suggest a simple method for repairing two weak PRFs affected by our attack. Moreover, we provide the first direct algorithm for a basic Mod-2/Mod-3 weak PRF with a random secret key even though it does not capture the current parameters. |
-
³í¹®
NUMBER | |
AUTHOR | Kim, Jeong Han |
TITLE | Linear Operators That Preserve the Genus of a Graph |
ARCHIVE | |
FILE | |
JOURNAL | MATHEMATICS, 2019 |
ABSTRACT | A graph has genus k if it can be embedded without edge crossings on a smooth orientable surface of genus k and not on one of genus k-1. A mapping of the set of graphs on n vertices to itself is called a linear operator if the image of a union of graphs is the union of their images and if it maps the edgeless graph to the edgeless graph. We investigate linear operators on the set of graphs on n vertices that map graphs of genus k to graphs of genus k and graphs of genus k+1 to graphs of genus k+1. We show that such linear operators are necessarily vertex permutations. Similar results with different restrictions on the genus k preserving operators give the same conclusion. |
-
³í¹®
NUMBER | |
AUTHOR | Kim, Jeong Han |
TITLE | Some advances on Sidorenkos conjecture |
ARCHIVE | |
FILE | |
JOURNAL | JOURNAL OF THE LONDON MATHEMATICAL SOCIETY-SECOND SERIES, 2018 |
ABSTRACT | A bipartite graph H is said to have Sidorenkos property if the probability that the uniform random mapping from V(H) to the vertex set of any graph G is a homomorphism is at least the product over all edges in H of the probability that the edge is mapped to an edge of G. In this paper, we provide three distinct families of bipartite graphs that have Sidorenkos property. First, using branching random walks, we develop an embedding algorithm which allows us to prove that bipartite graphs admitting a certain type of tree decomposition have Sidorenkos property. Second, we use the concept of locally dense graphs to prove that subdivisions of certain graphs, including cliques, have Sidorenkos property. Third, we prove that if H has Sidorenkos property, then the Cartesian product of H with an even cycle also has Sidorenkos property. |
-
³í¹®
NUMBER | |
AUTHOR | Kim, Jeong Han |
TITLE | On the total variation distance between the binomial random graph and the random intersection graph |
ARCHIVE | |
FILE | |
JOURNAL | RANDOM STRUCTURES & ALGORITHMS, 2018 |
ABSTRACT | When each vertex is assigned a set, the intersection graph generated by the sets is the graph in which two distinct vertices are joined by an edge if and only if their assigned sets have a nonempty intersection. An interval graph is an intersection graph generated by intervals in the real line. A chordal graph can be considered as an intersection graph generated by subtrees of a tree. In 1999, Karonski, Scheinerman, and Singer-Cohen introduced a random intersection graph by taking randomly assigned sets. The random intersection graph G(n, m; p) has n vertices and sets assigned to the vertices are chosen to be i.i.d. random subsets of a fixed set M of size m where each element of M belongs to each random subset with probability p, independently of all other elements in M. In 2000, Fill, Scheinerman, and Singer-Cohen showed that the total variation distance between the random graph G(n, m; p) and the Erdos-Renyi graph G(n, <(p))over cap> tends to 0 for any 0 <= p = p(n) <= 1 if m = n(alpha), alpha > 6, where fr is chosen so that the expected numbers of edges in the two graphs are the same. In this paper, it is proved that the total variation distance still tends to 0 for any 0 <= p = p(n) <= 1 whenever m >> n(4). |
-
³í¹®
NUMBER | |
AUTHOR | Kim, Jeong Han |
TITLE | TWO APPROACHES TO SIDORENKOS CONJECTURE |
ARCHIVE | |
FILE | |
JOURNAL | TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 2016 |
ABSTRACT | Sidorenkos conjecture states that for every bipartite graph H on {1,..., k} integral Pi((i, j)is an element of E(H)) h(x(i), y(j))d mu(vertical bar) (V(H)vertical bar) >= (integral h(x, y) d mu(2))(vertical bar) (E(H)vertical bar) holds, where mu is the Lebesgue measure on [0, 1] and h is a bounded, non-negative, symmetric, measurable function on [0, 1](2). An equivalent discrete form of the conjecture is that the number of homomorphisms from a bipartite graph H to a graph G is asymptotically at least the expected number of homomorphisms from H to the Erdos-Renyi random graph with the same expected edge density as G. In this paper, we present two approaches to the conjecture. First, we introduce the notion of tree-arrangeability, where a bipartite graph H with bipartition A boolean OR B is tree-arrangeable if neighborhoods of vertices in A have a certain tree-like structure. We show that Sidorenkos conjecture holds for all tree-arrangeable bipartite graphs. In particular, this implies that Sidorenkos conjecture holds if there are two vertices a(1), a(2) in A such that each vertex a is an element of A satisfies N(a) subset of N(a(1)) or N(a) subset of N(a(2)), and also implies a recent result of Conlon, Fox, and Sudakov (2010). Second, if T is a tree and H is a bipartite graph satisfying Sidorenkos conjecture, then it is shown that the Cartesian product T square H of T and H also satisfies Sidorenkos conjecture. This result implies that, for all d >= 2, the d-dimensional grid with arbitrary side lengths satisfies Sidorenkos conjecture. |
-
³í¹®
NUMBER | |
AUTHOR | Kim, Jeong Han |
TITLE | On coupon colorings of graphs |
ARCHIVE | |
FILE | |
JOURNAL | DISCRETE APPLIED MATHEMATICS, 2015 |
ABSTRACT | Let G be a graph with no isolated vertices. A k-coupon coloring of G is an assignment of colors from [k] := {1, 2,..., k} to the vertices of G such that the neighborhood of every vertex of G contains vertices of all colors from [k]. The maximum k for which a k-coupon coloring exists is called the coupon coloring number of G, and is denoted chi(c)(G). In this paper, we prove that every d-regular graph G has chi(c)(G) >= (1 - 0(1))d/log d as d -> infinity, and the proportion of d-regular graphs G for which chi(c)(G) <= (1 + 0(1))d/log d tends to 1 as vertical bar V(G)vertical bar -> infinity. An infective k-coloring of a graph G is an assignment of colors from [k] to the vertices of G such that no two vertices joined by a path of length two in G have the same color. The minimum k for which such a coloring exists is called the infective coloring number of G, denoted chi(i)(G). In this paper, we also discuss injective colorings of Hamming graphs. (C) 2015 Elsevier B.V. All rights reserved. |
-
³í¹®
NUMBER | |
AUTHOR | Kim, Jeong Han |
TITLE | UNIVERSALITY OF RANDOM GRAPHS FOR GRAPHS OF MAXIMUM DEGREE TWO |
ARCHIVE | |
FILE | |
JOURNAL | SIAM JOURNAL ON DISCRETE MATHEMATICS, 2014 |
ABSTRACT | For a family F of graphs, a graph G is called F-universal if G contains every graph in F as a subgraph. Let F-n(d) be the family of all graphs on n vertices with maximum degree at most d. Dellamonica, Kohayakawa, Rodl, and Rucinski [An improved upper bound on the density of universal random graphs, Random Structures & Algorithms, doi:10.1002/rsa.20545] showed that, for d = 3, the random graph G(n,p) is F-n(d)-universal with high probability provided p >= C(logn/n)(1/d) for a sufficiently large constant C = C(d). In this paper we prove the missing part of the result, that is, the random graph G(n, p) is F-n(2)-universal with high probability provided p = C(log n/n)(1/2) for a sufficiently large constant C. |

- Office:1232 / TEL) 82-2-958-2551 / FAX) 82-2-958-3870
- School of School of Computational Sciences, Korea Institute for Advanced Study
¼¿ïƯº°½Ã µ¿´ë¹®±¸ ȸ±â·Î 85(¼¿ïƯº°½Ã µ¿´ë¹®±¸ û·®¸®µ¿ 207-43) ¿ì:130-722