International Association
for Cryptologic Research

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.

MPC-in-the-head based protocols have recently gained much popularity and are at the brink of seeing widespread usage. With widespread use come the spectres of implementation issues and implementation attacks. Side-channel attacks are a serious threat to the security of implementations of secure cryptographic protocols due to unintended leakage of sensitive information. We show that implementations of protocols constructed by the MPC-in-the-head paradigm are vulnerable to such attacks. As a case study, we choose the ZKBoo-protocol of Giacomelli, Madsen, and Orlandi (USENIX 2016) and show that even a single leaked value is sufficient to break the security of the protocol. To show that this attack is not just a theoretical vulnerability, we apply differential power analysis to show the vulnerabilities of the device.

In order to remedy this situation, we extend and generalize the ZKBoo-protocol by making use of the notion of strong non-interference of Barthe et al. (CCS 2016). To apply this notion to ZKBoo, we construct novel versions of strongly non-interfering gadgets that balance the randomness across the different branches evenly. Finally, we show that each circuit can be decomposed into branches using only these balanced strongly non-interfering gadgets. This allows us to construct a version of ZKBoo, called $(n+1)$-ZKBoo secure against side-channel attacks with very limited overhead in both signature-size and running time. Furthermore, $(n+1)$-ZKBoo is scalable to the desired security against adversarial probes. We experimentally confirm that the attacks successful against ZKBoo no longer work on $(n+1)$-ZKBoo.

Smart contracts present a uniform approach for deploying distributed computation and have become a popular means to develop security critical applications. A major barrier to adoption for many applications is the public nature of existing systems, such as Ethereum. Several systems satisfying various definitions of privacy and requiring various trust assumptions have been proposed; however, none achieved the universality and uniformity that Ethereum achieved for non-private contracts: One unified method to construct most contracts. We provide a unified security model for private smart contracts which is based on the Universal Composition (UC) model and propose a novel core protocol, Kachina, for deploying privacy-preserving smart contracts, which encompasses previous systems. We demonstrate the Kachina method of smart contract development, using it to construct a contract that implements privacy-preserving payments, along the lines of Zerocash, which is provably secure in the UC setting and facilitates concurrency.

This paper proposes tweakable block cipher (TBC) based modes $\mathsf{PFB\_Plus}$ and $\mathsf{PFB}\omega$ that are efficient in threshold implementations (TI). Let $t$ be an algebraic degree of a target function, e.g.~$t=1$ (resp.~$t>1$) for linear (resp.~non-linear) function. The $d$-th order TI encodes the internal state into $d t + 1$ shares. Hence, the area size increases proportionally to the number of shares. This implies that TBC based modes can be smaller than block cipher (BC) based modes in TI because TBC requires $s$-bit block to ensure $s$-bit security, e.g. \textsf{PFB} and \textsf{Romulus}, while BC requires $2s$-bit block. However, even with those TBC based modes, the minimum we can reach is 3 shares of $s$-bit state with $t=2$ and the first-order TI ($d=1$).

Our first design $\mathsf{PFB\_Plus}$ aims to break the barrier of the $3s$-bit state in TI. The block size of an underlying TBC is $s/2$ bits and the output of TBC is linearly expanded to $s$ bits. This expanded state requires only 2 shares in the first-order TI, which makes the total state size $2.5s$ bits. We also provide rigorous security proof of $\mathsf{PFB\_Plus}$. Our second design $\mathsf{PFB}\omega$ further increases a parameter $\omega$: a ratio of the security level $s$ to the block size of an underlying TBC. We prove security of $\mathsf{PFB}\omega$ for any $\omega$ under some assumptions for an underlying TBC and for parameters used to update a state. Next, we show a concrete instantiation of $\mathsf{PFB\_Plus}$ for 128-bit security. It requires a TBC with 64-bit block, 128-bit key and 128-bit tweak, while no existing TBC can support it. We design a new TBC by extending \textsf{SKINNY} and provide basic security evaluation. Finally, we give hardware benchmarks of $\mathsf{PFB\_Plus}$ in the first-order TI to show that TI of $\mathsf{PFB\_Plus}$ is smaller than that of \textsf{PFB} by more than one thousand gates and is the smallest within the schemes having 128-bit security.

Event date: 19 November to 20 November 2020
Submission deadline: 20 September 2020
Notification: 25 October 2020

Event date: 18 November to 19 November 2020
Submission deadline: 14 June 2020
Notification: 26 July 2020

Event date: to
Submission deadline: 1 June 2021

Event date: 13 December to 16 December 2020
Submission deadline: 31 August 2020
Notification: 19 October 2020

The CHES 2020 Capture the Flag (CTF) is a side-channel cryptanalysis challenge against masked implementations of the Clyde-128 Tweakable Block Cipher (TBC) which is part of the Spook candidate to the NIST lightweight cryptography competition (https://www.spook.dev/).

Different targets are proposed in parallel, both in software and in hardware, corresponding to masked implementations with various number of shares. Challengers are provided with the source code of the implementations (C in software and Verilog in hardware/FPGA), a tool to predict intermediate values of the hardware implementation, profiling sets of traces including the nonces, (random) keys, (random) plaintexts and the randomness used for masking, test sets of traces corresponding to a few fixed keys (without the masking randomness), and finally prototype attacks against a single byte of the secret key for exemplary targets.

The goal of the challenge is to modify and improve the prototype attacks. The submitted attacks will be rated based on the number of measurements needed to reduce the rank of the master key below 2^32 using a rank estimation algorithm. All the attacks submitted will be made public to all challengers (under a GPLv3 license or alternatives).

Link to the challenge website: https://ctf.spook.dev/

High-assurance cryptography for IoT applications.

The RIOT-FP project is looking for a postdoctoral research to work with Inria's GRACE team (on the campus of École poytechnique in the southern suburbs of Paris) and the PROSECCO team (in central Paris). The project aims to develop high-speed, high-security, low-memory cryptographic primitives (especially post-quantum public-key algorithms), backed by proven implementations with safety guarantees for software execution on low-end IoT devices. The real-world objective is to provide some future-proofing for RIOT OS (https:/riot-os.org), a free and open-source operating system for low-end IoT devices.

Candidates are expected to have a strong background in cryptographic algorithms, IoT software security, or formally verified software. They must have, or expect to hold, a PhD in a field related to the project; they must also have strong programming experience and mathematical skills. They should have an international research profile, and be fluent in written and spoken English.

Closing date for applications:

Contact: Benjamin Smith, at inria dot fr

Cryptology forms the backbone of modern digital security. While in theory it is known how to make secure cryptosystems that are asymptotically secure, a considerable gap with practice is demonstrated time and again by breaks of practical, implemented cryptosystems, deployed as part of a larger security ecosystem. The project “concrete cryptology” aims to provide concrete and meaningful security guarantees from low-level implementation to high-level deployment.

The postdoc will have considerable freedom in selecting specific problems to work on within the larger scope of the project. One focus is the effect that side-channel attacks that do not result in full key recovery have on security, including provable security, higher up the chain. Another focus is the effect that large-scale deployment deviating from some abstract ideal has.

Simula UiB Offers

- Excellent opportunities for performing high-quality research, as part of a highly competent and motivated team of international researchers and engineers.

- An informal and inclusive international working environment

- Generous support for travel and opportunities to build international networks, through established collaboration with industry, exchange programs and research visits with other universities, and funding to attend conferences

- Modern office facilities located in downtown Bergen

- A competitive salary. Starting salary from NOK 532.300

- Numerous benefits: access to company cabin, BabyBonus arrangements, sponsored social events, generous equipment budgets (e.g., computer, phone and subscription), comprehensive travel/health insurance policy, etc

- Relocation assistance: accommodation, visas, complimentary Norwegian language courses, etc

- Administrative research support: e.g., quality assurance process for grant proposals (including RCN and EU programs)

- Wellness and work-life balance. Our employees’ health and well-being is a priority and we encourage them to make use of our flexible work arrangements to help balance their work and home lives efficiently

Closing date for applications:

Contact: Martijn Stam

More information: https://www.simula.no/about/job/call-post-doctoral-fellow-concrete-cryptography