International Association
for Cryptologic Research

Since its invention in 1982, the LLL lattice reduction algorithm (Lenstra, Lenstra, Lovasz 1982) has found countless applications. In cryptanalysis, the two most prominent applications of LLL and its generalisations --e.g. Slide, BKZ and SD-BKZ-- are factoring RSA keys with extra information on the secret key via Coppersmith's method and the cryptanalysis of lattice-based schemes.

After almost 40 years of cryptanalytic applications, predicting and optimising lattice reduction algorithms remains an active area of research. While we do have theorems bounding the worst-case performance of these algorithms, those bounds are asymptotic and not necessarily tight when applied to practical or even cryptographic instances. Reasoning about the behaviour of those algorithms relies on heuristics and approximations, some of which are known to fail for relevant corner cases.

Decades after Lenstra, Lenstra, and Lovász gave birth to this fascinating and lively research area, this state of affairs became a more pressing issue recently. Motivated by post-quantum security, standardisation bodies, governments and industry started to move towards deploying lattice-based cryptographic algorithms. This spurred the refinement of those heuristics and approximations, leading to a better understanding of the behaviour of these algorithms over the last few years.

Lattice reduction algorithms, such as LLL and BKZ, proceed with repeated local improvements to the lattice basis, and each such local improvement means solving the short(est) vector problem in a lattice of a smaller dimension. Therefore, two questions arise: how costly is it to find those local improvements and what is the global behaviour as those improvements are applied.

While those two questions may not be perfectly independent, we will, in this survey, focus on the second one, namely, the global behaviour of such algorithms, given oracle access for finding local improvements. Our focus on the global behaviour is motivated by our intent to draw more of the community's attention to this aspect. We will take a particular interest in the behaviour of such algorithms on a specific class of lattices, underlying the most popular lattice problems to build cryptographic primitives, namely the LWE problem and the NTRU problem. We will emphasise on the approximations that have been made, their progressive refinements and highlight open problems to be addressed.

We present probabilistic dynamic I/O automata, a framework to model dynamic probabilistic systems. Our work extends dynamic I/O Automata formalism [1] to probabilistic setting. The original dynamic I/O Automata formalism included operators for parallel composition, action hiding, action renaming, automaton creation, and behavioral sub-typing by means of trace inclusion. They can model mobility by using signature modification. They are also hierarchical: a dynamically changing system of interacting automata is itself modeled as a single automaton. Our work extends to probabilistic settings all these features. Furthermore, we prove necessary and sufficient conditions to obtain the implementation monotonicity with respect to automata creation and destruction. Our work lays down the premises for extending composable secure-emulation [3] to dynamic settings, an important tool towards the formal verification of protocols combining probabilistic distributed systems and cryptography in dynamic settings (e.g. blockchains, secure distributed computation, cybersecure distributed protocols etc).

Multi-party computation (MPC) allows two or more parties to jointly and securely compute functions over private inputs. Cryptographic protocols that realize MPC require functions to be expressed as Boolean or arithmetic circuits. Deriving such circuits is either done manually, or with hardware synthesis tools and specialized MPC compilers. Unfortunately, such existing tools compile only from a single front-end language and neglect decades of research for optimizing regular compilers.

In this paper, we make MPC practical for developers by automating circuit compilation based on the compiler toolchain LLVM. For this, we develop an LLVM optimizer suite consisting of multiple transform passes that operate on the LLVM intermediate representation (IR) and gradually lower functions to circuit level. Our approach supports various front-end languages (currently C, C++, and Fortran) and takes advantage of powerful source code optimizations built into LLVM. We furthermore make sure to produce circuits that are optimized for MPC, and even offer fully automated post-processing for efficient post-quantum MPC.

We empirically measure the quality of our compilation results and compare them to the state-of-the-art specialized MPC compiler HyCC (Büscher et al., CCS'2018). For all benchmarked HyCC example applications (e.g., biomatch and linear equation solving), our highly generalizable approach achieves similar quality in terms of gate count and composition.

Consensus protocols enable $n$ parties, each holding some input string, to agree on a common output even in the presence of corrupted parties. While the problem is well understood in the classic byzantine setting, recent work has pushed to understand the problem when realistic types of failures are considered and a majority of parties may be corrupt. Garay and Perry consider a model with both byzantine and crash faults and develop a corruption-optimal protocol with perfect security tolerating $t_c$ crash faults and $t_b$ byzantine faults for $n>t_c+3t_b$. Follow up work by Zikas, Hauser, and Maurer extends the model by considering receive-corrupt parties that may not receive messages sent to them, and send-corrupt parties whose sent messages may be dropped. Otherwise, receive-corrupt and send-corrupt parties behave honestly and their inputs and outputs are considered by the security definitions. Zikas, Hauser, and Maurer gave a perfectly secure, linear-round protocol for $n > t_r+t_s+3t_b$, where $t_r$ and $t_s$ represent thresholds on the number of parties that are receive- or send-corrupted.

In this paper we ask ``what are optimal thresholds in the cryptographic setting that can be tolerated with such mixes of corruptions and faults?" We develop an expected-constant round protocol tolerating $n > t_r+2t_s+2t_b$. We are unable to prove optimality of our protocol's corruption budget in the general case; however, when we constrain the adversary to either drop all or none of a sender's messages in a round, we prove our protocol achieves an optimal threshold of $n > t_r+t_s+2t_b$. We denote this weakening of a send corruption a \emph{spotty send corruption}.

In light of this difference in corruption tolerance due to our weakening of a send corruption, we ask ``how close (with respect to corruption thresholds) to a byzantine corruption is a send corruption?" We provide a treatment of the difficulty of dealing with send corruptions in protocols with sublinear rounds. As an illustrative and surprising example (even though not in sublinear rounds), we show that the classical Dolev-Strong broadcast protocol degrades from $n > t_b$ corruptions in the byzantine-only model to $n > 2t_s+2t_b$ when send-corrupt parties' outputs must be consistent with honest parties; we also show why other recent dishonest-majority broadcast protocols degrade similarly. We leave open the question of optimal corruption tolerance for both send- and byzantine corruptions.

Secure comparison (SC) is an essential primitive in Secure Multiparty Computation (SMC) and a fundamental building block in Privacy-Preserving Data Analytics. Although secure comparison has been studied since the introduction of SMC in the early 80s and many protocols have been proposed, there is still room for improvement, especially providing security against malicious adversaries who form the majority among the participating parties. It is not hard to develop an SC protocol secure against malicious majority based on the current state of the art SPDZ framework. SPDZ is design to work for arbitrary polynomially-bounded functionalities, and it may not provide the most efficient SMC implementation for a specific task, such as SC. In this paper, we propose a novel compiler that is specifically designed to convert most existing SC protocols with semi-honest security into the ones secure against the malicious majority. This compiler provides a flexible and efficient way to achieve both covert and active security for passively secure SC protocols.

Micro-architectural leakage is a reality even on low- to midrange commercial processors. Dealing with it is expensive, because micro-architectural leakage is often only discovered after implementation choices have been made (i.e. when evaluating the concrete implementation). We demonstrate that it is feasible, using a recent leakage modelling technique, to reverse engineer significant elements of the micro-architectural leakage of a mid-range commercial processor in a “grey-box” setting. Our approach first recovers the micro-architectural features of each stage in the pipeline, and the leakage of elements that are known to produce glitches. To put our reverse engineered micro-architectural leakage in context, we compare and contrast a leakage analysis of a relevant piece of masking code. More specifically, we compare the leakage that we would anticipate given our analysis, and predictions of the to-date most sophisticated leakage simulators (e.g. ELMO and MAPS) on the same piece of code. Our research demonstrates that reverse engineering of micro-architectural components (and their leakage) is clearly feasible using available side channel leakage, and following, it should be possible to build more accurate leakage simulators.

Property-preserving hash functions allow for compressing long inputs $x_0$ and $x_1$ into short hashes $h(x_0)$ and $h(x_1)$ in a manner that allows for computing a predicate $P(x_0, x_1)$ given only the two hash values without having access to the original data. Such hash functions are said to be adversarially robust if an adversary that gets to pick $x_0$ and $x_1$ after the hash function has been sampled, cannot find inputs for which the predicate evaluated on the hash values outputs the incorrect result.

In this work we construct robust property-preserving hash functions for the hamming-distance predicate which distinguishes inputs with a hamming distance at least some threshold $t$ from those with distance less than $t$. The security of the construction is based on standard lattice hardness assumptions.

Our construction has several advantages over the best known previous construction by Fleischhacker and Simkin (Eurocrypt 2021). Our construction relies on a single well-studied hardness assumption from lattice cryptography whereas the previous work relied on a newly introduced family of computational hardness assumptions. In terms of computational effort, our construction only requires a small number of modular additions per input bit, whereas the work of Fleischhacker and Simkin required several exponentiations per bit as well as the interpolation and evaluation of high-degree polynomials over large fields. An additional benefit of our construction is that the description of the hash function can be compressed to $\lambda$ bits assuming a random oracle. Previous work has descriptions of length $\bigO{\ell \lambda}$ bits for input bit-length $\ell$, which has a secret structure and thus cannot be compressed.

We prove a lower bound on the output size of any property-preserving hash function for the hamming distance predicate. The bound shows that the size of our hash value is not far from optimal.

We introduce a technique to obtain practical speed up for relation collection in class group computations. The idea is to perform a pseudo-random walk over the ideals. The ideals visited by the walk are used in the manner exactly as in the previous algorithm due to Gélin (2018). Under the heuristic assumption that the ideals visited by the walk behave as the ideals randomly generated in Gélin’s algorithm, the asymptotic complexity of the new algorithm remains the same as that of Gélin’s algorithm. The main advantage of the new method over Gélin’s method is that the pseudo-random walk requires a single ideal multiplication to generate the next ideal in the walk, whereas Gélin’s algorithm requires a number of ideal multiplications to generate each ideal to be tested. We have made Magma implementations of both the new algorithm and Gélin’s algorithm. Timing results confirm that there is indeed a substantial practical speed-up in relation collection by the new algorithm over Gélin’s algorithm.

CAS-Lock (proposed in CHES2020), is an advanced logic locking technique that harnesses the concept of single-point function in providing SAT-attack resiliency. It is claimed to be powerful and efficient enough in mitigating state-of-the-art attacks against logic locking techniques. Despite the security robustness of CAS-Lock as claimed by the authors, we expose a serious vulnerability by exploiting the same and device a novel attack algorithm. The proposed attack can reveal the correct key by extracting the Distinguishing Input Patterns (DIPs) pertaining to a carefully chosen key simulation of the locked design. The correct key is obtained from the combination of elements from the set of extracted DIPs. Our attack is successful against various AND/OR cascaded-chain configurations of CAS-Lock and reports a 100% success rate in recovering the correct key.

We take a look at the current implementation of NTRU submitted to the NIST post-quantum standardization project, and identify two strong sources of leakage in the unpacking of the secret key. The strength of the leakages is due to the target processor handling data with very different Hamming weight depending on parts of the secret key. We focus on using only these strong leakages, present a single-trace side-channel attack that reliably recovers a large portion of the secret key, and use lattice reduction techniques to find the remaining parts. Further, we show how small changes to the implementation greatly reduces the leakage without any overhead.

The amount of encrypted Internet traffic almost doubles every year thanks to the wide adoption of end-to-end traffic encryption solutions such as IPSec, TLS and SSH. Despite all the benefits of user privacy the end-to-end encryption provides, the encrypted internet traffic blinds intrusion detection system (IDS) and makes detecting malicious traffic hugely difficult. The resulting conflict between the user's privacy and security has demanded solutions for deep packet inspection (DPI) over encrypted traffic. The approach of those solutions proposed to date is still restricted in that they require intensive computations during connection setup or detection. For example, BlindBox, introduced by Sherry et al. (SIGCOMM 2015) enables inspection over the TLS-encrypted traffic without compromising users' privacy, but its usage is limited due to a significant delay on establishing an inspected channel. PrivDPI, proposed more recently by Ning et al. (ACM CCS 2019), improves the overall efficiency of BlindBox and makes the inspection scenario more viable.Despite the improvement, we show in this paper that the user privacy of Ning et al.'s PrivDPI can be compromised entirely by the rule generator without involving any other parties, including the middlebox. Having observed the difficulties of realizing efficiency and security in the previous work, we propose a new DPI system for encrypted traffic, named ``Practical and Privacy-Preserving Deep Packet Inspection (P2DPI)''. P2DPI enjoys the same level of security and privacy that BlindBox provides. At the same time, P2DPI offers fast setup and encryption and outperforms PrivDPI. Our results are supported by formal security analysis. We implemented our P2DPI and comparable PrivDPI and performed extensive experimentation for performance analysis and comparison.

We introduce the notion of a somewhere statistically sound (SSS) interactive argument, which is a hybrid between a statistically sound proof and a computationally sound proof (a.k.a. an argument).

- First, we show that Kilian's protocol, instantiated with a computationally non-signaling PCP (Brakerski, Holmgren, and Kalai, STOC 2017) and a somewhere statistically binding hash family (Hubacek and Wichs, ITCS 2015), is an SSS argument.

- Secondly, we show that the soundness of SSS arguments can be proved in a straight-line manner, implying that they are also post-quantum sound if the underlying assumption is post-quantum secure. This provides a straightforward proof that Kilian's protocol, instantiated this way, is post-quantum sound under the post-quantum hardness of LWE (though we emphasize that a computationally non-signaling PCP exists only for deterministic languages, and more generally, for specific subclasses of non-deterministic languages such as $\mathsf{NTISP}$, but not for all of $\mathsf{NP}$).

- We put forward a natural conjecture that constant-round SSS arguments can be soundly converted into non-interactive arguments via the Fiat-Shamir transformation. We argue that SSS arguments evade the current Fiat-Shamir counterexamples, including the one for Kilian's protocol (Bartusek, Bronfman, Holmgren, Ma and Rothblum, TCC 2019) by requiring additional properties from both the hash family and the PCP.

As an additional result, we show that by using a computationally non-signaling PCP and a somewhere statistically binding hash family, one can efficiently convert any succinct non-interactive argument (SNARG) for $\mathsf{BatchNP}$ into a SNARG for $\mathsf{P}$.

This paper studies the challenges of creating a mobile device based voting client. We discuss the issues related to standalone and mobile browser based voting applications. In both cases we discuss the problems of vote privacy, integrity and voting channel availability. We conclude that neither of the options can currently achieve the level of security PC-based voting clients can provide, with the attack surface being larger in the case of mobile browser based voting application.

Volumetric leakage in encrypted databases had been overlooked by the community for a long time until Kellaris et al. (CCS ’16) proposed the first database reconstruction attack leveraging communication volume. Their attack was soon improved and several query recovery attacks were discovered recently. In response to the advancements of volumetric leakage attacks, volume-hiding searchable symmetric encryption (SSE) schemes have been proposed (Kamara and Moataz, Eurocrypt ’19 & Patel et al., CCS ’19). In these schemes, the database is padded in a clever way so that the volume (i.e., the number of responses) for any search query is the same or computationally indistinguishable while keeping the storage complexity and search complexity as small as possible.

Unfortunately, existing volume-hiding SSE schemes do not support atomic updates (i.e., addition/deletion of an arbitrary keyword-document pair), which is the most common update operation considered in the SSE literature. Meanwhile, recent volumetric attacks (Wang et al., EuroS&P ’20 & Blackstone et al., NDSS ’20) indeed target dynamic databases.

We initiate a formal study of volume-hiding dynamic SSE. We extend the existing definition of volume-hiding leakage function into the dynamic setting and present efficient constructions VH-DSSE and VH-DSSE^k . VH-DSSE suffers from non-negligible correctness error. To remedy the disadvantage of VH-DSSE, we propose a multi-copy construction VH-DSSE^k that amplifies correctness by parallel repetition. As a side contribution, both VH-DSSE and VH-DSSE^k satisfy the strongest notions of backward-privacy, which is the first one in the literature, to the best of our knowledge.

In two of the main areas of post-quantum cryptography, based on lattices and codes, nearest neighbor techniques have been used to speed up state-of-the-art cryptanalytic algorithms, and to obtain the lowest asymptotic cost estimates to date [May-Ozerov, Eurocrypt'15; Becker-Ducas-Gama-Laarhoven, SODA'16]. These upper bounds are useful for assessing the security of cryptosystems against known attacks, but to guarantee long-term security one would like to have closely matching lower bounds, showing that improvements on the algorithmic side will not drastically reduce the security in the future. As existing lower bounds from the nearest neighbor literature do not apply to the nearest neighbor problems appearing in this context, one might wonder whether further speedups to these cryptanalytic algorithms can still be found by only improving the nearest neighbor subroutines. We derive new lower bounds on the costs of solving the nearest neighbor search problems appearing in these cryptanalytic settings. For the Euclidean metric we show that for random data sets on the sphere, the locality-sensitive filtering approach of [Becker-Ducas-Gama-Laarhoven, SODA 2016] using spherical caps is optimal, and hence within a broad class of lattice sieving algorithms covering almost all approaches to date, their asymptotic time complexity of $2^{0.292d + o(d)}$ is optimal. Similar conditional optimality results apply to lattice sieving variants, such as the $2^{0.265d + o(d)}$ complexity for quantum sieving [Laarhoven, PhD thesis 2016] and previously derived complexity estimates for tuple sieving [Herold-Kirshanova-Laarhoven, PKC 2018]. For the Hamming metric we derive new lower bounds for nearest neighbor searching which almost match the best upper bounds from the literature [May-Ozerov, Eurocrypt 2015]. As a consequence we derive conditional lower bounds on decoding attacks, showing that also here one should search for improvements elsewhere to significantly undermine security estimates from the literature.

Event date: 16 November to 17 November 2021
Submission deadline: 30 June 2021
Notification: 1 September 2021

We are seeking one to two software engineers who can contribute to implementing a software system for privacy-preserving DNA synthesis screening in the Secure DNA project. We are a group of researchers from Tsinghua University, MIT, Aarhus University, Shanghai Jiao Tong University, and other world-leading academic institutions. Our goal is to develop an automatic and accurate screening system that can effectively block hazardous DNA sequences from being produced, while at the same time providing superior levels of security guarantees, in terms of not disclosing the submitted DNA orders or the potential hazards that are not yet public. To learn more visit our website or read the technical whitepaper.

Your Responsibilities

• Develop and implement the software system that realizes secure DNA synthesis.
• Develop the frontend that integrates the system into the production environments of our DNA vendor partners.

Basic Requirements

• Strong software development experience, especially large-scale systems and/or security-critical software.
• Strong knowledge and experience in software programming, such as C++, Rust, or Go.
• Familiarity with common cryptographic software libraries and implementations.

Nice to Have

• Experience in distributed systems.
• Basic theoretical background in cryptography and system security.
• English communication and reading/writing capabilities.
• Passion for modern cryptography-based secure computing.

Benefits

• Involved in world-leading research projects and teamed up with top scientists around the world, including Turing award winners.
• Competitive salary and other benefits from Tsinghua University.
• Future opportunities in long-term collaboration with other research projects at Tsinghua.

Closing date for applications:

Contact: Mingyu Gao, gaomy@tsinghua.edu.cn

More information: https://www.securedna.org

We are seeking a principal software architect who can contribute to implementing a software system for privacy-preserving DNA synthesis screening in the Secure DNA project. We are a group of researchers from Tsinghua University, MIT, Aarhus University, Shanghai Jiao Tong University, and other world-leading academic institutions. Our goal is to develop an automatic and accurate screening system that can effectively block hazardous DNA sequences from being produced, while at the same time providing superior levels of security guarantees, in terms of not disclosing the submitted DNA orders or the potential hazards that are not yet public. To learn more visit our website or read the technical whitepaper.

Your Responsibilities

• Design and propose the system architecture for the software system that realizes the proposed algorithm based on distributed oblivious pseudo-random functions.
• Assemble and lead the engineer team to implement the proposed software system.
• Deploy the system into the production environments of our DNA vendor partners.

Basic Requirements

• 5+ years of experience working with secure software system development and deployment.
• Strong knowledge and experience in software programming, such as C++, Rust, or Go.
• Familiarity with common cryptographic software libraries and implementations.
• Fluent in English communication and reading/writing.

Nice to Have

• Experience in team management.
• Familiarity with modern cryptography-based securing computing algorithms.
• Some familiarity with basic biological knowledge and DNA synthesis.

Benefits

• Flexible work hours and arrangement; remote and/or part-time are both acceptable.
• Involved in world-leading research projects with Turing award winners.
• A critical role in implementing the important bio-security system that will be deployed world-wide.
• Competitive salary and other benefits from Tsinghua University.
• Future opportunities in long-term collaboration with other research projects at Tsingh

  Closing date for applications:

  Contact: Mingyu Gao, gaomy@tsinghua.edu.cn

  More information: https://www.securedna.org

We have multiple open positions within Surrey Centre for Cyber Security (SCCS) at the Department of Computer Science, University of Surrey, UK.

Early Career Fellowship in Cyber Security (Lecturer A)
https://jobs.surrey.ac.uk/vacancy.aspx?ref=026221

Lecturer / Senior Lecturer in Cyber Security
https://jobs.surrey.ac.uk/vacancy.aspx?ref=027721

Positions are available for researchers at different stages of their careers and in a range of security topics such as:

• applied cryptography (incl. post-quantum cryptography, distributed cryptography)
• privacy enhancing technologies (incl. anonymisation, secure multi-party computation, computing on encrypted data)
• software security (e.g., malware analysis)
• system security (incl., security of autonomous or cyber-physical systems)
• security architectures (incl., trusted computing, TEEs)
• security protocols for blockchain and/or machine learning
• tool-assisted formal verification of security and privacy

Please follow the above links for more details.

Closing date for applications:

Contact: Informal inquiries can be sent to Dr. Mark Manulis (m.manulis at surrey.ac.uk)

More information: https://www.surrey.ac.uk/department-computer-science

As a research engineer in the Cyber Security chair you will focus in applied and theoretical cryptography, network and information security. You will establish and work in a state-of-the-art IoT (Internet of Things) lab with smart devices ranging from Raspberry Pi's, sensors, smart microphones, toy cars, RFID tags, RFID readers, smart phones, biometric sensors and you will work with world-leading researchers to implement, test, and showcase secure and privacy-preserving protocols and algorithms. Many projects are done in collaboration with other academic and industrial partners. More specifically, the job includes:

• Development and implementation of concepts and research results, both individually and in collaboration with researchers and PhD students
• Run of experiments and simulation of realistic conditions to test the performance of developed algorithms and protocols
• Development, maintenance and organization of software
• Support to BSc, MSc and PhD students, postdocs and researchers who use the lab
• Responsibility for the daily routines in the lab, for example purchases, installations, bookings, inventory
• Demonstrations and lab tours for external visitors
• Producing media content for our group web page and social media platforms.

Your profile

• The successful applicant is expected to hold or to be about to receive a M.Sc. degree in Computer Science, Electrical Engineering, Applied Mathematics or similar fields, preferably with a focus in Security and Privacy for Computer Science Systems.
• We are looking for a strongly motivated and self-driven person who is able to work and learn new things independently.
• Good command of English is required.
• You should have a good academic track record and well developed analytical and problem solving skills.
• Excellent programming skills and familiarity with cryptographic libraries.
• Previous experience in implementation projects with C++, Matlab, Python is desired.

Deadline: 15 June 2021

Closing date for applications:

Contact: Prof. Katerina Mitrokotsa

More information: https://jobs.unisg.ch/offene-stellen/research-engineer-security-and-privacy-m-f-d/634aea27-37d2-4f1f-ab25-2d3c0a622fc0