IACR News
Here you can see all recent updates to the IACR webpage. These updates are also available:
19 June 2023
Subhadeep Banik, Francesco Regazzoni
Joel Gärtner
In this work we therefore use Regev's reduction to parametrize a cryptosystem, providing a reference as to what parameters are required to actually claim security from this reduction. This requires us to account for the concrete performance of this reduction, allowing the first parametrization of a cryptosystem that is provably secure based only on a conservative hardness estimate for a standard lattice problem. Even though we attempt to optimize the reduction, our system still requires significantly larger parameters than typical LWE-based cryptosystems, highlighting the significant gap between parameters that are used in practice and those for which worst-case reductions actually are applicable.
Nils Fleischhacker, Kasper Green Larsen, Mark Simkin
In this work, we show how to generalize the results of Fleischhacker, Larsen, and Simkin to encryption schemes with arbitrarily small plaintext spaces. Our construction follows the same general ideas laid out in previous works but modifies them in a way that allows compressing the encrypted vectors correctly with high probability, independently of the size of the plaintext space.
Lukáš Folwarczný, Mika Göös, Pavel Hubáček, Gilbert Maystre, Weiqiang Yuan
In particular, we improve over the prior work of Hubáček et al. (2020) in two ways: our result is established via a novel simpler combinatorial technique and applies to a broader class of semi black-box reductions.
Pierre-Antoine Tissot, Lilian Bossuet, Vincent Grosso
James Hsin-yu Chiang, Bernardo David, Mariana Gama, Christian Janos Lebeda
We explore round-differential-privacy in traditional “dark pool” market venues, which promise privacy-preserving trade execution to mitigate front-running; privately submitted trade orders and trade execution are kept private by the trusted venue operator. We observe that dark pools satisfy neither classic nor correlated-output differential privacy; in markets with low trade activity, the adversary may trivially observe recurring, honest trading patterns, and anticipate and front-run future trades. In response, we present the first round-differentially-private market mechanisms that formally mitigate information leakage from all trading activity of a user. This is achieved with fuzzy order matching, inspired by the standard randomized response mechanism; however, this also introduces a liquidity mismatch as buy and sell orders are not guaranteed to execute pairwise, thereby weakening output correlation; this mismatch is compensated for by a round-differentially-private liquidity provider mechanism, which freezes a noisy amount of assets from the liquidity provider for the duration of a privacy epoch, but leaves trader balances unaffected. We propose oblivious algorithms for realizing our proposed market mechanisms with secure multi-party computation (MPC) and implement these in the Scale-Mamba Framework using Shamir Secret Sharing based MPC. We demonstrate practical, round-differentially-private trading with comparable throughput as prior work implementing (traditional) dark pool algorithms in MPC; our experiments demonstrate practicality for both traditional finance and decentralized finance settings.
Brett Hemenway Falk, Daniel Noble, Tal Rabin
Shweta Agrawal, Melissa Rossi, Anshu Yadav, Shota Yamada
In this work, we advance this line of research by providing the first construction of multi-input attribute based encryption (${\sf MIABE}$) for the function class ${\sf NC_1}$ for any constant arity from evasive ${\sf LWE}$. Our construction can be extended to support the function class ${\sf P}$ by using evasive and a suitable strengthening of tensor ${\sf LWE}$. In more detail, our construction supports $k$ encryptors, for any constant $k$, where each encryptor uses the master secret key ${\sf msk}$ to encode its input $(\mathbf{x}_i, m_i)$, the key generator computes a key ${\sf sk}_f$ for a function $f \in {\sf NC}_1$ and the decryptor can recover $(m_1,\ldots,m_k)$ if and only if $f(\mathbf{x}_1,\ldots,\mathbf{x}_k)=1$. The only known construction for ${\sf MIABE}$ for ${\sf NC}_1$ by Agrawal, Yadav and Yamada (Crypto '22) supports arity $2$ and relies on pairings in the generic group model (or with a non-standard knowledge assumption) in addition to ${\sf LWE}$. Furthermore, it is completely unclear how to go beyond arity $2$ using this approach due to the reliance on pairings.
Using a compiler from Agrawal, Yadav and Yamada (Crypto '22), our ${\sf MIABE}$ can be upgraded to multi-input predicate encryption for the same arity and function class. Thus, we obtain the first constructions for constant-arity predicate and attribute based encryption for a generalized class such as ${\sf NC}_1$ or ${\sf P}$ from simple assumptions that may be conjectured post-quantum secure. Along the way, we show that the tensor ${\sf LWE}$ assumption can be reduced to standard ${\sf LWE}$ in an important special case which was not known before. This adds confidence to the plausibility of the assumption and may be of wider interest.
Daniel J. Bernstein, Tung Chou
Formally verifying complete proofs of attack performance is a natural response but crashes into an insurmountable structural problem: there are large gaps between the best proven cost among known attack algorithms and the best conjectured cost among known attack algorithms. Ignoring conjectured speedups would be a security disaster.
This paper presents a case study demonstrating the feasibility and value of successfully formalizing what state-of-the-art attack analyses actually do. The input to this formalization is not a proof, and the output is not a formally verified proof; the formalization process nevertheless enforces clear definitions, systematically accounts for all algorithm steps, simplifies review, improves reproducibility, and reduces the risk of error.
Concretely, this paper's CryptAttackTester (CAT) software includes formal specifications of (1) a general-purpose model of computation and cost metric, (2) various attack algorithms, and (3) formulas predicting the cost and success probability of each algorithm. The software includes general-purpose simulators that systematically compare the predictions to the observed attack behavior in the same model. The paper gives various examples of errors in the literature that survived typical informal testing practices and that would have been immediately caught if CAT-enforced links had been in place.
The case study in CAT is information-set decoding (ISD), the top attack strategy against the McEliece cryptosystem. CAT formalizes analyses of many ISD algorithms, covering interactions between (1) high-level search strategies from Prange, Lee–Brickell, Leon, Stern, Dumer, May–Meurer–Thomae, and Becker–Joux–May–Meurer; (2) random walks from Omura, Canteaut–Chabaud, Canteaut–Sendrier, and Bernstein–Lange–Peters; and (3) speedups in core subroutines such as linear algebra and sorting.
Renaud Dubois
Zeta Avarikioti, Stefan Schmid, Samarth Tiwari
We introduce the first rebalancing approach for PCNs that includes all users, following an “all for one and one for all” design philosophy that yields optimal throughput. The proposed approach introduces a double-auction rebalancing problem, which we term Musketeer, where users can participate as buyers (paying fees to rebalance) or sellers (charging fees to route transactions). The desired properties tailored to the unique characteristics of PCNs are formally defined, including the novel property of cyclic budget balance that is a stronger variation of strong budget balance. Basic results derived from auction theory, including an impossibility and multiple mechanisms that either achieve all desiderata under a relaxed model or sacrifice one of the properties, are presented. We also propose a novel mechanism that leverages time delays as an additional cost to users. This mechanism is provably truthful, cyclic budget balanced, individually rational, and economic efficient but only with respect to liquidity.
Sam Widlund
Mohammad Vaziri, Vesselin Velichkov
Vincent Meyers, Dennis R. E. Gnad, Nguyen Minh Dang, Falk Schellenberg, Amir Moradi, Mehdi B. Tahoori
Jesús García-Rodríguez, Stephan Krenn, Daniel Slamanig
While there are some previous works on bb-ABC in the literature, the state of affairs is not satisfactory. Firstly, in existing work the problem is treated in a very abstract way when it comes to the actual type of biometrics. Thus, it does not provide concrete solutions which allow for assessing their practicality when deployed in a real-world setting. Secondly, there is no formal model which rigorously captures bb-ABC systems and their security requirements, making it hard to assess their security guarantees. With this work we overcome these limitations and provide a rigorous formalization of bb-ABC systems. Moreover, we introduce two generic constructions which offer different trade-offs between efficiency and trust assumptions, and provide benchmarks from a concrete instantiation of such a system using facial biometrics. The latter represents a contact-less biometric feature that provides acceptable accuracy and seems particularly suitable to the above use-case.
16 June 2023
Sydney, Australia, 15 July - 17 July 2024
Submission deadline: 19 February 2024
Notification: 8 April 2024
Sydney, Australia, 15 July - 17 July 2024
Submission deadline: 6 November 2023
Notification: 22 January 2024
Raipur, India, 16 December - 20 December 2023
Submission deadline: 20 July 2023
Notification: 15 September 2023
Department of Informatics, University of Bergen, Norway
There is a vacancy for up to 3 positions as PhD Research Fellow in Informatics – Cryptology at the Department of Informatics. The positions are for a fixed-term period of 3 years with the possibility of a 4th year with compulsory other work (e.g. teaching duties at the Department). The positions are financed by the University of Bergen.
The successful candidates will be supervised by one of the faculty members at the Selmer center, depending on their interests and the nature of the research project.
Potential work tasks related to some of the topics:
- Statistical and algebraic cryptanalysis of modern block and stream ciphers
- Cryptanalysis of lattice-based postquantum cryptography protocols
- Construction of cryptographically optimal functions and related objects
- Design and analysis of symmetric ciphers, cryptographic hash functions and other related primitives
- Design and analysis of error-correcting codes and code-based cryptographic schemes
Please apply by September 15, 2023 through jobbnorge. Full job description available here: https://www.jobbnorge.no/en/available-jobs/job/246889/phd-research-fellow-in-informatics-cryptology-up-to-3-positions
Closing date for applications:
Contact: Assoc. Prof. Nikolay Kaleyski, Department of Informatics, University of Bergen.
More information: https://www.jobbnorge.no/en/available-jobs/job/246889/phd-research-fellow-in-informatics-cryptology-up-to-3-positions
University of St.Gallen, Switzerland
Our research interests are centered around information security and applied cryptography, with the larger goal of safeguarding communications and providing strong privacy guarantees. We are active in several areas, a subset of which include:
- Verifiable computation
- Secure, private and distributed aggregation
- Secure multi-party computation
- Privacy-preserving biometric authentication
- Anonymous credentials
- Distributed and privacy-preserving authentication
The starting date for the position is flexible and come with a very competitive salary. The selection process runs until the suitable candidate has been found. The University of St.Gallen conducts excellent research with international implications. The city of St.Gallen is located one hour from Zurich and offers a high quality of life.
Please apply by 30th June 2023 through the job portal (via link).
Closing date for applications:
Contact: https://jobs.unisg.ch/offene-stellen/postdoc-fellow-in-cryptography-information-security-m-f-d/25ddb9d0-5c47-41ac-8bde-5789dbaca5c4
More information: https://jobs.unisg.ch/offene-stellen/postdoc-fellow-in-cryptography-information-security-m-f-d/25ddb9d0-5c47-41ac-8bde-5789dbaca5c4