International Association
for Cryptologic Research

We propose a new construction for format-preserving encryption. Our design provides the flexibility for use in format-preserving encryption (FPE) and for static table-driven tokenization. Our algorithm is a substitution-permutation network based on random Sboxes. Using pseudorandom generators and pseudorandom functions, we prove a strong adaptive security based on the super-pseudorandom permutation assumption of our core design. We obtain empirical parameters to reach this assumption. We suggest parameters for quantum security.

Our design accommodates very small domains, with a radix $a$ from 4 to the Unicode alphabet size and a block length $\ell$ starting 2. The number of Sbox evaluations per encryption is asymptotically $\ell^{\frac32}$, which is also the number of bytes we need to generate using AES in CTR mode for each tweak setup. For instance, we tokenize 10 decimal digits using 29 (parallel) AES computations to be done only once, when the tweak changes.

Affine message authentication code (AMAC) (CRYPTO'14) is a group-based MAC with a specific algebraic structure. Downgradable AMAC (DAMAC) (CT-RSA'19) is an AMAC with a functionality that we can downgrade a message with an authentication tag while retaining validity of the tag. In this paper, we revisit DAMAC for two independent applications, namely downgradable identity-based signatures (DIBS) and trapdoor sanitizable signatures (TSS) (ACNS'08). DIBS are the digital signature analogue of downgradable identity-based encryption (CT-RSA'19), which allow us to downgrade an identity associated with a secret-key. In TSS, an entity given a trapdoor for a signed-message can partially modify the message while keeping validity of the signature. We show that DIBS can be generically constructed from DAMAC, and DIBS can be transformed into (wildcarded) hierarchical/wicked IBS. We also show that TSS can be generically constructed from DIBS. By instantiating them, we obtain the first wildcarded hierarchical/wicked IBS and the first invisible and/or unlinkable TSS. Moreover, we prove that DIBS are equivalent to not only TSS, but also their naive combination, named downgradable identity-based trapdoor sanitizable signatures.

It is known that the Byzantine consensus problem among $n$ processes cannot be solved in a non-synchronous system if the number of faulty processes exceeds $t_0$, where $t_0 = n/3$. Indeed, if the number of faulty processes is greater than the $t_0$ threshold, correct processes might never decide or (even worse) correct processes might decide and disagree. We focus in this paper on the latter case, where disagreement occurs. Specifically, we investigate the accountable Byzantine consensus problem in non-synchronous systems: the problem of solving Byzantine consensus whenever possible (i.e., whenever the number of faulty processes does not exceed the $t_0$ bound) and otherwise allowing correct processes to obtain a proof of culpability of (at least) $t_0 + 1$ faulty processes whenever correct processes disagree. We present three complementary contributions: (i) We give a simple transformation named $AB$ that enables any Byzantine consensus protocol to obtain accountability. Besides being simple, $ABC$ is also efficient: it induces an overhead of (1) two all-to-all communication rounds and $O(n^2)$ exchanged bits of information in all executions with up to $t_0$ faults, and (2) three all-to-all communication rounds and $O(n^3)$ exchanged bits of information otherwise. Therefore, any protocol that solves the Byzantine consensus problem with quadratic (or greater) communication complexity retains its complexity in solving the problem after our transformation. (ii) We show that $ABC$, despite its simplicity, allows for optimal communication complexity in solving the accountable Byzantine consensus problem. That is, (1) we prove that any accountable Byzantine consensus incurs cubic communication complexity whenever disagreement occurs, and (2) we demonstrate that the lower bound is tight by applying $ABC$ to any cubic Byzantine consensus protocol (e.g., binary DBFT). (iii) We show that $ABC$ is not limited to the Byzantine consensus problem. Specifically, we define a class of easily accountable agreement tasks and we prove that generalized $ABC$ transformation indeed provides accountability for such tasks. Important distributed tasks, like Byzantine reliable and Byzantine consistent broadcast, fall into this class.

In this paper, we propose a new block cipher-based authenticated encryption scheme, dubbed the Synthetic Counter with Masking~(SCM) mode. SCM follows the NSIV paradigm proposed by Peyrin and Seurin~(CRYPTO 2016), where a keyed hash function accepts a nonce N with associated data and a message, yielding an authentication tag T, and then the message is encrypted by a counter-like mode using both T and N. Here we move one step further by encrypting nonces; in the encryption part, the inputs to the block cipher are determined by T, counters, and an encrypted nonce, and all its outputs are also masked by an (additional) encrypted nonce, yielding keystream blocks.

As a result, we obtain, for the first time, a block cipher-based authenticated encryption scheme of rate 1/2 that provides n-bit security with respect to the query complexity (ignoring the influence of message length) in the nonce-respecting setting, and at the same time guarantees graceful security degradation in the faulty nonce model, when the underlying n-bit block cipher is modeled as a secure pseudorandom permutation. Seen as a slight variant of GCM-SIV, SCM is also parallelizable and inverse-free, and its performance is still comparable to GCM-SIV.

We present a variant of the Kate, Zaverucha and Goldberg polynomial commitment scheme [KZG] where $d$ polynomials can be opened at a point that is a $d$'th power, such that the amount of verifier group operations does not depend on $d$. Our method works by reducing opening multiple polynomials at a single point $x$, to opening a single polynomial at many points via an ``FFT-like identity''.

As an application we present a version of the PlonK zk-SNARK[GWC] with significantly improved verifier performance, at the cost roughly tripling the prover time. Specifically, in addition to the two pairings, the verifier only performs six scalar muliptlications, rather than 16 or 18 as in the versions presented in [GWC].

LightMAC, by Luykx et al., is a block cipher based message authentication code (MAC). The simplicity of design and low overhead allows it to have very compact implementations. As a result, it has been recently chosen as an ISO/IEC standard MAC for lightweight applications. LightMAC has been shown to achieve query-length independent security bound of $O(q^2/2^n)$ when instantiated with two independently keyed $n$-bit block ciphers, where $q$ denotes the number of MAC queries and the query-length is upper bounded by $(n-s)2^s$ bits for a fixed counter size $s$. In this paper, we aim to minimize the number of block cipher keys in LightMAC. First, we show that the original LightMAC instantiated with a single block cipher key, referred as 1k-LightMAC, achieves security bound of $O(q^2/2^n)$ while the query-length is less than $(n-s)\min\{2^{n/4},2^s\}$ bits. Second, we show that a minor variant of 1k-LightMAC, dubbed as LightMAC-ds, achieves security bound of $O(q^2/2^n)$ while query-length is upper bounded by $(n-s)2^{s-1}$ bits. Of independent interest, our security proof of 1k-LightMAC employs a novel sampling approach, called the reset-sampling, as a subroutine within the H-coefficient proof setup.

This work leverages on the framework of Karakostas et al. (SCN'20) by extending it to the realm of reputation and trust. At the best of our knowledge, it is the first to introduce reputation and trust to proof of stake systems. Namely, we show that their delegation framework can be repurposed to construct a trust layer over a proof of stake consensus protocol in addition to its original stake delegation application. Furthermore, we show that such extension yields a concrete reputation system satisfying the positive results of (1) Asharov et al. (Asiacrypt'13), therefore allowing the secure execution of multiparty protocols such as GMW (STOC' 87) and Damgard and Ishai (Crypto'05), and (2) Kleinrock et al. (Indocrypt'20), therefore allowing the construction of Reputation-fair Lottery and therefore Proof of Reputation. More concretely, our devised layer is used to construct a concrete reputation system based on arbitrary stake distribution. In this layer groups of users can freely ``assign their respective trust'' to members of a set of trustees, i.e., participants that offered themselves as receivers of such assignment. Furthermore, our work offers the advantage of providing a clear stake based criteria, verifiable in the ledger, and, therefore, naturally resistant to sybil attack, that the set of trustees indeed yields an honest majority. This setting provides a better situation than a simple assumption of honest majority, since it involves stake in a decentralized ledger, and the public verifiability of the reputation score via verification of the stake distribution.

Lightweight cryptography has recently gained importance as the number of Internet of things (IoT) devices connected to Internet grows. Its main goal is to provide cryptographic algorithms that can be run efficiently in resource-limited environments such as IoT. To meet the challenge, the National Institute of Standards and Technology (NIST) announced the Lightweight Cryptography (LWC) project. One of the finalists of the project is the TinyJAMBU cipher.

This work evaluates the security of the cipher. The tool used for the evaluation is the cube attack. We present five cube attacks DA1 - DA5. The first two attacks (DA1 and DA2) are launched against the initialisation phase of the cipher. The best result achieved for the attacks is a distinguisher for a 18-bit cube, where the cipher variant consists of the full initialisation phase together with 437 rounds of the encryption phase. The attacks DA3 - DA5 present a collection of distinguishers up to 437 encryption rounds, whose 32-bit cubes are chosen from the plaintext, nonce, or associated data bits. The results are confirmed experimentally. A conclusion from the work is that TinyJAMBU has a better security margin against cube attacks than claimed by the designers.

In this work we consider information-theoretically secure MPC against a mixed adversary who can corrupt $t_p$ parties passively, $t_a$ parties actively, and can make $t_f$ parties fail-stop. With perfect security, it is known that every function can be computed securely if and only if $3t_a + 2t_p + t_f < n$, and for statistical security the bound is $2t_a + 2t_p + t_f < n$.

These results say that for each given set of parameters $(t_a, t_p, t_f)$ respecting the inequality, there exists a protocol secure against this particular choice of corruption thresholds. In this work we consider a dynamic adversary. Here, the goal is a single protocol that is secure, no matter which set of corruption thresholds $(t_a, t_p, t_f)$ from a certain class is chosen by the adversary. A dynamic adversary can choose a corruption strategy after seeing the protocol and so is much stronger than a standard adversary.

Dynamically secure protocols have been considered before for computational security. Also the information theoretic case has been studied, but only considering non-threshold general adversaries, leading to inefficient protocols.

We consider threshold dynamic adversaries and information theoretic security. For statistical security we show that efficient dynamic secure function evaluation (SFE) is possible if and only if $2t_a + 2t_p + t_f < n$, but any dynamically secure protocol must use $\Omega(n)$ rounds, even if only fairness is required. Further, general reactive MPC is possible if we assume in addition that $2t_a+2t_f \leq n$, but fair reactive MPC only requires $2t_a + 2t_p + t_f < n$.

For perfect security we show that both dynamic SFE and verifiable secret sharing (VSS) are impossible if we only assume $3t_a + 2t_p + t_f < n$ and remain impossible even if we also assume $t_f=0$. On the other hand, perfect dynamic SFE with guaranteed output delivery (G.O.D.) is possible when either $t_p = 0$ or $t_a = 0$ i.e. if instead we assume $3t_a+t_f < n$ or $2t_p +t_f < n$. Further, perfect dynamic VSS with G.O.D. is possible under the additional conditions $3t_a + 3/2t_f \leq n$ or $2t_p + 2t_f \leq n$. These conditions are also sufficient for dynamic perfect reactive MPC.

Pairing computations on elliptic curves with odd prime degrees are rarely studied as low efficiency. Recently, Clarisse, Duquesne and Sanders proposed two new curves with odd prime embedding degrees: \textit{BW13-P310} and \textit{BW19-P286}, which are suitable for some special cryptographic schemes. In this paper, we propose efficient methods to compute the optimal ate pairing on this types of curves, instantiated by the \textit{BW13-P310} curve. We first extend the technique of lazy reduction into the finite field arithmetic. Then, we present a new method to execute Miller's algorithm. Compared with the standard Miller iteration formulas, the new ones provide a more efficient software implementation of pairing computations. At last, we also give a fast formula to perform the final exponentiation. Our implementation results indicate that it can be computed efficiently, while it is slower than that over the BLS-446 curve at the same security level.

Integers can be decomposed in multiple ways. The choice of a recoding technique is generally dictated by performance considerations. The usual metric for optimizing the decomposition is the Hamming weight. In this work, we consider a different metric and propose new modified forms (i.e., integer representations using signed digits) that satisfy minimality requirements under the new metric. Specifically, we introduce what we call balanced non-adjacent forms and prove that they feature a minimal Euclidean weight. We also present efficient algorithms to produce these new minimal forms. We analyze their asymptotic and exact distributions. We extend the definition to modular integers and show similar optimality results. The balanced non-adjacent forms find natural applications in fully homomorphic encryption as they optimally reduce the noise variance in LWE-type ciphertexts.

Let N = pq be an RSA modulus with balanced prime factors. In 2018, Murru and Saettone presented a variant of the RSA cryptosystem based on a cubic Pell equation in which the public key (N, e) and the private key (N, d) satisfy ed \equiv 1 mod (p^2+p+1)(q^2+q+1)). They claimed that the classical small private attacks on RSA such as Wiener's continued fraction attack do not apply to their scheme. In this paper, we show that, on the contrary, Wiener's method as well as the small inverse problem technique of Boneh and Durfee can be applied to attack their scheme. More precisely, we show that the proposed variant of RSA can be broken if d < N^{0:5694}. This shows that their scheme is in reality more vulnerable than RSA, where the bound of vulnerability is d < N^{0.292}.

We describe a protocol for two-party private set intersection (PSI) based on Diffie-Hellman key agreement. The protocol is proven secure against malicious parties, in the ideal permutation + random oracle model.

For small sets (500 items or fewer), our protocol requires the least time and communication of any known PSI protocol, even ones that are only semi-honest secure and ones that are not based on Diffie-Hellman. It is one of the few significant improvements to the 20-year old classical Diffie-Hellman PSI protocol of Huberman, Franklin, and Hogg (ACM Elec. Commerce 1999).

Our protocol is actually a generic transformation that constructs PSI from a class of key agreement protocols. This transformation is inspired by a technique of Cho, Dachman-Soled, and Jarecki (CT-RSA 2016), which we streamline and optimize in several important ways to achieve our superior efficiency.

Key trees are often the best solution in terms of transmission cost and storage requirements for managing keys in a setting where a group needs to share a secret key, while being able to efficiently rotate the key material of users (in order to recover from a potential compromise, or to add or remove users). Applications include multicast encryption protocols like LKH (Logical Key Hierarchies) or group messaging like the current IETF proposal TreeKEM.

A key tree is a (typically balanced) binary tree, where each node is identified with a key: leaf nodes hold users' secret keys while the root is the shared group key. For a group of size $N$, each user just holds $\log(N)$ keys (the keys on the path from its leaf to the root) and its entire key material can be rotated by broadcasting $2\log(N)$ ciphertexts (encrypting each fresh key on the path under the keys of its parents).

In this work we consider the natural setting where we have many groups with partially overlapping sets of users, and ask if we can find solutions where the cost of rotating a key is better than in the trivial one where we have a separate key tree for each group.

We show that in an asymptotic setting (where the number $m$ of groups is fixed while the number $N$ of users grows) there exist more general key graphs whose cost converges to the cost of a single group, thus saving a factor linear in the number of groups over the trivial solution.

As our asymptotic ``solution" converges very slowly and performs poorly on concrete examples, we propose an algorithm that uses a natural heuristic to compute a key graph for any given group structure. Our algorithm combines two greedy algorithms, and is thus very efficient: it first converts the group structure into a ``lattice graph", which is then turned into a key graph by repeatedly applying the algorithm for constructing a Huffman code.

To better understand how far our proposal is from an optimal solution, we prove lower bounds on the update cost of continuous group-key agreement and multicast encryption in a symbolic model admitting (asymmetric) encryption, pseudorandom generators, and secret sharing as building blocks.

Nearest neighbor search is a fundamental building-block for a wide range of applications. A privacy-preserving protocol for nearest neighbor search involves a set of clients who send queries to a remote database. Each client retrieves the nearest neighbor(s) to its query in the database without revealing any information about the query. For database privacy, the client must not learn anything beyond the query answer.

Existing protocols for private nearest neighbor search re- quire heavy cryptographic tools, resulting in poor practical performance or large client overheads. In this paper, we present the first lightweight protocol for private nearest neighbor search. Our protocol is instantiated using two non-colluding servers, each holding a replica of the database. The protocol supports an arbitrary number of clients simultaneously querying the database via these servers. Each query is only a single round of communication for the client and does not require any communication between servers.

If at least one of the servers is non-colluding, we ensure that (1) no information is revealed on the client’s query, (2) the total communication between the client and the servers is sublinear in the database size, and (3) each query answer only leaks a small and precisely quantified amount of information about the database to the client, even when the client is acting maliciously.

We implement our protocol and report its performance on real-world data. Our construction requires between 10 and 30 seconds of query latency over large databases of 10M feature vectors. Client overhead remained under 10&#956;s of processing time per query and typically less than 4 MB of communication, depending on parameters.

Evolving secret sharing is a special kind of secret sharing where the number of shareholders is not known beforehand, i.e., at time t = 0. In classical secret sharing such a restriction was assumed inherently i.e., the the number of shareholders was given to the dealer’s algorithm as an input. Evolving secret sharing relaxes this condition. Pramanik and Adhikari left an open problem regarding malicious shareholders in the evolving setup, which we answer in this paper. We introduce a new cheating model, called the almost semi-honest model, where a shareholder who joins later can check the authenticity of share of previous ones. We use collision resistant hash function to construct such a secret sharing scheme with malicious node identification. Moreover, our scheme preserves the share size of Komargodski et al. (TCC 2016).

Secure computing methods such as fully homomorphic encryption and hardware solutions such as Intel Software Guard Extension (SGX) have been applied to provide security for user input in privacy-oriented computation outsourcing. Fully homomorphic encryption is amenable to parallelization and hardware acceleration to improve its scalability and latency, but is limited in the complexity of functions it can efficiently evaluate. SGX is capable of arbitrarily complex calculations, but due to expensive memory paging and context switches, computations in SGX are bound by practical limits. These limitations make either of fully homomorphic encryption or SGX alone unsuitable for large-scale multi-user computations with complex intermediate calculations. In this paper, we present GPS, a novel framework integrating the Graphene, PALISADE, and SGX technologies. GPS combines the scalability of homomorphic encryption with the arbitrary computational abilities of SGX, forming a more functional and efficient system for outsourced secure computations with large numbers of users. We implement GPS using linear regression training as an instantiation, and our experimental results indicate a base speedup of 1.03x to 8.69x (depending on computation parameters) over an SGX-only linear regression training without multithreading or hardware acceleration. Experiments and projections show improvements over the SGX-only training of 3.28x to 10.43x using multithreading and 4.99x to 12.67 with GPU acceleration.

A multi-forkcipher (MFC) is a generalization of the forkcipher (FC) primitive introduced by Andreeva et al. at ASIACRYPT'19. An MFC is a tweakable cipher that computes $s$ output blocks for a single input block, with $s$ arbitrary but fixed. We define the MFC security in the ind-prtmfp notion as indistinguishability from $s$ tweaked permutations. Generalizing tweakable block ciphers (TBCs, $s = 1$), as well as forkciphers ($s=2$), MFC lends itself well to building simple-to-analyze modes of operation that support any number of cipher output blocks.

Our main contribution is the generic CTR encryption mode GCTR that makes parallel calls to an MFC to encrypt a message $M$. We analyze the set of all 36 ``simple and natural'' GCTR variants under the nivE security notion by Peyrin and Seurin from CRYPTO'16. Our proof method makes use of an intermediate abstraction called tweakable CTR (TCTR) that captures the core security properties of GCTR common to all variants, making their analyses easier. Our results show that many of the schemes achieve from well beyond birthday bound (BBB) to full $n$-bit security under nonce respecting adversaries and some even BBB and close to full $n$-bit security in the face of realistic nonce misuse conditions.

We finally present an efficiency comparison of GCTR using $\mathsf{ForkSkinny}$ (an MFC with $s=2$) with the traditional CTR and the more recent CTRT modes, both are instantiated with the $\mathsf{SKINNY}$ TBC. Our estimations show that any GCTR variant with $\mathsf{ForkSkinny}$ can achieve an efficiency advantage of over $20\%$ for moderately long messages, illustrating that the use of an efficient MFC with $s\geq 2$ brings a clear speed-up.

Secure Multi-party Computation (MPC) allows to securely compute on private data. To make MPC practical, logic synthesis can be used to automatically translate a description of the function to be computed securely into optimized and error-free boolean circuits. TinyGMW (Demmler et al., CCS'15) used industry-grade hardware synthesis tools (DC, Yosys) to generate depth-optimized circuits for MPC. To evaluate their optimized circuits, they used the ABY framework (Demmler et al., NDSS'15) for secure two-party computation. The recent ABY2.0 framework (Patra et al., USENIX Security'21) presented round-efficient constructions using multi-input AND gates and improved over ABY by at least 6x in online communication for 4-input AND gate evaluation.

In this work, we propose SynCirc, an efficient hardware synthesis framework designed for MPC applications. Our framework is based on Verilog and the open-source tool Yosys-ABC. It provides custom libraries and new constraints that accommodate multi-input AND gates. With this, we improve over TinyGMW by up to 3x in multiplicative depth with a corresponding improvement in online round complexity. Moreover, we provide efficient realizations of several new building blocks including comparison, multiplexers, and equality check. For these building blocks, we achieve improvements in multiplicative depth/online rounds between 22.3% and 66.7%. With these improvements, our framework makes multi-round MPC better-suited for high-latency networks such as the Internet. With respect to the look-up table based approach of Dessouky et al (NDSS’17), our framework improves the online communication by 1.3x - 18x.

In this short note, we introduce Bandersnatch, a new elliptic curve built over the BLS12-381 scalar field. The curve is equipped with an efficient endomorphism, allowing a fast scalar multiplication algorithm. Our benchmark shows that the multiplication is 42% faster, compared to another curve, called Jubjub, having similar properties. Nonetheless, Bandersnatch does not provide any performance improvement for either rank 1 constraint systems (R1CS) or multi scalar multiplications, compared to the Jubjub curve.