IACR News
Here you can see all recent updates to the IACR webpage. These updates are also available:
14 October 2022
Jiangshan Long, Chenxu Wang, Changhai Ou, Zhu Wang, Yongbin Zhou, Ming Tang
Haruhisa Kosuge, Keita Xagawa
Sam Gunn, Nathan Ju, Fermi Ma, Mark Zhandry
Commitments to quantum states open the door to many new cryptographic possibilities. Our flagship application of a succinct QSC is a quantum-communication version of Kilian's succinct arguments for any language that has quantum PCPs with constant error and polylogarithmic locality. Plugging in the PCP theorem, this yields succinct arguments for NP under significantly weaker assumptions than required classically; moreover, if the quantum PCP conjecture holds, this extends to QMA. At the heart of our security proof is a new rewinding technique for extracting quantum information.
Mingxun Zhou, Elaine Shi, T-H. Hubert Chan, Shir Maimon
Despite the promises of differential obliviousness (DO), a significant barrier that hinders its broad application is the lack of composability. In particular, when we apply one DO algorithm to the output of another DO algorithm, the composed algorithm may no longer be DO (with reasonable parameters). More specifically, the outputs of the first DO algorithm on two neighboring inputs may no longer be neighboring, and thus we cannot directly benefit from the DO guarantee of the second algorithm.
In this work, we are the first to explore a theory of composition for differentially oblivious algorithms. We propose a refinement of the DO notion called $(\epsilon, \delta)$-neighbor-preserving-DO, or $(\epsilon, \delta)$-NPDO for short, and we prove that our new notion indeed provides nice compositional guarantees. In this way, the algorithm designer can easily track the privacy loss when composing multiple DO algorithms.
We give several example applications to showcase the power and expressiveness of our new NPDO notion. One of these examples is a result of independent interest: we use the compositional framework to prove an optimal privacy amplification theorem for the differentially oblivious shuffle model. In other words, we show that for a class of distributed differentially private mechanisms in the shuffle-model, one can replace the perfectly secure shuffler with a DO shuffler, and nonetheless enjoy almost the same privacy amplification enabled by a shuffler.
Gabrielle De Micheli, Daniele Micciancio
Binyi Chen, Benedikt Bünz, Dan Boneh, Zhenfei Zhang
We present HyperPlonk, an adaptation of Plonk to the boolean hypercube, using multilinear polynomial commitments. HyperPlonk retains the flexibility of Plonk but provides several additional benefits. First, it avoids the need for an FFT during proof generation. Second, and more importantly, it supports custom gates of much higher degree than Plonk without harming the running time of the prover. Both of these can dramatically speed up the prover's running time. Since HyperPlonk relies on multilinear polynomial commitments, we revisit two elegant constructions: one from Orion and one from Virgo. We show how to reduce the Orion opening proof size to less than 10kb (an almost factor 1000 improvement) and show how to make the Virgo FRI-based opening proof simpler and shorter.
Marijn F. Stollenga
We introduce Proof-of-Space Search (PoSS) which embraces Hellman's time-memory trade-off to create a much simpler algorithm that avoids the Nothing-at-Stake problem. Additionally, we greatly stabilise block-times using a novel dynamic Logarithmic Embargo (LE) rule. Combined, we show that PoSSLE is a simple and stable alternative to PoW with many of its properties, while being an estimated 10 times more energy efficient and sustaining consistent block times.
Paul Bunn, Eyal Kushilevitz, Rafail Ostrovsky
In this paper, we present a protocol for the NIAR model that improves upon the results from [SW21] in two ways:
- Improved computational efficiency (quadratic to near linear): Our protocol matches the communication complexity of [SW21] for each sender/receiver, while reducing the computational overhead for the router to polylog overhead instead of linear overhead.
- Relaxation of assumptions: Security of the protocol in [SW21] relies on the Decisional Linear assumption in bilinear groups; while security for our protocol follows from the existence of any rate-1 oblivious transfer (OT) protocol (instantiations of this primitive are known to exist under DDH, QR and LWE [DGI19,GHO20]).
Miguel Ambrona, Marc Beunardeau, Anne-Laure Schmitt, Raphaël R. Toledo
Christina Boura, Nicolas David, Rachelle Heim Boissier, Maria Naya-Plasencia
Lucjan Hanzlik, Julian Loss, Benedikt Wagner
In this paper, we introduce a blind signature scheme that eliminates all of the above drawbacks at the same time. Namely, we show a round-optimal, concretely efficient, concurrently secure, and stateless blind signature scheme in which communication and computation are independent of the number of signing interactions. Our construction also naturally generalizes to the partially blind signature setting.
Our scheme is based on the CDH assumption in the asymmetric pairing setting and can be instantiated using a standard BLS curve. We obtain signature and communication sizes of 9KB and 36KB, respectively. To further improve the efficiency of our scheme, we show how to obtain a scheme with better amortized communication efficiency. Our approach batches the issuing of signatures for multiple messages.
Xiutao Feng, Xiaoshan GAO, Zhangyi WANG, Xiangyong ZENG
Hoeteck Wee
Shweta Agrawal, Simran Kumari, Anshu Yadav, Shota Yamada
1. Public Trace Setting: We provide a construction which (i) achieves optimal parameters, (ii) supports embedding identities (from an exponential space) in user secret keys, (iii) relies on polynomial hardness assumptions, namely compact functional encryption (${\sf FE}$) and a key-policy attribute based encryption (${\sf ABE}$) with special efficiency properties constructed by Boneh et al. (Eurocrypt 2014) from Learning With Errors (${\sf LWE}$), and (iv) enjoys adaptive security with respect to the revocation list. The previous best known construction by Nishimaki, Wichs and Zhandry (Eurocrypt 2016) which achieved optimal parameters and embedded identities, relied on indistinguishability obfuscation, which is considered an inherently subexponential assumption and achieved only selective security with respect to the revocation list. 2. Secret Trace Setting: We provide the first construction with optimal ciphertext, public and secret key sizes and embedded identities from any assumption outside Obfustopia. In detail, our construction relies on Lockable Obfuscation which can be constructed using ${\sf LWE}$ (Goyal, Koppula, Waters and Wichs, Zirdelis, Focs 2017) and two ${\sf ABE}$ schemes: (i) the key-policy scheme with special efficiency properties by Boneh et al. (Eurocrypt 2014) and (ii) a ciphertext-policy ${\sf ABE}$ for ${\sf P}$ which was recently constructed by Wee (Eurocrypt 2022) using a new assumption called evasive and tensor ${\sf LWE}$. This assumption, introduced to build an ${\sf ABE}$, is believed to be much weaker than lattice based assumptions underlying ${\sf FE}$ or ${\sf iO}$ -- in particular it is required even for lattice based broadcast, without trace.
Moreover, by relying on subexponential security of ${\sf LWE}$, both our constructions can also support a super-polynomial sized revocation list, so long as it allows efficient representation and membership testing. Ours is the first work to achieve this, to the best of our knowledge.
Trey Li
Dana Dachman-Soled, Huijing Gong, Tom Hanson, Hunter Kippen
Trey Li
11 October 2022
IST Austria, TU Graz, TU Vienna, University of Vienna, University of Klagenfurt
We offer 14 interdisciplinary and interconnected research projects at the intersection of Cryptography, System Security, and Formal Methods. The projects are listed below, each is led by a PI in collaboration with at least another member of the SPyCoDe faculty
- Cross-Layer Security for Blockchain Consensus (Pietrzak, ISTA)
- Cross-Layer Side-Channel Security (Gruss, TU Graz)
- Cryptographic Techniques for Blockchain Security (Andreeva, TU Vienna)
- Cryptographic Techniques for System Security (Eichlseder, TU Graz)
- Enforcement of Security and Privacy Policies across Multi-Party Code (Lindorfer, TU Vienna)
- Formal Verification of Side Channel Properties (Bloem, TU Graz)
- Game-Theoretic Models for Blockchain Applications (Fuchsbauer, TU Vienna)
- Interface Theory for Security and Privacy Employer (Henzinger, ISTA)
- Logic-based Reasoning for Hyperproperties (Kovács, TU Vienna)
- Quantitative and Probabilistic Security Analysis (Oswald, U Klagenfurt)
- Secure Blockchains in Network Transition Periods (Ullrich, U Vienna)
- Secure Network and Hardware for Efficient Blockchains (ISTA, Kokoris-Kogias)
- Security and Privacy by Design for Smart Contracts (Maffei, TU Vienna)
- Side-Channel Resistant System Design (Mangard, Graz)
Closing date for applications:
Contact: Olha Denisova recruiting-questions@spycode.at for questions about the application. Any of the affiliated faculty (https://spycode.at/people/) with questions about their projects.
More information: https://spycode.at/apply/
EPFL, Switzerland
The Laboratory for Computation Security at EPFL, led by Prof. Alessandro Chiesa, is hiring a Cryptography Engineer.
You will join the lab as a full-time developer, and collaborate with other researchers (graduate students and postdoctoral scholars) to create high-quality open-source software that realizes complex cryptographic protocols.
The group's research include, but is not limited to, computational complexity, zero-knowledge proofs, succint non-interactive arguments (SNARGs) and privacy-enhancing technologies (such as peer-to-peer private payment systems and smart contracts).
Responsabilities:- Realizing secure and efficient implementations of new cryptographic protocols
- Developing and contributing to open-source libraries for cryptographic proofs
- Helping prepare pedagogical material (software projects for courses)
- Master's degree in Computer Science (or equivalent engineering experience)
- Experience in software development with Rust and C++
- Knowledge of basic algebra (groups, finite fields, ...) and basic cryptography (hash functions, encryption, ...)
Closing date for applications:
Contact: Alessandro Chiesa
More information: https://recruiting.epfl.ch/Vacancies/2318/Description/2
University of South Florida, St Petersburg, Florida
Closing date for applications:
Contact: Jean-François Biasse
More information: https://www.mathjobs.org/jobs/list/20917