IACR News
Here you can see all recent updates to the IACR webpage. These updates are also available:
08 March 2022
CryptoLux Group, University of Luxembourg
The University of Luxembourg invites applications for a Ph.D. position in the general area of symmetric cryptography. The successful candidate will join the CryptoLux group of Prof. Alex Biryukov, which is affiliated to both the Department of Computer Science (DCS) and the Interdisciplinary Center for Security, Reliability and Trust (SnT).
Research Topics- Cryptanalysis and design of cryptographic primitives, lightweight ciphers, hash functions
- Financial cryptography (security of distributed ledgers, smart contracts)
- Privacy-enhancing technologies (Tor-like networks, privacy for cryptocurrencies, blockchains)
- White-box cryptography
- M.Sc. degree in computer science or applied mathematics with outstanding grades (GPA >= 85%)
- Strong mathematical and/or algorithmic CS background
- Some background in cryptography or information security
- Good programming skills (C/C++, Python, math tools, etc.)
- Fluent written and verbal communication skills in English
The University of Luxembourg offers a Ph.D. study program with an initial contract of 36 months, with a further possible 1-year extension if required. The successful candidate will work in one of the most international universities in the world and will have a chance to participate in a well-known security research center. The position will be available from April 2022.
Applications, written in English, should be sent by email to alex.biryukov@uni.lu. The application material should include a curriculum vitae (with photo, educational background, work experience), a brief research statement and topics of particular interest to the candidate (max. 1 page), a transcript of all modules and results from university-level courses taken (with overall GPAs) and contact information for 2-3 references.
Application deadline: 15 March 2022. Early submission is encouraged; applications will be processed upon arrival.
Closing date for applications:
Contact: Prof. Alex Biryukov (email: alex.biryukov@uni.lu)
07 March 2022
Shweta Agrawal, Fuyuki Kitagawa, Anuja Modi, Ryo Nishimaki, Shota Yamada, Takashi Yamakawa
- We construct an adaptively secure (AD-SIM) FE for Turing machines, supporting dynamic bounded collusion, from sub-exponential LWE. This improves the result of Agrawal et al. which achieved only non-adaptive (NA-SIM) security in the dynamic bounded collusion model.
- Towards achieving the above goal, we construct a ciphertext policy FE scheme (CPFE) for circuits of unbounded size and depth, which achieves AD-SIM security in the dynamic bounded collusion model from IBE and laconic oblivious transfer (LOT). Both IBE and LOT can be instantiated from a large number of mild assumptions such as the computational Diffie-Hellman assumption, the factoring assumption, and polynomial LWE.
- We construct an AD-SIM secure FE for Turing machines, supporting dynamic bounded collusions, from LOT, ABE for NC1 (or NC) and private information retrieval (PIR) schemes which satisfy certain properties. This significantly expands the class of assumptions on which AD-SIM secure FE for Turing machines can be based. In particular, it leads to new constructions of FE for Turing machines including one based on polynomial LWE and one based on the combination of the bilinear decisional Diffie-Hellman assumption and the decisional Diffie-Hellman assumption on some specific groups. In contrast the only prior construction by Agrawal et al. achieved only NASIM security and relied on sub-exponential LWE.
To achieve the above result, we define the notion of CPFE for read only RAM programs and succinct FE for LOT, which may be of independent interest.
- We also construct an ABE scheme for Turing machines which achieves AD-IND security in the standard model supporting dynamic bounded collusions. Our scheme is based on IBE and LOT. Previously, the only known candidate that achieved AD-IND security from IBE by Goyal et al. relied on the random oracle model.
Damiano Abram, Peter Scholl
Zvika Brakerski, Pedro Branco, Nico Döttling, Sihang Pu
To achieve rate-$1$ both on the receiver's and sender's end, we use the LPN assumption, with slightly sub-constant noise rate $1/m^{\epsilon}$ for any $\epsilon>0$ together with either the DDH, QR or LWE assumptions. In terms of efficiency, our protocols only rely on linear homomorphism, as opposed to the FHE-based solution which inherently requires an expensive ``bootstrapping'' operation. We believe that in terms of efficiency we compare favorably to existing batch-OT protocols, while achieving superior communication complexity. We show similar results for Oblivious Linear Evaluation (OLE).
For our DDH-based solution we develop a new technique that may be of independent interest. We show that it is possible to ``emulate'' the binary group $\mathbb{Z}_2$ (or any other small-order group) inside a prime-order group $\mathbb{Z}_p$ in a function-private manner. That is, $\mathbb{Z}_2$ operations are mapped to $\mathbb{Z}_p$ operations such that the outcome of the latter do not reveal additional information beyond the $\mathbb{Z}_2$ outcome. Our encoding technique uses the discrete Gaussian distribution, which to our knowledge was not done before in the context of DDH.
Cyprien Delpech de Saint Guilhem, Emmanuela Orsini, Titouan Tanguy, Michiel Verbauwhede
Shahar P. Cohen, Moni Naor
1. Breaking the $ \Omega(\sqrt n) $ bound in the simultaneous message case or the $ \Omega(\log n) $ bound in the interactive communication case, implies the existence of distributional collision-resistant hash functions (dCRH). This is shown using techniques from Babai and Kimmel (CCC '97). Note that with a CRH the lower bounds can be broken.
2. There are no protocols of constant communication in this preset randomness settings (unlike the plain public randomness model).
The other model we study is that of a stateful ``free talk", where participants can communicate freely before the inputs are chosen and may maintain a state, and the communication complexity is measured only afterwards. We show that efficient protocols for equality in this model imply secret key-agreement protocols in a constructive manner. On the other hand, secret key-agreement protocols imply optimal (in terms of error) protocols for equality.
Peihan Miao, Sikhar Patranabis, Gaven Watson
In this paper, we bridge this gap by showing the first feasibility results for realizing unidirectional UE and PRE from a new generic primitive that we call Key and Plaintext Homomorphic Encryption (KPHE) – a public-key encryption scheme that supports additive homomorphisms on its plaintext and key spaces simultaneously. We show that KPHE can be instantiated from DDH or LWE. This yields, in particular, the first constructions of unidirectional UE and PRE from DDH, as well as the first constructions of unidirectional UE and PRE from LWE that do not resort to FHE or lattice trapdoors.
Our constructions achieve the strongest notions of post-compromise security in the standard model. Our UE schemes also achieve “backwards-leak directionality” of key updates (a notion we discuss is equivalent, from a security perspective, to that of unidirectionality with no-key updates). Our results establish (somewhat surprisingly) that unidirectional UE and PRE schemes satisfying such strong security notions do not, in fact, require stronger/more structured cryptographic assumptions as compared to bidirectional schemes.
Muhammad ElSheikh, Amr M. Youssef
Ashrujit Ghoshal, Ilan Komargodski
In this work, we confirm the STB conjecture in many new parameter settings. For instance, in one result, we show that the conjecture holds for all constant values of $B$, significantly extending the result of Akshima et al. Further, using combinatorial properties of graphs, we are able to confirm the conjecture even for super constant values of $B$, as long as some restriction is made on $S$. For instance, we confirm the conjecture for all $B \le T^{1/4}$ as long as $S \le T^{1/8}$. Technically, we develop structural characterizations for bounded-length collisions in MD hashing that allow us to give a compression argument in which the number of cases needed to be handled does not explode.
Ittai Abraham, Danny Dolev, Ittay Eyal, Joseph Y. Halpern
We propose a more robust approach that we call epsilon-sure Nash equilibrium, in which each miner's behavior is almost always a strict best response, and present Colordag, the first blockchain protocol that is an epsilon-sure Nash equilibrium for miners with less than 1/2 of the mining power. To achieve this, Colordag utilizes three techniques. First, it assigns blocks colors; rewards are assigned based on each color separately. By choosing sufficiently many colors, we can make sensitivity to network latency negligible. Second, Colordag penalizes forking---intentional bifurcation of the blockdag. Third, Colordag prevents miners from retroactively changing rewards. All this results in an epsilon-sure Nash equilibrium: Even when playing an extremely strong adversary with perfect knowledge of the future (specifically, when agents will generate blocks and when messages will arrive), correct behavior is a strict best response with high probability.
Olivier Blazy, Sayantan Mukherjee, Huyen Nguyen, Duong Hieu Phan, Damien Stehle
Marina Krček, Thomas Ordas, Daniele Fronte, Stjepan Picek
To negate the effect of variation, we propose a novel method combining memetic algorithm with machine learning approach called a decision tree. Our approach improves the memetic algorithm by using prior knowledge of the target introduced in the initial phase of the memetic algorithm. In our experiments, the decision tree rules enhance the performance of the memetic algorithm by finding more interesting faults on different samples of the same target. Our approach shows more than two orders of magnitude better performance than random search and up to 60% better performance than previous state-of-the-art results with a memetic algorithm. Another advantage of our approach is human-readable rules, allowing the first insights into the explainability of target characterization for laser fault injection.
Ben Smyth, Michael R. Clarkson
Yu Long Chen, Avijit Dutta, Mridul Nandi
Nick Frymann, Daniel Gardham, Mark Manulis
We present two approaches, called remote and direct delegation of WebAuthn credentials, maintaining the standard's properties. Both approaches are compatible with Yubico's recent Asynchronous Remote Key Generation (ARKG) primitive proposed for backing up credentials. For remote delegation, the account owner stores delegation credentials at the relying party on behalf of proxies, whereas the direct variant uses a delegation-by-warrant approach, through which the proxy receives delegation credentials from the account owner and presents them later to the relying party. To realise direct delegation we introduce Proxy Signature with Unlinkable Warrants (PSUW), a new proxy signature scheme that extends WebAuthn's unlinkability property to proxy users and can be constructed generically from ARKG.
We discuss an implementation of both delegation approaches, designed to be compatible with WebAuthn, including extensions required for CTAP, and provide a software-based prototype demonstrating overall feasibility. On the performance side, we observe only a minor increase of a few milliseconds in the signing and verification times for delegated WebAuthn credentials based on ARKG and PSUW primitives. We also discuss additional functionality, such as revocation and permissions management, and mention usability considerations.
Sílvia Casacuberta, Julia Hesse, Anja Lehmann
Jakub Breier, Xiaolu Hou
Irem Keskinkurt Paksoy, Murat Cenk
Yanhong Fan,Muzhou Li,Chao Niu,Zhenyu Lu,Meiqin Wang
Nir Bitansky, Zvika Brakerski, Yael Tauman Kalai
We initiate the study of constructive quantum reductions and present positive and negative results for converting large classes of classical reductions to the post-quantum setting in a constructive manner. We show that any non-interactive non-adaptive reduction from assumptions with a polynomial solution space (such as decision assumptions) can be made post-quantum constructive. In contrast, assumptions with super-polynomial solution space (such as general search assumptions) cannot be generally converted.
Along the way, we make several additional contributions:
1. We put forth a framework for reductions (or general interaction) with stateful solvers for a computational problem, that may change their internal state between consecutive calls. We show that such solvers can still be utilized. This framework and our results are meaningful even in the classical setting. 2. A consequence of our negative result is that quantum auxiliary input that is useful against a problem with a super-polynomial solution space cannot be generically ``restored'' post-measurement. This shows that the novel rewinding technique of Chiesa et al. (FOCS 2021) is tight in the sense that it cannot be extended beyond a polynomial measurement space.