International Association
for Cryptologic Research

We introduce a family of extensions to the one-out-of-many proofs of Groth and Kohlweiss (Eurocrypt 2015), which efficiently prove statements about many messages among a list of commitments. These extensions prove knowledge of a secret subset of the list, and assert that the commitments in the subset satisfy certain properties (expressed as linear equations). Our communication remains logarithmic; our computation increases only by a logarithmic multiplicative factor. Our work introduces a new "circular rotation" technique, and a novel instantiation of the number-theoretic transform.

Applying these techniques, we construct a protocol for the Anonymous Zether payment system—as proposed in Bünz, Agrawal, Zamani, and Boneh (FC'20)—which improves upon the communication complexity attained by existing efforts. We describe an open-source, Ethereum-based implementation of our protocol.

We propose a framework for cryptanalysis of lattice-based schemes, when side information---in the form of ``hints''--- about the secret and/or error is available. Our framework generalizes the so-called primal lattice reduction attack, and allows the progressive integration of hints before running a final lattice reduction step. Our techniques for integrating hints include sparsifying the lattice, projecting onto and intersecting with hyperplanes, and/or altering the distribution of the secret vector. Our main contribution is to propose a toolbox and a methodology to integrate such hints into lattice reduction attacks and to predict the performance of those lattice attacks with side information.

While initially designed for side-channel information, our framework can also be used in other cases: exploiting decryption failures, or simply exploiting constraints imposed by certain schemes (LAC, Round5, NTRU), that were previously not known to (sligthly) benefit from lattice attacks.

We implement a Sage 9.0 toolkit to actually mount such attacks with hints when computationally feasible, and to predict their performances on larger instances. We provide several end-to-end application examples, such as an improvement of a single trace attack on Frodo by Bos et al (SAC 2018). Contrary to ad-hoc practical attacks exploiting side-channel leakage, our work is a generic way to estimate security loss even given very little side-channel information.

Defining unforgeability and designing cryptographic primitives that provide unforgeability in the quantum setting, i.e. where the adversary has quantum capabilities including quantum oracle access to the primitive, has proven to be a hard challenge. The classical notions and techniques do not transpose directly to the quantum setting. In this paper, we continue the line of work initiated by Boneh and Zhandry at CRYPTO 2013 and EUROCRYPT 2013 in which they formally define the notion of unforgeability against quantum adversaries specifically for Message Authentication Codes and Digital Signatures schemes. We develop a general and parameterized quantum game-based security framework for both classical and quantum primitives modelled by unitary transformations. We provide general possibility and impossibility results for such primitives. In particular, we show that no unitary primitive can provide existential unforgeability against quantum adversaries. Our main impossibility result relies on a new and generic quantum attack. We demonstrate this attack both on classical and quantum primitives to show its applicability as well as the completeness of our definitions of security. On the other hand, we show that selective unforgeability is satisfied by a specific class of unitaries that we term unknown unitaries.

We present attacks on 21-rounds of SIMON 32/64, 21-rounds of SIMON 48/96, 25-rounds of SIMON 64/128, 35-rounds of SIMON 96/144 and 43-rounds of SIMON 128/256, often with direct recovery of the full master key without repeating the attack over multiple rounds. These attacks result from the observation that, after four rounds of encryption, one bit of the left half of the state of 32/64 SIMON depends on only 17 key bits (19 key bits for the other variants of SIMON). Further, linear cryptanalysis requires the guessing of only 16 bits, the size of a single round key of SIMON 32/64. We partition the key into smaller strings by focusing on one bit of state at a time, decreasing the cost of the exhaustive search of linear cryptanalysis to 16 bits at a time for SIMON 32/64. We also present other example linear cryptanalysis, experimentally verified on 8, 10 and 12 rounds for SIMON 32/64.

Recent work using groups of unknown order to construct verifiable delay functions, polynomial commitment schemes and non interactive zero knowledge proofs have provoked fresh interest in the construction of efficient cryptographic groups of unknown order. It has been suggested that the Jacobian of hyperelliptic curves of genus 3 could be suitable for this purpose. Regrettably, efficient algorithms to compute the order of the Jacobian of a hyperelliptic curve are known. Concretely, it is unclear whether these groups are competitive with RSA groups or class groups at or above the 128 bit security level.

Light key schedule has found many applications in lightweight blockciphers, e.g. LED, PRINTcipher and LBlock. In this paper, we study an interesting question of how to design a as light as possible key schedule from the view of provable security and revisit the four-round key-alternating Feistel cipher by Guo and Wang in Asiacrypt 18. We optimize the construction by Guo and Wang and propose a four-round key-alternating Feistel cipher with an ultra-light (in fact non-existent) key schedule. We prove our construction retain the same security level as that of Guo and Wang's construction. To the best of our knowledge, this is the first provably secure key-alternating Feistel cipher using identical round function and one n-bit master key but with ultra-light (non-existent) key schedule. We also investigate whether the same renement works for the three-round key-alternating Feistel cipher. This time we show a distinguishing attack on such three-round construction with only four encryption queries. On the positive side, we prove that three-round key-alternating Feistel cipher with a suitable key schedule is a pseudorandom permutation. This is also the first provable-security result for three-round key-alternating Feistel cipher.

This paper introduces a new cryptographic primitive called a private resource allocator (PRA) that can be used to allocate resources (e.g., network bandwidth, CPUs) to a set of clients without revealing to the clients whether any other clients received resources. We give several constructions of PRAs that provide guarantees ranging from information-theoretic to differential privacy. PRAs are useful in preventing a new class of attacks that we call allocation-based side-channel attacks. These attacks can be used, for example, to break the privacy guarantees of anonymous messaging systems that were designed specifically to defend against side-channel and traffic analysis attacks. Our implementation of PRAs in Alpenhorn, which is a recent anonymous messaging system, shows that PRAs increase the network resources required to start a conversation by up to 16X (can be made as low as 4X in some cases), but add no overhead once the conversation has been established.

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.