Abstracts

• Hao Chen (Facebook, U.S.A.)

  • User data protection via Privacy Enhancing Technologies

  • Abstract: We will sample several applications of privacy enhancing technologies in the tech industry to protect user data  Examples may include: anonymous credentials service, WhatsApp encrypted backup, WhatsApp key transparency, private lift and private attribution.

• Minki Hhan (KIAS, Korea)

  • Quantum Complexity for Discrete Logarithms and Related Problems

  • Abstract: In this talk, we study the quantum computational complexity of the discrete logarithm and related group-theoretic problems in the context of ``generic algorithms''---that is, algorithms that do not exploit any properties of the group encoding. We first establish a generic model of quantum computation for group-theoretic problems, which we call the quantum generic group model, as a quantum analog of its classical counterpart. Shor's algorithm for the discrete logarithm problem and related algorithms can be described in this model. 

We show the quantum complexity lower bounds and (almost) matching algorithms of the discrete logarithm and related problems in this model. Precisely, we prove that any generic quantum discrete logarithm algorithm for the underlying group G must make Omega(log |G|) depth of group operation queries. This shows that Shor's algorithm that makes O(|G|) group operations is asymptotically optimal among the generic quantum algorithms, even considering parallel algorithms. Furthermore, we extend this result to the generic hybrid quantum-classical algorithms and the bounded-size quantum memory setting, showing that variants of Shor's discrete logarithm algorithm are essentially optimal in each setting.

This talk is based on a joint work with Takashi Yamakawa and Aaram Yun.

• Akinori Hosoyamada (NTT, Japan)

  • On Quantum Cryptanalysis in Symmetric-Key Cryptography

  • Abstract: This talk surveys research on post-quantum security in symmetric-key cryptography, mainly from the viewpoint of cryptanalysis using quantum algorithms. Starting with how research on classical symmetric cryptanalysis progresses in the first place, I will provide a comprehensive overview from the very basics to state of the art.

• Seongkwang Kim (Samsung SDS, Korea)

  • Signature schemes based on the MPC-in-the-Head paradigm

  • Abstract: MPC-in-the-Head (MPCitH), proposed by Ishai et al. (STOC ’07), is a paradigm to construct a zero-knowledge proof (ZKP) system from a multiparty computation (MPC) protocol. Since Chase et al. first proposed the MPCitH-based signature scheme Picnic (CCS ’17), there have been many studies on combining MPCitH and symmetric primitives. One of the main advantages of MPCitH-based signature schemes is that their security solely depends on the security of the one-way function used in key generation, which makes them more reliable compared to the schemes whose security is based on the hardness assumption of certain mathematical problems with a potential gap in the security reduction. In this talk, we survey the history of signature schemes based on MPCitH and symmetric primitives, from Picnic to a very recent scheme, AIMer.

• Sungwook Kim (Seoul Women’s University, Korea)

  • Title: Polynomial Commitment Schemes for zk-SNARKs

  • Abstract: Zero-Knowledge Succinct Non-interactive Arguments of Knowledge (zk-SNARKs) are non-interactive proof systems that validate NP statements with a short and efficiently verifiable proof without revealing any information other than the correctness of the statements. The main ingredient for zk-SNARKs is a polynomial commitment scheme. In a polynomial commitment scheme, a prover commits a polynomial and a verifier sends a random point to the prover. The prover then evaluates the polynomial on the given point with generating a proof that the evaluated value is correctly computed according to the committed function. In this talk we present a new efficient polynomial commitment schemes without a trusted setup. 

• Young-Sik Kim (Chosun University, Korea)

  • Privacy-Preserving Machine Learning over Fully Homomorphic Encryption

  • Abstract: Privacy issues in machine learning applications have received increasing attention in recent years.  For example, people have been surprised by the amazing performance of ChatGPT, but at the same time, privacy issues are considered a real threat.

Fully homomorphic encryption (FHE) is one of the most appropriate tools for privacy-preserving machine learning (PPML) to ensure strong security in the cryptographic sense. FHE is an encryption scheme that enables a server to process the encrypted data of clients without decrypting them. It allows the clients to outsource the processing of sensitive data to an untrusted server without leaking any information about the data. However, most current practical FHE schemes support only limited arithmetic operations and 1D data structures. In addition, due to the computational complexity of homomorphic encryption, it has been questioned whether performing the large number of operations required by machine learning over the FHE domain is practical.

In this talk, I will address these issues and introduce the method and latest achievements of deep convolutional neural networks based on homomorphic encryption. In particular, I will briefly introduce the following three points in this context: i) RNS-CKKS fully homomorphic encryption scheme, including high-precision bootstrapping schemes. ii) Polynomial approximation of the activation function and multiplexed parallel convolution for efficient CNN operations over FHE. iii) Privacy-preserving deep convolutional neural networks for ResNet and VGGNet with CIFAR and ImageNet datasets.

• Chohong Min (Ewha Womans University, Korea)

  • Overview of CKKS Homomorphic Encryption System and its enhancement by EvalRound algorithm

  • Abstract: CKKS is a homomorphic encryption system that deals with real/complex valued data.  The system is fully homomorphic encryption, due to the bootstrapping algorithm applied when levels run out. The bootstrapping algorithm has many parameters to be tuned. We in this talk present some statistical analyses of CKKS bootstrappings that help to efficiently tune the parameters.  In addition, EvalRound algorithm is introduced to substitute the conventional EvalMod algorithm in the bootstrapping.

• Jeongeun Park (KU Leuven, Belgium)

  • Panacea: Non-interactive and Stateless Oblivious RAM

  • Abstract: Oblivious RAM (ORAM) allows a client to outsource storage to a remote server while hiding the data access pattern from the server. Many ORAM designs have been proposed to reduce the computational overhead and bandwidth blowup for the client. A recent work, Onion Ring ORAM (CCS’19), is able to achieve O(1) bandwidth blowup in the online phase using fully homomorphic encryption (FHE) techniques, at the cost of a computationally expensive client-side offline phase. Furthermore, such a scheme can be categorized as a stateful construction, meaning that the client has to locally maintain a dynamic state representing the order of remote database elements.
    
    We present Panacea: a novel design of ORAM based on FHE techniques, that is non-interactive and stateless, achieves O(1) bandwidth blowup, and does not require an expensive offline phase for the client to perform; in that sense, our design is the first of its kind among other ORAM designs. To provide the client with such performance benefits, our design delegates all expensive computation to the resourceful server. We additionally show how to boost the server performance significantly using probabilistic batch codes at the cost of only 1.5x in additional bandwidth blowup and 3x expansion in server storage, but less amortized bandwidth. Our experimental results show that our design, with the batching technique, is practical in terms of server computation overhead as well. Specifically, for a database size of 2^19, it takes only 1.16 seconds of amortized computation time for a server to respond to a query. As a result of the statelessness and low computational overhead on the client, and reasonable computational overhead on the server, our design is very suitable to be deployed as a cloud-based privacy-preserving storage outsourcing solution with a portable client running on a lightweight device.

• Alain Passelègue (Inria & ENS Lyon, France)

  • Constrained pseudorandom functions from homomorphic secret sharing

  • In this work, published at Eurocrypt 2023 (https://eprint.iacr.org/2023/387.pdf), we propose and analyze a simple strategy for constructing 1-key constrained pseudorandom functions (CPRFs) from homomorphic secret sharing (HSS). Notably, we obtain the first (1-key selectively secure, private) CPRFs for inner product and for NC1 from the DCR assumption, and more. We also revisit two applications of HSS, equipped with these additional properties, to secure computation: we obtain secure computation in the silent preprocessing model with one party being able to precompute its whole preprocessing material before even knowing the other party, and we construct one-sided statistically secure computation with sublinear communication for restricted forms of computation.

• Damien Robert (Inria Bordeaux Sud-Ouest, France)

  • Efficient representation of isogenies

  • Abstract: We introduce an efficient representation of isogenies between elliptic curves (or abelian varieties), which allows to evaluate isogenies on any point in polylogarithmic time. We explain how to work with this representation: computing the dual isogeny, the sum of two isogenies, dividing an isogeny... We then give some algorithmic and cryptographic applications of this representation.

• Yongsoo Song (Seoul National University, Korea)

  • Practical Lattice-based Proof of Knowledge from Hint-MLWE

  • Abstract: In the last decade, zero-knowledge proof of knowledge protocols have been extensively studied to achieve active security of various cryptographic protocols, however, the existing solutions simply seek zero-knowledge for both message and randomness, which is an overkill in many applications since protocols may remain secure even if some information about randomness is leaked to the adversary.

We develop this idea to improve the state-of-the-art proof of knowledge protocols for RLWE-based public-key encryption and BDLOP commitment schemes. In a nutshell, we present new proof of knowledge protocols without using noise flooding or rejection sampling which are provably secure under a computational hardness assumption, called Hint-MLWE. Our approach enjoys the best of two worlds because it has no computational overhead from repetition (abort) and achieves a polynomial overhead between the honest and proven languages.

• Takashi Yamakawa (NTT, Japan)

  • Quantum Advantage from Cryptographic Assumptions

  • Abstract: TBA