International Association
for Cryptologic Research

We put forth a new framework for building pairing-based non-interactive zero- knowledge (NIZK) arguments for a wide class of algebraic languages, which are an extension of linear languages, containing disjunctions of linear languages and more. Our approach differs from the Groth-Sahai methodology, in that we rely on pairings to compile a $\Sigma$-protocol into a NIZK. Our framework enjoys a number of interesting features: – conceptual simplicity, parameters derive from the $\Sigma$-protocol; – proofs as short as resulting from the Fiat-Shamir heuristic applied to the underlying $\Sigma$-protocol; – fully adaptive soundness and perfect zero-knowledge in the common random string model with a single random group element as CRS; – yields simple and efficient two-round, public coin, publicly-verifiable perfect witness-indistinguishable (WI) arguments (ZAPs) in the plain model. To our knowledge, this is the first construction of two-rounds statistical witness-indistinguishable arguments from pairing assumptions. Our proof system relies on a new (static, falsifiable) assumption over pairing groups which generalizes the standard kernel Diffie-Hellman assumption in a natural way and holds in the generic group model (GGM) and in the algebraic group model (AGM). Replacing Groth-Sahai NIZKs with our new proof system allows to improve several important cryptographic primitives. In particular, we obtain the shortest tightly-secure structure-preserving signature scheme (which are a core component in anonymous credentials), the shortest tightly-secure quasi-adaptive NIZK with unbounded simulation soundness (which in turns implies the shortest tightly-mCCA-secure cryptosystem), and shorter ring signatures.

We revisit the security of various generalized Feistel networks. Concretely, for unbalanced, alternating, type-1, type-2, and type-3 Feistel networks built from random functions, we substantially improve the coupling analyzes of Hoang and Rogaway (CRYPTO 2010). For a tweakable blockcipher-based generalized Feistel network proposed by Coron et al. (TCC 2010), we present a coupling analysis and for the first time show that with enough rounds, it achieves 2n-bit security, and this provides highly secure, double-length tweakable blockciphers.

The PhD student will join the Prof. Mitrokotsa's group, working in the area of information and communication security and machine learning with a focus on mechanisms and protocols for secure and private machine learning. More precisely, we envision secure and privacy-preserving machine learning algorithms for artificial intelligence applications in everyday life that can provide confidentiality and integrity guarantees. In particular the main aims of the project are to: (i) Safeguard the privacy of individuals that participate by either providing their data to build the AI system or being end-users of the system, (ii) safeguard the integrity of the system by ensuring its robustness to adversarial inputs and cryptographically limiting the possible points of adversarial manipulation.

Closing date for applications:

Contact: Katerina Mitrokotsa, aikmitr@chalmers.se

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

Algorand is looking for a Cryptography Intern to join our Team. This is an opportunity for someone who is genuinely excited by new technologies to influence the design and implementation of Algorand’s consensus infrastructure. You will be working on a fast-paced, rapidly growing, high-profile project with a significant opportunity for industry-level impact on emerging blockchain and cryptocurrency technologies. Core Responsibilities: Design and build cryptographic protocols and schemes for privacy preserving assets Design and build cryptographic protocols for cross-chain transfers Partner with the larger organization (including Product and Engineering) regarding the implementation of designs at scale Be a key part of an inclusive environment that fosters collaboration and creativity both internally and externally Requirements & Qualifications: Masters in Computer Science or related technical field is required; PhD (either earned or in progress) preferred Expertise in distributed computation, probabilistic analysis, data structure, algorithm design and analysis required Experience with zero-knowledge proofs and proof systems Solid mathematics training, highly capable of abstract thinking and modeling Good written communication and ability to communicate technical information with wide variety of audiences Exposure to game theory, cryptography, or distributed systems preferred Experience in driving the implementation of complex theoretical designs or as a technical participant for highly scalable distributed system designs preferred Enjoyment for working in a highly collaborative, fast-paced, and dynamic environment Internships at Algorand, Inc. are non-exempt temporary positions, with hourly rates set to market standards. You must be a matriculated university student, scheduled to return in the Fall.

Closing date for applications:

Contact: Makena Stone

A postdoctoral positions related to privacy-enhancing cryptography in distributed ledgers. Strong applicants in other areas of cryptography, or security & privacy might also be considered. Candidates should have a PhD in cryptography, or a security & privacy related field.

Closing date for applications:

Contact: Interested persons please email with a cover letter and updated curriculum vitae to mkohlwei@ed.uk.ac. The position will be available until filled; only short-listed candidates will be notified.

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.