International Association
for Cryptologic Research

Identity-based encryption (IBE), introduced by Shamir in 1984, eliminates the need for public-key infrastructure. The sender can simply encrypt a message by using the recipient's identity (such as their email or IP address) without needing to look up the public key. In particular, when ciphertexts of an IBE scheme do not reveal the identity of the recipient, this scheme is known as an anonymous IBE scheme. Recently, Blazy et al. (ARES'19) analyzed the trade-off between public safety and unconditional privacy in anonymous IBE and introduced a new notion that incorporates traceability into anonymous IBE, called anonymous IBE with traceable identities (AIBET). However, their construction is based on the discrete logarithm assumption, which is insecure in the quantum era. In this paper, we first formalize the consistency of tracing key of the AIBET scheme to ensure that no adversary can obtain information with the use of wrong tracing keys. Subsequently, we present a generic formulation concept that can be used to transform structure-specific lattice-based anonymous IBE schemes into an AIBET scheme. Finally, we apply this concept to Katsumata and Yamada's compact anonymous IBE scheme (Asiacrypt'16) to obtain the first quantum-resistant AIBET scheme that is secure under the ring learning with errors assumption.

Protecting secrets is a key challenge in our contemporary information-based era. In common situations, however, revealing secrets appears unavoidable, for instance, when identifying oneself in a bank to retrieve money. In turn, this may have highly undesirable consequences in the unlikely, yet not unrealistic, case where the bank’s security gets compromised. This naturally raises the question of whether disclosing secrets is fundamentally necessary for identifying oneself, or more generally for proving a statement to be correct. Developments in computer science provide an elegant solution via the concept of zero-knowledge proofs: a prover can convince a verifier of the validity of a certain statement without facilitating the elaboration of a proof at all. In this work, we report the experimental realisation of such a zero-knowledge protocol involving two separated verifier-prover pairs. Security is enforced via the physical principle of special relativity, and no computational assumption (such as the existence of one-way functions) is required. Our implementation exclusively relies on off-the-shelf equipment and works at both short (60 m) and long distances (400 m) in about one second. This demonstrates the practical potential of multi-prover zero-knowledge protocols, promising for identification tasks and blockchain-based applications such as cryptocurrencies or smart contracts.

Key distribution protocols deal with generating, exchanging, and storing information (especially shared keys). In this paper, we compare three different types of protocols: classical, quantum key distribution, and blockchain-based protocols, with examples from each category, presenting the particularities and challenges of each one, including solutions and the impact of these protocols.

This paper studies zero-knowledge SNARKs for NP, where the prover incurs $O(N)$ finite field operations to prove the satisfiability of an $N$-sized R1CS instance. We observe that recent work of Bootle, Chiesa, and Groth (BCG, TCC 20) provides a polynomial commitment scheme that, when combined with the linear-time interactive proof system of Spartan (CRYPTO 20), yields linear-time SNARKs for R1CS. Specifically, for security parameter $\lambda$, and for an $N$-sized R1CS instance over a field of size $\exp(\lambda)$ and fixed $\epsilon > 0$, the prover incurs $O(N)$ finite field operations to produce a proof of size $O_\lambda(N^\epsilon)$ that can be verified in $O_\lambda(N^\epsilon)$---after a one-time preprocessing step, which requires $O(N)$ finite field operations. This reestablishes the main result of BCG. Arguably, our approach is conceptually simpler and more direct. Additionally, the polynomial commitment scheme that we distill from BCG is of independent interest; it improves over the prior state of the art by offering the first scheme where the time to commit and to prove an evaluation of a committed polynomial are both $O(N)$ finite field operations for an $N$-sized polynomial.

We further observe that one can render the aforementioned SNARK zero knowledge and reduce the proof size and verifier time to polylogarithmic---while maintaining a linear-time prover---by outsourcing the verifier's work via one layer of proof composition with an existing zkSNARK as the ``outer'' proof system. A similar result was recently obtained by Bootle, Chiesa, and Liu (ePrint 2020/1527).

Nowadays, genomic sequencing has become much more affordable for many people and, thus, many people own their genomic data in a digital format. Having paid for genomic sequencing, they want to make use of their data for different tasks that are possible only using genomics, and they share their data with third parties to achieve these tasks, e.g., to find their relatives in a genomic database. As a consequence, more genomic data get collected worldwide. The upside of the data collection is that unique analyses on these data become possible. However, this raises privacy concerns because the genomic data uniquely identify their owner, contain sensitive data about his/her risk for getting particular diseases, and even sensitive information about his/her family members.

In this paper, we introduce EPISODE - a highly efficient privacy-preserving protocol for Similar Sequence Queries (SSQs), which can be used for finding genetically similar individuals in an outsourced genomic database, i.e., securely aggregated from data of multiple institutions. Our SSQ protocol is based on the edit distance approximation by Asharov et al. (PETS'18), which we further optimize and extend to the outsourcing scenario. We improve their protocol by using more efficient building blocks and achieve a 5-6x run-time improvement compared to their work in the same two-party scenario.

Recently, Cheng et al. (ASIACCS'18) introduced protocols for outsourced SSQs that rely on homomorphic encryption. Our new protocol outperforms theirs by more than factor 24000x in terms of run-time in the same setting and guarantees the same level of security. In addition, we show that our algorithm scales for practical database sizes by querying a database that contains up to a million short sequences within a few minutes, and a database with hundreds of whole-genome sequences containing 75 million alleles each within a few hours.

The Google Titan Security Key is a FIDO U2F hardware device proposed by Google (available since July 2018) as a two-factor authentication token to sign in to applications (e.g. your Google account). We present here a side-channel attack that targets the Google Titan Security Key’s secure element (the NXP A700X chip) by the observation of its local electromagnetic radiations during ECDSA signatures (the core cryptographic operation of the FIDO U2F protocol). This work shows that an attacker can clone a legitimate Google Titan Security Key.

To understand the NXP ECDSA implementation, find a vulnerability and design a key-recovery attack, we had to make a quick stop on Rhea (NXP J3D081 JavaCard smartcard). Freely available on the web, this product looks very much like the NXP A700X chip and uses the same cryptographic library. Rhea, as an open JavaCard platform, gives us more control to study the ECDSA implementation.

We could then show that the electromagnetic side-channel signal bears partial information about the ECDSA ephemeral key. The sensitive information is recovered with a non-supervised machine learning method and plugged into a customized lattice-based attack scheme.

Finally, 4000 ECDSA observations were enough to recover the (known) secret key on Rhea and validate our attack process. It was then applied on the Google Titan Security Key with success (this time with 6000 observations) as we were able to extract the long term ECDSA private key linked to a FIDO U2F account created for the experiment.

Cautionary Note: Two-factor authentication tokens (like FIDO U2F hardware devices) primary goal is to fight phishing attacks. Our attack requires physical access to the Google Titan Security Key, expensive equipment, custom software, and technical skills.

Thus, as far as the work presented here goes, it is still safer to use your Google Titan Security Key or other impacted products as FIDO U2F two-factor authentication token to sign in to applications rather than not using one.

Nevertheless, this work shows that the Google Titan Security Key (and other impacted products) would not avoid unnoticed security breach by attackers willing to put enough effort into it. Users that face such a threat should probably switch to other FIDO U2F hardware security keys, where no vulnerability has yet been discovered.

Electronic voting consists of the methods that use an electronic system in the process of recording, counting or transmitting votes. It is relatively a new concept used in the democratic processes and especially in the context of COVID19. It’s aim is to reduce errors and to improve the integrity of the election process. In this paper, we provide a review of the existing systems used in Europe. Initially, we mention the factors that influence the adoption of such systems at a large scale. We further describe the systems used in Russia (Moscow’s primary) and in Romania (for counting the ballots). These systems are analyzed in order to find out if they respect technical challenges such as verifiability, dependability, security, anonymity and trust.

Cramer and Shoup introduced at Eurocrypt’02 the concept of hash proof system, also designated as smooth projective hash functions. Since then, they have found several applications, from building CCA-2 encryption as they were initially created for, to being at the core of several authenticated key exchange or even allowing witness encryption. In the post-quantum setting, the very few candidates use a language based on ciphertexts to build their hash proof system. This choice seems to inherently introduce a gap, as some elements outside the language could not be distinguish from those in the language. This creates a lawless zone, where an adversary can possibly mount an undetectable attack, particularly problematic when trying to prove security in the UC framework. We show that this gap could be completely withdrawn using code-based cryptography. Starting from RQC, a candidate selected for the second round of the National Institute of Standards and Technology (NIST) post-quantum cryptography standardization project, we show how to build such a hash proof system from code-based cryptography and present a way, based on a proof of knowledge, to fully negate the gap. We propose two applications of our construction, a witness encryption scheme and a password authenticated key exchange (PAKE).

Recently, federated learning (FL) has been subject to both security and privacy attacks posing a dilemmatic challenge on the underlying algorithmic designs: On the one hand, FL is shown to be vulnerable to backdoor attacks that stealthily manipulate the global model output using malicious model updates, and on the other hand, FL is shown vulnerable to inference attacks by a malicious aggregator inferring information about clients' data from their model updates. Unfortunately, existing defenses against these attacks are insufficient and mitigating both attacks at the same time is highly challenging because while defeating backdoor attacks requires the analysis of model updates, protection against inference attacks prohibits access to the model updates to avoid information leakage. In this work, we introduce FLGUARD, a novel in-depth defense for FL that tackles this challenge. To mitigate backdoor attacks, it applies a multilayered defense by using a Model Filtering layer to detect and reject malicious model updates and a Poison Elimination layer to eliminate any effect of a remaining undetected weak manipulation. To impede inference attacks, we build private FLGUARD that securely evaluates the FLGUARD algorithm under encryption using sophisticated secure computation techniques. We extensively evaluate FLGUARD against state-of-the-art backdoor attacks on several datasets and applications, including image classification, word prediction, and IoT intrusion detection. We show that FLGUARD can entirely remove backdoors with a negligible effect on accuracy and that private FLGUARD is practical.

Post-quantum cryptography (PQC) is a trend that has a deserved NIST status, and which aims to be resistant to quantum computer attacks like Shor and Grover algorithms. NIST is currently leading the third-round search of a viable set of standards, all based on traditional approaches as code-based, lattice-based, multi quadratic-based, or hash-based cryptographic protocols [1]. We choose to follow an alternative way of replacing all numeric field arithmetic with GF(2^8) field operations [2]. By doing so, it is easy to implement R-propped asymmetric systems as the present paper shows [3,4]. Here R stands for Rijndael as we work over the AES field. This approach yields secure post-quantum protocols since the resulting multiplicative monoid is immune against quantum algorithms and resist classical linearization attacks like Tsaban’s Algebraic Span [5] or Roman’kov linearization attacks [6]. The Burmester-Desmedt (B-D) conference key distribution protocol [7] has been proved to be secure against passive adversaries if the computational Diffie-Hellman problem remains hard. The authors refer that the proposed scheme could also be secure against active adversaries under the same assumptions as before if an authentication step is included to foil attacks like MITM (man in the middle). Also, this protocol proved to be semantical secure against adaptative IND-CPA2 [8, 9] if the discrete log problem is intractable. We discuss the features of our present work and a practical way to include an authentication step. Classical and quantum security levels are also discussed. Finally, we present a numerical example of the proposed R-Propped protocol.

The Cryptography and Privacy Research Group at Microsoft Research, Redmond, is looking for candidates for Researcher positions.

Topics of particular interest to us include (but are not limited to) secure computing (FHE, MPC, TEE), ML privacy, end-to-end encryption, web privacy and security, post-quantum cryptography, and zero-knowledge proofs. Our work ranges from protocol design and security analysis to cryptography and privacy engineering, so we encourage people with any relevant experiences to apply.

Responsibilities: Working with other researchers and multi-disciplinary teams to create and build practical solutions to real-world privacy problems. Publishing papers in academic conferences.

Required Qualifications:

• A PhD (or close to completion) in computer science, electrical engineering, mathematics, or a related field
• Publications in top conferences, or submitted/accepted papers in top journals.

Apply: https://careers.microsoft.com/us/en/job/953748/Researcher-Cryptography-and-Privacy-Microsoft-Research

Closing date for applications:

Contact: Kim Laine, Melissa Chase, or Esha Ghosh

More information: https://careers.microsoft.com/us/en/job/953748/Researcher-Cryptography-and-Privacy-Microsoft-Research

The Cryptography and Privacy Research Group at Microsoft Research, Redmond, is looking for candidates for Post-Doc Researcher positions.

Topics of particular interest to us include (but are not limited to) secure computing (FHE, MPC, TEE), ML privacy, end-to-end encryption, web privacy and security, post-quantum cryptography, and zero-knowledge proofs. Our work ranges from protocol design and security analysis to cryptography and privacy engineering, so we encourage people with any relevant experiences to apply.

Responsibilities: Working with other researchers and multi-disciplinary teams to create and build practical solutions to real-world privacy problems. Publishing papers in academic conferences.

Required Qualifications: A PhD (or close to completion) in computer science, electrical engineering, mathematics, or a related field Publications in top conferences, or submitted/accepted papers in top journals.

Apply: https://careers.microsoft.com/us/en/job/953746/Post-Doc-Researcher-Cryptography-and-Privacy-Microsoft-Research

Closing date for applications:

Contact: Kim Laine, Melissa Chase, or Esha Ghosh

More information: https://careers.microsoft.com/us/en/job/953746/Post-Doc-Researcher-Cryptography-and-Privacy-Microsoft-Research

We have an open PhD position in the domain of Scalable and Secure Data Sharing funded FWO SBO (strategic basic research) project MOZAIK. The prospective candidate is expected to investigate how conventional lightweight symmetric ciphers perform over MPC, as well as benchmark their performance over MPC. The work also entails provable security in this context. The candidate must hold a Master's degree in mathematics / computer science / electrical engineering / cryptography. Strong background in mathematics / computer science / cryptography is expected. Any prior publications and experience in C/C++ and Python are merited. Please visit our website to find out more details as well as the exact application procedure.

Closing date for applications:

Contact: jobs-cosic@esat.kuleuven.be

More information: https://www.esat.kuleuven.be/cosic/vacancies/

COSIC is hiring a motivated researcher who fit into the following profile: Postdoc researcher to work on efficient MPC protocols for privacy-preserving machine learning Job description: We have an open postdoc position in the domain of Scalable and Secure Data Sharing funded FWO SBO (strategic basic research) project MOZAIK. The prospective candidate is expected to design and develop efficient MPC protocols for privacy-preserving data analytics. The work includes, but not limited to, investigating machine learning algorithms that best suit MPC and that can be efficiently implemented over MPC. You will be working closely with tools such as https://github.com/KULeuven-COSIC/SCALE-MAMBA. Specific skills required:The candidate must hold a PhD degree in Cryptography or a related subject with strong publication records in crypto/security venues. In addition to a strong background in both public and symmetric cryptography, good knowledge in MPC, machine learning algorithms, and cryptographic protocols are expected.

Closing date for applications:

Contact: jobs-cosic@esat.kuleuven.be

More information: https://www.esat.kuleuven.be/cosic/vacancies/

The term permissionless has established itself within the context of blockchain and distributed ledger research to characterize protocols and systems that exhibit similar properties to Bitcoin. However, the notion of what is meant by permissionlessness is often vague or left implicit within the various literature, rendering it imprecise and hard to compare. We hereby shed light onto this topic by revising research that either incorporates or defines the term permissionless and systematically expose the properties and characteristics that its utilization intends to capture. Based on this review, we highlight current shortcomings and blind spots within the available definitions. In particular, the ability to freely perform transactions between users is often not adequately incorporated and different actor roles are left unspecified. Furthermore, the topics of privacy and governance appear to be largely overlooked.

In this paper we propose new techniques related to division property. We describe for the first time a practical algorithm for computing the propagation tables of 16-bit Super-Sboxes, increasing the precision of the division property by removing a lot of false division trails. We also improve the complexity of the procedure introduced by Lambin et al. (Design, Codes and Cryptography, 2020) to extend a cipher with linear mappings and show how to decrease the number of transitions to look for. While search procedures for integral distinguishers most often rely on MILP or SAT solvers for their ease of programming the propagation constraints, such generic solvers can only handle small 4/8-bit Sboxes. Thus we developed an ad-hoc tool handling larger Sboxes and all the improvements described in the paper. As a result, we found new integral distinguishers on SKINNY-64, HIGHT and Midori-64.

Fast Near collision attacks on the stream ciphers Grain v1 and A5/1 were presented at Eurocrypt 2018 and Asiacrypt 2019 respectively. They use the fact that the entire internal state can be split into two parts so that the second part can be recovered from the first one which can be found using the keystream prefix and some guesses of the key materials. In this paper we reevaluate the complexity of these attacks and show that actually they are inferior to previously known results. Basically, we show that their complexity is actually much higher and we point out the main problems of these papers based on information theoretic ideas. We also check that some distributions do not have the predicted entropy loss claimed by the authors. Checking cryptographic attacks with galactic complexity is difficult in general. In particular, as these attacks involve many steps it is hard to identify precisely where the attacks are flawed. But for the attack against A5/1, it could have been avoided if the author had provided a full experiment of its attack since the overall claimed complexity was lower than 232 in both time and memory

In this paper we describe a new tool to search for boomerang distinguishers. One limitation of the MILP model of Liu et al. is that it handles only one round for the middle part while Song et al. have shown that dependencies could affect much more rounds, for instance up to 6 rounds for SKINNY. Thus we describe a new approach to turn an MILP model to search for truncated characteristics into an MILP model to search for truncated boomerang characteristics automatically handling the middle rounds. We then show a new CP model to search for the best possible instantiations to identify good boomerang distinguishers. Finally we systematized the method initiated by Song et al. to precisely compute the probability of a boomerang. As a result, we found many new boomerang distinguishers up to 24 rounds in the TK3 model. In particular, we improved by a factor $2^{30}$ the probability of the best known distinguisher against 18-round SKINNY-128/256.

This paper makes a comprehensive comparison of the efficiencies of vectorized implementations of Kummer lines and Montgomery curves at various security levels. For the comparison, nine Kummer lines are considered, out of which eight are new, and new assembly implementations of all nine Kummer lines have been made. Seven previously proposed Montgomery curves are considered and new vectorized assembly implementations have been made for five of them. Our comparisons show that for all security levels, Kummer lines are consistently faster than Montgomery curves, though the speed-up gap is not much.

To maintain the secure information sharing among vehicles in the Internet of Vehicles, various message authentication schemes were proposed. Recently, Sutrala et al. proposed a conditional privacy preserving authentication scheme (``On the Design of Conditional Privacy Preserving Batch Verification-Based Authentication Scheme for Internet of Vehicles Deployment,'' IEEE Trans. Veh. Technol., vol. 69, no. 5, pp. 5535-5548, May 2020.) to against various potential attacks. However, our observations show that, contrary to what is claimed, the scheme is insecure. Any (malicious) vehicle can forge signature for any message, which can be validated successfully and cannot be traceable. Our observations also show that, the security proof based on the standard random oracle model is wrong.