IACR News
Here you can see all recent updates to the IACR webpage. These updates are also available:
15 November 2020
Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, Peter Scholl
We present efficient constructions of PCFs for a broad class of useful correlations, including oblivious transfer and multiplication triple correlations, from a variable-density variant of the Learning Parity with Noise assumption (VDLPN). We also present several cryptographic applications that motivate our efficient PCF constructions.
The VDLPN assumption is independently motivated by two additional applications. First, different flavors of this assumption give rise to weak pseudorandom function candidates in depth-2 $\mathsf{AC}^0[\oplus]$ that can be conjectured to have subexponential security, matching the best known learning algorithms for this class. This is contrasted with the quasipolynomial security of previous (higher-depth) $\mathsf{AC}^0[\oplus]$ candidates. We support our conjectures by proving resilience to several classes of attacks. Second, VDLPN implies simple constructions of pseudorandom generators and weak pseudorandom functions with security against XOR related-key attacks.
Congwei Zhou, Bin Hu, Jie Guan
Jamie Cui, Chaochao Chen, Li Wang
New Insights On Differential And Linear Bounds Using Mixed Integer Linear Programming (Full Version)
Anubhab Baksi
Our analysis shows, there are SBoxes for which the CH modelling can yield incorrect modelling. As such, using the CH modelling may lead to incorrect differential or linear bounds. This arises from the observation that although the CH is generated for a certain set of points, there can be points outside this set which also satisfy all the inequalities of the CH. As apparently no variant of the CH modelling can circumvent this problem, we propose a new modelling for differential and linear bounds. Our modelling makes use of every points of interest individually. This modelling works for an arbitrary SBox, and is able to find the exact bound.
Additionally, we also explore the possibility of using redundant constraints, such that the run time for an MILP solver can be reduced while keeping the optimal result unchanged. For this purpose, we revisit the CH modelling and use the CH constraints as redundant constraints (on top of our usual constraints, which ensure the aforementioned problem does not occur). In fact, we choose two heuristics from the convex hull modelling. The first uses all the inequalities of a convex hull, while second uses a reduced number of inequalities. Apart from that, we also propose to use the solutions for the smaller rounds as another heuristic to find the optimal bound for a higher round.
With our experiments on round-reduced GIFT-128, we show it is possible to reduce the run time a few folds using a suitable choice of redundant constraints. Further, we observe the necessity to consider separate heuristics for the differential and linear cases. We also present the optimal linear bounds for 11- and 12-rounds of GIFT-128, extending from the best-known result of 10-rounds.
Daniele Micciancio, Jessica Sorrell
Prior work of Brakerski and D\"{o}ttling uses transference theorems to show that either a lattice or its dual must have short vectors, the existence of which guarantees lossy encryption for encodings with respect to that lattice, and therefore statistical sender privacy. In the case of ideal lattices from embeddings of cyclotomic integers, the existence of one short vector implies the existence of many, and therefore encryption with respect to either a lattice or its dual is guaranteed to ``lose" more information about the message than can be ensured in the case of general lattices. This additional structure of ideals of cyclotomic integers allows for efficiency improvements beyond those that are typical when moving from the generic to ideal lattice setting, resulting in smaller message sizes for sender and receiver, as well as a protocol that is simpler to describe and analyze.
Antigoni Polychroniadou, Yifan Song
Ofer Grossman, Justin Holmgren, Eylon Yogev
Carsten Baum, Alex J. Malozemoff, Marc Rosen, Peter Scholl
We present an interactive zero-knowledge proof system for arithmetic circuits, called Mac'n'Cheese, with a focus on supporting large circuits while using low computational resources. Our work follows the commit-and-prove paradigm instantiated using information-theoretic MACs based on vector oblivious linear evaluation to achieve high efficiency. We additionally show how to optimize disjunctions, with a general OR transformation for proving the disjunction of $m$ statements that has communication complexity proportional to the longest statement (plus an additive term logarithmic in $m$). These disjunctions can further be nested, allowing efficient proofs about complex statements with many levels of disjunctions. We also show how to make Mac'n'Cheese non-interactive (after a preprocessing phase) using the Fiat-Shamir transform, and with only a small degradation in soundness.
We have implemented the non-interactive variant of the online phase of Mac'n'Cheese and can achieve 2.5 $\mu s$ per multiplication gate while requiring a minimal amount of memory: for proving the knowledge of two 512-by-512 matrices that equal some fixed public matrix we require less than 36~MB of memory for both the prover and verifier. We achieve this through a streaming approach which is compatible with our disjunctions over sub-circuits.
Michael Walter
Chen-Da Liu-Zhang, Varun Maram, Ueli Maurer
This paper investigates the achievability of broadcast in 'general networks', i.e., networks where only some subsets of minicast channels may be available, thereby addressing open problems posed in [JMS12,Ray15]. To that end, we propose a hierarchy over all possible general adversaries, and identify for each class of general adversaries 1) a set of minicast channels that are necessary to achieve broadcast and 2) a set of minicast channels that are sufficient to achieve broadcast. In particular, this allows us to derive bounds on the amount of $b$-minicasts that are necessary and that suffice towards constructing broadcast in general $b$-minicast networks.
Palash Sarkar
Johannes Mueller
In this paper, we revisit VoteAgain from a security perspective. We show that for each security property, i.e., ballot privacy, verifiability, and coercion-resistance, there exists (at least) one attack which breaks the respective property under the trust assumptions for which the property was claimed to hold true. But our results are even more disillusioning: first, there exists a voting authority in VoteAgain which needs to be trusted for all security properties; second, all voting authorities in VoteAgain need to be trusted for coercion-resistance.
It will be interesting and challenging future work to mitigate, or even remove, these undesirably strong trust assumptions without affecting the usability and superior efficiency of VoteAgain.
Kyoungbae Jang, Hyunjun Kim, Siwoo Eum, Hwajeong Seo
Chen-Dong Ye, Tian Tian
Syh-Yuan Tan, Thomas Gross
Stéphanie Delaune, Patrick Derbez, Paul Huynh, Marine Minier, Victor Mollimard, Charles Prud'homme
In this paper, we compare existing automatic tools to find the best differential characteristic on the SKINNY block cipher. As usually done in the literature, we split this search in two stages denoted by Step 1 and Step 2. In Step 1, each difference variable is abstracted with a Boolean variable and we search for the value that minimizes the trail weight, whereas Step 2 tries to instantiate each difference value while maximizing the overall differential characteristic probability. We model Step 1 using a MILP tool, a SAT tool, an ad-hoc method and a CP tool based on the Choco-solver library and provide performance results. Step 2 is modeled using the Choco-solver as it seems to outperform all previous methods on this stage.
Notably, for SKINNY-128 in the SK model and for 13 rounds, we retrieve the results of Abdelkhalek et al. within a few seconds (to compare with 16 days) and we provide, for the first time, the best differential related-tweakey characteristic up to respectively 14 and 12 rounds for the TK1 and TK2 models.
Beer Sheva, Israel, 8 July - 9 July 2021
14 November 2020
The conference program and details on how to join can be found at https://tcc.iacr.org/2020/program.php
13 November 2020
University of St. Gallen, Switzerland
Topics of research interest include:
- Verifiable computation
- Secure Multi Party Computation
- Privacy-preserving authentication
- Cryptographic primitives
- Publications in top venues in Cryptography and Information Security
- Young researchers who hold a doctorate (PhD) or will complete their doctorate within the next six months
- Young researchers with a completed doctorate (PhD) have been awarded the degree at most two years before 15th of Jan 2021.
Deadline for project proposal: 15th of Jan. 2021
To Apply: Send your cv and research statement to aikaterini.mitrokotsa@unisg.ch with subject ''Post-doc Fellowship'' by the 9th of Dec. 2020
Closing date for applications:
Contact: Katerina Mitrokotsa
CryptoLux Group, University of Luxembourg
The CryptoLux group of the University of Luxembourg has a vacancy for a post-doctoral researcher in the area of symmetric cryptography. The successful candidate will contribute to a research project entitled Analysis and Protection of Lightweight Cryptographic Algorithms (APLICA), which is funded by the Luxembourgish Fonds National de la Recherche and the German Research Foundation. Starting in 2021, APLICA will run over a period of 3 years as a joint research project between the CryptoLux group and the Workgroup for Symmetric Cryptography of Ruhr-University Bochum. The mission of the APLICA project is to develop new cryptanalytic techniques for lightweight authenticated encryption algorithms and hash functions, and to design and implement new countermeasures against side-channel attacks that are suitable for constrained devices.
Candidates must have a Ph.D. degree in symmetric cryptography or a closely related field. Preference will be given to candidates with a strong publication record that includes at least one paper at an IACR conference/workshop or one of the top-4 security conferences. Experience in software development for embedded systems or mounting side-channel attacks is a plus. Candidates with an interest to conduct research in one of the following areas are particularly encouraged to apply:
- Cryptanalysis of authenticated encryption algorithms or hash functions
- Leakage resilience or leakage reduction by design (e.g. modes of operation)
- Security evaluation of leakage-resilient primitives or constructions
The position is available from Jan. 2021 on basis of a fixed-term contract for 3 years. The University of Luxembourg offers excellent working conditions and a highly competitive salary. Interested candidates are invited to send their application by email to Alex Biryukov before Dec. 15, 2020 (early submission is strongly encouraged, applications will be processed upon receipt). The application material should contain a cover letter explaining the candidate's research interests, a CV (incl. photo), a list of publications, scans of diploma certificates, and contact details of 3 references
Closing date for applications:
Contact: Prof. Alex Biryukov (alex.biryukov@uni.lu)
More information: https://www.fnr.lu/projects/analysis-and-protection-of-lightweight-cryptographic-algorithms/