- 15:20 - 16:20 : 손용하, 129-310 - 16:20 - 17:20 : 김지승, 129-310 - 17:20 - 18:20 : 김동우, 129-310 - 손용하 제목 : On the Concrete Hardness of Small-secret Learning With Errors 초록 : During the past decades, the Learning With Errors (LWE) problem has brought many fruitful applications in the modern cryptographic world. In the practical use of LWE based cryptosystems, it is quite common to choose the secret to be extremely small: one popular choice is ternary ($pm 1, 0$) coefficient vector, and some further use ternary vector having only small numbers of nonzero coefficient, what is called sparse and ternary vector. However, this use of small secret may also benefits to attack algorithms against LWE, and currently LWE-based cryptosystems including homomorphic encryptions (HE) set parameters based on the attack complexity of those improved attacks. In this thesis, we propose new attack algorithms for small secret LWE that shows the best performance. The first one is due to the dual attack, where an efficient variant of the dual attack for sparse and small secret LWE was reported by Albrecht (Eurocrypt 2017]. We propose a new hybrid of dual and meet-in-the-middle (MITM) attack, which outperforms the improved variant on the same LWE parameter regime. The second one comes from Howgrave-Graham`s hybrid attack, which was originally designed to solve the NTRU problem, with respect to sparse and ternary secret LWE case, and also refine the previous analysis for the hybrid attack in line with LWE setting. We also implement a sage module that estimates the attack complexity of our algorithm upon LWE-estimator, and our attack shows significant performance improvement for the LWE parameter for FHE. For example, for a dimension $n=32768$, modulus $q=2^{628}$ and ternary secret key with Hamming weight 64 which is one parameter set used for HEAAN bootstrapping (Eurocrypt 2018), the hybrid-dual attack takes $2^{112.5}$ operations (and $2^{70.6}$ bit memory) while the previous best attack requires $2^{127.2}$ operations as reported by LWE-estimator. Moreover, the parameter sets with a dimension $n = 65536,$ modulus $q = 2^{1240}$ with the same Hamming weight $h = 64,$ which was estimated to satisfy $ge 128$ bit-security by the previously considered attacks, is newly estimated to provide only $113$ bit-security by the hybrid attack. - 김지승 제목 : Mathematical Analysis of Indistinguishability Obfuscations 초록 : Indistinguishability obfuscation (iO) is a weak notion of the program obfuscation which requires that if two functionally equivalent circuits are given, their obfuscated programs are indistinguishable. The existence of iO implies numerous cryptographic primitives such as multilinear map, functional encryption, non interactive multi-party key exchange. In general, many iO schemes are based on branching programs, and candidates of multilinear maps represented by GGH13, CLT13 and GGH15. In this thesis, we present cryptanalyses of branching program based iO over such multilinear maps. First, we propose cryptanalyses of all existing branching program based iO schemes over GGH13 for all recommended parameter settings. To achieve this, we introduce two novel techniques, `program converting` using NTRU-solver and `matrix zeroizing`, which can be applied to a wide range of obfuscation constructions. We then show that there exists polynomial time reduction from the NTRU problem to all known branching program based iO over GGH13. As the second work, we present classical polynomial time attacks against the FRS obfuscation (with one zerotest parameter), which is robust against all known classical cryptanalyses on obfuscators, when instantiated with the CLT13 multilinear map. We heuristically reproduce a new zerotest parameter from the original one. It is used in two cryptanalyses; One analysis enables to obtain all secret elements of CLT13, but it requires extra parameter constraints. The other analysis shows that the FRS obfuscation does not satisfy the desired security without any additional constraints. Moreover, we propose a new attack on iO based on GGH15 which exploits statistical properties rather than algebraic approaches. We apply our attack to recent two obfuscations called CVW and BGMZ obfuscation. Thus, we.. break the CVW obfuscation under the current parameter setup, and show that algebraic security model of BGMZ obfuscation is not enough to achieve ideal security. We show that our attack is lying outside of the algebraic security model by presenting some parameters not captured by the proof of the model. - 김동우 제목 : Verifiable Computing for Approximate Arithmetic 초록 : Verifiable computing (VC) is a complexity-theoretic method to secure the integrity of computations. The need is increasing as more computations are outsourced to untrusted parties, e.g., cloud platforms. Existing techniques, however, have mainly focused on exact computations, but not approximate arithmetic (e.g., floating-point or fixed-point arithmetic). This makes it hard to apply them to certain types of computations (e.g., machine learning, data analysis, and scientific computation) that inherently require approximate arithmetic. In this thesis, we present an efficient interactive proof system for arithmetic circuits with rounding gates that can represent approximate arithmetic. The main idea is to reduce the rounding gate into a small sub-circuit without rounding, and reuse the machinery of the Goldwasser, Kalai, and Rothblum`s protocol (also known as the GKR protocol) and its recent refinements. Specifically, we shift the algebraic structure from a field to a ring to better deal with the notion of ``digits``, and generalize the original GKR protocol over a ring. Then, we reduce the rounding operation to a low-degree polynomial in a ring, and develop a novel, optimal circuit construction of an arbitrary polynomial to transform the rounding polynomial to an optimal circuit representation. Moreover, we further optimize the proof generation cost for rounding by employing a Galois ring. We provide experimental results that show the efficiency of our system for approximate arithmetic. For example, our implementation performed two orders of magnitude better than the existing system for a nested 128 by 128 matrix multiplication of depth 12 on the 16-bit fixed-point arithmetic.