SG Crypto Workshop

cryptography talks in Singapore

Home / Directions

Workshop on Jan 8 & 9, 2026

We are organizing a cryptography workshop at NUS, with a focus on quantum and post-quantum cryptography.

  • Dates: Jan 8 and 9, 2026 (Thu & Fri).
  • Venue: NUS, COM3-01-21 COM1, 02-12
  • Please register (free, lunch provided). Deadline 4.1.26

Organizers. Divesh Aggarwal (NUS/CQT) and Hoeteck Wee (NTT Research)

Program

Jan 8 (Thu).

10:00-10:05 Welcome
10:05-10:50 Rohit Chatterjee Public Key Encryption from the MinRank Problem slides
10:50-11:15 Coffee Break
11:15-12:00 Divesh Aggarwal Worst-Case to Average-Case Hardness of LWE: An Alternative Perspective
12:00-12:20 Kel Zin Tan Improved Search-to-Decision Reduction for Random Local Functions slides
12:20-14:00 Lunch (provided)
14:00-14:45 Shota Yamada Zeroizing Attacks against Evasive and Circular Evasive LWE slides
14:45-15:05 Tianyu Zhang Quantum Cryptanalysis: An Overview slides
15:05-15:30 Coffee Break
15:30-16:15 Surya Mathialagan SNARGs for NP and Non-Signaling PCPs, Revisited slides
16:15-16:35 Enhui Lim Bootstrapping with RMFE for fully homomorphic encryption

Jan 9 (Fri).

10:00-10:45 Rahul Jain Commitments are equivalent to statistically-verifiable one-way state generators slides
10:45-11:15 Coffee Break
11:15-12:00 Takashi Yamakawa Quantum Cryptography and Hardness of Non-Collapsing Measurements
12:00-12:20 Srijita Kundu Are uncloneable proof and advice states strictly necessary? slides
12:20-14:00 Lunch (provided)
14:00-14:45 Kai-Min Chung Complexity theory for quantum-input decision problems and computational hardness in quantum cryptography slides
14:45-15:05 Naresh Boddu On Split-State Quantum Tamper Detection
15:05-15:30 Coffee Break
15:30-16:15 Yilei Chen LWE with Quantum Amplitudes slides
16:15-16:35 Tran Ngo A quasi-polynomial time algorithm for the extrapolated dihedral coset problem over power-of-two moduli

Abstracts

Worst-Case to Average-Case Hardness of LWE: An Alternative Perspective Divesh Aggarwal (NUS/CQT)

In this work, we study the worst-case to average-case hardness of the Learning with Errors problem (LWE) under an alternative measure of hardness, the maximum success probability achievable by a probabilistic polynomial-time (PPT) algorithm. Previous works by Regev (STOC 2005), Peikert (STOC 2009), and Brakerski, Peikert, Langlois, Regev, Stehle (STOC 2013) give worst-case to average-case reductions from lattice problems to LWE, specifically from the approximate decision variant of the Shortest Vector Problem (GapSVP) and the Bounded Distance Decoding (BDD) problem. These reductions, however, are lossy in the sense that even the strongest assumption on the worst-case hardness of GapSVP or BDD implies only mild hardness of LWE. Our alternative perspective gives a much tighter reduction and strongly relates the hardness of LWE to that of BDD. In particular, we show that under a reasonable assumption about the success probability of solving BDD via a PPT algorithm, we obtain a nearly tight lower bound on the highest possible success probability for solving LWE via a PPT algorithm. Our results not only refine our understanding of the computational complexity of LWE, but also provide a useful framework for analyzing the practical security implications.

On Split-State Quantum Tamper Detection Naresh Boddu

Tamper-detection codes (TDCs) are fundamental objects at the intersection of cryptography and coding theory. A TDC encodes messages in such a manner that tampering the codeword causes the decoder to either output the original message, or reject it. In this work, we study quantum analogs of one of the most well-studied adversarial tampering models: the so-called $t$-split-state tampering model, where the codeword is divided into $t$ shares, and each share is tampered with ``locally”. It is impossible to achieve tamper detection in the split-state model using classical codewords. Nevertheless, we demonstrate that the situation changes significantly if the message can be encoded into a multipartite quantum state, entangled across the $t$ shares. Concretely, we define a family of quantum TDCs defined on any $t\geq 3$ shares, which can detect arbitrary split-state tampering so long as the adversaries are unentangled, or even limited to a finite amount of pre-shared entanglement. Previously, this was only known in the limit of asymptotically large $t$. As our flagship application, we show how to augment threshold secret sharing schemes with similar tamper-detecting guarantees. We complement our results by establishing connections between quantum TDCs and quantum encryption schemes.

Public Key Encryption from the MinRank Problem Rohit Chatterjee (NUS)

We construct a public-key encryption scheme from the hardness of the (planted) MinRank problem over uniformly random instances. This corresponds to the hardness of decoding random linear rank-metric codes. Existing constructions of public-key encryption from such problems require hardness for structured instances arising from the masking of efficiently decodable codes. Central to our construction is the development of a new notion of duality for rank-metric codes.

LWE with Quantum Amplitudes Yilei Chen (Tsinghua)

One of the recent attempts of quantumly solving LWE tries to make use of LWE with quantum amplitudes, where the LWE error distributions are encoded as quantum amplitudes. I will survey a few recent papers that explore several algorithms, hardness results and applications of LWE with quantum amplitudes. I will also explain the interesting findings behind the use of complex Gaussian as the LWE amplitudes.

The talk is mostly based on https://eprint.iacr.org/2021/1093 (Eurocrypt 2022), https://eprint.iacr.org/2023/1498 (Crypto 2025). I will also survey other recent papers.

Bio: Yilei Chen is an assistant professor at Tsinghua University. His main research interest is in cryptography and quantum computation.

Complexity theory for quantum-input decision problems and computational hardness in quantum cryptography Kai-Min Chung (Academia Sinica)

(Abstract forth-coming)

Are uncloneable proof and advice states strictly necessary? Srijita Kundu (Foxconn Research)

Yes, we show that they are. We initiate the study of languages that necessarily need uncloneable quantum proofs and advice. We define strictly uncloneable versions of the classes QMA, BQP/qpoly and FEQP/qpoly (which is the class of relational problems solvable exactly with polynomial-sized quantum advice). Strictly uncloneable QMA is defined to be the class of languages in QMA that only have uncloneable proofs, i.e., given any family of candidate proof states, a polynomial-time cloning algorithm cannot act on it to produce states that are jointly usable by k separate polynomial-time verifiers, for arbitrary polynomial k. This is a stronger notion of uncloneable proofs and advice than those considered in previous works, which only required the existence of a single family of proof or advice states that are uncloneable. We show that in the quantum oracle model, there exist languages in strictly uncloneable QMA and strictly uncloneable BQP/qpoly. The language in strictly uncloneable QMA also gives a quantum oracle separation between QMA and the class cloneableQMA introduced by Nehoran and Zhandry (2024). We also show without using any oracles that the language, used by Aaronson, Buhrman and Kretschmer (2024) to separate FEQP/qpoly and FBQP/poly, is in strictly uncloneable FEQP/qpoly.

Commitments are equivalent to statistically-verifiable one-way state generators Rahul Jain (NUS/CQT)

One-way state generators (OWSG) are natural quantum analogs to classical one-way functions. We consider statistically-verifiable OWSGs (sv-OWSG), which are (potentially) weaker objects than OWSGs. We show that O(n/log(n))-copy sv-OWSGs (n represents the input length) are equivalent to poly(n)-copy sv-OWSGs and to quantum commitments. Since known results show that o(n/log(n))-copy OWSGs cannot imply commitments (unless they exist unconditionally), this shows that O(n/log(n))-copy sv-OWSGs are the weakest OWSGs from which we can get commitments (and hence much of quantum cryptography).

Our construction follows along the lines of Hastad, Impagliazzo, Levin, and Luby [HILL 99], who obtained classical pseudorandom generators (PRG) from classical one-way functions (OWF), however, with crucial modifications. Our construction, when applied to the classical case, provides an alternative to the classical construction to obtain a classical mildly non-uniform PRG from any classical OWF (from which a uniform PRG can be obtained following along [HILL 99]). Since we do not argue conditioned on the output, our construction and analysis are arguably simpler and may be of independent interest.

Talk based on:

Commitments are equivalent to one-way state generators. Rishabh Batra, Rahul Jain. FOCS, 2024. QCrypt, 2024. TQC, 2025. ArXiv:2404.03220.

Bootstrapping with RMFE for fully homomorphic encryption Enhui Lim (NTU)

BGV and BFV homomorphic encryption schemes are commonly instantiated using power-of-two cyclotomic orders. Field Instruction Multiple Data (FIMD) was introduced in 2022 to increase packing capacity in the case of small primes, by using reverse multiplication-friendly embeddings (RMFEs) to encode more data into each plaintext slot. However, FIMD did not admit bootstrapping, a core protocol for ensuring ciphertexts can undergo further multiplications.

This talk presents our 2025 work on bootstrapping for RMFE-packed ciphertexts. We first adapt the digit extraction algorithm to work over RMFE-packed ciphertexts, by applying the recode map after every evaluation of the lifting polynomial. To reduce capacity loss, we introduce correction maps to the Halevi-Shoup digit extraction algorithm, to remove all but the final recode of RMFE digit extraction.

We implement several workflows for bootstrapping RMFE-packed ciphertexts in HElib, and benchmark them against thin bootstrapping for m = 32768. Our experiments show that the basic strategy of recoding multiple times in digit extraction yield better data packing, but result in very low remaining capacity and latencies of up to hundreds of seconds. On the other hand, using correction maps gives up to 6 additional multiplicative depth and brings latencies often below 10 seconds, at the cost of lower packing capacity.

SNARGs for NP and Non-Signaling PCPs, Revisited Surya Mathialagan (NTT Research)

We revisit the question of whether one can build succinct non-interactive arguments (SNARGs) for all of NP under standard assumptions such as the Learning With Errors (LWE) assumption. Our approach uses non-signaling probabilistically checkable proofs, following the framework of Kalai, Raz, and Rothblum (STOC 2014). In particular, we point out that working with exponential-length PCPs appears to avoid all currently known barriers to such constructions.

Our main result is a candidate non-adaptive SNARG for NP, whose soundness we prove under two assumptions:

  1. a standard cryptographic assumption, such as LWE (or alternatives like bilinear-map assumptions), and

  2. a mathematical conjecture about multivariate polynomials over the reals.

More precisely, the conjecture gives an upper bound on the minimum total coefficient size of Nullstellensatz proofs—specifically, proofs of membership in a concrete polynomial ideal as studied by Potechin and Zhang (ICALP 2024). Importantly, this conjecture is purely mathematical in nature: it is not a cryptographic or computational hardness assumption.

A particularly notable aspect of our work is that the security analysis makes non-black-box use of the SNARG adversary. This allows us to bypass the black-box barrier of Gentry and Wichs (STOC 2011). As a result, our work offers a blueprint for constructing SNARGs for NP that fall outside the reach of the Gentry–Wichs impossibility framework.

A quasi-polynomial time algorithm for the extrapolated dihedral coset problem over power-of-two moduli Tran Ngo (NUS)

The Learning With Errors (LWE) problem, introduced by Regev (STOC’05), is one of the fundamental problems in lattice-based cryptography, believed to be hard even for quantum adversaries. Regev (FOCS’02) showed that LWE reduces to the quantum Dihedral Coset Problem (DCP). Later, Brakerski, Kirshanova, Stehlé and Wen (PKC’18) showed that LWE reduces to a generalization known as the Extrapolated Dihedral Coset Problem (EDCP). We present a quasi-polynomial time quantum algorithm for the EDCP problems over power-of-two moduli using a quasi-polynomial number of samples, which also applies to the SLWE problem defined by Chen, Liu, and Zhandry (Eurocrypt’22). Our EDCP algorithm can be viewed as a provable variant to the “Simon-meets-Kuperberg” algorithm introduced by Bonnetain and Naya-Plasencia (Asiacrypt’18), adapted to the EDCP setting. We stress that our algorithm does not affect the security of LWE with standard parameters, as the reduction from standard LWE to EDCP limits the number of samples to be polynomial.

Improved Search-to-Decision Reduction for Random Local Functions Kel Zin Tan (NUS)

A random local function defined by a d-ary predicate P is one where each output bit is computed by applying P to d randomly chosen bits of its input. These represent natural distributions of instances for constraint satisfaction problems. They were put forward by Goldreich as candidates for low-complexity one-way functions, and have subsequently been widely studied also as potential pseudo-random generators.

We present a new search-to-decision reduction for random local functions defined by any predicate of constant arity. Given any efficient algorithm that can distinguish, with advantage ϵ, the output of a random local function with m outputs and n inputs from random, our reduction produces an efficient algorithm that can invert such functions with O(m{(n/ϵ)}^2) outputs, succeeding with probability Ω(ϵ). This implies that if a family of local functions is one-way, then a related family with shorter output length is family of pseudo-random generators.

Prior to our work, all such reductions that were known required the predicate to have additional sensitivity properties, whereas our reduction works for any predicate. Our results also generalise to some super-constant values of the arity d, and to noisy predicates.

Zeroizing Attacks against Evasive and Circular Evasive LWE Shota Yamada (AIST)

We develop new attacks against the Evasive LWE family of assumptions, in both the public and private-coin regime. To the best of our knowledge, ours are the first attacks against Evasive LWE in the public-coin regime, for any instantiation from the family. Our attacks are summarized below.

Public-Coin Attacks.

  1. The recent work by Hseih, Lin and Luo [HLL23] constructed the first Attribute Based Encryption (ABE) for unbounded depth circuits by relying on the “circular’’ evasive LWE assumption. This assumption has been popularly considered as a safe, public-coin instance of Evasive LWE in contrast to its “private-coin’’ cousins (for instance, see [CW25, DJM+25a]). We provide the first attack against this assumption, challenging the widely held belief that this is a public-coin assumption.

  2. We demonstrate a counter-example against vanilla public-coin evasive LWE by Wee [Wee22] in an unnatural parameter regime. Our attack crucially relies on the error in the pre-condition being larger than the error in the post-condition, necessitating a refinement of the assumption.

Private-Coin Attacks.

  1. The recent work by Agrawal, Kumari and Yamada [AKY24a] constructed the first functional encryption scheme for pseudorandom functionalities (PRFE) and extended this to obfuscation for pseudorandom functionalities (PRIO) [AKY24c] by relying on private-coin evasive LWE. We provide a new attack against the assumption stated in the first posting of their work (subsequently refined to avoid these attacks).

  2. The recent work by Branco et al. [BDJ+25] (concurrently to [AKY24c]) provides a construction of obfuscation for pseudorandom functionalities by relying on private-coin evasive LWE. We provide a new attack against their stated assumption.

  3. Branco et al. [BDJ+25] showed that there exist contrived, “self-referential’’ classes of pseudorandom functionalities for which pseudorandom obfuscation cannot exist. We extend their techniques to develop an analogous result for pseudorandom functional encryption.

While Evasive LWE was developed to specifically avoid “zeroizing attacks’’, our work shows that in certain settings, such attacks can still apply.

Quantum Cryptography and Hardness of Non-Collapsing Measurements Takashi Yamakawa (NTT SIL)

One-way puzzles (OWPuzzs) introduced by Khurana and Tomer [STOC 2024] are a natural quantum analogue of one-way functions (OWFs), and one of the most fundamental primitives in “Microcrypt,” where OWFs do not exist but quantum cryptography is possible. OWPuzzs are implied by almost all quantum cryptographic primitives, and they imply several important applications such as non-interactive commitments and multi-party computations. A significant goal in the field of quantum cryptography is to base OWPuzzs on plausible assumptions that will not imply OWFs.

In this paper, we base OWPuzzs on hardness of non-collapsing measurements. To that end, we introduce a new complexity class called SampPDQP, which is a sampling version of the decision class PDQP introduced in Aaronson, Bouland, Fitzsimons, and Lee (ITCS 2016). We show that if SampPDQP is hard on average for quantum polynomial time, then OWPuzzs exist. SampPDQP is the class of sampling problems that can be solved by a classical polynomial-time algorithm that can make a single query to a non-collapsing measurement oracle, which is a “magical” oracle that can sample measurement results on quantum states without collapsing the states. Such non-collapsing measurements are highly unphysical operations that should be hard to realize in quantum polynomial time.

We also study upper bounds of the hardness of SampPDQP. We introduce a new primitive, distributional collision-resistant puzzles (dCRPuzzs), which are a natural quantum analogue of distributional collision-resistant hashing (Dubrov and Ishai, STOC 2006). We show that dCRPuzzs imply average-case hardness of SampPDQP (and therefore OWPuzzs as well). We also show that two-message honest-statistically-hiding commitments with classical communication and one-shot signatures (Amos, Georgiou, Kiayias, Zhandry, STOC 2020) imply dCRPuzzs.

Bio: Takashi Yamakawa is a Senior Distinguished Researcher at NTT Social Informatics Laboratories. He obtained his PhD in Science from the University of Tokyo and joined NTT in 2017.

Quantum Cryptanalysis: An Overview Tianyu Zhang (NTU)

This talk will provide an overview of quantum cryptanalysis on symmetric-key primitives. We will first discuss the standard assumptions on the capabilities of quantum adversaries, followed by a brief introduction on the fundamental quantum toolsets, then explain how these tools are exploited to construct attacks in the quantum setting. This talk aims to clarify both the power and the limitations of quantum computing in symmetric-key cryptanalysis.