International Association
for Cryptologic Research

Statistical testing is a mechanism that has been included in various domains or fields, providing a method for making quantitative decisions about a particular sample. The statistical testing plays a big role in selecting and testing random and pseudorandom generators whose output may be used in the field of cryptography, specifically for the encryption, decryption and the keys or sub-keys generation. In this paper we study one of the NIST 800-22 random number generation tests. We give an overview for the statistical testing and its importance for cryptography, then we focus on one of the tests, specifically the Binary Matrix Rank Test. We provide a logical schema and a new code implementation in Python 3. Further we evaluate the test, by running it on a collection of well chosen test samples and gathering the results based on which we do an assumption. More exactly, we validate if the binary sequence input can be classified as random or not depending on the bits density.

In this paper, we study quantum key-recovery attacks on block ciphers. While it is well known that a quantum adversary can generically speed up an exhaustive search of the key, much less is known on how to use specific vulnerabilities of the cipher to accelerate this procedure. In this context, we show how to convert classical boomerang and mixing boomerang attacks into efficient quantum key-recovery attacks. In some cases, we can even obtain a quadratic speedup, the same as simple differential attacks. We apply this technique to a 5-round attack on SAFER++.

Hash-based signatures offer a conservative alternative to post-quantum signatures with arguably better-understood security than other post-quantum candidates. Nevertheless, a major drawback that makes it less favorable to deploy in practice is the (relatively) large size of the signatures, and long signing and verification time.

In this paper, we introduce SPHINCS-$\alpha$, a stateless hash-based signature scheme, which benefits from a twofold improvement. First, we provide an improved Winternitz one-time signature with an efficient size-optimal encoding, which might be of independent interest. Second, we give a variant of the few-time signature scheme, FORC, by applying the Winternitz method. Plugging the two improved components into the framework of the state-of-the-art (stateless) hash-based SPHINCS$^+$, with carefully chosen parameter choices, yields a certain degree of performance improvement. In particular, under the ``small'' series parameter set aiming for compact signatures, our scheme reduces signature size and signing time by 8-11% and 3-15% respectively, compared to SPHINCS$^+$ at all security levels. For the ``fast'' series that prioritizes computation time, our scheme exhibits a better performance in general. E.g., when instantiating the simple tweakable hash function with SHA-256, our scheme reduces the signing and verification time by 7-10% and up to 10% respectively, while keeping roughly the same signature size. The security proofs/estimates follow the framework of SPHINCS$^+$. To facilitate a fair comparison, we give the implementation of SPHINCS-$\alpha$ by adapting that of SPHINCS$^+$, and we provide a theoretical estimate in the number of hash function calls.

In this work, we present a fast and first-order secure Kyber implementation optimized for ARM Cortex-M4. Most notably, to our knowledge this is the first liberally-licensed open-source Cortex-M4 implementation of masked Kyber. The ongoing NIST standardization process for post-quantum cryptography and newly proposed side-channel attacks have increased the demand for side-channel analysis and countermeasures for the finalists. On the foundation of the commonly used PQM4 project, we make use of the previously presented optimizations for Kyber on a Cortex-M4 and further combine different ideas from various recent works to achieve a better performance and improve the security in comparison to the original implementations. We show our performance results for first-order secure implementations. Our masked Kyber768 decapsulation on the ARM Cortex-M4 requires only 2 978 441 cycles, including randomness generation from the internal RNG. We then practically verify our implementation by using the t-test methodology with 100 000 traces.

Falcon is a very efficient and compact lattice-based signature finalist of the NIST's Post-Quantum standardization campaign. This work assesses Falcon's side-channel resistance by analyzing two vulnerabilities, namely the pre-image computation and the trapdoor sampling. The first attack is an improvement of Karabulut and Aysu (DAC 2021). It overcomes several difficulties inherent to the structure of the stored key like the Fourier representation and directly recovers the key with a limited number of traces and a reduced complexity. The main part of this paper is dedicated to our second attack: we show that a simple power analysis during the signature execution could provide the exact value of the output of a subroutine called the base sampler. This intermediate value does not directly lead to the secret and we had to adapt the so-called hidden parallelepiped attack initially introduced by Nguyen and Regev in Eurocrypt 2006 and reused by Ducas and Nguyen in Asiacrypt 2012. We extensively quantify the resources for our attacks and experimentally demonstrate them with Falcon's reference implementation on the ELMO simulator (McCann, Oswald and Whitnall USENIX 2017) and on a ChipWhisperer Lite with STM32F3 target (ARM Cortex M4). While the success of these attacks may be unsurprising because the reference implementation does not claim any side-channel protection, these new attacks highlight the need for side-channel protection for one of the three finalists of NIST's standardization campaign by pointing out the vulnerable parts and quantifying the resources of the attacks.

Smart-contract ledger platforms, like Ethereum, rate-limit their workload with incentives. Users issue orders, called transactions, with assigned fees, and system operators, called miners, confirm them and receive the fees. The combination of limited throughput and varying demand results in a volatile fee market, where under-paying transactions are not confirmed. However, the security of prominent smart contracts, securing billions of dollars, critically relies on their transactions being confirmed in specific, future time frames. Despite theoretical and practical active efforts, guaranteeing timely confirmation remained an open problem.

We present LedgerHedger, a mechanism for assuring that a miner will confirm a user's transaction in a target time frame. As the name implies, LedgerHedger employs hedging~-- the user pays for her transaction in advance and the miner commits to confirm it even if the required fee rises. But unlike regulated markets, there are no external enforcers, and miners unilaterally choose which transactions to confirm. Due to the amounts at stake, relying on miner altruism does not suffice.

Therefore, LedgerHedger uses a combination of collateral deposits to incentivize correct behavior. The contract requires the issuer to deposit her payment and the miner to deposit a collateral. During the target time frame, the miner is incentivized to confirm the issuer's transaction if it exists, but is also capable of withdrawing the payment and the collateral if not.

LedgerHedger gives rise to a game, where the parties can only take specific actions. For a wide range of parameter values there is a subgame perfect equilibrium where both parties act as desired. We implement LedgerHedger and deploy it on an Ethereum test network, showing its efficacy and minor overhead.

For Multi-key Fully Homomorphic scheme(MKFHE) based on the Learning With Error(LWE) problem, in order to enable multi-key function, ciphertext expansion is required. In order to achieve ciphertext expansion, the random matrix used in encryption must be encrypted. For an boolean circuit with input length $N$, multiplication depth $L$, security parameter $\lambda$ , the number of additional encryptions introduced to achieve ciphertext expansion is $O(N\lambda^6L^4)$, which is a lot of overhead for computationally sensitive local users. In order to alleviate this overhead, we proposed a weak version of the MKFHE, using the leakage resilient property of Leftover Hash Lemma(LHL), the first weak version of the MKFHE scheme is constructed under plain model. The total private key is the sum of all participant keys. We note that previous MKFHE schemes with this key structure are all based on Common Reference String Model(CRS). Our scheme is simpler and more efficient in construction: we don’t need to encrypt the random matrix, so the extra overhead $O(N\lambda^6L^4)$ is reduced to $O(N)$.

For MKFHE based on Ring Learing With Error(RLWE) problem, since the Regularity Lemma on rings does not have the corresponding leakage resilient property, we can only construct the weak-MKFHE scheme under the random oracle model.

We present new side-channel attacks on SIKE, the isogeny-based candidate in the NIST PQC competition. Previous works had shown that SIKE is vulnerable to differential power analysis and pointed to coordinate randomization as an effective countermeasure. We show that coordinate randomization alone is not sufficient, as SIKE is vulnerable to a class of attacks similar to refined power analysis in elliptic curve cryptography, named zero-value attacks. We describe and confirm in the lab two such attacks leading to full key recovery, and analyze their countermeasures.

The topic of this contribution is the cryptanalytic use of spurious keys, i.e. non-target keys returned by exhaustive key search. We show that the counting of spurious keys allows the construction of distinguishing attacks against block ciphers that are generically expected to start working at (marginally) lower computational cost than is required to find the target key by exhaustive search. We further show that if a brute force distinguisher does return a strong distinguishing signal, fairly generic optimizations to random key sampling will in many circumstances render the cost of detecting the signal massively lower than the cost of exhaustive search.

We then use our techniques to quantitatively characterize various non-Markov properties of round-reduced Speck32/64. We fully compute, for the first time, the ciphertext pair distribution of 3-round Speck32/64 with one input difference $\Delta$ without any approximations and show that it differs markedly from Markov model predictions; we design a perfect distinguisher for the output distribution induced by the same input difference for 5-round Speck32/64 that is efficient enough to process millions of samples on an ordinary PC in a few days; we design a generic two-block known-plaintext distinguisher against Speck32/64 and show that it achieves 58 percent accuracy against 5-round Speck, equivalent e.g. to a linear distinguisher with $\approx 50$ percent bias.

Turning our attention back to differential cryptanalysis, we show that our known-plaintext distinguisher automatically handles the 5-round output distribution induced by input difference $\Delta$ as well as the perfect differential distinguisher, but that no significant additional signal is obtained from knowing the plaintexts. We then apply the known-plaintext brute force distinguisher to 7-round Speck32/64 with fixed input difference $\Delta$, finding that it achieves essentially the same distinguishing advantage as state-of-the-art techniques (neural networks with key averaging). We also show that our techniques can precisely characterize non-Markov properties in longer differential trails for Speck32/64.

In this paper, we present an asynchronous Byzantine reliable broadcast (RBC) protocol with balanced costs and an improved asynchronous verifiable information dispersal (AVID) protocol. Our RBC protocol broadcasts a message $M$ among $n$ nodes with total communication cost $O(n|M|+\kappa n^2)$ and per-node communication cost $O(|M|+\kappa n)$. In contrast, the state-of-the-art reliable broadcast protocol has imbalanced costs where the broadcaster incurs $O(n|M|)$ while other nodes incur a communication cost of $O(|M|+\kappa n)$. We then use our new RBC protocol and additional techniques to design an asynchronous verifiable information dispersal (AVID) protocol with total dispersal cost $O(|M|+\kappa n^2)$ and retrieval cost $O(|M|+\kappa n)$. In our AVID protocol, the clients incur a communication cost of $O(|M|+\kappa n)$ in comparison to $O(|M|+\kappa n\log n)$ cost of prior best AVID protocol that does not require any trusted setup. Moreover, each node in our AVID protocol incurs a storage cost of $O(|M|/n+\kappa)$ bits, whereas in prior best AVID protocol each node incurs a storage cost of $O(|M|/n+\kappa \log n)$ bits. Finally, we present lower bound results on per-node communication cost of any deterministic \rbc\ protocol and the total communication cost of dispersal and retrieval phase in any deterministic \avid\ protocol. Both our balanced RBC and AVID protocols have near-optimal communication costs.

End-to-end encrypted file-sharing systems enable users to share files without revealing the file contents to the storage servers. However, the servers still learn metadata, including user identities and access patterns. Prior work tried to remove such leakage but relied on strong assumptions. Metal (NDSS '20) is not secure against malicious servers. MCORAM (ASIACRYPT '20) provides confidentiality against malicious servers, but not integrity.

Titanium is a metadata-hiding file-sharing system that offers confidentiality and integrity against malicious users and servers. Compared with MCORAM, which offers confidentiality against malicious servers, Titanium also offers integrity. Experiments show that Titanium is 5x-200x faster or more than MCORAM.

In this paper, we present a high-speed, unified elliptic curve cryptography (ECC) processor for arbitrary Weierstrass curves over GF(p), which to the best of our knowledge, outperforms other similar works in terms of execution time. Our approach employs the combination of the schoolbook long and Karatsuba multiplication algorithm for the elliptic curve point multiplication (ECPM) to achieve better parallelization while retaining low complexity. In the hardware implementation, the substantial gain in speed is also contributed by our n-bit pipelined Montgomery Modular Multiplier (pMMM), which is constructed from our n-bit pipelined multiplier-accumulators that utilizes digital signal processor (DSP) primitives as digit multipliers. Additionally, we also introduce our unified, pipelined modular adder-subtractor (pMAS) for the underlying field arithmetic, and leverage a more efficient yet compact scheduling of the Montgomery ladder algorithm. The implementation for 256-bit modulus size on the 7-series FPGA: Virtex-7, Kintex-7, and XC7Z020 yields 0.139, 0.138, and 0.206 ms of execution time, respectively. Furthermore, since our pMMM module is generic for any curve in Weierstrass form, we support multi-curve parameters, resulting in a unified ECC architecture. Lastly, our method also works in constant time, making it suitable for applications requiring high speed and SCA-resistant characteristics.

The concept of lightweight cryptography has gained in popularity recently, also due to various competitions and standardization efforts specifically targeting more efficient algorithms, which are also easier to implement.

One of the important properties of lightweight constructions is the area of a hardware implementation, or in other words, the size of the implementation in a particular environment. Reducing the area usually has multiple advantages like decreased production cost or lower power consumption.

In this paper, we focus on MAC functions and on ASIC implementations in hardware, and our goal is to minimize the area requirements in this setting. For this purpose, we design a new MAC scheme based on the well-known Pelican MAC function. However, in an effort to reduce the size of the implementation, we make use of smaller internal permutations. While this certainly leads to a higher internal collision probability, effectively reducing the allowed data, we show that the full security is still maintained with respect to other attacks, in particular forgery and key recovery attacks. This is useful in scenarios which do not require large amounts of data.

Our detailed estimates, comparisons, and concrete benchmark results show that our new MAC scheme has the lowest area requirements and offers competitive performance. Indeed, we observe an area advantage of up to 30% in our estimated comparisons, and an advantage of around 13% compared to the closest competitor in a concrete implementation.

The School of Economics in the Faculty of Commerce at the University of Cape Town is inviting applications for PhD students and Postdoctoral Research Fellows. The overarching theme of the fellowships is “the data economy” and students and recent graduates with a background in economics, computer science, mathematics, finance, and related disciplines are invited to apply. Any of the following research areas ar of particular interest: The economics of privacy Privacy-preserving technology Data marketplaces The economics of innovation Successful applicants will work within a research group that strives for academic excellence and is interested in various aspects of data ownership, from analyzing its theoretical foundation in the economics of property rights and privacy, to developing practical tools and studying existing applications. In this context, open source software, artistic work, and scholarly research are three examples where at least a weak notion of data ownership can be studied. Applications open now and are considered on a rolling basis until 30 April or until the positions are filled. Appointments are for as soon as is feasible. The tenure of the Postdoctoral fellowship is for up to three years, while the tenure for PhD positions is usually three years, but can be extended for up to five years. Due to the ongoing pandemic, successful applicants can choose to work remotely in 2022. Postdoctoral fellows receive a fellowship of R350,000 per annum and no benefits are included in the value of the fellowship. An additional travel allowance of R30,000 p.a. is available for successful applicants. The successful applicant will be required to comply with the University’s approved policies, procedures and practices for the postdoctoral sector. PhD students receive a fellowship of R210,000 p.a. and an additional travel allowance of R20,000 p.a. in addition to access to university-wide funding for conference travel. We typically arrange for PhD students to spend at least one semester at a leading international university and help organize an internship at a leading international policy institution or fintech company.

Closing date for applications:

Contact: anda.ngcaba@uct.ac.za co-pierre.georg@uct.ac.za

The position is with the Security and Privacy group, part of the School of Informatics at The University of Edinburgh. The Security and Privacy group carries out research on all aspects of security and privacy, including applied and theoretical cryptography, software security, systems and hardware security, human factors, protocol analysis, verification and quantum/post-quantum cryptography. The successful candidate will have a PhD (or be near to completion); experience as an established researcher in one or more areas of security and privacy including but not limited to cryptography, database security, distributed systems security, hardware security, Internet of Things (IoT) security, network security, systems security; enthusiasm to undertake original research including leading a research group; the ability to engage with undergraduate and postgraduate teaching and academic supervision; and the ability to be involved in enhancing eLearning security initiatives.

Closing date for applications:

Contact: Aggelos Kiayias

More information: https://elxw.fa.em3.oraclecloud.com/hcmUI/CandidateExperience/en/sites/CX_1001/job/2980/?utm_medium=jobshare

We explain how a differential fault analysis (DFA) works on AES 128, 192 or 256 bits.

This book chapter outlines techniques for breaking cryptography by taking advantage of implementation mistakes made in practice, with a focus on those that exploit the mathematical structure of the most widely used public-key primitives.

This paper proposes the first practical pairing-free three-move blind signature schemes that (1) are concurrently secure, (2) produce short signatures (i.e., three or four group elements/scalars), and (3) are provably secure either in the generic group model (GGM) or the algebraic group model (AGM) under the (plain or one-more) discrete logarithm assumption (beyond additionally assuming random oracles). We also propose a partially blind version of one of our schemes. Our schemes do not rely on the hardness of the ROS problem (which can be broken in polynomial time) or of the mROS problem (which admits sub-exponential attacks). The only prior work with these properties is Abe’s signature scheme (EUROCRYPT ’02), which was recently proved to be secure in the AGM by Kastner et al. (PKC ’22), but which also produces signatures twice as long as those from our scheme. The core of our proofs of security is a new problem, called weighted fractional ROS (WFROS), for which we prove (unconditional) exponential lower bounds.

The Signal protocol is a secure messaging protocol providing end-to-end encrypted asynchronous communication. In this paper, we focus on a method capable of hiding membership information from the viewpoint of non group members in a secure group messaging (SGM) protocol, which we call "membership privacy''. Although Chase et al. (ACM CCS 2020) have considered the same notion, their proposal is an extension of Signal so called "Pairwise Signal'' where a group message is repeatedly sent over individual Signal channels. Thus their protocol is not scalable. In this work, we extend the Cohn-Gordon et al. SGM protocol (ACM CCS 2018), which we call the Asynchronous Ratcheting Trees (ART) protocol, to add membership privacy. We employ a key-private and robust public-key encryption (Abdalla et al., TCC2010/JoC2018) for hiding membership-related values in the setup phase. Furthermore, we concentrate on the fact that a group common key provides anonymity. This fact is used to encrypt membership information in the key update phase. Our extension does not affect the forward secrecy and post-compromise security of the original ART protocol. Although the efficiency of each user in the setup phase is worsened, the setup phase is run only once, and it seems to be acceptable. Any additional cost for key update does not depend on the number of group members (specifically, one encryption and decryption of a symmetric key-encryption scheme and one execution of a key-derivation function for each key update are employed). Therefore, the proposed protocol can add membership privacy to the ART protocol with a quite small overhead.

The probing security model is widely used to formally prove the security of masking schemes. Whenever a masked implementation can be proven secure in this model with a reasonable \emph{leakage rate}, it is also provably secure in a realistic leakage model known as the \emph{noisy leakage model}. This paper introduces a new framework for the composition of probing-secure circuits. We introduce the security notion of \emph{input-output separation} (IOS) for a refresh gadget. From this notion, one can easily compose gadgets satisfying the classical probing security notion --which does not ensure composability on its own-- to obtain a \emph{region probing secure} circuit. Such a circuit is secure against an adversary placing up to $t$ probes in each gadget composing the circuit, which ensures a tight reduction to the more realistic noisy leakage model. After introducing the notion and proving our composition theorem, we compare our approach to the composition approaches obtained with the (Strong) Non-Interference (S/NI) notions as well as the Probe-Isolating Non-Interference (PINI) notion. We further show that any uniform SNI gadget achieves the IOS security notion, while the converse is not true. We further describe a refresh gadget achieving the IOS property for any linear sharing with a quasilinear complexity $\Theta(n \log n)$ and a $O(1/\log n)$ leakage rate (for an $n$-size sharing). This refresh gadget is a simplified version of the quasilinear SNI refresh gadget proposed by Battistello, Coron, Prouff, and Zeitoun (ePrint~2016). As an application of our composition framework, we revisit the quasilinear-complexity masking scheme of Goudarzi, Joux and Rivain (Asiacrypt~2018). We improve this scheme by generalizing it to any base field (whereas the original proposal only applies to field with $n$th powers of unity) and by taking advantage of our composition approach. We further patch a flaw in the original security proof and extend it from the random probing model to the stronger region probing model. Finally, we present some application of this extended quasilinear masking scheme to AES and MiMC and compare the obtained performances.