International Association
for Cryptologic Research

In this paper, we completely study two classes of Boolean functions that are suited for hybrid symmetric-FHE encryption with stream ciphers like FiLIP. These functions (which we call homomorphic-friendly) need to satisfy contradictory constraints: 1) allow a fast homomorphic evaluation, and have then necessarily a very elementary structure, 2) be secure, that is, allow the cipher to resist all classical attacks (and even more, since guess and determine attacks are facilitated in such framework). Because of constraint 2, these functions need to have a large number of variables (often more than 1000), and this makes even more difficult to satisfy constraint 1 (hence the interest of these two classes). We determine exactly all the main cryptographic parameters (algebraic degree, resiliency order, nonlinearity, algebraic immunity) for all functions in these two classes and we give close bounds for the others (fast algebraic immunity, dimension of the space of annihilators of minimal degree). This is the first time that this is done for all functions in classes of a sufficient cryptographic interest.

Private stream aggregation (PSA) allows an untrusted data aggregator to compute statistics over a set of multiple participants' data while ensuring the data remains private. Existing works rely on a trusted party to enable an aggregator to achieve offline fault tolerance, but in the real world this may not be practical. We develop a new framework that supports PSA in a way that is robust to online user faults, while still supporting a strong guarantee on each individual’s privacy. We first must define a new level of security in the presence of online faults and malicious adversaries because the existing definition does not account for online faults. After this we describe a general framework that allows existing work to reach this new level of security. Furthermore, we develop the first protocol that provably reaches this level of security by leveraging trusted hardware. After we develop a methodology to outsource computationally intensive work to higher performance devices, while still allowing for strong privacy, we reach new levels of scalability and communication efficiency over existing work seeking to support offline fault tolerance, and achieve differential privacy.

CPU caches are a powerful source of information leakage. To develop practical cache-based attacks, there is an increasingly need to automate the process of finding exploitable cache-based side-channels in computer systems. Cache template attack is a generic technique that utilizes Flush+Reload attack in order to automatically exploit cache vulnerability of Intel platforms. Cache template attack on T-table-based AES implementation consists of two phases including the profiling phase and the key exploitation phase. Profiling is a preprocessing phase to monitor dependencies between the secret key and behavior of the cache memory. In addition, the addresses of T-tables can be obtained automatically. In the key exploitation phase, most significant bits (MSBs) of the secret key bytes are retrieved by monitoring exploitable addresses. In this paper, we propose a simple yet effective searching technique which accelerates the profiling phase by a factor of at most 64. To verify the theoretical model of our technique, we implement the described attack on AES. The experimental results showed the profiling phase runtime of the cache template attack is around 10 minutes while our method speeds up the running of this phase to around 9 seconds.

We have a vacancy for a PhD Candidate at NTNU, in the Department of Information Security and Communication Technology (IIK), in the area of cryptography. The candidate will work in the general areas of privacy-preserving computation, lattice-based cryptography and post-quantum cryptography. This will be under the supervision of Dr. Anamaria Costache, in the cryptography team at NTNU. The cryptography team at NTNU is heavily involved in research in these areas, and so the successful candidate will benefit from a good research support system. A good work environment is characterized by diversity. We encourage qualified candidates to apply, regardless of their gender, functional capacity or cultural background. If you have any questions about the position, please contact Dr. Anamaria Costache, Anamaria.costache@ntnu.no. If you have any questions about the recruitment process, please contact HR officer Stine Terese Ruen Nymoen, stine.t.r.nymoen@ntnu.no. For a detailed description of the requirements, please go the link below. Application deadline 25/01/2021.

Closing date for applications:

Contact: Dr. Anamaria Costache, anamaria.costache@ntnu.no

More information: https://www.jobbnorge.no/en/available-jobs/job/197509/phd-candidate-in-cryptography

Applications are invited for a research intern position at the IMDEA Software Institute, Madrid, Spain. The successful applicant will work under the supervision of Ignacio Cascudo in a project in the area of cryptography, where the topic will be related to mathematical aspects of privacy-preserving protocols such as secure multiparty computation protocols, secret sharing or zero knowledge proofs.

Who should apply?
Applicants should be MSc students in computer science, mathematics or a related discipline. The applicants should in particular have strong background in mathematics and some background and interest in cryptography. Good teamwork and communication skills, including excellent spoken and written English are also required.

Working at IMDEA Software
The position is based in Madrid, Spain, where the IMDEA Software Institute is situated. The institute provides for travel expenses and an internationally competitive stipend. The working language at the institute is English.

Dates
The internship duration is intended to be for 4-6 months (with some flexibility). The starting period would be March 2021 or later.

How to apply?
Applicants interested in the position should submit their application at https://careers.software.imdea.org/ using reference code 2020-12-intern-mpc. Deadline for applications is January 25th, 2021.

For enquiries about the position, please contact: Ignacio Cascudo, ignacio.cascudo (at) imdea.org

Closing date for applications:

Contact: Ignacio Cascudo

More information: https://careers.software.imdea.org/

The cryptography team at Ant Group (formerly known as Ant Finance and Alipay) is looking for multiple applied cryptographers or engineers at all levels. We are a team to bridge the academia world and the industry; to promote new crypto solutions via solving real world problems.

Candidates are expected to be developing cryptographic libraries and/or conduct related researches with a growing team of researchers and engineers. Candidates are likely to be working in one of the following directions:

• homomorphic encryptions
• multiparty computations
• zero-knowledge proofs

Knowledge of at least one of the above fields is a MUST. Please highlight in your CV your previous publications or open-source projects in those domains.

Bonus points:

• experience in developing cryptographic libraries
• top tier publications in cryptography or security
• experience with Rust

Location:

• Beijing
• Hangzhou

Closing date for applications:

Contact: Zhenfei Zhang

The Max Planck Institutes for Informatics (Saarbruecken), Software Systems (Saarbruecken and Kaiserslautern), and Security and Privacy (Bochum) offer research internships in all areas of Computer Science. An internship at a Max Planck Institute is a way to pursue world-class research in computer science! Our internships are also an excellent way to explore research or new research areas for the first time.

Internships are open to exceptional Bachelors, Masters, and Doctoral students worldwide, as well as exceptional individuals from industry interested in gaining academic research experience in computer science. Intern positions are limited and admissions are very competitive

We welcome interns all year round, but most interns prefer the summer months. Every intern works directly with an assigned faculty mentor at one of the participating institutes. Internship projects are based on the intern’s academic interests, maturity and prior experience.

All interns receive a monthly stipend, free (shared) housing, and travel to- and from- the institute hosting the internship. A typical internship lasts 12 to 14 weeks, but longer internships are possible.

Application Deadlines for Summer Internships:

• Early Deadline: 31 December (for internships starting in May or June)
• Late Deadline: 31 January (for internships starting in July or August)

For an internship starting at any other time, please apply at least 4 months before your intended started date.

More information can be obtained at https://www.cis.mpg.de/internships

We understand that travel restrictions due to the ongoing COVID-19 pandemic may prevent interns from traveling to host institutes right now. In such a case, the intern and the mentor may agree mutually to complete the internship remotely. The intern will still be paid the monthly stipend.

Closing date for applications:

Contact: Catalin Hritcu

More information: https://www.cis.mpg.de/internships

With the NIST Post quantum cryptography competition in final round, the importance of implementation security is highlighted in the latest call. In this regard, we report practical side-channel assisted message recovery attacks over embedded implementations of several post-quantum public key encryption (PKE) and key encapsulation mechanisms (KEM) based on the Learning With Errors (LWE) and Learning With Rounding (LWR) problem, which include three finalists and three semi-finalist candidates of the NIST standardization process. The proposed attacks target storage of the decrypted message in memory, a basic operation found in all libraries and typically unavoidable in any embedded implementation. We also identify interesting ciphertext malleability properties for LWE/LWR-based PKEs and exploit them to generalise proposed attack to different implementation choices as well as implementations protected with side-channel countermeasures such as shuffling and masking. All proposed attacks are validated on ARM Cortex-M4 microcontroller, targeting optimized open source implementations of PQC schemes using electromagnetic side-channel measurements.

This article explores the use of elliptic curves with order 2r = 2 mod 4, which we call double-odd elliptic curves. This is a very large class, comprising about 1/4th of all curves over a given field. On such curves, we manage to define a prime order group with appropriate characteristics for building cryptographic protocols:

- Element encoding is canonical, and verified upon decoding. For a 2n-bit group (with n-bit security), encoding size is 2n + 1 bits, i.e. as good as compressed points on classic prime order curves.

- Unified and complete formulas allow secure and efficient computations in the group.

- Efficiency is on par with twisted Edwards curves, and in some respects slightly better; e.g. half of double-odd curves have formulas for computing point doublings with only six multiplications (down to 1M+5S per doubling on some curves).

We describe here various formulas and discuss implementations. We also define two specific parameter choices for curves with 128-bit security, called do255e and do255s. Our own implementations on 64-bit x86 (Coffee Lake) and low-end ARM Cortex M0+ achieve generic point multiplication in 76696 and 2.19 million cycles, respectively, with curve do255e.

Our main result is a quantum public-key encryption scheme based on the Extrapolated Di- hedral Coset problem (EDCP) which is equivalent, under quantum polynomial-time reductions, to the Learning With Errors (LWE) problem. For limited number of public keys (roughly linear in the security parameter), the proposed scheme is information-theoretically secure. For poly- nomial number of public keys, breaking the scheme is as hard as solving the LWE problem. The public keys in our scheme are quantum states of size Õ(n) qubits. The key generation and decryption algorithms require Õ(n) qubit operations while the encryption algorithm takes O(1) qubit operations.

In this work we focus on improving the communication complexity of the online phase of honest majority MPC protocols. To this end, we present a general and simple method to compile arbitrary secret-sharing-based passively secure protocols defined over an arbitrary ring that are secure up to additive attacks in a malicious setting, to actively secure protocols with abort. The resulting protocol has a total communication complexity in the online phase of $1.5(n-1)$ shares, which amounts to $1.5$ shares per party asymptotically. An important aspect of our techniques is that they can be seen as generalization of ideas that have been used in other works in a rather ad-hoc manner for different secret-sharing protocols. Thus, our work serves as a way of unifying key ideas in recent honest majority protocols, to understand better the core techniques and similarities among these works. Furthermore, for $n=3$, when instantiated with replicated secret-sharing-based protocols (Araki et al. CCS 2016), the communication complexity in the online phase amounts to only $1$ ring element per party, matching the communication complexity of the BLAZE protocol (Patra & Suresh, NDSS 2020), while having a much simpler design.

LWE based key-exchange protocols lie at the heart of post-quantum public-key cryptography. However, all existing protocols either lack the non-interactive nature of Diffie-Hellman key-exchange or polynomial LWE-modulus, resulting in unwanted efficiency overhead.

We study the possibility of designing non-interactive LWE-based protocols with polynomial LWE-modulus. To this end,

• We identify and formalize simple non-interactive and polynomial LWE-modulus variants of existing protocols, where Alice and Bob simultaneously exchange one or more (ring) LWE samples with polynomial LWE-modulus and then run individual key reconciliation functions to obtain the shared key.

• We point out central barriers and show that such non-interactive key-exchange protocols are impossible if:

1) the reconciliation functions first compute the inner product of the received LWE sample with their private LWE secret. This impossibility is information theoretic.

2) one of the reconciliation functions does not depend on the error of the transmitted LWE sample. This impossibility assumes hardness of LWE.

• We give further evidence that progress in either direction, of giving an LWE-based NIKE protocol or proving impossibility of one will lead to progress on some other well-studied questions in cryptography.

Overall, our results show possibilities and challenges in designing simple (ring) LWE-based non-interactive key exchange protocols.

Physical security of NIST lightweight cryptography competition candidates is gaining importance as the standardization process progresses. Side-channel attacks (SCA) are a well-researched topic within the physical security of cryptographic implementations. It was shown that collisions in the intermediate values can be captured by side-channel measurements to reduce the complexity of the key retrieval to trivial numbers.

In this paper, we target a specific bit permutation vulnerability in the block cipher GIFT that allows the attacker to mount a key recovery attack. We present a novel SCA methodology called DCSCA - Differential Ciphertext SCA, which follows principles of differential fault analysis, but instead of the usage of faults, it utilizes SCA and statistical distribution of intermediate values. We simulate the attack on a publicly available bitslice implementation of GIFT, showing the practicality of the attack. We further show the application of the attack on GIFT-based AEAD schemes (GIFT-COFB, ESTATE, HYENA, and SUNDAE-GIFT) proposed for the NIST LWC competition. DCSCA can recover the master key with $2^{13.39}$ AEAD sessions, assuming 32 encryptions per session.

Nowadays, information is known as the main asset of each organization, which causes data generation to be exponentially increasing. Hence, different capacity issues and requirements show up with it, e.g. storage and maintenance of generating data, searching among them, and analyzing them. Cloud computing is one of the common technologies used to meet these requirements. Popularity of this technology is extremely growing as it can be used to handle high amount of data in a cost efficient and highly available (anytime and anywhere) manner. However, there are still extensive security challenges (e.g. data confidentiality) with this technology. Cryptography is one of the main methods used to fulfill privacy preserving of people and organizations. Encryption methods can impressively keep data private, so it is not possible to search among encrypted messages in order to retrieve information, after applying traditional encryption. Searchable encryption can enable searching among encrypted data and overcome this shortage. However, much more research is required to enable whole data searching while proper level of security would be achieved for these systems. In this paper, a technique to perform searching by the third party is introduced. When a number of nodes are interacting and some of them may upload malicious documents, this technique can be useful. Furthermore, document categorization is another application of the referred scheme.

Password-hardened encryption (PHE) was introduced by Lai et al. at USENIX 2018 and immediately productized by VirgilSecurity. PHE is a password-based key derivation protocol that involves an oblivious external crypto service for key derivation. The security of PHE protects against offline brute-force attacks, even when the attacker is given the entire database. Furthermore, the crypto service neither learns the derived key nor the password. PHE supports key-rotation meaning that both the server and crypto service can update their keys without involving the user.

While PHE significantly strengthens data security, it introduces a single point of failure because key-derivation always requires access to the crypto service. In this work, we address this issue and simultaneously increase security by introducing threshold password-hardened encryption. Our formalization of this primitive revealed shortcomings of the original PHE definition that we also address in this work. Following the spirit of prior works, we give a simple and efficient construction using lightweight tools only. We also implement our construction and evaluate its efficiency. Our experiments confirm the practical efficiency of our scheme and show that it is more efficient than common memory-hard functions, such as scrypt. From a practical perspective this means that threshold PHE can be used as an alternative to scrypt for password protection and key-derivation, offering better security in terms of offline brute force attacks.

Oblivious RAM enables oblivious access to memory in the single-client setting, which may not be the best fit in the network setting. Multi-client oblivious RAM (MCORAM) considers a collaborative but untrusted environment, where a database owner selectively grants read access and write access to different entries of a confidential database to multiple clients. Their access pattern must remain oblivious not only to the server but also to fellow clients. This upgrade rules out many techniques for constructing ORAM, forcing us to pursue new techniques.

MCORAM not only provides an alternative solution to private anonymous data access (Eurocrypt 2019) but also serves as a promising building block for equipping oblivious file systems with access control and extending other advanced cryptosystems to the multi-client setting.

Despite being a powerful object, the current state-of-the-art is unsatisfactory: The only existing scheme requires $O(\sqrt n)$ communication and client computation for a database of size $n$. Whether it is possible to reduce these complexities to $\mathsf{polylog}(n)$, thereby matching the upper bounds for ORAM, is an open problem, i.e., can we enjoy access control and client-obliviousness under the same bounds?

Our first result answers the above question affirmatively by giving a construction from fully homomorphic encryption (FHE). Our main technical innovation is a new technique for cross-key trial evaluation of ciphertexts.

We also consider the same question in the setting with $N$ non-colluding servers, out of which at most $t$ of them can be corrupt. We build multi-server MCORAM from distributed point functions (DPF), and propose new constructions of DPF via a virtualization technique with bootstrapping, assuming the existence of homomorphic secret sharing and pseudorandom generators in NC0, which are not known to imply FHE.

A ring signature scheme allows the signer to sign on behalf of an ad hoc set of users, called a ring. The verifier can be convinced that a ring member signs, but cannot point to the exact signer. Ring signatures have become increasingly important today with their deployment in anonymous cryptocurrencies. Conventionally, it is implicitly assumed that all ring members are equally likely to be the signer. This assumption is generally false in reality, leading to various practical and devastating deanonymizing attacks in Monero, one of the largest anonymous cryptocurrencies. These attacks highlight the unsatisfactory situation that how a ring should be chosen is poorly understood.

We propose an analytical model of ring samplers towards a deeper understanding of them through systematic studies. Our model helps to describe how anonymous a ring sampler is with respect to a given signer distribution as an information-theoretic measure. We show that this measure is robust, in the sense that it only varies slightly when the signer distribution varies slightly. We then analyze three natural samplers -- uniform, mimicking, and partitioning -- under our model with respect to a family of signer distributions modeled after empirical Bitcoin data. We hope that our work paves the way towards researching ring samplers from a theoretical point of view.

The recent development of machine learning and cloud computing arises a new privacy problem; how can one outsource computation on confidential data? Homomorphic encryption (HE) is a solution for that as it allows computation on encrypted data without decryption. The Cheon-Kim-Kim-Song (CKKS) scheme (Asiacrypt '17) is one of the highlighted fully homomorphic encryption (FHE) schemes as it is efficient to deal with encrypted real numbers, which are the usual data type for many applications such as machine learning. This paper proposes a generally applicable method to achieve high-precision approximate FHE using the following two techniques. First, we apply the concept of signal-to-noise ratio (SNR) and propose a method of maximizing the SNR of encrypted data by reordering homomorphic operations in the CKKS scheme. For that, the error variance is minimized instead of the upper bound of error when we deal with encrypted data. Second, we propose a novel polynomial approximation method for the CKKS scheme from the same perspective of minimizing error variance. We especially apply the approximation method to the bootstrapping of the CKKS scheme, where we achieve the smaller error variance in the bootstrapping compared to the prior arts. The performance improvement of the proposed methods for the CKKS scheme is verified by implementation over HE libraries: HEAAN and SEAL. The implementation results show that the message precision of the CKKS scheme is improved by reordering homomorphic operations and using the proposed polynomial approximation. Specifically, the proposed method uses only depth 8, although the bootstrapping precision is increased by 1 bit compared to that of the previous method using depth 11. We also suggest a loose lower bound of bootstrapping error in the CKKS scheme and show that the proposed method’s bootstrapping error is only 2.8 bits on average larger than the lower bound. Therefore, various applications’ quality of services using the proposed CKKS scheme, such as privacy-preserving machine learning, can be improved without compromising performance and security.

Public-key encryption (PKE) schemes or key-encapsulation mechanisms (KEMs) are fundamental cryptographic building blocks to realize secure communication protocols. There are several known transformations that generically turn weakly secure schemes into strongly (i.e., IND-CCA) secure ones. While most of these transformations require the weakly secure scheme to provide perfect correctness, Hofheinz, Hövelmanns, and Kiltz (HHK) (TCC 2017) have recently shown that variants of the Fujisaki-Okamoto (FO) transform can work with schemes that have negligible correctness error in the (quantum) random oracle model (QROM). Many recent schemes in the NIST post-quantum competition (PQC) use variants of these transformations. Some of their CPA-secure versions even have a non-negligible correctness error and so the techniques of HHK cannot be applied.

In this work, we study the setting of generically transforming PKE schemes with potentially large, i.e., non-negligible, correctness error to ones having negligible correctness error. While there have been previous treatments in an asymptotic setting by Dwork, Naor, and Reingold (EUROCRYPT 2004), our goal is to come up with practically efficient compilers in a concrete setting and apply them in two different contexts. Firstly, we show how to generically transform weakly secure deterministic or randomized PKEs into CCA-secure KEMs in the (Q)ROM using variants of HHK. This applies to essentially all candidates to the NIST PQC based on lattices and codes with non-negligible error for which we provide an extensive analysis. We thereby show that it improves some of the code-based candidates. Secondly, we study puncturable KEMs in terms of the Bloom Filter KEM (BFKEM) proposed by Derler et al. (EUROCRYPT 2018) which inherently have a non-negligible correctness error. BFKEMs are a building block to construct fully forward-secret zero round-trip time (0-RTT) key-exchange protocols. In particular, we show the first approach towards post-quantum secure BFKEMs generically from lattices and codes by applying our techniques to identity-based encryption (IBE) schemes with (non-)negligible correctness error.

Distributed ORAM (DORAM) is a multi-server variant of Oblivious RAM. Originally proposed to lower bandwidth, DORAM has recently been of great interest due to its applicability to secure computation in the RAM model, where circuit complexity and rounds of communication are equally important metrics of efficiency.

In this work, we construct the first DORAM schemes in the 2-server, semi-honest setting that simultaneously achieve sublinear server computation and constant rounds of communication.

We provide two constant-round constructions, one based on square root ORAM that has $O(\sqrt{N}\log N)$ local computation and another based on secure computation of a doubly efficient PIR that achieves local computation of $O(N^\epsilon)$ for any $\epsilon > 0$ but that allows the servers to distinguish between reads and writes. As a building block in the latter construction, we provide secure computation protocols for evaluation and interpolation of multivariate polynomials based on the Fast Fourier Transform, which may be of independent interest.