International Association
for Cryptologic Research

The PhD students will join Prof. Mitrokotsa's group focusing on security and cryptography, working in the area of privacy-preserving biometric authentication and within the Marie Curie ITN project: "TRESPASS-ETN: Training in Secure and Privacy-preserving biometrics". Privacy-preserving biometric authentication focuses on guaranteeing accurate biometric authentication, while at the same time providing strong privacy guarantees (e.g., avoid tracking, profiling of users and leakage of sensitive information). The focus of one of the PhD positions would be to examine how to guarantee privacy-preservation in biometric authentication systems by employing advanced cryptographic methods such as secure multiparty computation (SMPC) primitives (e.g., homomorphic encryption) and verifiable computation (when biometric authentication is applied in a distributed setting). The second PhD position will focus on employing differentially private mechanisms in the biometric authentication process. The goal is to achieve high accuracy in the authentication process, while at the same time avoid any leakage of information.
Please apply:
https://www.chalmers.se/en/about-chalmers/Working-at-Chalmers/Vacancies/Pages/default.aspx?rmpage=job&rmjob=p8404

Closing date for applications:

Contact: Professor Aikaterini Mitrokotsa (Networks and Systems), aikmitr@chalmers.se

More information: https://www.chalmers.se/en/about-chalmers/Working-at-Chalmers/Vacancies/Pages/default.aspx?rmpage=job&rmjob=p8404

We are looking for postdoctoral researchers with an excellent track record in one of the following fields of applied cryptography:

• symmetric-key cryptology such as block ciphers, stream ciphers, hash functions, message authentication codes, authenticated encryption schemes, etc.
• post-quantum cryptology
• cryptology for emerging technologies such as IoT and public ledger/blockchain
• side-channel analysis, whitebox cryptography, countermeasures
• implementation aspects of cryptography in software or hardware
• provable security of symmetric cryptographic primitives and modes of operation

The appointment is for 3 years with a flexible starting date in 2020. We offer a competitive salary, a team of other postdocs as well as PhD students within the field to work with, a dynamic and highly international work environment as well as possibilities to conduct top-notch research in any subdomain of applied cryptology.

More information: https://www.jobbnorge.no/en/available-jobs/job/183156/postdoctoral-research-fellow-position-in-informatics-applied-cryptology

Closing date for applications:

Contact: Prof. Andrey Bogdanov, andrey.bogdanov@uib.no

Call for 3 Years Funded Doctoral Positions

Safety and Security in Industry Research Lab (SafeSecLab)

https://karriere.tuwien.ac.at/Job/126869?culture=en

Deadline: 19.03.2020

Cyber-physical production systems (CPPS) need suitable networked architectures that take into account and combine safety (operation of the system must not pose any danger) and security (protection against unauthorized manipulation). As part of the newly founded "TÜV AUSTRIA Safety and Security in Industry Research Lab" (SafeSecLab), several related research questions are addressed within the framework of dissertation projects (3 years funding) at TU Wien.

Open PhD topics:

• Safety and Security Modelling
• Safe and Secure System Architectures
• Automated Risk Management
• Secure Hardware Design

More details can be found on the application website: https://karriere.tuwien.ac.at/Job/126869?culture=en

Closing date for applications:

Contact: Wolfgang Kastner

More information: https://karriere.tuwien.ac.at/Job/126869?culture=en

Access and search pattern leakage have been shown to be detrimental to the security of encrypted databases that allow for range queries, as shown by an extensive body of work on efficient attacks that reconstruct one-dimensional databases. We are the first to go beyond one dimension, exploring the threat of access and search pattern leakage in two dimensions. First, we unveil an intrinsic limitation of reconstruction attacks by showing that there can be an exponential number of distinct databases that produce the same access and search pattern leakage. Next, we present attacks that reconstruct (1) the horizontal and vertical order of the points from the access pattern leakage, and (2) the coordinates of the points from the access and search pattern leakage. Our algorithms run in polynomial time and return a linear-size encoding of all databases consistent with the given leakage profile.

In this paper, we put forth the problem of bequeathing cryptoassets. In this problem, a testator wishes to bequeath cryptoassets - e.g. secrets, static keys or cryptocurrency - to their heirs. Crucially, the testator should retain control of their assets before their passing. Additionally testator needs to maintain privacy, i.e. beneficiaries must not learn the bequest, moreover, beneficiaries must not be able to determine whether they will inherit at all before testator's decease. We formally define the security goals of a cryptographic will (cryptowill) protocol and subsequently present schemes fulfilling the required security properties.

We revisit recent works by Don, Fehr, Majenz and Schaffner and by Liu and Zhandry on the security of the Fiat-Shamir transformation of $\Sigma$-protocols in the quantum random oracle model (QROM). Two natural questions that arise in this context are: (1) whether the results extend to the Fiat-Shamir transformation of *multi-round* interactive proofs, and (2) whether Don et al.'s $O(q^2)$ loss in security is optimal. Firstly, we answer question (1) in the affirmative. As a byproduct of solving a technical difficulty in proving this result, we slightly improve the result of Don et al., equipping it with a cleaner bound and an even simpler proof. We apply our result to digital signature schemes showing that it can be used to prove strong security for schemes like MQDSS in the QROM. As another application we prove QROM-security of a non-interactive OR proof by Liu, Wei and Wong. As for question (2), we show via a Grover-search based attack that Don et al.'s quadratic security loss for the Fiat-Shamir transformation of $\Sigma$-protocols is optimal up to a small constant factor. This extends to our new multi-round result, proving it tight up to a factor that depends on the number of rounds only, i.e. is constant for any constant-round interactive proof.

Keeping cryptocurrency spending keys safe and being able to use them when signing a transaction is a well-known problem, addressed by hardware wallets. Our work focuses on a transaction signing process for privacy-centric cryptocurrency Monero, in the hardware wallets. We designed, implemented, and analyzed a privacy-preserving transaction signing protocol that runs on a hardware wallet and protects the spending keys. Moreover, we also implemented a privacy-preserving multi-party version of the Bulletproof zero-knowledge prover algorithm, which runs on a hardware wallet with constant memory. We present the protocols and evaluate their performance on a real hardware wallet.

In this work we study the leakage resilience of authenticated encryption schemes. We show that, if one settles for non-adaptive leakage, leakage-resilient authenticated encryption schemes can be built solely from leakage-resilient pseudorandom functions. Degabriele et al. (ASIACRYPT 2019) introduce the FGHF' construction which allows to build leakage-resilient authenticated encryption schemes from functions which, under leakage, retain both pseudorandomness and unpredictability. We revisit their construction and show the following. First, pseudorandomness and unpredictability do not imply one another in the leakage setting. Unfortunately, this entails that any instantiation of the FGHF' construction indeed seems to require a function that is proven both pseudorandom and unpredictable under leakage. Second, however, we show that the unpredictability requirement is an artefact that stems from the underlying composition theorem of the N2 construction given by Barwell et al. (ASIACRYPT 2017). By recasting this composition theorem, we show that the unpredictability requirement is unnecessary for the FGHF' construction. Thus, leakage-resilient AEAD schemes can be obtained by instantiating the FGHF' construction with functions that are solely pseudorandom under leakage.

Authenticated Encryption has emerged as a high-performance and resource-efficient solution to achieve message authentication in addition to encryption. This has motivated extensive study of algorithms for Authenticated Encryption with Associated Data (AEAD). While there have been significant efforts to benchmark these algorithms on hardware and software platforms, very little work has focused on the integration of these ciphers onto a System-on-Chip (SoC). This work looks at design alternatives for the SoC integration of few of the finalists of the Competition for Authenticated Encryption: Security, Applicability, and Robustness (CAESAR). We highlight the penalty on area and performance that is incurred during SoC integration, and analyze the impact of design choices on the same. Our observations indicate that integration onto a system significantly affects the lightweight and high-performance properties of these ciphers, and achieving a trade-off requires careful design decisions.

The last few years have witnessed increasing interest in the deployment of zero-knowledge proof systems, in particular ones with succinct proofs and efficient verification (zk-SNARKs). One of the main challenges facing the wide deployment of zk-SNARKs is the requirement of a trusted key generation phase per different computation to achieve practical proving performance. Existing zero-knowledge proof systems that do not require trusted setup or have a single trusted preprocessing phase suffer from increased proof size and/or additional verification overhead. On the other other hand, although universal circuit generators for zk-SNARKs (that can eliminate the need for per-computation preprocessing) have been introduced in the literature, the performance of the prover remains far from practical for real-world applications.

In this paper, we first present a new zk-SNARK system that is well-suited for randomized algorithms---in particular it does not encode randomness generation within the arithmetic circuit allowing for more practical prover times. Then, we design a universal circuit that takes as input any arithmetic circuit of a bounded number of operations as well as a possible value assignment, and performs randomized checks to verify consistency. Our universal circuit is linear in the number of operations instead of quasi-linear like other universal circuits. By applying our new zk-SNARK system to our universal circuit, we build MIRAGE, a universal zk-SNARK with very succinct proofs---the proof contains just one additional element compared to the per-circuit preprocessing state-of-the-art zk-SNARK by Groth (Eurocrypt 2016). Finally, we implement MIRAGE and experimentally evaluate its performance for different circuits and in the context of privacy-preserving smart contracts.

Nakamoto consensus, arguably the most exciting development in distributed computing in the last few years, is in a sense a recasting of the traditional state-machine-replication problem in an unauthenticated setting, where furthermore parties come and go without warning. The protocol relies on a cryptographic primitive known as proof of work (PoW) which is used to throttle message passing with the PoW difficulty level being adjusted appropriately throughout the course of the protocol execution.

While the original formulation was only accompanied by rudimentary analysis, significant and steady progress has been made in abstracting out the protocol’s properties and providing a formal analysis under various restrictions, starting with the work by Garay, Kiayias and Leonardos [Eurocrypt ’15], for a simplified version of the protocol which excluded PoW difficulty adjustment and assumed a fixed number of parties as well as synchronous communication rounds. These assumptions have since been somewhat relaxed, first by Pass, Seeman and Shelat [Eurocrypt ’17] who also focused on the simplified version of the protocol but on the bounded-delay model of communication, and by Garay, Kiayias and Leonardos [Crypto ’17] who looked into the full protocol including the PoW difficulty adjustment mechanism with a variable number of parties but assuming synchronous communication and a predetermined schedule of participation. Despite the above progress, the full analysis of the protocol in the more realistic setting of bounded delays and dynamic participation has remained elusive.

This paper’s main result is the proof that Nakamoto’s protocol achieves, under suitable conditions, consistency and liveness in bounded-delay networks with adaptive (as opposed to predetermined) dynamic participation assuming, as before, that the majority of the computational power favors the honest parties. While our techniques draw from previous analyses, our objective is significantly more challenging, demanding the introduction of new techniques and insights in order to realize it.

Quantum computers promise to solve hard mathematical problems such as integer factorization and discrete logarithms in polynomial time, making standardized public-key cryptography (such as digital signature and key agreement) insecure. Lattice-Based Cryptography (LBC) is a promising post-quantum public-key cryptographic protocol that could replace standardized public-key cryptography, thanks to the inherent post-quantum resistant properties, efficiency, and versatility. A key mathematical tool in LBC is the Number Theoretic Transform (NTT), a common method to compute polynomial multiplication that is the most compute-intensive routine, and which requires acceleration for practical deployment of LBC protocols. In this paper, we propose, a high-throughput Processing In-Memory (PIM) accelerator for NTT-based polynomial multiplier with the support of polynomials with degrees up to 32k. Compared to the fastest FPGA implementation of an NTT-based multiplier, achieves on average 31x throughput improvement with the same energy and only 28% performance reduction, thereby showing promise for practical deployment of LBC.

With the dawn of quantum computers, higher security than $128$ bits has become desirable for primitives and modes. During the past decade, highly secure hash functions, MACs, and encryption schemes have been built primarily on top of keyless permutations, which simplified their analyses and implementation due to the absence of a key schedule. However, the security of these modes is most often limited to the birthday bound of the state size, and their analysis may require a different security model than the easier-to-handle secret-permutation setting. Yet, larger state and key sizes are desirable not only for permutations but also for other primitives such as block ciphers. Using the additional public input of tweakable block ciphers for domain separation allows for exceptionally high security or performance as recently proposed modes have shown. Therefore, it appears natural to ask for such designs.

While security is fundamental for cryptographic primitives, performance is of similar relevance. Since 2009, processor-integrated instructions have allowed high throughput for the AES round function, which already motivated various constructions based on it. Moreover, the four-fold vectorization of the AES instruction sets in Intel's Ice Lake architecture is yet another leap in terms of performance and gives rise to exploit the AES round function for even more efficient designs.

This work tries to combine all aspects above into a primitive and to build upon years of existing analysis on its components. We propose Pholkos, a family of (1) highly efficient, (2) highly secure, and (3) tweakable block ciphers. Pholkos is no novel round-function design, but utilizes the AES round function, following design ideas of Haraka and AESQ to profit from earlier analysis results. It extends them to build a family of primitives with state and key sizes of $256$ and $512$ bits for flexible applications, providing high security at high performance. Moreover, we propose its usage with a $128$-bit tweak to instantiate high-security encryption and authentication schemes such as SCT, ThetaCB3, or ZAE. We study its resistance against the common attack vectors, including differential, linear, and integral distinguishers using a MILP-based approach and show an isomorphism from the AES to Pholkos-$512$ for bounding impossible-differential, or exchange distinguishers from the AES. Our proposals encrypt at around $1$--$2$ cycles per byte on Skylake processors, while supporting a much more general application range and considerably higher security guarantees than comparable primitives and modes such as PAEQ/AESQ, AEGIS, Tiaoxin346, or Simpira.

Recently, Kamara and Moataz described the first encrypted relational database solution with support for a non-trivial fraction of SQL that does not make use of property-preserving encryption (Asiacrypt, 2018). More precisely, their construction, called SPX, handles the set of conjunctive SQL queries. While SPX was shown to be optimal for the subset of uncorrelated conjunctive SQL queries, it did not handle correlated queries optimally. Furthermore, it only handles queries in heuristic normal form. In this work, we address these limitations by proposing an extension of SPX that handles all conjunctive SQL queries optimally no matter what form they are in.

Motivated by the impact of fast algebraic attacks on stream ciphers, and recent constructions using a threshold function as part of the filtering function, we study the fast algebraic immunity of threshold functions. As a first result, we determine exactly the fast algebraic immunity of all majority functions in more than $8$ variables. Then, For all $n\geq 8$ and all threshold value between $1$ and $n$ we exhibit the fast algebraic immunity for most of the thresholds, and we determine a small range for the value related to the few remaining cases. Finally, provided $m\geq 2$, we determine exactly the fast algebraic immunity of all threshold functions in $3\cdot 2^m$ or $3\cdot 2^m +1$ variables.

Privacy and machine learning are difficult to coexist due to their nature: parivacy should be kept from others while machine learning requires large amount of data. Among several possible solutions to this problem, Fully Homomorphic Encryption has been a center of intensive researches in this field. FHE enables linear operations of ciphertext. To take advantage of this property, many protocols to achieve statistical operaions have been proposed. On the other hand, many of them are impractical. Some of the approaches introduce cryptosystems that are not familiar. Moreover, most of their protocols are approximation which might sensitively depend on our choice of parameters. In this paper, we propose fast, simple, and exact privacy-preserving linear equation solver using FHE. Our two-party protocol is secure against at least semi-honest model, and we can exactly calculate the model even without the bootstrapping.

OR-proofs enable a prover to show that it knows the witness for one of many statements, or that one out of many statements is true. OR-proofs are a remarkably versatile tool, used to strengthen security properties, design group and ring signature schemes, and achieve tight security. The common technique to build OR-proofs is based on an approach introduced by Cramer, Damgård, and Schoenmakers (CRYPTO’94), where the prover splits the verifier’s challenge into random shares and computes proofs for each statement in parallel. In this work we study a different, less investigated OR-proof technique, put forward by Abe, Ohkubo, and Suzuki (ASIACRYPT’02). The difference is that the prover now computes the individual proofs sequentially. We show that such sequential OR-proofs yield signature schemes which can be proved secure in the non-programmable random oracle model. We complement this positive result with a black-box impossibility proof, showing that the same is unlikely to be the case for signatures derived from traditional OR-proofs. We finally argue that sequential-OR signature schemes can be proved secure in the quantum random oracle model, albeit with very loose bounds and by programming the random oracle.

Inner product encryption is a powerful cryptographic primitive, where a private key and a ciphertext are both associated with a predicate vector and an attribute vector, respectively. A successful decryption requires the inner product of the predicate vector and the attribute vector to be zero. Most of the existing inner product encryption schemes suffer either long private key or heavy decryption cost. In this manuscript, an efficient inner product encryption is proposed. The length for a private key is only an element in $\mathbb{G}$ and an element in $\mathbb{Z}_p$. Besides, only a pairing is needed for decryption. Moreover, both formal security proof and implementation result are demonstrated in this manuscript. To the best of our knowledge, our scheme is the most efficient one in terms of the private key length and the number of pairings for decryption.

Decades of research in both cryptography and distributed systems has extensively studied the problem of state machine replication, also known as Byzantine consensus. A consensus protocol must satisfy two properties: consistency and liveness. These properties ensure that honest participating nodes agree on the same log and dictate when fresh transactions get added. They fail, however, to ensure against adversarial manipulation of the actual ordering of transactions in the log. Indeed, in leader-based protocols (almost all protocols used today), malicious leaders can directly choose the final transaction ordering.

To rectify this problem, we propose a third consensus property: transaction order-fairness. We initiate the first formal investigation of order-fairness and explain its fundamental importance. We provide several natural definitions for order-fairness and analyze the assumptions necessary to realize them.

We also propose a new class of consensus protocols called Aequitas. Aequitas protocols are the first to achieve order-fairness in addition to consistency and liveness. They can be realized in a black-box way using existing broadcast and agreement primitives (or indeed using any consensus protocol), and work in both synchronous and asynchronous network models.

Since the introduction of the ring-learning with errors problem, the number theoretic transform (NTT) based polynomial multiplication algorithm has been studied extensively. Due to its faster quasilinear time complexity, it has been the preferred choice of cryptographers to realize ring-learning with errors cryptographic schemes. Compared to NTT, Toom-Cook or Karatsuba based polynomial multiplication algorithms, though being known for a long time, still have a fledgling presence in the context of post-quantum cryptography. In this work, we observe that the pre- and post-processing steps in Toom-Cook based multiplications can be expressed as linear transformations. Based on this observation we propose two novel techniques that can increase the efficiency of Toom-Cook based polynomial multiplications. Evaluation is reduced by a factor of 2, and we call this method precomputation, and interpolation is reduced from quadratic to linear, and we call this method lazy interpolation. As a practical application, we applied our algorithms to the Saber post-quantum key-encapsulation mechanism. We discuss in detail the various implementation aspects of applying our algorithms to Saber. We show that our algorithm can improve the efficiency of the computationally costly matrix-vector multiplication by12−37%compared to previous methods on their respective platforms. Secondly, we propose different methods to reduce the memory footprint of Saber for Cortex-M4microcontrollers. Our implementation shows between2.6 and 5.7KB reduction in memory usage with respect to the smallest implementation in the literature.