IACR News
Here you can see all recent updates to the IACR webpage. These updates are also available:
11 August 2022
Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, Peter Scholl
In this work, we design a new class of efficient PCGs based on different flavors of the ring-LPN assumption. Our new PCGs can generate OLE correlations, authenticated multiplication triples, matrix product correlations, and other types of useful correlations over large fields. These PCGs are more efficient by orders of magnitude than the previous constructions and can be used to improve the preprocessing phase of many existing MPC protocols.
Kai Hu, Thomas Peyrin, Meiqin Wang
In this paper, we propose a systematic method to find all IDs for SPN block ciphers. The idea is to partition the whole difference pair space into lots of small disjoint sets, each of which has a representative difference pair. All difference pairs in one small set are possible if its representative pair is possible, and this can be conveniently checked by the MILP model. In this way, the overall search space is drastically reduced to a practical size by excluding the sets containing no IDs. We then examine the remaining difference pairs to identify all IDs (if some IDs exist). If our method cannot find any ID, the target cipher is proved free of ID distinguishers.
Our method works especially well for SPN ciphers with block size 64. We apply our method to SKINNY-64 and successfully find all 432 and 12 truncated IDs (we find all IDs but all of them can be assembled into certain truncated IDs) for 11 and 12 rounds, respectively. We also prove, for the first time, that 13-round SKINNY-64 is free of ID distinguishers even when considering the differential transitions through the Difference Distribution Table (DDT). Similarly, we find all 12 truncated IDs (all IDs are assembled into 12 truncated IDs) for 13-round CRAFT and prove there is no ID for 14 rounds. For SbPN cipher GIFT-64, we prove that there is no ID for 8 rounds.
For SPN ciphers with larger block sizes, we show that our idea is also useful to strengthen the current search methods. For example, if we consider the Sbox to be ideal and only consider the branch number information of the diffusion matrix, we can find all 6,750 truncated IDs for 6-round Rijndael-192 in 1 second and prove that there is no truncated ID for 7 rounds. Previously, we need to solve approximately $2^{48}$ MILP models to achieve the same goal. For GIFT-128, we exhausted all difference patterns that have an active superbox in the plaintext and ciphertext and proved there is no ID of such patterns for 8 rounds.
Although we have searched for a larger or even full space for IDs, no longer ID distinguishers have been found. This implies the reasonableness of the intuition that a small number (usually one or two) of active bits/words at the beginning and end of an ID will be the longest.
Tommy Hollenberg, Mike Rosulek, Lawrence Roy
We then focus on a smaller subclass of block cipher modes, which iterate over the blocks of the plaintext, repeatedly applying the same Linicrypt program. For these Linicrypt block cipher modes, we are able to give a sound and complete characterization of IND\$-CPA security. Our characterization is linear-algebraic in nature and is easy to check for a candidate mode. Interestingly, we prove that a Linicrypt block cipher mode is secure if and only if it is secure against adversaries who choose all-zeroes plaintexts.
Rachit Garg, Dakshita Khurana, George Lu, Brent Waters
All prior works on non-interactive non-malleable or CCA commitments without setup first construct a "base" scheme for a relatively small identity/tag space, and then build a tag amplification compiler to obtain commitments for an exponential-sized space of identities. Prior black-box constructions either add multiple rounds of interaction (Goyal, Lee, Ostrovsky and Visconti, FOCS 2012) or only achieve security against uniform adversaries (Garg, Khurana, Lu and Waters, Eurocrypt 2021).
Our key technical contribution is a novel tag amplification compiler for CCA commitments that replaces the non-interactive proof of consistency required in prior work. Our construction satisfies the strongest known definition of non-malleability, i.e., CCA2 (chosen commitment attack) security. In addition to only making black-box use of the base scheme, our construction replaces sub-exponential NIWIs with sub-exponential hinting PRGs, which can be obtained based on assumptions such as (sub-exponential) CDH or LWE.
Magali Bardet, Pierre Briaud, Maxime Bros, Philippe Gaborit, Jean-Pierre Tillich
However, we prove here that the analysis performed in [2] for one of these attacks which consists in mixing the MaxMinors modeling with the Support-Minors modeling to solve RD is too optimistic and leads to underestimate the overall complexity. This is done by exhibiting linear dependencies between these equations and by considering an Fqm version of these modelings which turns out to be instrumental for getting a better understanding of both systems. Moreover, by working over Fqm rather than over Fq, we are able to drastically reduce the number of variables in the system and we (i) still keep enough algebraic equations to be able to solve the system, (ii) are able to analyze rigorously the complexity of our approach. This new approach may improve the older MaxMinors approach on RD from [1,2] for certain parameters. We also introduce a new hybrid approach on the Support-Minors system whose impact is much more general since it applies to any MinRank problem. This technique improves significantly the complexity of the Support-Minors approach for small to moderate field sizes.
References:
[1] An Algebraic Attack on Rank Metric Code-Based Cryptosystems, Bardet, Briaud, Bros, Gaborit, Neiger, Ruatta, Tillich, EUROCRYPT 2020.
[2] Improvements of Algebraic Attacks for solving the Rank Decoding and MinRank problems, Bardet, Bros, Cabarcas, Gaborit, Perlner, Smith-Tone, Tillich, Verbel, ASIACRYPT 2020.
Ivan De Oliveira Nunes, Peter Rindal, Maliheh Shirvanian
In this work we develop Oblivious Extractors: a new construction that allows an Authenticator to authenticate a user without requiring neither the user to send a biometric to the Authenticator, nor the server to send the HD to the client. Oblivious Extractors provide concrete security advantages for biometric-based authentication systems. From the perspective of secure storage, an oblivious extractor is as secure as its non-oblivious fuzzy extractor counterpart. In addition, it enhances security against aforementioned statistical and re-usability attacks. To demonstrate the construction’s practicality, we implement and evaluate a biometric-based authentication prototype using Oblivious Extractors.
Nina Bindel, Cas Cremers, Mang Zhao
Jiaojiao Wu, Jianfeng Wang, Xinwei Yong, Xinyi Huang, Xiaofeng Chen
09 August 2022
University of Birmingham, UK
The School of Computer Science at the University of Birmingham seeks to recruit outstanding computer scientists for the role of Assistant Professor / Associate Professor, with a particular interest in the areas of Systems Security and/or Hardware Security.
The Birmingham Centre for Cyber Security and Privacy conducts internationally competitive research in all aspects of cyber security and privacy. The Centre is recognised by EPSRC/NCSC as an Academic Centre of Excellence in Cyber Security Research, and its MSc in Cyber Security is NSCS-accredited.
We encourage applications that either complement our existing strengths or open-up new areas with strong potential for collaboration. Candidates are welcome from both early career and established stages with an emphasis on a growing international reputation. We provide an inclusive environment and are committed to a recruitment process free from discrimination. We believe that supporting a variety of career trajectories is vital for world class computer science to flourish.
For further information and to apply (closing date 16 August 2022), use the following URL: https://bham.taleo.net/careersection/external/jobdetail.ftl?job=220001IU&tz=GMT%2B01%3A00&tzname=Europe%2FLondon
Closing date for applications:
Contact: For informal enquiries, contact David Oswald (d.f.oswald@bham.ac.uk) or Mark Ryan (m.d.ryan@bham.ac.uk)
More information: https://bham.taleo.net/careersection/external/jobdetail.ftl?job=220001IU&tz=GMT%2B01%3A00&tzname=Europe%2FLondon
Research & Development Group, Horizen Labs
Horizen Labs is a blockchain technology company that designs, develops, and delivers powerful, scalable, and reliable distributed ledger solutions for business.
Our Core Engineering Team is an innovative and collaborative group of researchers and software engineers who are dedicated to the design and development of world-class blockchain-based products. We are looking for a cryptographer, or applied cryptographer, to join our growing crypto team based in Milan, Italy. Currently, the team is developing a protocol suite for SNARK-based proof-composition, but its duties reach beyond that, developing privacy-enhancing solutions for our sidechain ecosystem.
Responsabilities- Design privacy-enhancing technology built on SNARK-based protocols
- Perform collaborative research and assist technical colleagues in their development work
- Participate in standards-setting
- Ph.D. in mathematics, computer science, or cryptography
- Solid foundations in zero-knowledge and cryptographic protocols
- Publications in acknowledged venues on applied or theoretical cryptography, preferably cryptographic protocols or PETs
- Strong problem-solving skills
- The ability to work in a team setting as well as autonomously
- Foundations in blockchain technology and experience in reading Rust are a plus
- A competitive salary plus pre-series A stock options
- Flexible working hours, including the possibility of remote working
- The opportunity to work with talented minds on challenging topics in this field, including the most recent advancements in zero-knowledge
- A nice and informal team setting to conduct research and development of high-quality open source solutions
If you are interested in this position, you might want to take a look at our recent publications (IACR eprints 2021/930, 2021/399, 2020/123) and our latest podcast on zeroknowledge.fm (Episode 178). For further questions, please contact the email below.
Closing date for applications:
Contact: Raffaella Lixi raffaella@horizenlabs.io
More information: https://horizenlabs.io/careers/job/?gh_jid=4116067004
Research & Development Group, Horizen Labs
Horizen Labs is a blockchain technology company that designs, develops, and delivers powerful, scalable, and reliable distributed ledger solutions for business.
We are looking for an engineer who will contribute in building the cryptographic infrastructure of our Web 3.0-enabled blockchain ecosystem. You will be involved in the design and implementation of our zero-knowledge Layer 2 scaling solution based on STARK-proven virtual machines. Our international team works in a stimulating and innovative environment, where people’s technical expertise and experience contribute to the development of cutting-edge blockchain technology.
Requirements- Experience in implementing zero-knowledge proving systems or related cryptographic primitives;
- Comfortable in implementing low-level operations such as finite field arithmetics, hash functions, etc.;
- Enthusiastic about algorithmic improvements and code optimization.
- Plonk, STARKs, AIR circuits,
- EVM, zk-VMs,
- C/C++/Rust programming language
- Competitive salary, yearly bonus, and stock options
- Flexible working hours, fully remote if preferred
- The opportunity to work with talented minds on innovative, high-quality open source solutions.
If you want to get more knowledge about our technology, read our Whitepapers at the website: https://www.horizen.io/research/
Closing date for applications:
Contact: Raffaella Lixi raffaella@horizenlabs.io
More information: https://horizenlabs.io/careers/job/?gh_jid=4534454004
Research & Development Group, Horizen Labs
Horizen Labs is a blockchain technology company that designs, develops, and delivers powerful, scalable, and reliable distributed ledger solutions for business.
Our Core Engineering Team is an innovative and collaborative group of researchers and software engineers who are dedicated to the design and development of world-class blockchain-based products. We are working on cutting edge tech, including zkSNARKS, proof systems and zkVMs, to fundamentally change the way of building decentralized and scalable Web3 applications. We are looking for a Lead Zero-Knowledge Cryptographer for our cryptographic team distributed across the globe. Amongst other projects, the team is dedicated to the design of our Layer-2 scaling solution based on STARK-proven virtual machines. You will help our team grow, conduct research and lay out SNARK-based cryptographic protocols, working on related cutting-edge technologies such as zkVMs.
RequirementsYou should be aware of state of the art proving systems such as Plonk and STARKs, and have a solid background in computational models and blockchain technologies. Additional requirements are represented by:
- Ph.D. in mathematics, computer science, or cryptography;
- Solid foundations in zero-knowledge and cryptographic protocols ;
- Publications in acknowledged venues on applied or theoretical cryptography, preferably cryptographic protocols, and PETs;
- Strong problem-solving skills;
- The ability to work in a team setting as well as autonomously
Experience in reading code (e.g. C++, Rust) though not mandatory, it is welcomed.
We offer:- Competitive salary, yearly bonus, and stock options
- Flexible working hours, fully remote if preferred
- The opportunity to work with talented minds on innovative, high-quality open source solutions.
If you want to get more knowledge about our technology, read our Whitepapers at the website: https://www.horizen.io/research/
Closing date for applications:
Contact: Raffaella Lixi raffaella@horizenlabs.io
More information: https://horizenlabs.io/careers/job/?gh_jid=4536288004
Dalian university of technology
Open Positions: 03 Post-doctoral research fellows for three years contract. The salary is $50,000 -- $70,000 per year plus Superannuation. Housing/renting is covered.
Responsibilities:
- Conduct research on state-of-the-art cryptography and cyber-security research fields.
- Analyze project requirements and provide technical and functional recommendations.
- Implement cryptographic libraries and security frameworks.
- Propose new projects and research directions.
- Ph.D. degree in Cryptography, Applied Cryptography, Information Theory, or Mathematics.
- Knowledge of cryptography and cybersecurity.
- Familiar with C, C++, Python, or JAVA
- Self-motivated, reliable, creative, can work independently and want to do excellent research.
Closing date for applications:
Contact: kumar.abdal@protonmail.com
Cryptology Group, CWI, Amsterdam, The Netherlands
The Cryptology Group at CWI in Amsterdam invites applications for a 3-year postdoc position within the NWO NWA consortium project HAPKIDO. The successful candidate is expected to do cutting edge research on the topic of post-quantum cryptography, but ideally has also some interest in practical aspects of the migration to post-quantum secure schemes.
Candidates are required to hold a PhD in mathematics or computer science, with a specialization in cryptology, and they are expected to have a good knowledge of post-quantum cryptography and/or of quantum information science in general. Candidates must have a strong track record (ideally with publications at IACR conferences) and good academic writing and presentation skills.
The position is with a flexible starting date, available as of immediately. Applications will be reviewed continuously until the position is filled.
All applications should include a motivation letter, a detailed resume (including a list of publications), a research statement (max 2 pages) discussing prior, current and future research, and the names of at least three references.
Questions and applications should be sent to serge.fehr@cwi.nl.
Closing date for applications:
Contact: Serge Fehr
Rex Fernando, Yuval Gelles, Ilan Komargodski, Elaine Shi
Motivated by the need to perform large-scale data analytics in a privacy-preserving manner, several recent works have presented generic compilers that transform algorithms in the MPC model into secure counterparts, while preserving various efficiency parameters of the original algorithms. The first paper, due to Chan et al. (ITCS ’20), focused on the honest majority setting. Later, Fernando et al. (TCC ’20) considered the dishonest majority setting. The latter work presented a compiler that transforms generic MPC algorithms into ones which are secure against semi-honest attackers that may control all but one of the parties involved. The security of their resulting algorithm relied on the existence of a PKI and also on rather strong cryptographic assumptions: indistinguishability obfuscation and the circular security of certain LWE-based encryption systems.
In this work, we focus on the dishonest majority setting, following Fernando et al. In this setting, the known compilers do not achieve the standard security notion called malicious security, where attackers can arbitrarily deviate from the prescribed protocol. In fact, we show that unless very strong setup assumptions as made (such as a programmable random oracle), it is provably impossible to withstand malicious attackers due to the stringent requirements on space and round complexity.
As our main contribution, we complement the above negative result by designing the first general compiler for malicious attackers in the dishonest majority setting. The resulting protocols withstand all-but-one corruptions. Our compiler relies on a simple PKI and a (programmable) random oracle, and is proven secure assuming LWE and SNARKs. Interestingly, even with such strong assumptions, it is rather non-trivial to obtain a secure protocol.
Luciano Maino, Chloe Martindale
Cody Freitag, Rafael Pass, Naomi Sirkin
Our main results show the existence of a publicly-verifiable, non-interactive, SPARG for P assuming polynomial hardness of LWE. Our SPARG construction relies on the elegant recent delegation construction of Choudhuri, Jain, and Jin (FOCS'21) and combines it with techniques from Ephraim et al (EuroCrypt'20).
We next demonstrate how to make our SPARG time-independent–where the prover and verifier do not need to known the running-time t in advance; as far as we know, this yields the first construction of a time-tight delegation scheme with time-independence based on any hardness assumption.
We finally present applications of SPARGs to the constructions of VDFs (Boneh et al, Crypto'18), resulting in the first VDF construction from standard polynomial hardness assumptions (namely LWE and the minimal assumption of a sequentially hard function).
Shweta Agrawal, Anshu Yadav, Shota Yamada
1. Formalizing Security: We provide definitions for ${\sf miABE}$ and ${\sf miPE}$ in the {symmetric} key setting and formalize security in the standard indistinguishability (IND) paradigm, against unbounded collusions.
2. Two-input ${\sf ABE}$ for ${\sf NC}_1$ from ${\sf LWE}$ and Pairings: We provide the first constructions for two-input key-policy ${\sf ABE}$ for ${\sf NC}_1$ from ${\sf LWE}$ and pairings. Our construction leverages a surprising connection between techniques recently developed by Agrawal and Yamada (Eurocrypt, 2020) in the context of succinct single-input ciphertext-policy ${\sf ABE}$, to the seemingly unrelated problem of two-input key-policy ${\sf ABE}$. Similarly to Agrawal-Yamada, our construction is proven secure in the bilinear generic group model. By leveraging inner product functional encryption and using (a variant of) the KOALA knowledge assumption, we obtain a construction in the standard model analogously to Agrawal, Wichs and Yamada (TCC, 2020).
3. Heuristic two-input ${\sf ABE}$ for ${\sf P}$ from Lattices: We show that techniques developed for succinct single-input ciphertext-policy ${\sf ABE}$ by Brakerski and Vaikuntanathan (ITCS 2022) can also be seen from the lens of ${\sf miABE}$ and obtain the first two-input key-policy ${\sf ABE}$ from lattices for ${\sf P}$.
4. Heuristic three-input ${\sf ABE}$ and ${\sf PE}$ for ${\sf NC}_1$ from Pairings and Lattices: We obtain the first three-input ${\sf ABE}$ for ${\sf NC}_1$ by harnessing the powers of both the Agrawal-Yamada and the Brakerski-Vaikuntanathan constructions.
5. Multi-input ${\sf ABE}$ to multi-input ${\sf PE}$ via Lockable Obfuscation: We provide a generic compiler that lifts multi-input ${\sf ABE}$ to multi-input ${\sf PE}$ by relying on the hiding properties of Lockable Obfuscation (${\sf LO}$) by Wichs-Zirdelis and Goyal-Koppula-Waters (FOCS 2018), which can be based on ${\sf LWE}$. Our compiler generalizes such a compiler for single-input setting to the much more challenging setting of multiple inputs. By instantiating our compiler with our new two and three-input ${\sf ABE}$ schemes, we obtain the first constructions of two and three-input ${\sf PE}$ schemes.
Our constructions of multi-input ${\sf ABE}$ provide the first improvement to the compression factor of non-trivially exponentially efficient Witness Encryption defined by Brakerski et al. (SCN 2018) without relying on compact functional encryption or indistinguishability obfuscation. We believe that the unexpected connection between succinct single-input ciphertext-policy ${\sf ABE}$ and multi-input key-policy ${\sf ABE}$ may lead to a new pathway for witness encryption.
Albert Yu, Donghang Lu, Aniket Kate, Hemanta K. Maji
This work identifies and presents SIM, a secure protocol for the functionality of interval membership testing. This security functionality, in particular, facilitates secure less-than-zero testing and, in turn, secure comparison. A key technical challenge is to support a fast online protocol for testing in large rings while keeping the precomputation tractable. Motivated by the map-reduce paradigm, this work introduces the innovation of (1) computing a sequence of intermediate functionalities on a partition of the input into input blocks and (2) securely aggregating the output from these intermediate outputs. This innovation allows controlling the size of the precomputation through a granularity parameter representing these input blocks' size -- enabling application-specific automated compiler optimizations.
To demonstrate our protocols' efficiency, we implement and test their performance in a high-demand application: privacy-preserving machine learning. The benchmark results show that switching to our protocols yields significant performance improvement, which indicates that using our protocol in a plug-and-play fashion can improve the performance of various security applications. Our new paradigm of protocol design may be of independent interest because of its potential for extensions to other functionalities of practical interest.
Fukang Liu, Willi Meier, Santanu Sarkar, Takanori Isobe
In this paper, we improve the attacks on LowMC in a model where memory consumption is costly. First, a new attack on 3-round LowMC with full S-box layers with negligible memory complexity is found, which can outperform Bouillaguet et al.'s fast exhaustive search attack and can achieve better time-memory tradeoffs than Dinur's algorithm. Second, we extend the 3-round attack to 4 rounds to significantly reduce the memory complexity of Dinur's algorithm at the sacrifice of a small factor of time complexity. For LowMC instances with 1 S-box per round, our attacks are shown to be much faster than the MITM attacks. For LowMC instances with 10 S-boxes per round, we can reduce the memory complexity from 32GB ($2^{38}$ bits) to only 256KB ($2^{21}$ bits) using our new algebraic attacks rather than the MITM attacks, while the time complexity of our attacks is about $2^{3.2}\sim 2^{5}$ times higher than that of the MITM attacks. A notable feature of our new attacks (apart from the 4-round attack) is their simplicity. Specifically, only some basic linear algebra is required to understand them and they can be easily implemented.