Maciej Obremski
Picture by Zahra Jafargholi
BIO:
I am a Research Assistant Professor at School of Computing, National University of Singapore. Before that I have spent 5 years in Divesh Aggarwal's group at National University of Singapore, at first as a Research Fellow, and since 2020 as a Senior Research Fellow. Before joining NUS I spent 3 years as a Post-doc at Aarhus University (Denmark) with Ivan Damgård and Jesper Buus Nielsen and 2 years at University of Warsaw (Poland). I got my Ph.D. in 2013 from the University of Warsaw under the supervision of Stefan Dziembowski.
My research revolves around the theory of computer science, mostly focused on problems inspired by the modern cryptography. We live in the world where cryptographic devices are physical objects that can leak information as well as be tampered with, and I'm excited to partake in the line of research that models and tackles the problems of leakage an tamper resilient cryptography
Research Interests:
Information Theoretic Cryptography
Randomness and Randomness Extractors
Non-Malleable Codes and Secret Sharing
Other Information:
Email: cqtmlo@nus.edu.sg
Supervision:
Eldon Chung (awarded PhD in May'24)
Program Committee member:
Publications:
My Google Scholar page.My DBLP page.
Survey
Survey: Non-malleable code in the split-state model
In Submission
Distributed Samplers D Abram, M Obremski, P Scholl
In submission
On the randomized complexity of range avoidance, with applications to cryptography and metacomplexityE Chung, A Golovnev, Z Li, M Obremski, S Saraogi, N Stephens-Davidowitz
In submission
Published
Improved Reductions from Noisy to Bounded and Probing Leakages via Hockey-Stick Divergences
M Obremski, J Ribeiro, L Roy, FX Standaert, D VenturiCrypto 2024
Invertible Bloom Lookup Tables with Less Memory and Randomness
N Fleischhacker, KG Larsen, M Obremski, M SimkinESA 2024D Aggarwal, N Boddu, R Jain, M ObremskiIEEE Transactions on Information Theory 2024
Extractors: Low Entropy Requirements Colliding With Non-MalleabilityE Chung, M Obremski, D Aggarwal (order randomized)Crypto 2023
Engineering an Efficient DNF Counter
Soos, Aggarwal, Chakraborty, Meel, ObremskiIJCAI 2023
Distributed Shuffling in Adversarial Environments
KG Larsen, M Obremski, M SimkinITC 2023
On Secret Sharing, Randomness, and Random-less Reductions for Secret SharingD Aggarwal, E Chung, M Obremski, J Ribeiro
TCC 2022
Public Randomness Extraction with Ephemeral Roles and Worst-Case CorruptionsJB Nielsen, J Ribeiro, M Obremski (order randomized)Crypto 2022
Two-Source Non-Malleable Extractors and Applications to Privacy Amplification with Tamperable Memory ,
(Old version: Computational and Information-Theoretic Two-Source (Non-Malleable) Extractors)
Non-malleable Codes with rate 1/3 via Rate BoostersD Aggarwal, S Sekar, B Kanukurthi, M Obremski, S L B Obbattu (order randomized)STOC 2022
Algebraic Restriction Codes and their ApplicationsD Aggarwal, N Dottling, J Dujmovic, M Hajiabadi, G Malavolta, M ObremskiITCS 2022, Algorithmica 2023
The Mother of All Leakages: How to Simulate Noisy Leakages via Bounded Leakage (Almost) for Free
G Brian, A Faonio,M Obremski, J Ribeiro, M Simkin, M Skórski, D VenturiEurocrypt 2021, IEEE Transactions on Information Theory 2022A constant rate non-malleable code in the split-state model
D Aggarwal, M ObremskiFOCS 2020Extractors Lower Bounds, Revisited
D Aggarwal, S Guo, M Obremski, J Ribeiro, N Stephens-DavidowitzRandom 2020Non-Malleable Secret Sharing against Bounded Joint-Tampering Attacks in the Plain Model
G Brian, A Faonio, M Obremski, M Simkin, D Venturi CRYPTO 2020Complexity of Estimating Renyi Entropy of Markov Chains
M Obremski, M SkórskiISIT 2020How to Extract Useful Randomness from Unreliable Sources
D Aggarwal, M Obremski, J Ribeiro, L Siniscalchi, I ViscontiEurocrypt 2020Stronger leakage-resilient and non-malleable secret-sharing schemes for general access structures
D Aggarwal, I Damgard, JB Nielsen, M Obremski, E Purwanto, J Ribeiro, M SimkinCRYPTO’19Continuous non-malleable codes in the 8-split-state model
D Aggarwal, N Dottling, JB Nielsen, M Obremski, E PurwantoEurocrypt'19I Damgård, T Kazana, M Obremski, V Raj, L SiniscalchiTCC 2018,Leakage-resilient Algebraic Manipulation Detection Codes with Optimal Parameters
D Aggarwal, T Kazana, M ObremskiISIT 2018M Obremski, M SkorskiISIT 2018Inception makes non-malleable codes stronger
D Aggarwal, T Kazana, M ObremskiTCC 2017Renyi Entropy Estimation Revisited
M Obremski, M SkorskiApprox 2017Non-malleable Reductions and Applications
D Aggarwal, Y Dodis, T Kazana, M ObremskiSTOC 2015Leakage-resilient non-malleable codes
D Aggarwal, S Dziembowski, T Kazana, M ObremskiTCC 2015Non-malleable codes from two-source extractors
S Dziembowski, T Kazana, M ObremskiCRYPTO 2013