International Association
for Cryptologic Research

The School of Computer Science & IT at University College Cork is a partner in the Science Foundation Ireland Centre for Research Training on Artificial Intelligence, which funds a number of 4-year PhD scholarships. The scholarships include full payment of university fees and a monthly tax-free stipend of €1,500, as well as a budget for equipment, travel, and training.

We are currently looking for candidates interested to work on privacy-preserving machine learning/artificial intelligence. Topics of interests include: advanced encryption for neural networks; anonymity and differential privacy; model ownership (watermarking and fingerprinting) and related attacks.

Interested candidates should write to Dr Paolo Palmieri (p.palmieri@cs.ucc.ie). Expressions of interest for the 2021-2022 call need to be received by February 26, 2021. Early applications will be given priority.

Applicants should include:

1. a brief cover letter (1 page max) explaining their interest in the project topic, and mentioning any previous experience in privacy/cryptography/security;
2. a curriculum vitae, mentioning the final grade/CGPA for each degree.

Shortlisted students will be asked to submit a full application (including academic transcripts, evidence of English language proficiency, and references) at a later stage.

Closing date for applications:

Contact: Dr. Paolo Palmieri (p.palmieri@cs.ucc.ie)

The Department of Electrical and Computer Engineering in the Schulich School of Engineering at the University of Calgary is pleased to invite applications for a tenure-track Assistant Professor position in Secure Software Systems with an anticipated start date of July 1, 2021. Candidates with an earned doctoral degree in Software Engineering or a related discipline, or those who will have earned a doctoral degree by the anticipated start date, and who have the potential for excellence in research and teaching are invited to apply. The successful candidate should have research experience in one of the following topics:

engineering safe, dependable, and secure software systems

privacy and security in software

security testing

secure software defined network

cybersecurity

The successful candidate will have a demonstrated record of high-quality research publications. They are expected to demonstrate the potential to establish an externally funded research program, and to achieve international recognition within five years. They will have the ability to attract excellent trainees, students, and future researchers. The successful candidates will develop and teach a range of undergraduate and graduate courses in the Software Engineering Program. The successful candidate will have excellent written and oral communication skills and provide evidence of successful teaching ability. Candidates should be eligible for registration as a Professional Engineer with the Association of Professional Engineers and Geoscientists of Alberta (APEGA). Experience working in industry or on industrial projects is an asset.

Closing date for applications:

Contact: Prof. Andy Knight (Department Head) Email: eceinfo@ucalgary.ca

More information: https://engg.careers.ucalgary.ca/jobs/6242346-assistant-professor-secure-software-systems-department-of-electrical-and-computer-engineering

Event date: 26 July to 28 July 2021
Submission deadline: 15 March 2021
Notification: 12 April 2021

Event date: 8 September to 10 September 2021
Submission deadline: 29 March 2021
Notification: 28 May 2021

The differential-linear attack, combining the power of the two most effective techniques for symmetric-key cryptanalysis, was pro- posed by Langford and Hellman at CRYPTO 1994. From the exact for- mula for evaluating the bias of a differential-linear distinguisher (JoC 2017), to the differential-linear connectivity table (DLCT) technique for dealing with the dependencies in the switch between the differential and linear parts (EUROCRYPT 2019), and to the improvements in the con- text of cryptanalysis of ARX primitives (CRYPTO 2020), we have seen significant development of the differential-linear attack during the last four years. In this work, we further extend this framework by replacing the differential part of the attack by rotational-xor differentials. Along the way, we establish the theoretical link between the rotational-xor dif- ferential and linear approximations, revealing that it is nontrivial to directly apply the closed formula for the bias of ordinary differential- linear attack to rotational differential-linear cryptanalysis. We then re- visit the rotational cryptanalysis from the perspective of differential- linear cryptanalysis and generalize Morawiecki et al.’s technique for an- alyzing Keccak, which leads to a practical method for estimating the bias of a (rotational) differential-linear distinguisher in the special case where the output linear mask is a unit vector. Finally, we apply the rota- tional differential-linear technique to the permutations involved in FRIET, Xoodoo, Alzette, and SipHash. This gives significant improvements over existing cryptanalytic results, or offers explanations for previous exper- imental distinguishers without a theoretical foundation. To confirm the validity of our analysis, all distinguishers with practical complexities are verified experimentally.

Succinct non-interactive arguments (SNARGs) in the random oracle model (ROM) have several attractive features: they are plausibly post-quantum; they can be heuristically instantiated via lightweight cryptography; and they have a transparent (public-coin) parameter setup.

The canonical construction of a SNARG in the ROM is due to Micali (FOCS 1994), who showed how to use a random oracle to compile any probabilistically checkable proof (PCP) with sufficiently-small soundness error into a corresponding SNARG. Yet, while Micali's construction is a seminal result, it has received little attention in terms of analysis in the past 25 years.

In this paper, we observe that prior analyses of the Micali construction are not tight and then present a new analysis that achieves tight security bounds. Our result enables reducing the random oracle's output size, and obtain corresponding savings in concrete argument size.

Departing from prior work, our approach relies on precisely quantifying the cost for an attacker to find several collisions and inversions in the random oracle, and proving that any PCP with small soundness error withstands attackers that succeed in finding a small number of collisions and inversions in a certain tree-based information-theoretic game.

AEGIS-128 and Tiaoxin are two AES-based primitives submitted to the CAESAR competition. Among them, AEGIS-128 has been selected in the final portfolio for high-performance applications, while Tiaoxin is a third-round candidate. Although both primitives adopt a stream cipher based design, they are quite different from the well-known bit-oriented stream ciphers like Trivium and the Grain family. Their common feature consists in the round update function, where the state is divided into several 128-bit words and each word has the option to pass through an AES round or not. During the 6-year CAESAR competition, it is surprising that for both primitives there is no third-party cryptanalysis of the initialization phase. Due to the similarities in both primitives, we are motivated to investigate whether there is a common way to evaluate the security of their initialization phases. Our technical contribution is to write the expressions of the internal states in terms of the nonce and the key by treating a 128-bit word as a unit and then carefully study how to simplify these expressions by adding proper conditions. As a result, we found that there are several groups of weak keys with $2^{96}$ keys each in 5-round AEGIS-128 and 8-round Tiaoxin, which allows us to construct integral distinguishers with time complexity $2^{32}$ and data complexity $2^{32}$. Based on the distinguisher, the time complexity to recover the weak key is $2^{72}$ for 5-round AEGIS-128. However, the weak key recovery attack on 8-round Tiaoxin will require the usage of a weak constant occurring with probability $2^{-32}$. We expect that this work can advance the understanding of the designs similar to AEGIS and Tiaoxin.

Efficient Reed-Solomon code reconstruction algorithms, for example, by Guruswami and Wootters (STOC--2016), translate into local leakage attacks on Shamir secret-sharing schemes over characteristic-2 fields. However, Benhamouda, Degwekar, Ishai, and Rabin (CRYPTO--2018) showed that the Shamir secret sharing scheme over prime-fields is leakage resilient to one-bit local leakage if the reconstruction threshold is roughly 0.87 times the total number of parties. In several application scenarios, like secure multi-party multiplication, the reconstruction threshold must be at most half the number of parties. Furthermore, the number of leakage bits that the Shamir secret sharing scheme is resilient to is also unclear.

Towards this objective, we study the Shamir secret-sharing scheme's leakage-resilience over a prime-field $F$. The parties' secret-shares, which are elements in the finite field $F$, are naturally represented as $\lambda$-bit binary strings representing the elements $\{0,1,\dotsc,p-1\}$. In our leakage model, the adversary can independently probe $m$ bit-locations from each secret share. The inspiration for considering this leakage model stems from the impact that the study of oblivious transfer combiners had on general correlation extraction algorithms, and the significant influence of protecting circuits from probing attacks has on leakage-resilient secure computation.

Consider arbitrary reconstruction threshold $k\geq 2$, physical bit-leakage parameter $m\geq 1$, and the number of parties $n\geq 1$. We prove that Shamir's secret-sharing scheme with random evaluation places is leakage-resilient with high probability when the order of the field $F$ is sufficiently large; ignoring polylogarithmic factors, one needs to ensure that $\log \abs F \geq n/k$. Our result, excluding polylogarithmic factors, states that Shamir's scheme is secure as long as the total amount of leakage $m\cdot n$ is less than the entropy $k\cdot\lambda$ introduced by the Shamir secret-sharing scheme. Note that our result holds even for small constant values of the reconstruction threshold $k$, which is essential to several application scenarios.

To complement this positive result, we present a physical-bit leakage attack for $m=1$ physical bit-leakage from $n=k$ secret shares and any prime-field $F$ satisfying $\abs F=1\mod k$. In particular, there are (roughly) $\abs F^{n-k+1}$ such vulnerable choices for the $n$-tuple of evaluation places. We lower-bound the advantage of this attack for small values of the reconstruction threshold, like $k=2$ and $k=3$, and any $\abs F=1\mod k$. In general, we present a formula calculating our attack's advantage for every $k$ as $\abs F\rightarrow\infty.$

Technically, our positive result relies on Fourier analysis, analytic properties of proper rank-$r$ generalized arithmetic progressions, and B\'ezout's theorem to bound the number of solutions to an equation over finite fields. The analysis of our attack relies on determining the ``discrepancy'' of the Irwin-Hall distribution. A probability distribution's discrepancy is a new property of distributions that our work introduces, which is of potential independent interest.

In this paper, we firstly presented optimized implementations of Montgomery multiplication on 64-bit ARM processors by taking advantages of Karatsuba algorithm and efficient multiplication instruction sets for ARM64 architectures. The implementation of Montgomery multiplication improved the performance of public key cryptography (e.g. CSIDH, ECC, and RSA) implementations on ARM64 architectures, directly. Last but not least, the performance of Karatsuba algorithm does not ensure the fastest speed record, while it is determined by the clock cycles per multiplication instruction of target ARM architectures. In particular, recent Apple processors based on ARM64 architecture show lower cycles per instruction of multiplication than that of ARM Cortex-A series. For this reason, the schoolbook method shows much better performance than the sophisticated Karatsuba algorithm on Apple processors. With this observation, we can determine the proper approach for multiplication of cryptography library (e.g. MS-SIDH) on Apple processors and ARM Cortex-A processors.

Agreement protocols for partially synchronous or asynchronous networks tolerate fewer than one-third Byzantine faults. If parties are equipped with trusted hardware that prevents equivocation, then fault tolerance can be improved to fewer than one-half Byzantine faults, but typically at the cost of increased communication complexity. In this work, we present results that use small trusted hardware without worsening communication complexity assuming the adversary controls a fraction of the network that is less than one-half. Our results include a version of HotStuff that retains linear communication complexity in each view and a version of the VABA protocol with quadratic communication, both leveraging trusted hardware to tolerate a minority of corruptions. Our results use expander graphs to achieve efficient communication in a manner that may be of independent interest.

Distributed ledgers implement a storage layer, on top of which a shared state is maintained in a decentralized manner. In UTxO-based ledgers, like Bitcoin, the shared state is the set of all unspent outputs (UTxOs), which serve as inputs to future transactions. The continuously increasing size of this shared state will gradually render its maintenance unaffordable. Our work investigates techniques that minimize the shared state of the distributed ledger, i.e., the in-memory UTxO set. To this end, we follow two directions: a) we propose novel transaction optimization techniques to be followed by wallets, so as to create transactions that reduce the shared state cost and b) propose a novel fee scheme that incentivizes the creation of "state-friendly" transactions. We devise an abstract ledger model, expressed via a series of algebraic operators, and define the transaction optimization problem of minimizing the shared state; we also propose a multi-layered algorithm that approximates the optimal solution to this problem. Finally, we define the necessary conditions such that a ledger’s fee scheme incentivizes proper state management and propose a state efficient fee function for Bitcoin.

Sequences of consecutive Legendre and Jacobi symbols as pseudorandom bit generators have been proposed for cryptographic use in 1988. Since then they were mostly forgotten in the applications. However, recently revived interest is shown to pseudorandom functions (PRF) based on the Legendre and power residue symbols, due to their extreme efficiency in the multi-party setting and their conjectured post-quantum security. The lack of provable security results hinders the deployment of PRFs based on quadratic and power residue symbols. On the other hand, the security of the Legendre PRF and other variants do not seem to be related to standard cryptographic assumptions, e.g. discrete logarithm or factoring.

Therefore, in this work, we show that key-recovery attacks against the Legendre PRF are equivalent to solving a specific family of multivariate quadratic (MQ) equation system over a finite prime field. This new perspective sheds some light on the complexity of key-recovery attacks against the Legendre PRF. This allows us to take the first steps in settling the provable security of the Legendre PRF and other variants. We do this by conducting extensive algebraic cryptanalysis on the resulting MQ instance. We show how the currently best-known techniques and attacks fall short in solving these sparse quadratic equation systems. Another benefit of viewing the Legendre PRF as an MQ instance is that it facilitates new applications of the Legendre PRF, such as verifiable random function or oblivious (programmable) pseudorandom function. These new applications can be used in cryptographic protocols, such as state of the art proof-of-stake consensus algorithms or private set intersection protocols.

Group signatures allow users to create signatures on behalf of a group while remaining anonymous. Such signatures are a powerful tool to realize privacy-preserving data collections, where e.g., sensors, wearables or vehicles can upload authenticated measurements into a data lake. The anonymity protects the user’s privacy yet enables basic data processing of the uploaded unlinkable information. For many applications, full anonymity is often neither desired nor useful though, and selected parts of the data must eventually be correlated after being uploaded. Current solutions of group signatures do not provide such functionality in a satisfactory way: they either rely on a trusted party to perform opening or linking of signatures, which clearly conflicts with the core privacy goal of group signatures; or require the user to decide upon the linkability of signatures before they are generated.

In this paper we propose a new variant of group signatures that provides linkability in a flexible and user-centric manner. Users – and only they – can decide before and after signature creation whether they should remain linkable or be correlated. To prevent attacks where a user omits certain signatures when a sequence of events in a certain section (e.g., time frame), should be linked, we further extend this new primitive to allow for sequential link proofs. Such proofs guarantee that the provided sequence of data is not only originating from the same signer, but also occurred in that exact order and contains all of the user’s signatures within the time frame. We formally define the desired security and privacy properties, propose a provably secure construction based on DL-related assumptions and report on a prototypical implementation of our scheme.

Existing Byzantine fault-tolerant (BFT) state-machine replication (SMR) protocols in the standard (bounded) synchrony and weak synchrony models rely on equivocation detection to ensure safety. To perform a commit (or output a transaction block), this detection inherently requires $O(n^2)$ communication overhead among $n$ nodes and waiting for $O(\Delta)$ time, where $\Delta$ is the worst-case network delay. The quadratic communication overhead limits scalability. Moreover, as the typical network latency $\delta$ tends to be much smaller than $\Delta$, $51\%$ honest-majority (and hence synchronous or weakly synchronous) solutions become slow as compared to $67\%$ honest-majority asynchronous protocols working at network speed.

The observation that SMR commits do not have to be treated separately motivates this work. We propose UCC (Unique Chain Commit) rule, a novel yet simple rule for hash chains where extending a block by including its hash is treated as a vote for the block and all its direct and indirect parents. When a block obtains $f+1$ such votes, where $f$ is the maximum number of faulty nodes in the system, we commit the block and its parents. We use this UCC rule to design Apollo, an SMR protocol with rotating leaders which has a linear communication complexity. Apollo proposes and commits a block every $\delta$ time units with every block having a latency of $(f+1)\delta$. When compared to existing works which use equivocation detection, we improve the optimistic commit latency when $(f+1)\delta<2\Delta$. We prove the security of our protocol in both standard and weak synchrony models. We also implement and compare Apollo with the state of the art protocol, and demonstrate Apollo having commit latencies independent of and less than the $\Delta$ parameter, and also show significant gains in response rates with increasing $n$. For instance, when $n=3$, Apollo can commit blocks of size $2000$ as fast $3$ ms. For $n=65$, Apollo produces $3$x more committed transactions per second than the state of the art Sync HotStuff protocol.

Various Artificial Intelligence (AI) techniques are combined with classic side-channel methods to improve the efficiency of attacks. Among them, Genetic Algorithms based Correlation Power Analysis (GA-CPA) is proposed to launch attacks on hardware cryptosystems to extract the secret key efficiently. However, the convergence rate is unsatisfactory due to two problems: individuals of the initial population generally have low fitnesses, and the mutation operation is hard to generate high-quality components. In this paper, we give an analysis framework to solve them. Firstly, we employ lists of sorted candidate key bytes obtained with CPA to initialize the population with high quality candidates. Secondly, we guide the mutation operation with lists of candidate keys sorted according to fitnesses, which are obtained by exhausting the values of a certain key byte and calculating the corresponding correlation coefficients with the whole key. Thirdly, key enumeration algorithms are utilized to deal with ranked candidates obtained by the last generation of GA-CPA to improve the success rate further. Simulation experimental results show that our method reduces the number of traces by 33.3\% and 43.9\% compared to CPA with key enumeration and GA-CPA respectively when the success rate is fixed to 90\%. Real experiments performed on SAKURA-G confirm that the number of traces required in our method is much less than the numbers of traces required in CPA and GA-CPA. Besides, we adjust our method to deal with DPA contest v1 dataset, and achieve a better result of 40.76 traces than the winning proposal of 42.42 traces. The computation cost of our proposal is nearly 16.7\% of the winner.

The notion of functional encryption (FE) was proposed as a generalization of plain public-key encryption to enable a much more fine-grained handling of encrypted data, with advanced applications such as cloud computing, multi-party computations, obfuscating circuits or Turin machines. While FE for general circuits or Turin machines gives a natural instantiation of the many cryptographic primitives, existing FE schemes are based on indistinguishability obfuscation or multilinear maps which either rely on new computational hardness assumptions or heuristically claimed to be secure. In this work, we present new techniques directly yielding FE for inner product functionality where secret-keys provide access control via polynomial-size bounded-depth circuits. More specifically, we encrypt messages with respect to attributes and embed policy circuits into secret-keys so that a restricted class of receivers would be able to learn certain property about the messages. Recently, many inner product FE schemes were proposed. However, none of them uses a general circuit as an access structure. Our main contribution is designing the first construction for an attribute-based FE scheme in key-policy setting for inner products from well-studied Learning With Errors (LWE) assumption. Our construction takes inspiration from the attribute-based encryption of Boneh et al. from Eurocrypt 2014 and the inner product functional encryption of Agrawal et al. from Crypto 2016. The scheme is proved in a stronger setting where the adversary is allowed to ask secret-keys that can decrypt the challenge ciphertext. Doing so requires a careful setting of parameters for handling the noise in ciphertexts to enable correct decryption. Another main advantage of our scheme is that the size of ciphertexts and secret-keys depends on the depth of the circuits rather than its size. Additionally, we extend our construction in a much desirable multi-input variant where secret-keys are associated with multiple policies subject to different encryption slots. This enhances the applicability of the scheme with finer access control.

Attribute-based encryption (ABE) is a cryptographic primitive which supports fine-grained access control on encrypted data, making it an appealing building block for many applications. Pair encodings (Attrapadung, EUROCRYPT 2014) are simple primitives that can be used for constructing fully secure ABE schemes associated to a predicate relative to the encoding. We propose a generic transformation that takes any pair encoding scheme (PES) for a predicate $P$ and produces a PES for its negated predicate $\bar{P}$ . This construction finally solves a problem that was open since 2015. Our techniques bring new insight to the expressivity and generality of PES and can be of independent interest. We also provide, to the best of our knowledge, the first pair encoding scheme for negated doubly spatial encryption (obtained with our transformation) and explore several other consequences of our results.

Payment-channel networks (PCN) are the most prominent approach to tackle the scalability issues of current permissionless blockchains. A PCN reduces the load on-chain by allowing arbitrarily many off-chain multi-hop payments (MHP) between any two users connected through a path of payment channels. Unfortunately, current protocols for MHP are far from satisfactory. One round MHP (e.g., Interledger) are insecure as a malicious intermediary can steal the payment funds. Two-round MHP (e.g., Lightning Network (LN)) follow the 2-phase-commit paradigm as in databases to overcome this issue. However, when tied with economical incentives, 2-phase-commit brings other security threats (i.e., wormhole attacks), staggered collateral (i.e., funds are locked for a time proportional to the payment path length) and dependency on specific scripting language functionality (e.g., hash time lock contracts) that hinders a wider deployment in practice.

We present Blitz, a novel MHP protocol that demonstrates for the first time that we can achieve the best of the two worlds: a single round MHP where no malicious intermediary can steal coins. Moreover, Blitz provides privacy for sender and receiver, it is not prone to the wormhole attack and it requires only constant collateral. Additionally, we construct MHP using only digital signatures and a timelock functionality, both available at the core of virtually every cryptocurrency today. We provide the cryptographic details of Blitz and we formally prove its security. Furthermore, our experimental evaluation on an LN snapshot shows that the LN collateral results in between 4x and 33x more unsuccessful payments than the Blitz collateral (both compared to a baseline), reduce the size of the payment contract by 26% and prevent up to 0.3 BTC (3397 USD in October 2020) in fees being stolen over a three day period as it avoids wormhole attacks by design.

In this paper, we compare several non-tight degree evaluation methods i.e., Boura and Canteaut's formula, Carlet's formula as well as Liu's numeric mapping and division property proposed by Todo, and hope to find the best one from these methods for practical applications. Specifically, for the substitution-permutation-network (SPN) ciphers, we first deeply explore the relationships between division property of an Sbox and its algebraic properties (e.g., the algebraic degree of its inverse). Based on these findings, we can prove theoretically that division property is never worse than Boura and Canteaut's and Carlet's formulas, and we also experimentally verified that the division property can indeed give a better bound than the latter two methods. In addition, for the nonlinear feedback shift registers (NFSR) based ciphers, according to the propagation of division property and the core idea of numeric mapping, we give a strict proof that the estimated degree using division property is never greater than that of numeric mapping. Moreover, our experimental results on Trivium and Kreyvium indicate the division property actually derives a much better bound than the numeric mapping. To the best of our knowledge, this is the first time to give a formal discussion on the relationships between division property and other degree evaluation methods, and we present the first theoretical proof and give the experimental verification to illustrate that division property is the optimal one among these methods in terms of the accuracy of the upper bounds on algebraic degree.

Outsourcing computation allows resource limited clients to access computing on demand. Various types of clusters, grids, and clouds, such as Microsoft’s Azure and Amazon’s EC2, form today’s outsourced computing infrastructure. A basic requirement of outsourcing is providing guarantee that the computation result is correct. We consider an automated and efficient way of achieving assurance where the computation is replicated and outsourced to two contractors by a smart contract that will decide on the correctness of the computation result, by comparing the two received results. We show that all previous incentivized outsourcing protocols with proven correctness fail when automated by a smart contract, because of copy attack where a contractor simply copies the submitted response of the other contractor. We then design an incentive mechanism that uses two lightweight response-checking protocols, and employ monetary reward, fine, and bounty to incentivize correct computation. We use game theory to model and analyze our mechanism, and prove that it has a single Nash equilibrium, corresponding to the contractors’ strategy of correctly computing the result. Our work provides a foundation for incentivized computation in the smart contract setting and opens new research directions.