International Association
for Cryptologic Research

FORS is the underlying hash-based few-time signing scheme in SPHINCS+, one of the nine signature schemes which advanced to round 2 of the NIST Post-Quantum Cryptography standardization competition. In this paper, we analyze the security of FORS with respect to adaptive chosen message attacks. We show that in such a setting, the security of FORS decreases significantly with each signed message when compared to its security against non-adaptive chosen message attacks. We propose a chaining mechanism that with slightly more computation, dynamically binds the Obtain Random Subset (ORS) generation with signing, hence, eliminating the oine advantage of adaptive chosen message adversaries. We apply our chaining mechanism to FORS and present DFORS whose security against adaptive chosen message attacks is equal to the non-adaptive security of FORS. In a nutshell, using SPHINCS+-128s parameters, FORS provides 75-bit security and DFORS achieves 150-bit security with respect to adaptive chosen message attacks after signing one message. We note that our analysis does not affect the claimed security of SPHINCS+. Nevertheless, this work provides a better understanding of FORS and other HORS variants and furnishes a solution if new adaptive cryptanalytic techniques on SPHINCS+ emerge.

Genome-Wide Association Studies (GWAS) seek to identify genetic variants associated with a trait, and have been a powerful approach for understanding complex diseases. A critical challenge for GWAS has been the dependence on individual-level data that typically have strict privacy requirements, creating an urgent need for methods that preserve the individual-level privacy of participants. Here, we present a privacy-preserving framework based on several advances in homomorphic encryption and demonstrate that it can perform an accurate GWAS analysis for a real dataset of more than 25,000 individuals, keeping all individual data encrypted and requiring no user interactions. Our extrapolations show that it can evaluate GWAS of 100,000 individuals and 500,000 SNPs in 5.6 hours on a single server node (or in 11 minutes on 31 server nodes running in parallel). Our performance results are more than one order of magnitude faster than prior state-of-the-art results using secure multi-party computation, which requires continuous user interactions, with the accuracy of both solutions being similar. Our homomorphic encryption advances can also be applied to other domains where large-scale statistical analyses over encrypted data are needed.

Fire alarm and signaling systems are a networked system of fire detectors, fire control units, automated fire extinguishers, and fire notification appliances. Malfunction of these safety-critical cyber-physical systems may lead to chaotic evacuations, property damages, and even loss of human life. Therefore, reliability is one of the most crucial factors for fire detectors. Indeed, even a single report of a fire cannot be ignored considering the importance of early fire detection and suppression. In this paper, we show that wide-area smoke detectors, which are globally installed in critical infrastructures such as airports, sports facilities, and auditoriums, have significant vulnerabilities in terms of reliability; one can remotely and stealthily induce false fire alarms and suppress real fire alarms with a minimal attacker capability using simple equipment. The practicality and generalizability of these vulnerabilities has been assessed based on the demonstration of two types of sensor attacks on two commercial-off-the-shelf optical beam smoke detectors from different manufacturers. Further, the practical considerations of building stealthy attack equipment has been analyzed, and an extensive survey of almost all optical beam smoke detectors on the market has been conducted. In addition, we show that the current standards of the fire alarm network connecting the detector and a control unit exacerbate the problem, making it impossible or very difficult to mitigate the threats we found. Finally, we discuss hardware and software-based possible countermeasures for both wide-area smoke detectors and the fire alarm network; the effectiveness of one of the countermeasures is experimentally evaluated.

The Gimli permutation was proposed in CHES 2017, which is distinguished from other well-known permutation-based primitives for its cross-platform performance. One main strategy to achieve such a goal is to utilize a sparse linear layer (Small-Swap and Big-Swap), which occurs every two rounds. In addition, the round constant addition occurs every four rounds and only one 32-bit word is affected by it. The above two facts have been exploited by \mbox{Liu-Isobe-Meier} to mount a distinguishing attack on 14 rounds of Gimli permutation with time complexity 1 by utilizing the internal difference. Inspired by the \mbox{14-round} distinguisher, we demonstrate that it is feasible to extend it to the full Gimli permutation with time complexity $2^{129}$ by further taking advantage of its weak diffusion. The corresponding technique is named as hybrid zero internal differential since the internal difference and XOR difference are simultaneously traced. Our distinguisher can be interpreted as a variant of the common differential distinguisher and \mbox{zero-sum} distinguisher. Apart from the permutation itself, combined with some new properties of the SP-box, the weak diffusion can also be utilized to accelerate the preimage attacks on reduced \mbox{Gimli-Hash} and Gimli-XOF-128 with a divide-and-conquer method. As a consequence, the preimage attack on 2-round Gimli-Hash is practical and it can reach up to 5 rounds. For Gimli-XOF-128, our preimage attack can reach up to 9 rounds. To the best of our knowledge, this is the first attack on the full Gimli permutation and our preimage attacks on reduced Gimli-Hash and Gimli-XOF-128 are the best so far. Since Gimli is included in the second round candidates in NIST's Lightweight Cryptography Standardization process, we expect that our analysis can advance the understanding of Gimli. It should be emphasized that this work can not threaten the security of the hash scheme and authenticated encryption scheme built on Gimli.

We present ZeroJoin, a practical privacy-enhancing protocol for blockchain transactions. ZeroJoin can be considered a combination of ZeroCoin and CoinJoin. It borrows ideas from both but attempts to overcome some of their drawbacks. Like ZeroCoin, our protocol uses zero-knowledge proofs and a pool of participants. However, unlike ZeroCoin, our proofs are very efficient, and our pool size is not monotonously increasing. Thus, our protocol overcomes the two major drawbacks of ZeroCoin. Our approach can also be considered a non-interactive variant of CoinJoin, where the interaction is replaced by a public transaction on the blockchain. The security of ZeroJoin is based on the Decision Diffie-Hellman (DDH) assumption. We also present ErgoMix, a practical implementation of ZeroJoin on top of Ergo, a smart contract platform based on Sigma protocols. While ZeroJoin contains the key ideas, it leaves open the practical issue of handling fees. The key contribution of ErgoMix is a novel approach to handle fee in ZeroJoin.

Successful contact tracing effectively facilitates the fight against pandemics of highly contagious diseases such as COVID-19. Existing efforts either rely on effective yet privacy-invasive surveillance infrastructure, or focus on privacy-preserving decentralised solutions which may limit their effectiveness. The former collects vast amounts of sensitive data such as identity, location and social interactions of every user, which allows function creep. The latter relies on users' willingness to share their risk scores with authorities, which limits their ability to quickly identify people at-risk and to run analytics. We propose a practical solution that aims to strike a balance between functionality and privacy: one that does not collect sensitive information, such as, location data, while at the same time allowing effective tracing and notifying the close contacts of infected users. To protect users' privacy, our solution uses local proximity tracing based on broadcasting and recording constantly changing anonymous public keys via short-range communication, for example, Bluetooth. These public keys are used to establish a shared secret key between two people in close contact. These three keys are then used to generate two unique per-user-per-contact hashes: one for infection registration and one for health status query. These hashes are never revealed to the public. To support functionality, risk score computation is performed centrally, which provides the health authorities with minimal, yet insightful and actionable data. Data minimization is achieved by the use of per-user-per-contact hashes and by enforcing role separation. In our design, the health authorities and the GPs act as proxies, while the matching between hashes is outsourced to a third-party, i.e. the matching service. This separation ensures that out-of-scope information, such as social interaction within the population, is hidden from the health authorities and, at the same time, the matching service does not learn sensitive information about the users. Our solution requires a degree of trust in the entities involved that is considerably lower w.r.t. centralised alternatives.

The down-scaling of circuit technology has led to stronger leakage currents in CMOS standard cells. This source of power consumption is data dependent and can be utilized to extract secrets from cryptographic devices. We propose Balanced Static Power Logic (BSPL), the first leakage-balancing approach that achieves optimal data-independence with respect to drain-source leakage. We re-design fundamental standard cells in such a way that their leakage current is essentially constant, irrespective of inputs and outputs, barring process variations. Even in presence of considerable intra-die variations, modeled by Monte Carlo simulations, BSPL gates still maintain a significantly reduced mutual information between the circuit’s input and conducted leakage current.

We define a set called the pAPN-spectrum of an $(n,n)$-function $F$, which measures how close $F$ is to being an APN function, and investigate how the size of the pAPN-spectrum changes when two of the outputs of a given $F$ are swapped. We completely characterize the behavior of the pAPN-spectrum under swapping outputs when $F(x) = x^{2^n-2}$ is the inverse function over $\mathbb{F}_{2^n}$. We also investigate this behavior for functions from the Gold and Welch monomial APN families, and experimentally determine the size of the pAPN-spectrum after swapping outputs for representatives from all infinite monomial APN families up to dimension $n = 10$.

Auguste Kerckhoffs' seminal article is ritually mentioned in countless cryptography articles and Ph.D. theses.

In 1998 the first author published a little-known biographic sketch of Kerckhoffs in Esperanto. In 2013 we undertook the project to develop, complete and enrich this little-known notice with new material and publish an extended account of Kerckhoffs' life. This was unfortunately interrupted by the passing away of the first author in 2015.

This article is an attempt to provide the most comprehensive biography of Auguste Kerckhoffs.

Payment Channel Networks (PCNs) enable fast, scalable, and cheap payments by moving transactions off-chain, thereby overcoming debilitating drawbacks of blockchains. However, current algorithms exhibit frequent payment failures when a payment is routed via multiple intermediaries. One of the key challenges for designing PCNs is to drastically reduce this failure rate. In this paper, we design a Bitcoin-compatible protocol that allows intermediaries to split payments on the path. Intermediaries can thus easily adapt the routing to the local conditions, which the sender is unaware of. Our protocol provides both termination and atomicity of payments, and provably guarantees that no participant loses funds even in the presence of malicious parties. An extended version of our protocol further provides unlinkability between two partial split payments belonging to the same transaction, which -- as we argue -- is important to guarantee the success of split payments. Besides formally modeling and proving the security of our construction, we conducted an in-depth simulation-based evaluation of various routing algorithms and splitting methods. Concretely, we present Interdimensional SpeedyMurmurs, a modification of the SpeedyMurmurs protocol that increases the flexibility of the route choice combined with splitting. Even in the absence of splitting, Interdimensional SpeedyMurmurs increases the success ratio of transactions drastically in comparison to a Lightning-style protocol, by up to $1/3$. Splitting further increases the probability of success, e.g., from about $84\%$ to $97\%$ in one scenario.

Current permissionless cryptocurrencies such as Bitcoin suffer from a limited transaction rate and slow confirmation time, which hinders their large scale adoption. Payment channels are one of the most promising solutions to address these problems, as they allow two end-points of the channel to perform arbitrarily many payments in a peer-to-peer fashion while uploading only two transactions on the blockchain. This concept has been generalized into payment-channel networks where a path of payment channels is used to settle the payment between two users that might not share a channel between them. However, this approach requires the active involvement of each user in the path, making the system less reliable (they might be offline), more expensive (they charge fees per payment) and slower (intermediaries need to be actively involved in the payment). To mitigate this issue, recent work has introduced the concept of virtual channels, which involve intermediaries only in the initial creation of a bridge between payer and payee, who can later on independently perform arbitrarily many off-chain transactions. Unfortunately, existing constructions are only available for Ethereum, as they rely on its account model and Turing-complete scripting language. The realization of virtual channels in other blockchain technologies with limited scripting capabilities, like Bitcoin, was considered so far an open challenge.

In this work, we present the first virtual channel protocols that are built on the UTXO-model and require a script language supporting only a digital signature scheme and a timelock functionality, being thus backwards compatible with virtually every cryptocurrency, including Bitcoin. We formalize the security properties of virtual channels as an ideal functionality in the Universal Composability framework, and prove that our protocol constitutes a secure realization thereof. We have prototyped and evaluated our protocol on the Bitcoin blockchain, demonstrating its efficiency: for $n$ sequential payments, they require an off-chain exchange of $11+2\cdot(n-1)$ transactions or a total of $4219+695\cdot(n-1)$ bytes, with no on-chain footprint in the optimistic case.

Efficient user revocation and description of the access policy are essential to enhance the practicality of attribute-based encryption (ABE) in real-life scenarios, such as cloud-assisted IoT. Nevertheless, existing ABE works fail to balance the two vital indicators. Motivated by this, in this paper, we present a revocable ciphertext-policy attribute-based encryption with arithmetic span programs (R-CPABE-ASP) for cloud-assisted IoT. For the first time, the presented R-CPABE-ASP achieves efficient user revocation and expressive description of access policy simultaneously. In R-CPABE-ASP, each attribute involved in access policy is merely used once to check whether a user owns access to shared data. Hence, the R-CPABE-ASP work enables efficient data encryption compared with existing revocable ABE works by reducing unnecessary cost for defining access policy. Meanwhile, the forward security of sensitive data is ensured by periodical update of encrypted data such that the capability of revocable storage is also assured in R-CPABE-ASP. As shown in the outsourced version of R-CPABE-ASP, The costly part for users to decrypt the data is outsourced to powerful cloud servers. There- fore, users in our R-CPABE-ASP can access their data in a more efficient way by merely one exponential operation. Finally, we carry out detailed theoretical analysis and experimental simulations to evaluate the performance of our work. The results fairly show that our proposed work is efficient and feasible in cloud-assisted IoT.

Approximate homomorphic encryption, called Cheon-Kim-Kim-Song (CKKS) scheme, is a fully homomorphic encryption scheme that supports arithmetic operations for real or complex number data encrypted. Since the bootstrapping of the CKKS scheme is a big bottleneck for practical use, this makes many cryptographers optimize its bootstrapping, but they cannot obtain its optimal solution. One of the core procedures in the bootstrapping is to approximate the modular reduction function, and several works have been done for the polynomial approximation of this function in the minimax aspect. In this paper, we obtain a fast algorithm to derive the optimal minimax generalized approximate polynomial of any continuous functions over any union of the finite number of intervals, which uses a variant of the Remez algorithm, called modified Remez algorithm. Using that results, we derive the optimal minimax approximate polynomial for the modular reduction function rather than the sine or cosine function in the CKKS scheme. From the numerical analysis, there is some gap of the approximation error by two in the logarithm scale between the cosine minimax approximation and the proposed direct minimax approximation. There is some inherent flat error region for the cosine minimax approximation such that the minimax approximation error does not decrease as the degree of the approximation polynomial increases, but the approximation error for the proposed one is improved as the degree of approximation polynomial increases. Further, we propose a composite function approximation using inverse sine function to obtain approximation error smaller than the fundamental flat error with a small number of the non-scalar multiplications. For the direct approximation, we reduce the number of non-scalar multiplications by 30% by using odd function property of the minimax approximate polynomial of modular reduction function. From the numerical analysis, it is known that the composite function approximation is desirable when the running time of bootstrapping is important, and the direct approximation with odd function optimization is desirable when the depth is important.

BIG is a 128-bit block cipher proposed by Demeri et al. in 2019. The number of rounds is 18 for high security. The designer evaluated its security against linear cryptanalysis. On the other hand, it has not been reported the security of BIG against higher order differential attack, which is one of the algebraic attacks. In this paper, we focused on a higher order differential of BIG. We found a new 15-round saturation characteristc of BIG using 1-st order differential by computer experiment. Exploiting this characteristic, we show that full-round BIG can be attacked with 6 chosen plaintexts and 2^(2.7) encryption operations.

The theoretical idea of using FHE to realize MPC has been therefor over a decade. Existing threshold (and multi-key) FHE schemes were constructed by modifying and analyzing a traditional single-keyFHE in a case-by-case manner, thus technically highly-demanding.This work explores a new approach to build threshold FHE (therebyMPC schemes) through tailoring generic MPC protocols to the base FHE scheme while requiring no effort in FHE redesign. We applied our approach to two representative Ring-LWE-based FHE schemes: CKKS and GHS, producing GMPFHE-CKKS and GMPFHE-GHS. We developed MPC protocols based on GMPFHE-CKKS and GMPFHE-GHS which are secure against any number of passive but colluding adversaries. The online cost of our MPC protocol is O(|C|), as opposed to O(|C|·n^2) for existing MPC protocols, and our offline cost is independent of |C|. We experimentally show that the GMPFHE-CKKS-based MPC protocol offers unparalleled amortized performance on multi-party neural network evaluation.

We report an important implementation vulnerability exploitable through physical attacks for message recovery in five lattice-based public-key encryption schemes (PKE) and Key Encapsulation Mechanisms (KEM) - NewHope, Kyber, Saber, Round5 and LAC that are currently competing in the second round of NIST's standardization process for post-quantum cryptography. The reported vulnerability exists in the message decoding function which is a fundamental kernel present in lattice-based PKE/KEMs and further analysis of the implementations in the public pqm4 library revealed that the message decoding function is implemented in a similar manner in all the identified schemes and thus they all share the common side-channel vulnerability that leaks individual bits of the secret message. We demonstrate that the identified vulnerability can be exploited through a number of practical electromagnetic side-channel attacks, fault attacks and combined attacks on implementations from the pqm4 library running on the ARM Cortex-M4 microcontroller. As a key contribution, we also demonstrate the first practical EM-based combined side-channel and fault attack on lattice-based PKE/KEMs.

In a blockchain system, address is an essential primitive which is used in transaction. The $\textit{Stealth Address}$, which has an underlying address info of two public keys ($A,B$ ), was developed by Monero blockchain in 2013, in which a one-time public key is used as the transaction destination, to protect the recipient privacy. At almost same time, $\textit{hierarchical deterministic wallets}$ scheme was proposed as $\textit{bip-32}$ for Bitcoin, which makes it possible to share an $\textit{extended public key}$ ($K,c$) between sender and receiver, where $K$ is a public key and $c$ is a 256-bits chain code, and only receiver knows the corresponding private key of this $K$. With the $\textit{bip-32}$ scheme, the sender may derive the child public key $K_i$ with the child number $i$ by him/herself, without needing to request a new address for each payment from the receiver, make each transaction have a different destination key for privacy. This paper introduces an improved stealth address scheme which has an underlying address data of $(A_i,B_i,i)$, where $i$ is a child number and $i\in [0,2^{31}-1]$. The sender gets the receiver’s address info $(A_i,B_i,i)$, generates a random secret number $r\in [0,2^{64}-1]$ and calculate a Pedersen commitment \(C=A_iB_ih^{R^{'}.x}\) where \(R^{'}=B_i^r\), then the sender may use this commitment $C$ or \(Hash(C)\) as the destination key for the output and packs the \((R,i)\) somewhere into the transaction. This improved stealth address scheme makes it possible to manage multiple stealth addresses in one wallet, therefore the user is able to share different addresses for different senders.

The bit-based division property (BDP) is the most effective technique for finding integral characteristics of symmetric ciphers. Recently, automatic search tools have become one of the most popular approaches to evaluating the security of designs against many attacks. Constraint-aided automatic tools for the BDP have been applied to many ciphers with simple linear layers like bit-permutation. Constructing models of complex linear layers accurately and efficiently remains hard. A straightforward method proposed by Sun \etal (called the \s method), decomposes a complex linear layer into basic operations like \texttt{COPY} and \texttt{XOR}, then models them one by one. However, this method can easily insert invalid division trails into the solution pool, which results in a quicker loss of the balanced property than the cipher itself would. In order to solve this problem, Zhang and Rijmen propose the \zr method to link every valid trail with an invertible sub-matrix of the matrix corresponding to the linear layer, and then generate linear inequalities to represent all the invertible sub-matrices. Unfortunately, the \zr method is only applicable to invertible binary matrices (defined in Definition 3).

To avoid generating a huge number of inequalities for all the sub-matrices, we build a new model that only includes that the sub-matrix corresponding to a valid trail should be invertible. The computing scale of our model can be tackled by most of SMT/SAT solvers, which makes our method practical. For applications, we improve the previous BDP for LED and MISTY1. We also give the 7-round BDP results for Camellia with $FL/FL^{-1}$, which is the longest to date.

Furthermore, we remove the restriction of the \zr method that the matrix has to be invertible, which provides more choices for future designs. Thanks to this, we also reproduce 5-round key-dependent integral distinguishers proposed at Crypto 2016 which cannot be obtained by either the \s or \zr methods.

The MixColumns operation is an important component providing diffusion for the AES. The branch number of it ensures that any continuous four rounds of the AES have at least 25 active S-Boxes, which makes the AES secure against the differential and linear cryptanalysis. However, the choices of the coefficients of the MixColumns matrix may undermine the AES security against some novel-type attacks. A particular property of the AES MixColumns matrix coefficient has been noticed in recent papers that \emph{each row or column of the matrix has elements that sum to zero}. Several attacks have been developed taking advantage of the coefficient property.

In this paper we investigate further the influence of the specific coefficient property on the AES security. Our target, which is also one of the targets of the previous works, is a 5-round AES variant with a secret S-Box. We will show how we take advantage of the coefficient property to extract the secret key directly without any assistance of the S-Box information. Compared with the previous similar attacks, the present attacks here are the best in terms of the complexity under the chosen-plaintext scenario.

We construct the most efficient two-round adaptively secure bit-OT in the Common Random String (CRS) model. The scheme is UC secure under the Decisional Diffie-Hellman (DDH) assumption. It incurs O(1) exponentiations and sends O(1) group elements, whereas the state of the art requires O(k^2) exponentiations and communicates poly(k) bits, where k is the computational security parameter. Along the way, we obtain several other efficient UC-secure OT protocols under DDH :

- The most efficient yet two-round adaptive string-OT protocol assuming programmable random oracle. Furthermore, the protocol can be made non-interactive in the simultaneous message setting, assuming random inputs for the sender.

- The first two-round string-OT with amortized constant exponentiations and communication overhead which is secure in the observable random oracle model.

- The first two-round receiver equivocal string-OT in the CRS model that incurs constant computation and communication overhead.

We also obtain the first non-interactive adaptive string UC-commitment in the CRS model which incurs a sublinear communication overhead in the security parameter. Specifically, we commit to polylog(k) bits while communicating O(k) bits. Moreover, it is additively homomorphic in nature.

We can also extend our results to the single CRS model where multiple sessions share the same CRS. As a corollary, we obtain a two-round adaptively secure MPC protocol in this model.