International Association
for Cryptologic Research

Tropical linear algebra has been recently put forward by Grigoriev and Shpilrain ~\cite{grigoriev2014tropical,grigoriev2018tropical} as a promising platform for the implementation of protocols of Diffie-Hellman and Stickel type. Based on the CSR expansion of tropical matrix powers, we suggest a simple algorithm for the following tropical discrete logarithm problem: ``Given that $A=V\otimes F^{\otimes t}$ for a unique $t$ and matrices $A$, $V$, $F$ of appropriate dimensions, find this $t$.'' We then use this algorithm to suggest a simple attack on a protocol based on the tropical semidirect product. The algorithm and the attack are guaranteed to work in some important special cases and are shown to be efficient in our numerical experiments.

We give secure parameter suggestions to use sparse secret vectors in LWE based encryption schemes. This should replace existing security parameters, because homomorphic encryption(HE) schemes use quite different variables from the existing parameters. In particular HE schemes using sparse secrets should be supported by experimental analysis, here we summarize existing attacks to be considered and security levels for each attacks. Based on the analysis and experiments, we compute optimal scaling factors for CKKS.

We describe the binary numeral tree—a type of binary tree uniquely suited to processing unbounded streams of data—and present a number of algorithms for efficiently constructing and verifying Merkle proofs within such trees. Specifically, we present existence proofs for single leaves, for a contiguous range of leaves, and for multiple disjoint ranges. We also introduce Merkle "diff" proofs, which assert that an arbitrary modification was correctly applied to an existing tree. Each algorithm, operating on a tree with $n$ leaves and $k$ disjoint proof ranges, requires $\mathcal{O}(\log_2(n))$ space and $\mathcal{O}(n)$ time, and yields proofs of size $\mathcal{O}(k\log_2 (n))$. Furthermore, each algorithm operates in streaming fashion, requiring only a single in-order pass over the leaf data.

Being based on a sound theoretical basis, masking schemes are commonly applied to protect cryptographic implementations against Side-Channel Analysis (SCA) attacks. Constructing SCA-protected AES, as the most widely deployed block cipher, has been naturally the focus of several research projects, with a direct application in industry. The majority of SCA-secure AES implementations introduced to the community opted for low area and latency overheads considering Application-Specific Integrated Circuit (ASIC) platforms. Albeit a few, those which particularly targeted Field Programmable Gate Arrays (FPGAs) as the implementation platform yield either a low throughput or a not-highly secure design. In this work, we fill this gap by introducing first-order glitch-extended probing secure masked AES implementations highly optimized for FPGAs, which support both encryption and decryption. Compared to the state of the art, our designs efficiently map the critical non-linear parts of the masked S-box into the built-in Block RAMs (BRAMs). The most performant variant of our constructions accomplishes five first-order secure AES encryptions/decryptions simultaneously in 50 clock cycles. Compared to the equivalent state-of-the-art designs, this leads to at least 70% reduction in utilization of FPGA resources (slices) at the cost of occupying BRAMs. Last but not least, we provide a wide range of such secure and efficient implementations supporting a large set of applications, ranging from low-area to high-throughput.

The modern financial world has seen a significant rise in the use of cryptocurrencies in recent years, partly due to the convincing lures of anonymity promised by these schemes. Bitcoin, despite being considered as the most widespread among all, is claimed to have significant lapses in relation to its anonymity. Unfortunately, studies have shown that many cryptocurrency transactions can be traced back to their corresponding participants through the analysis of publicly available data, to which the cryptographic community has responded by proposing new constructions with improved anonymity claims. Nevertheless, the absence of a common metric for evaluating the level of anonymity achieved by these schemes has led to a number of disparate ad hoc anonymity definitions, making comparisons difficult. The multitude of these notions also hints at the surprising complexity of the overall anonymity landscape.

In this study, we introduce such a common framework to evaluate the nature and extent of anonymity in (crypto)currencies and distributed transaction systems, irrespective of their implementation. As such, our work lays the foundation for formalising security models and terminology across a wide range of anonymity notions referenced in the literature, while showing how ``anonymity'' itself is a surprisingly nuanced concept.

Blockchains suffer from a critical scalability problem where traditionally each network node maintains all network state, including records since the establishment of the blockchain. Sketches are popular hash-based data structures used to represent a large amount of data while supporting particular queries such as on set membership, cardinality estimation and identification of large elements. Often, to achieve time and memory savings, sketches allow potential inaccuracies in answers to the queries. The design of popular blockchain networks such as Bitcoin and Ethereum makes use of sketches for various tasks such as summarization of transaction blocks or declaring the interests of light nodes. Similarly, they seem natural to deal with the size of the state in blockchains. In this paper, we study existing and potential future applications of sketches in blockchains. We first summarize current blockchain use cases of sketches. Likewise, we explore how this coupling can be generalized to a wider range of sketches and additional functionalities. In particular, we explain how sketches can detect anomalies based on efficient an summary of the state or traffic.

In a two-party Circuit-based Private Set Intersection (PSI), $P_{0}$ and $P_{1}$ hold sets $X$ and $Y$ respectively and wish to securely compute a function $f$ over the set $X \cap Y$ (e.g., cardinality, sum over associated attributes, and threshold intersection). Following a long line of work, Pinkas et al. ($\mathsf{PSTY}$, Eurocrypt 2019) showed how to construct such a Circuit-PSI protocol with linear communication complexity. However, their protocol has super-linear computational complexity.

In this work, we construct Circuit-PSI protocols with linear computational and communication cost. Further, our protocols are concretely more efficient than $\mathsf{PSTY}$ -- we are $\approx 2.3\times$ more communication efficient and are up to $2.8\times$ faster in LAN and WAN network settings. We obtain our improvements through a new primitive called Relaxed Batch Oblivious Programmable Pseudorandom Functions ($\mathsf{RB\text{-}OPPRF}$) that can be seen as a strict generalization of Batch $\mathsf{OPPRF}$s in $\mathsf{PSTY}$. While using Batch $\mathsf{OPPRF}$s, in the context of Circuit-PSI results, in protocols with super-linear computational complexity, we construct $\mathsf{RB\text{-}OPPRF}$s that can be used to build linear cost and concretely efficient Circuit-PSI protocols. We believe that the $\mathsf{RB\text{-}OPPRF}$ primitive could be of independent interest. As another contribution, we provide more communication efficient protocols (than prior works) for the task of private set membership -- a primitive used in many PSI protocols including ours.

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/