International Association
for Cryptologic Research

The lattice-based CRYSTALS-Dilithium signature schemes has been selected for standardization by the NIST. As part of the selection process, a large number of implementations for platforms like x86, ARM Cortex-M4, or - on the hardware side - Xilinx Artix-7 have been presented and discussed by experts. Moreover, the software implementations have been subject to side-channel analysis with several attacks being published. Until now, however, an analysis of Dilithium hardware implementations and their peculiarities have not taken place. With this work, we aim to fill this gap, presenting an analysis of vulnerable operations and practically showing a successful profiled SPA and a CPA on a recent hardware implementation by Beckwith et al. Our SPA attack requires 700000 profiling traces and targets the first NTT stage. After profiling, we can find pairs of coefficients with 1101 traces. The CPA attack finds secret coefficients with as low as 66000 traces. Our attack emphasizes that noise-generation in hardware is not sufficient as mitigation measure for SCA. As a consequence, we present countermeasures and show that they effectively prevent both attacks.

We construct succinct non-interactive arguments (SNARGs) for bounded-depth computations assuming that the decisional Diffie-Hellman (DDH) problem is sub-exponentially hard. This is the first construction of such SNARGs from a Diffie-Hellman assumption. Our SNARG is also unambiguous: for every (true) statement $x$, it is computationally hard to find any accepting proof for $x$ other than the proof produced by the prescribed prover strategy.

We obtain our result by showing how to instantiate the Fiat-Shamir heuristic, under DDH, for a variant of the Goldwasser-Kalai-Rothblum (GKR) interactive proof system. Our new technical contributions are (1) giving a $TC^0$ circuit family for finding roots of cubic polynomials over a special family of characteristic $2$ fields (Healy-Viola, STACS '06) and (2) constructing a variant of the GKR protocol whose invocations of the sumcheck protocol (Lund-Fortnow-Karloff-Nisan, STOC '90) only involve degree $3$ polynomials over said fields. Along the way, since we can instantiate Fiat-Shamir for certain variants of the sumcheck protocol, we also show the existence of (sub-exponentially) computationally hard problems in the complexity class $\mathsf{PPAD}$, assuming the sub-exponential hardness of DDH. Previous $\mathsf{PPAD}$ hardness results all required either bilinear maps or the learning with errors assumption.

Biometric data are uniquely suited for connecting individuals to their digital identities. Deriving cryptographic key exchange from successful biometric authentication therefore gives an additional layer of trust compared to password-authenticated key exchange. However, biometric data differ from passwords in two crucial points: firstly, they are sensitive personal data that need to be protected on a long-term basis. Secondly, efficient feature extraction and comparison components resulting in high intra-subject tolerance and low inter-subject distinguishability, documented with good biometric performance, need to be applied in order to prevent zero-effort impersonation attacks.

In this work, we present a protocol for secure and efficient biometrics-authenticated key exchange that fulfils the above requirements of biometric information protection compliant with ISO/IEC 24745. The protocol is based on established fuzzy vault schemes and validated with good recognition performance. We build our protocol from established primitives for password-authenticated key exchange using oblivious pseudo-random functions. Our protocol is independent of the biometric modality and can be instantiated both based on the security of discrete logarithms and lattices.

We provide an open-source implementation of our protocol instantiated with elliptic curves and a state-of-the art unlinkable fingerprint fuzzy vault scheme that is practical with transaction times of less than one second from the image capture to the completed key exchange.

The MPC-in-the-Head paradigm is a popular framework to build zero-knowledge proof systems using techniques from secure multi-party computation (MPC). While this paradigm is not restricted to a particular secret sharing scheme, all the efficient instantiations proposed so far rely on additive secret sharing.

In this work, we show how applying a threshold linear secret sharing scheme (threshold LSSS) can be beneficial to the MPC-in-the-Head paradigm. For a general MPC protocol model capturing most of the existing MPCitH schemes, we show that our approach improves the soundness of the underlying proof system from $1/N$ down to $1/\binom{N}{\ell}$, where $N$ is the number of parties and $\ell$ is the threshold of the sharing scheme. While very general, our technique is limited to a number of parties $N \leq |\mathbb{F}|$, where $\mathbb{F}$ is the field underlying the statement, because of the MDS conjecture.

Applying our approach with a low-threshold LSSS also boosts the performance of the proof system by making the MPC emulation cost independent of $N$ for both the prover and the verifier. The gain is particularly significant for the verification time which becomes logarithmic in $N$ (while the prover still has to generate and commit the $N$ input shares). We further generalize and improve our framework: we show how homomorphic commitments can get rid of the linear complexity of the prover, we generalize our result to any quasi-threshold LSSS, and we describe an efficient batching technique relying on Shamir's secret sharing. We finally apply our techniques to specific use-cases. We first propose a variant of the recent SDitH signature scheme achieving new interesting trade-offs. In particular, for a signature size of 10 KB, we obtain a verification time lower than $0.5$ ms, which is competitive with SPHINCS+, while achieving much faster signing. We further apply our batching technique to two different contexts: batched SDitH proofs and batched proofs for general arithmetic circuits based on the Limbo proof system. In both cases, we obtain an amortized proof size lower than $1/10$ of the baseline scheme when batching a few dozen statements, while the amortized performances are also significantly improved.

CRYSTALS-Dilithium has been selected by the NIST as the new standard for post-quantum digital signatures. In this work, we revisit the side-channel countermeasures of Dilithium in three directions. First, we improve its sensitivity analysis by classifying intermediate computations according their physical security requirements. This allows us to identify which parts of Dilithium must be protected against Differential Power Analysis (DPA), which parts must be protected against Simple Power Analysis (SPA) and which parts can leak in an unbounded manner. Second, we provide improved gadgets dedicated to Dilithium, taking advantage of recent advances in masking conversion algorithms. Third, we combine these contributions with standard shuffling techniques in order to design so-called leveled implementations that offer an improved security vs. performance trade-off compared to the state-of-the-art. Our benchmarking results additionally put forward that the randomized version of Dilithium can lead to significantly more efficient implementations (than its deterministic version) when side-channel attacks are a concern.

Deniable public-key encryption (DPKE) is a cryptographic primitive that allows the sender of an encrypted message to later claim that they sent a different message.

DPKE's threat model assumes powerful adversaries who can coerce users to reveal plaintexts; it is thus reasonable to consider other advanced capabilities, such as the ability to subvert algorithms in a so-called Algorithm Substitution Attack (ASA). An ASA replaces a trusted algorithm with a subverted version that undermines security from the point of view of the adversary while remaining undetected by users. ASAs have been considered against a number of primitives including digital signatures, symmetric encryption and pseudo-random generators. However, public-key encryption has presented a less fruitful target, as the sender's only secrets are plaintexts and ASA techniques generally do not provide sufficient bandwidth to leak these.

In this work, we show that subversion attacks against deniable encryption schemes present an attractive opportunity for an adversary. We note that whilst the notion is widely accepted, there are as yet no practical deniable PKE schemes; we demonstrate the feasibility of ASAs targeting deniable encryption using a representative scheme as a proof of concept. We also provide a formal model and discuss how to mitigate ASAs targeting deniable PKE schemes. Our results strengthen the security model for deniable encryption and highlight the necessity of considering subversion in the design of practical schemes.

An emerging direction of investigating the resilience of post-quantum cryptosystems under side-channel attacks is to consider the situations where leaked information is combined with traditional attack methods in various forms. In CRYPTO 2020, Dachman-Soled et al. integrated hints from side-channel information to the primal attack against LWE schemes. This idea is further developed in this paper. An accurate characterization of the information from perfect hints and modular hints is obtained through the establishment of an interesting decomposition of $\mathbb{Z}^n$. It is observed that modular hints with modulus $p$ produce some orthogonal projection of the secret in $\mathbb{Z}_p$, which is exactly an extension of the case of perfect hints in $\mathbb{R}$. Based on these, a new attack framework is described when some modular hints with modulus $q$ are available. In this framework, an adversary first reduces the LWE instance using such hints, and then performs various attacks on the new instance. One of the key characters of our framework is that the dimension of the secret in the new instance always decreases under some moderate conditions. A comparison with the previous work shows that our approach is in some sense more essential and applicable to various kinds of attacks. The new way of integrating modular hints to primal attack improves the existing work. The first attempt of using modular hints in dual attack and BKW attack is also discussed in the paper and better analysis results are produced. Experiments have been carried out and shown that multiple modular hints with modulus $q$ can indeed significantly reduce their attack costs. For examples, with just 100 hints, the blocksize can be reduced by 101 and the time complexity can be reduced by a factor of $2^{30}$ in both primal attack and dual attack against a Newhope1024 instance. As for the BKW attack, if 90 hints are available, the number of queries to the LWE oracle can be decreased by a factor of $2^{60}$, as do the time complexity and memory complexity when attacking an instance of Regev cryptosystem $(384,147457,39.19)$.

Combining theoretical-based traditional attack method with practical-based side-channel attack method provides more accurate security estimations for post-quantum cryptosystems. In CRYPTO 2020, Dachman-Soled et al. integrated hints from side-channel information to the primal attack against LWE schemes. This paper develops a general Fourier analytic framework to work with the dual attack in the presence of hints. Distinguishers that depend on specific geometric properties related to hints are established. The Fourier transform of discretized multivariate conditional Gaussian distribution on $\mathbb{Z}_q^d$ is carefully computed and estimated, some geometric characteristics of the resulting distinguisher are explored and a new model of dual attack is proposed. In our framework, an adversary performs the BKZ algorithm directly in a projected lattice to find short projection components, and then recovers them by MLLL algorithm to make a distinction. This method relies on a reasonable assumption and is backed up by naturally formed mathematical arguments. The improvements and the assumption are validated by experiments. For examples, for a Kyber768 instance, with 200 hints, the blocksize can be reduced by at least 188 and the time complexity can be reduced by a factor of greater than $2^{55}$. After adding 300 hints to a FireSaber instance, even in the worst case, the blocksize drops from 819 to 542, and the cost drops from $2^{255.61}$ to $2^{174.72}$.

Physically Unclonable Functions (PUFs) have emerged as a viable and cost-effective method for device authentication and key generation. Recently, CMOS image sensors have been exploited as PUF for hardware fingerprinting in mobile devices. As CMOS image sensors are readily available in modern devices such as smartphones, laptops etc., it eliminates the need for additional hardware for implementing a PUF structure. In ISIC2014, an authentication protocol has been proposed to generate PUF signatures using a CMOS image sensor by leveraging the fixed pattern noise (FPN) of certain pixel values. This makes the PUF candidate an interesting target for adversarial attacks. In this work, we testify that a simple sorting attack and a win-rate (WR) based sorting attack can be launched in this architecture to predict the PUF response for given a challenge. We also propose a modified authentication protocol as a countermeasure to make it resilient against simple sorting and WR sorting attacks. The proposed work reduces the accuracy of prediction due to simple sorting attack and WR sorting attack by approximately 14% compared to the existing approach.

Homomorphic equality operator is essential for many secure computation tasks such as private information retrieval (PIR). However, the folklore homomorphic equality operator is typically considered to be impractical as its multiplicative depth depends on the input bit-length. In Usenix SEC '22, Mahdavi-Kerschbaum propose a homomorphic equality operator with a constant multiplicative depth, based on constant-weight code. On that basis, they propose constant-weight PIR (CwPIR for short); compared with other PIR protocols, CwPIR is more friendly to databases with large payloads and can support keyword query almost for free. Unfortunately, CwPIR cannot support databases with a large number of elements, which limits its real-world impact.

In this paper, we propose a homomorphic constant-weight equality operator that supports batch processing, hence it can perform thousands of equality checks with a much smaller amortized cost. Based on this improved homomorphic equality operator, we propose a novel PIR protocol named PIRANA, which inherits all advantages of CwPIR with a significant improvement in supporting more elements. We further extend PIRANA to support multi-query. To the best of our knowledge, PIRANA is the first multi-query PIR that can save both computation and communication. Our experimental results show that our single-query PIRANA is upto 30.8× faster than CwPIR; our multi-query PIRANA saves upto 163.9× communication over the state-of-the-art multi-query PIR (with a similar computational cost).

The bottleneck in the proving algorithm of most of elliptic-curve-based SNARK proof systems is the Multi-Scalar-Multiplication (MSM) algorithm. In this paper we give an overview of a variant of the Pippenger MSM algorithm together with a set of optimizations tailored for curves that admit a twisted Edwards form. This is the case for SNARK-friendly chains and cycles of elliptic curves, which are useful for recursive constructions. Accelerating the MSM over these curves on mobile devices is critical for deployment of recursive proof systems on mobile applications. This work is implemented in Go and uses hand-written arm64 assembly for accelerating the finite field arithmetic (bigint). This work was implemented as part of a submission to the ZPrize competition in the open division “Accelerating MSM on Mobile” (https://www.zprize.io/). We achieved a 78% speedup over the ZPrize baseline implementation in Rust.

Lightweight cryptography is a viable solution for constrained computational environments that require a secure communication channel. To standardize lightweight primitives, NIST has published a call for algorithms that address needs like compactness, low-latency, low-power/energy, etc. Among the candidates, the GIFT family of block ciphers was utilized in various NIST candidates due to its high-security margin and small gate footprint. As a result of their hardware-oriented design, software implementations of GIFT require additional optimization techniques such as bitslicing and fixslicing to achieve optimal performance. Even though the performance of these methods has been assessed for several ISA families such as x86 and ARM, there is currently a lack of data with regards to their acceleration capabilities for RISC-V. Since this ISA is an important element of the growing open-hardware movement, our goal is to address this knowledge gap. Therefore, we have developed several assembly implementations for both GIFT-64 and GIFT-128, using the RV32I ISA, and performed a quantitative assessment of their performance using a physical board i.e., Hifive1 Rev B. Our study has shown that by using bitslicing the number of clock cycles can be reduced by 69.33% for GIFT-64 and 71.38% for GIFT-128, compared to a naive assembly implementation, while fixslicing decreases the number of clock cycles by 85.7% (GIFT-64) and 81.28% (GIFT-128). Nonetheless, the preferred technique is fixslicing with key pre-computation, which can achieve a reduction of 88.69% (GIFT-64) and 95.05% (GIFT-128), while maintaining relatively low memory requirements of 938 bytes (GIFT-64) and 1388 bytes (GIFT-128), respectively.

FUTURE is a recently proposed, lightweight block cipher. It has an AES-like, SP-based, 10-round encryption function, where, unlike most other lightweight constructions, the diffusion layer is based on an MDS matrix. Despite its relative complexity, it has a remarkable hardware performance due to careful design decisions.

In this paper, we conducted a MILP-based analysis of the cipher, where we incorporated exact probabilities rather than just the number of active S-boxes into the model. Through the MILP analysis, we were able to find differential and linear distinguishers for up to 5 rounds of FUTURE, extending the known distinguishers of the cipher by one round.

Secure message transmission (SMT) constitutes a fundamental network-layer building block for distributed protocols over incomplete networks. More specifically, a sender $\mathbf{S}$ and a receiver $\mathbf{R}$ are connected via $\ell$ disjoint paths, of which at most $t$ paths are controlled by the adversary.

\emph{Perfectly-secure} SMT protocols in synchronous and asynchronous networks are resilient up to $\ell/2$ and $\ell/3$ corruptions respectively. In this work, we ask whether it is possible to achieve a perfect SMT protocol that simultaneously tolerates $t_s < \ell/2$ corruptions when the network is synchronous, and $t_a < \ell/3$ when the network is asynchronous.

We completely resolve this question by showing that perfect SMT is possible if and only if $2t_a + t_s < \ell$. In addition, we provide a concretely round-efficient solution for the (slightly worse) trade-off $t_a + 2t_s < \ell$.

As a direct application of our results, following the recent work by Appan, Chandramouli, and Choudhury [PODC'22], we obtain an $n$-party perfectly-secure synchronous multi-party computation protocol with asynchronous fallback over any network with connectivity $\ell$, as long as $t_a + 3t_s

2 PhD positions are available at the AtlanTTic Research Center (https://atlanttic.uvigo.es/en/) from the Universidade de Vigo. The positions are available to start at the end of 2022, covering a duration of 3-4 years, and including travel budget for attendance to conference and summer schools.

The workplace is in the city of Vigo, being ranked by OCU as the Spanish city with the highest life quality (https://www.idealista.com/en/news/lifestyle-in-spain/2021/06/02/13426-quality-of-life-in-spain-spanish-cities-with-the-best-and-worst-quality-of-life).

Both positions are funded by TRUMPET, which is an European project whose aim is to research and develop novel privacy enhancement methods for Federated Learning, and to deliver a scalable Federated AI service platform for the analysis of cross-border European datasets. The privacy guarantees of the platform will be validated for the scenario of cancer data coming from different European hospitals.

PhD candidates will contribute to two different central aspects: (1) research and implementation of secure methods for machine learning, and (2) measure the existing privacy leakage in federated learning scenarios.

Intended tasks:

Research and develop novel methods to enhance the privacy of federated learning.

Implement and evaluate their impact on data privacy.

Run of experiments and simulation of realistic conditions to test performance.

Management of scientific reports and publication of the obtained results in scientific journals and/or conference proceedings.

Your profile:

Master’s degree or equivalent in Electrical/Telecommunications Engineering, Computer Science, Mathematics or similar, and strong background in either cryptography or machine learning.

Good communication/writing skills in English.

Good programming skills and flexibility to work with different secure computation and machine learning libraries.

Experience in domains such as cryptography, secure multi-party computation and machine learning will be positively evaluated.

Closing date for applications:

Contact: For more details, send an email to Alberto Pedrouzo (apedrouzo@gts.uvigo.es).

The Role
a16z Crypto Research is a new kind of multidisciplinary lab that bridges the worlds of academic theory and industry practice to advance the science and technology of the next generation of the internet. In addition to fundamental research, we collaborate with portfolio companies to solve hard technical and conceptual problems. We are seeking students with a strong research background and an interest in blockchains and web3 to join the group for the summer. Specific research areas of interest include cryptography, security, distributed computing, economics, incentives, finance, governance, market and mechanism design. This list is not exhaustive and we encourage applicants with different backgrounds who may have unique perspectives on the space to apply.

Responsibilities
-Pursue fundamental research on topics relevant to the firm
-Work with portfolio companies on technical research problems
-Contribute to blog posts, white papers, and other public expository content
-Meet with visitors from academia and industry and attend seminars

A typical schedule will have an intern spending ⅓ of their time working with the portfolio, ⅓ of the time pursuing personal research interests, and ⅓ of their time meeting with visitors/attending seminars, etc.

In-person residency required in New York, NY
Duration of internship: May 30–August 18, 2023 (minimum residency 10 weeks, maximum 12 weeks)

Preferred Qualifications A typical successful candidate is:

-Enrolled in a quantitative PhD program such as computer science, mathematics, economics, etc. (Exceptional masters and undergraduate students will also be considered.)
-Passionate and knowledgeable about blockchains/Web3 and their underlying technologies.
-Familiar with fundamental research and publishing in peer-reviewed conferences and journals.

Letters of recommendation (1-2 letters, optional): recommenders should email their letters of support to crypto-research-applications@a16z.com, with the name of the applicant in the subject line.

Closing date for applications:

Contact: Tim Roughgarden

More information: https://a16z.com/about/jobs/?gh_jid=5345713003

We look for an outstanding PhD candidate to work on computer security and privacy-preserving technologies. The successful candidate will join an exciting international research environment and have the opportunity to participate in the activities of the CRISES research group led by Prof. Dr. Josep Domingo-Ferrer.

Closing date for applications:

Contact: Dr. Rolando Trujillo

We are looking for a candidate for a Ph.D. position at the Department of Computer Science and Mathematics at Universitat Rovira i Virgili (www.urv.cat), focussing on information-theoretic cryptography.

This position is funded by a 4-years PhD scholarship (that is equivalent to the former FPI grants). Candidates who have completed (or are about to complete) a master in mathematics, computer science, or computer engineering are welcome to start the application by sending an email with a CV and a motivation letter to oriol.farras@urv.cat before November 15. Applicants should be able to start the PhD between January and July 2023. After receiving the email, we will provide more details about the grant application and the potential research projects. Students with a background in cryptography, algebraic geometry, matroid theory, or complexity theory are especially encouraged to apply.

Closing date for applications:

Contact: Oriol Farràs, oriol.farras@urv.cat

https://crises-deim.urv.cat/oriolfv/

TCC 2022 will take place in Chicago, USA on November 7-10 2022.

Early Registration Closes on Oct 23rd https://tcc.iacr.org/2022/registration.php

Multiple PhD positions are available at the Cybersecurity and Applied cryptography research group at the Institute of Computer Science, at the University of St. Gallen, led by Prof. Katerina Mitrokotsa. https://cybersecurity.unisg.ch The positions are available to start in the beginning of 2023, and are funded with a competitive salary. The workplace is in the beautiful city of St. Gallen located 50 min away from Zurich and offers a very high quality of life. The selection process runs until suitable candidates have been found. The student is expected to work on topics that include security and privacy issues in biometric authentication. More precisely, the student will be working on investigating efficient and privacy-preserving authentication that provides: i) provable security, and ii) rigorous privacy guarantees.
Key Responsibilities:

• Perform exciting and challenging research in the domain of information security and cryptography
• Support and assist in teaching computer security and cryptography courses

Your Profile:

• The PhD student is expected to have a MSc degree or equivalent, and strong background in cryptography, network security and mathematics
• Experience in one or more domains such as cryptography, design of protocols, secure multi-party computation and differential privacy is beneficial
• Excellent programming skills
• Excellent written and verbal communication skills in English

Deadline: 31 Oct. 2022

Closing date for applications:

Contact: Katerina Mitrokotsa

More information: https://jobs.unisg.ch/offene-stellen/funded-phd-student-in-applied-cryptography-privacy-preserving-biometric-authentication-m-f-d/e7a9e90b-02cd-45d0-ad4f-fc02131eaf86