International Association
for Cryptologic Research

A zero-knowledge proof is a cryptographic primitive that is a versatile building block for both cryptographic protocols alongside a wide range of applications from cryptocurrencies to privacy-preserving auditing. Unfortunately, when the proof statements become very large, existing zero-knowledge proof systems easily reach their limits: either the computational overhead, the memory footprint, or the required bandwidth exceed levels that would be tolerable in practice.

We present an interactive zero-knowledge proof system for arithmetic circuits, called Mac'n'Cheese, with a focus on supporting large circuits while using low computational resources. Our work follows the commit-and-prove paradigm instantiated using information-theoretic MACs based on vector oblivious linear evaluation to achieve high efficiency. We additionally show how to optimize disjunctions, with a general OR transformation for proving the disjunction of $m$ statements that has communication complexity proportional to the longest statement (plus an additive term logarithmic in $m$). These disjunctions can further be nested, allowing efficient proofs about complex statements with many levels of disjunctions. We also show how to make Mac'n'Cheese non-interactive (after a preprocessing phase) using the Fiat-Shamir transform, and with only a small degradation in soundness.

We have implemented the non-interactive variant of the online phase of Mac'n'Cheese and can achieve 2.5 $\mu s$ per multiplication gate while requiring a minimal amount of memory: for proving the knowledge of two 512-by-512 matrices that equal some fixed public matrix we require less than 36~MB of memory for both the prover and verifier. We achieve this through a streaming approach which is compatible with our disjunctions over sub-circuits.

In this work we apply the dynamical systems analysis of Hanrot et al. (CRYPTO'11) to a class of lattice block reduction algorithms that includes (natural variants of) slide reduction and block-Rankin reduction. This implies sharper bounds on the polynomial running times (in the query model) for these algorithms and opens the door to faster practical variants of slide reduction. We give heuristic arguments showing that such variants can indeed speed up slide reduction significantly in practice. This is confirmed by experimental evidence, which also shows that our variants are competitive with state-of-the-art reduction algorithms.

Broadcast is a primitive which allows a specific party to distribute a message consistently among $n$ parties, even if up to $t$ parties exhibit malicious behaviour. In the classical model with a complete network of bilateral authenticated channels, the seminal result of Pease et al. [PSL80] shows that broadcast is achievable if and only if $t < n/3$. There are two generalizations suggested for the broadcast problem -- with respect to the adversarial model and the communication model. Fitzi and Maurer [FM98] consider a (non-threshold) 'general adversary' that is characterized by the subsets of parties that could be corrupted, and show that broadcast can be realized from bilateral channels if and only if the union of no three possible corrupted sets equals the entire set of $n$ parties. On the other hand, Considine et al. [CFF+05] extend the standard model of bilateral channels with the existence of $b$-minicast channels that allow to locally broadcast among any subset of $b$ parties; the authors show that in this enhanced model of communication, secure broadcast tolerating up to $t$ corrupted parties is possible if and only if $t < \frac{b-1}{b+1}n$. These generalizations are unified in the work by Raykov [Ray15], where a tight condition on the possible corrupted sets is presented such that broadcast is achievable from a complete set of $b$-minicasts.

This paper investigates the achievability of broadcast in 'general networks', i.e., networks where only some subsets of minicast channels may be available, thereby addressing open problems posed in [JMS12,Ray15]. To that end, we propose a hierarchy over all possible general adversaries, and identify for each class of general adversaries 1) a set of minicast channels that are necessary to achieve broadcast and 2) a set of minicast channels that are sufficient to achieve broadcast. In particular, this allows us to derive bounds on the amount of $b$-minicasts that are necessary and that suffice towards constructing broadcast in general $b$-minicast networks.

We describe an algorithm to compute square roots modulo a prime $p=2^nm$, with $m$ odd and $n\geq 1$, which requires $\mathfrak{T}+O(n^{3/2})$ operations (i.e., squarings and multiplications), where $\mathfrak{T}$ is the number of operations required to exponentiate an element of $\mathbb{Z}_p$ to the power $(m-1)/2$. This improves upon the Tonelli-Shanks (TS) algorithm which requires $\mathfrak{T}+O(n^{2})$ operations. Bernstein had proposed a table look-up based variation of the TS algorithm which requires $\mathfrak{T}+O((n/w)^{2})$ operations and $O(2^wn/w)$ storage, where $w$ is a parameter. A table look-up variant of the new algorithm requires $\mathfrak{T}+O((n/w)^{3/2})$ operations and the same storage. In practical terms, the new algorithm is shown to require significantly less number of operations for concrete values of $n$. \\ {\bf Key Words:} square root, Tonelli-Shanks algorithm, table look-up.

Designing secure e-voting systems is notoriously hard, and this is even more the case when coercion-resistance comes into play. Recently, Lueks, Querejeta-Azurmendi, and Troncoso proposed VoteAgain (Usenix Security 2020) which aims to provide coercion-resistance for real practical elections where usability and efficiency are particularly important. To this end, VoteAgain is based on the re-voting paradigm to protect voters against coercion, and it employs a novel tallying mechanism with quasilinear complexity to achieve high efficiency.

In this paper, we revisit VoteAgain from a security perspective. We show that for each security property, i.e., ballot privacy, verifiability, and coercion-resistance, there exists (at least) one attack which breaks the respective property under the trust assumptions for which the property was claimed to hold true. But our results are even more disillusioning: first, there exists a voting authority in VoteAgain which needs to be trusted for all security properties; second, all voting authorities in VoteAgain need to be trusted for coercion-resistance.

It will be interesting and challenging future work to mitigate, or even remove, these undesirably strong trust assumptions without affecting the usability and superior efficiency of VoteAgain.

Grover search algorithm can be used to find the $n$-bit secret key at the speed of $\sqrt{n}$, which is the most effective quantum attack method for block ciphers. In order to apply the Grover search algorithm, the target block cipher should be implemented in quantum circuits. Many recent research works optimized the expensive substitute layer to evaluate the need for quantum resources of AES block ciphers. Research on the implementation of quantum circuits for lightweight block ciphers such as SIMON, SPECK, HIGHT, CHAM, LEA, and Gimli, an active research field, is also gradually taking place. In this paper, we present optimized implementations of GIFT block ciphers for quantum computers. To the best of our knowledge, this is the first implementation of GIFT in quantum circuits. Finally, we estimate quantum resources for applying the Grover algorithm to the our optimized GIFT quantum circuit.

The cube attack is one of the most important cryptanalytic techniques against Trivium. Many improvements have been proposed and lots of key-recovery attacks based on cube attacks have been established. However, among these key-recovery attacks, few attacks can recover the 80-bit full key practically. In particular, the previous best practical key-recovery attack was on 784-round Trivium proposed by Fouque and Vannet at FSE 2013 with on-line complexity about $2^{39}$. To mount a practical key-recovery attack against Trivium on a PC, a sufficient number of low-degree superpolies should be recovered, which is around 40. This is a difficult task both for experimental cube attacks and division property based cube attacks with randomly selected cubes due to lack of efficiency. In this paper, we give a new algorithm to construct candidate cubes targeting at linear superpolies in cube attacks. It is shown by our experiments that the new algorithm is very effective. In our experiments, the success probability is $ 100\% $ for finding linear superpolies using the constructed cubes. As a result, we mount a practical key-recovery attack on 805-round Trivium, which increases the number of attacked initialisation rounds by 21. We obtain over 1000 cubes with linear superpolies for 805-round Trivium, where 42 linearly independent ones could be selected. With these superpolies, for 805-round Trivium, the 80-bit key could be recovered within on-line complexity $ 2^{41.40} $, which could be carried out on a single PC equipped with a GTX-1080 GPU in several hours. Furthermore, the new algorithm is applied to 810-round Trivium, a cube of size 43 is constructed and two subcubes of size 42 with linear superpolies for 810-round Trivium are found.

A graph signature scheme is a digital signature scheme that allows a recipient to obtain a signature on a graph and subsequently prove properties thereof in zero-knowledge proofs of knowledge. In this paper, we present an efficient and provably secure graph signature scheme in the standard model with tight reduction. Based on the MoniPoly ABC, the MoniPoly graph signature scheme can provide show proofs on logical statements such as the existence of vertices, graph connectivity or isolation.

Evaluating resistance of ciphers against differential cryptanalysis is essential to define the number of rounds of new designs and to mount attacks derived from differential cryptanalysis.

In this paper, we compare existing automatic tools to find the best differential characteristic on the SKINNY block cipher. As usually done in the literature, we split this search in two stages denoted by Step 1 and Step 2. In Step 1, each difference variable is abstracted with a Boolean variable and we search for the value that minimizes the trail weight, whereas Step 2 tries to instantiate each difference value while maximizing the overall differential characteristic probability. We model Step 1 using a MILP tool, a SAT tool, an ad-hoc method and a CP tool based on the Choco-solver library and provide performance results. Step 2 is modeled using the Choco-solver as it seems to outperform all previous methods on this stage.

Notably, for SKINNY-128 in the SK model and for 13 rounds, we retrieve the results of Abdelkhalek et al. within a few seconds (to compare with 16 days) and we provide, for the first time, the best differential related-tweakey characteristic up to respectively 14 and 12 rounds for the TK1 and TK2 models.

Event date: 8 July to 9 July 2021

(virtual) TCC 2020 starts on Monday Nov 16th with an exciting keynote talk on "The Impact of Cryptographic Thinking on TCS and Beyond" by Avi Wigderson.

The conference program and details on how to join can be found at https://tcc.iacr.org/2020/program.php

The University of St. Gallen in Switzerland and the chair of Cyber Security invites applications from PhD holders in the area of cryptography and information security. The researcher will join a group of researchers focusing in applied and theoretical cryptography, network and information security and privacy-preservation led by Prof. Katerina Mitrokotsa. We are affiliated to the Department of Computer Science (DCS) and the Institute of Computer Science. The postdoctoral fellowship is available for three years and a project proposal needs to be submitted that will be evaluated by the research committee.
Topics of research interest include:

• Verifiable computation
• Secure Multi Party Computation
• Privacy-preserving authentication
• Cryptographic primitives

Requirements:

• Publications in top venues in Cryptography and Information Security
• Young researchers who hold a doctorate (PhD) or will complete their doctorate within the next six months
• Young researchers with a completed doctorate (PhD) have been awarded the degree at most two years before 15th of Jan 2021.

Deadline for applicants to be considered: 7th of Dec. 2020
Deadline for project proposal: 15th of Jan. 2021
To Apply: Send your cv and research statement to aikaterini.mitrokotsa@unisg.ch with subject ''Post-doc Fellowship'' by the 9th of Dec. 2020

Closing date for applications:

Contact: Katerina Mitrokotsa

The CryptoLux group of the University of Luxembourg has a vacancy for a post-doctoral researcher in the area of symmetric cryptography. The successful candidate will contribute to a research project entitled Analysis and Protection of Lightweight Cryptographic Algorithms (APLICA), which is funded by the Luxembourgish Fonds National de la Recherche and the German Research Foundation. Starting in 2021, APLICA will run over a period of 3 years as a joint research project between the CryptoLux group and the Workgroup for Symmetric Cryptography of Ruhr-University Bochum. The mission of the APLICA project is to develop new cryptanalytic techniques for lightweight authenticated encryption algorithms and hash functions, and to design and implement new countermeasures against side-channel attacks that are suitable for constrained devices.

Candidates must have a Ph.D. degree in symmetric cryptography or a closely related field. Preference will be given to candidates with a strong publication record that includes at least one paper at an IACR conference/workshop or one of the top-4 security conferences. Experience in software development for embedded systems or mounting side-channel attacks is a plus. Candidates with an interest to conduct research in one of the following areas are particularly encouraged to apply:

• Cryptanalysis of authenticated encryption algorithms or hash functions
• Leakage resilience or leakage reduction by design (e.g. modes of operation)
• Security evaluation of leakage-resilient primitives or constructions

The position is available from Jan. 2021 on basis of a fixed-term contract for 3 years. The University of Luxembourg offers excellent working conditions and a highly competitive salary. Interested candidates are invited to send their application by email to Alex Biryukov before Dec. 15, 2020 (early submission is strongly encouraged, applications will be processed upon receipt). The application material should contain a cover letter explaining the candidate's research interests, a CV (incl. photo), a list of publications, scans of diploma certificates, and contact details of 3 references

Closing date for applications:

Contact: Prof. Alex Biryukov (alex.biryukov@uni.lu)

More information: https://www.fnr.lu/projects/analysis-and-protection-of-lightweight-cryptographic-algorithms/

The University of Luxembourg invites applications from M.Sc. holders in the general area of applied cryptography. Cryptolux.org is a team of cryptographers and security researchers interested in applied cryptography, cryptanalysis, privacy, cryptographic blockchains and is led by Prof. Alex Biryukov.

Area (potential topics of the thesis)

• Cryptanalysis and design of cryptographic primitives
• Lightweight block ciphers, hash functions, authenticated encryption schemes
• Privacy Enhancing Technology (Tor-like networks, privacy for cryptocurrencies, blockchains)
• Blockchain Cryptography
• White-box cryptography

The University offers a Ph.D. study program with an Initial contract of 36 months, with a further possible 1-year extension if required. The University offers competitive salaries and is an equal opportunity employer.

Starting date 1-Feb-2020 or later upon agreement. Early submission is encouraged; applications will be processed upon receipt.

Closing date for applications:

Contact: Prof. Alex Biryukov

More information: https://www.cryptolux.org/index.php/Vacancies

The CryptoLux group of the University of Luxembourg invites applications from Ph.D. holders in the general area of applied cryptography. CryptoLux is a group of cryptographers and security researchers interested in applied cryptography, cryptanalysis, privacy and is led by Prof. Alex Biryukov.

• Design and cryptanalysis of symmetric cryptographic primitives
• Cryptocurrencies, ZK proofs, blockchain
• Privacy enhancing technologies, Tor, etc
• Side-channel attacks and countermeasures
• White-box cryptography

Your Profile

• A Ph.D. degree in Computer Science, Applied Mathematics or a related field
• Competitive research record in applied cryptography or information security (at least one paper in top 10 IT security conferences or several papers at conferences like ToSC, CHES, PETS, PKC)
• Strong mathematical and algorithmic CS background
• Good development skills in C or C++ and/or scripting languages
• Fluent written and verbal English

We offer

The University offers a two-year employment contract (Ref: F1-070025, OTP code R-STR-8019-00-A), which may be extended up to five years. The University offers highly competitive salaries and is an equal opportunity employer.

Closing date for applications:

Contact: Alex Biryukov

More information: https://www.cryptolux.org

Several PhD student openings in the domains of cryptography, computer security, privacy, and blockchain-based systems are available at the University of Connecticut (UConn), Computer Science and Engineering department, led by Prof. Ghada Almashaqbeh. The positions provide a great opportunity for students with interest in interdisciplinary projects that combine knowledge from various fields towards the design of secure systems and protocols. We target real-world timely problems and aim to provide secure and practical solutions backed by rigorous foundations and efficient implementations/thorough performance testing. We are also interested in conceptual projects that contribute in bridging the gap between theory and practice of Cryptography. For more information about our current and previous projects please check https://ghadaalmashaqbeh.github.io/research/. For interested students, please send your CV to ghada.almashaqbeh@uconn.edu and provide any relevant information about the topics you want to work on and the skills/related background you have.

Closing date for applications:

Contact: Ghada Almashaqbeh

More information: https://ghadaalmashaqbeh.github.io/

We present a garbling scheme for quantum circuits, thus achieving a decomposable randomized encoding scheme for quantum computation. Specifically, we show how to compute an encoding of a given quantum circuit and quantum input, from which it is possible to derive the output of the computation and nothing else. 

In the classical setting, garbled circuits (and randomized encodings in general) are a versatile cryptographic tool with many applications such as secure multiparty computation, delegated computation, depth-reduction of cryptographic primitives, complexity lower-bounds, and more. However, a quantum analogue for garbling general circuits was not known prior to this work. We hope that our quantum randomized encoding scheme can similarly be useful for applications in quantum computing and cryptography.

To illustrate the usefulness of quantum randomized encoding, we use it to design a conceptually-simple zero-knowledge (ZK) $\Sigma$-protocol for the complexity class QMA. Our protocol has a single-bit challenge, and allows the inputs to be delayed to the last round. The only previously-known ZK $\Sigma$-protocol for QMA is due to Broadbent and Grilo (FOCS 2020), which does not have the aforementioned properties.

Transferable e-cash is the most faithful digital analog of physical cash, as it allows users to transfer coins between them without interacting with the bank (or a "ledger"). Strong anonymity requirements and the need for mechanisms to trace illegal behavior (double-spending of coins) have made instantiating the concept notoriously hard. Baldimtsi et al. (PKC'15) have given a first instantiation, which relied on a powerful cryptographic primitive that made the scheme non-practical.

In this paper we first revisit the model for transferable e-cash, proposing simpler yet stronger security definitions and then give the first concrete instantiation of the primitive, basing it on bilinear groups, and analyze its concrete efficiency.

We present a novel public key encryption scheme that enables users to exchange many bits messages by means of \emph{at least} two large prime numbers in a Goldwasser-Micali manner. Our cryptosystem is in fact a generalization of the Joye-Libert scheme (being itself an abstraction of the first probabilistic encryption scheme). We prove the security of the proposed cryptosystem in the standard model (based on the gap $2^k$-residuosity assumption) and report complexity related facts. We also describe an application of our scheme to biometric authentication and discuss the security of our suggested protocol. Last but not least, we indicate several promising research directions.

A special class of linear codes, having important applications in secret sharing and secure two-party computation, called minimal is characterized by the property that none of the codewords is covered by some other codeword. Denoting by $w_{min}$ and $w_{max}$ the minimal and maximal weight of a binary linear code respectively, a sufficient but not necessary condition for achieving minimality is that $w_{min} /w_{max} > 1/2$ (called Ashikhmin-Barg’s bound). Those minimal codes satisfying the condition $w_{min} /w_{max} \leq 1/2$ are called wide in this article (generally harder to construct), whereas codes satisfying $w_{min} /w_{max} > 1/2$ are called narrow. In this article, we first show that the so-called direct sum of Boolean functions of the form $h(x,y) = f(x) + g(y)$ induces narrow minimal codes whenever g is a bent function. Then, we introduce the concept of non-covering permutations (referring to the property of minimality) which is shown to be sufficient for providing many infinite classes of minimal binary linear codes of larger dimension by employing a suitable subspace of derivatives of the bent function g. In the second part of this article, we first provide one efficient method (with easily satisfied initial conditions) of generating wide minimal codes. Then, we again consider the use of derivatives (along with the underlying Boolean function given as the direct sum) for the purpose of defining another class of wide minimal codes. To the best of our knowledge, the latter method is the most general framework for designing wide binary linear codes. It uses a (suitable) subspace of derivatives of $h(x,y) = f(x) + g(y)$, where $g$ is a bent function and f satisfies certain minimality requirements. For a fixed suitable function $f$, one can derive a huge class of non-equivalent wide binary linear codes of the same length by varying the permutation $\phi$ when specifying the bent function $g(y^{(1)} , y^{(2)} ) = $\phi( y^{(2)} )\cdot y^{(1)} $ in the Maiorana-McFarland class.