International Association
for Cryptologic Research

In this paper, we propose a formal security model and a construction methodology of interactive aggregate message authentication with detecting functionality (IAMD). The IAMD is an interactive aggregate MAC protocol which can identify invalid messages with a small amount of tag-size. Several aggregate MAC schemes that can specify invalid messages has been proposed so far by using non-adaptive group testing in the prior work. In this paper, we utilize adaptive group testing to construct IAMD scheme, and we show that the resulting IAMD scheme can identify invalid messages with a small amount of tag-size compared to the previous schemes.

NIST is currently conducting the 3rd round of a survey to find post-quantum class asymmetric protocols (PQC) [1]. We participated in a joint-team with a fellow researcher of the Interamerican Open University (UAI) with a Key-Exchange Protocol (KEP) called HK17 [2]. The proposal was flawed because Bernstein [3] found a weakness, which was later refined by Li [4] using a quadratic reduction of octonions and quaternions, albeit no objection about the published non-commutative protocol and the one-way trapdoor function (OWTF). This fact promoted the search for a suitable algebraic platform. HK17 had its interest because it was the only first-round offer strictly based on canonical group theory [5]. At last, we adapted the original protocol with the R-propping solution of 3-dimensional tensors [6], yielding Bernstein attack fruitless. Therefore, an El Gamal IND-CCA2 cipher security using Cao [7] arguments are at hand.

This paper proposes two different methods to perform NTT-based polynomial multiplication in polynomial rings that do not naturally support such a multiplication. We demonstrate these methods on the NTRU Prime key-encapsulation mechanism (KEM) proposed by Bernstein, Chuengsatiansup, Lange, and Vredendaal, which uses a polynomial ring that is, by design, not amenable to use with NTT. One of our approaches is using Good's trick and focuses on speed and supporting more than one parameter set with a single implementation. The other approach is using a mixed-radix NTT and focuses on the use of smaller multipliers and less memory. On an ARM Cortex-M4 microcontroller, we show that our three NTT-based implementations, one based on Good's trick and two mixed-radix NTTs, provide between 32% and 17% faster polynomial multiplication. For the parameter-set ntrulpr761, this results in between 16% and 9% faster total operations (sum of key generation, encapsulation, and decapsulation) and requires between 15% and 39% less memory than the current state-of-the-art NTRU Prime implementation on this platform, which is using Toom-Cook-based polynomial multiplication.

This short report contains results of a brief cryptanalysis of the initialisation phase of ZUC-256. We find IV differentials that persist for 26 of the 33 initialisation rounds, and Key differentials that persist for 28 of the 33 rounds.

Boneh-Durfee proposed (at Eurocrypt 1999) a polynomial time attacks on RSA small decryption exponent which exploits lattices and sub-lattice structure to obtain an optimized bounds d < N^0.284 and d < N^0.292 respectively using lattice based Coppersmith’s method. In this paper we propose a special case of Boneh-Durfee’s attack with respect to large private exponent (i.e. d = N^&#949; > e = N^&#945; where &#949; and &#945; are the private and public key exponents respectively) for some &#945; &#8804; &#949;, which satisfy the condition d > &#966;(N) &#8722; N^&#949;. We analyzed lattices whose basis matrices are triangular and non-triangular using large decryption exponent and focus group attacks respectively. The core objective is to explore RSA polynomials underlying algebraic structure so that we can improve the performance of weak key attacks. In our solution, we implemented the attack and perform several experiments to show that an RSA cryptosystem successfully attacked and revealed possible weak keys which can ultimately enables an adversary to factorize the RSA modulus.

This paper studies concrete security with respect to expected-time adversaries. Our first contribution is a set of generic tools to obtain tight bounds on the advantage of an adversary with expected-time guarantees. We apply these tools to derive bounds in the random-oracle and generic-group models, which we show to be tight.

As our second contribution, we use these results to derive concrete bounds on the soundness of public-coin proofs and arguments of knowledge. Under the lens of concrete security, we revisit a paradigm by Bootle at al. (EUROCRYPT '16) that proposes a general Forking Lemma for multi-round protocols which implements a rewinding strategy with expected-time guarantees. We give a tighter analysis, as well as a modular statement. We adopt this to obtain the first quantitative bounds on the soundness of Bulletproofs (Bünz et al., S&P 2018), which we instantiate with our expected-time generic-group analysis to surface inherent dependence between the concrete security and the statement to be proved.

The only known non-interactive zero-knowledge (NIZK) protocol that is secure against adaptive corruption of the prover is based on that of Groth-Ostrovsky-Sahai (JACM'11) (GOS). However that protocol does not guarantee full adaptive soundness. Abe and Fehr (TCC'07) construct an adaptively sound variant of the GOS protocol under a knowledge-of-exponent assumption, but knowledge assumptions of this type are inherently incompatible with universally composable (UC) security.

We show the first NIZK which is triply adaptive: it is a UC NIZK protocol in a multi-party, multi-instance setting, with adaptive corruptions and no data erasures. Furthermore, the protocol provides full adaptive soundness. Our construction is very different than that of GOS: it is based on the recent NIZK of Canetti et al (STOC'19), and can be based on a variety of assumptions (e.g. LWE, or LPN and DDH). We also show how to get a succinct reference string assuming LWE or DDH from GOS-like techniques.

Public key encryption with keyword search (PEKS) is first introduced by Boneh et al. enabling a cloud server to search on encrypted data without leaking any information of the keyword. In almost all PEKS schemes, the privacy of trapdoor is vulnerable to inside keyword guessing attacks (KGA), i.e., the server can generate the ciphertext by its own and then run the test algorithm to guess the keyword contained in the trapdoor. To sole this problem, Huang et al. proposed the public-key authenticated encryption with keyword search (PAEKS) achieving trapdoor privacy (TP) security, in which data sender not only encrypts the keyword but also authenticates it by using his/her secret key. Qin et al. introduced the notion of multi-ciphertext indistinguishability (MCI) security to capture outside chosen multi-ciphertext attacks, in which the adversary needs to distinguish two tuples of ciphertexts corresponding with two sets of keywords. They analysed that Huang's work cannot achieve MCI security, so they proposed an improved scheme to match both the MCI security and trapdoor privacy (TP) security. In addition, they also defined the notion of multi-trapdoor privacy (MTP) security, which requires to distinguish two tuples of trapdoors corresponding with two sets of keywords.

Unfortunately, trapdoor generation algorithms of all above works are deterministic, which means they are unable to capture the security requirement of MTP. How to achieve MTP security against inside multi-keyword guessing attacks,i.e., designing a probabilistic trapdoor generation algorithm, is still an open problem.

In this paper, we solve this problem. We initially propose two public-key authenticated encryption with keyword search schemes achieving both MCI security and MTP security simultaneously. We provide formal proof of our schemes in the random oracle model.

Non-committing encryption (NCE) introduced by Canetti et al. (STOC '96) is a central tool to achieve multi-party computation protocols secure in the adaptive setting. Recently, Yoshida et al. (ASIACRYPT '19) proposed an NCE scheme based on the hardness of the DDH problem, which has ciphertext expansion $\mathcal{O}(\log\lambda)$ and public-key expansion $\mathcal{O}(\lambda^2)$. In this work, we improve their result and propose a methodology to construct an NCE scheme that achieves constant ciphertext expansion.Our methodology can be instantiated from the DDH assumption and the LWE assumption. When instantiated from the LWE assumption, the public-key expansion is $\lambda\cdot\mathsf{poly}(\log\lambda)$. They are the first NCE schemes satisfying constant ciphertext expansion without using iO or common reference strings. Along the way, we define a weak notion of NCE, which satisfies only weak forms of correctness and security.We show how to amplify such a weak NCE scheme into a full-fledged one using wiretap codes with a new security property.

The Global and Externalized UC frameworks [Canetti-Dodis-Pass-Walfish, TCC 07] extend the plain UC framework to additionally handle protocols that use a ``global setup'', namely a mechanism that is also used by entities outside the protocol. These frameworks have broad applicability: Examples include public-key infrastructures, common reference strings, shared synchronization mechanisms, global blockchains, or even abstractions such as the random oracle. However, the need to work in a specialized framework has been a source of confusion, incompatibility, and an impediment to broader use.

We show how security in the presence of a global setup can be captured within the plain UC framework, thus significantly simplifying the treatment. This is done as follows:

- We extend UC-emulation to the case where both the emulating protocol $\pi$ and the emulated protocol $\phi$ make subroutine calls to protocol $\gamma$ that is accessible also outside $\pi$ and $\phi$. As usual, this notion considers only a single instance of $\phi$ or $\pi$ (alongside $\gamma$).

- We extend the UC theorem to hold even with respect to the new notion of UC emulation. That is, we show that if $\pi$ UC-emulates $\phi$ in the presence of $\gamma$, then $\rho^{\phi\rightarrow\pi}$ UC-emulates $\rho$ for any protocol $\rho$, even when $\rho$ uses $\gamma$ directly, and in addition calls many instances of $\phi$, all of which use the same instance of $\gamma$. We prove this extension using the existing UC theorem as a black box, thus further simplifying the treatment.

We also exemplify how our treatment can be used to streamline, within the plain UC model, proofs of security of systems that involve global set-up, thus providing greater simplicity and flexibility.

This article describes some approaches to bounding non-minimum weight differentials (EDP) and linear hulls (ELP) in 2-round LSX-cipher. We propose a dynamic programming algorithm to solve this problem. For 2-round Kuznyechik the nontrivial upper bounds on all differentials (linear hulls) with $18$ and $19$ active Sboxes was obtained. These estimates are also holds for other differentials (linear hulls) with a larger number of active Sboxes. We obtain a similar result for 2-round Khazad. As a consequence, the exact value of the maximum expected differential (linear) probability (MEDP/MELP) was computed for this cipher.

Over 20 Round 2 candidates in the NIST Lightweight Cryptography (LWC) process have been implemented in hardware by groups from all over the world. In August and September 2020, all implementations compliant with the LWC Hardware API, proposed in 2019, have been submitted for FPGA benchmarking to George Mason University’s LWC benchmarking team, who co-authored this report. The received submissions were first verified for correct functionality and compliance with the hardware API's specification. Then, formulas for the execution times in clock cycles, as a function of input sizes, have been confirmed using behavioral simulation. If needed, appropriate corrections were introduced in collaboration with the submission teams. The compatibility of all implementations with FPGA toolsets from three major vendors, Xilinx, Intel, and Lattice Semiconductor was verified. Optimized values of the maximum clock frequency and resource utilization metrics, such as the number of look-up tables (LUTs) and flip-flops (FFs), were obtained by running optimization tools, such as Minerva, ATHENa, and Xeda. The raw post-place and route results were then converted into values of the corresponding throughputs for long, medium-size, and short inputs. The overhead of modifying vs. reusing a key between two consecutive inputs was quantified. The results were presented in the form of easy to interpret graphs and tables, demonstrating the relative performance of all investigated algorithms. For a few submissions, the results of the initial design-space exploration were illustrated as well. An effort was made to make the entire process as transparent as possible and results easily reproducible by other groups.

This paper will contain the analysis of frontrunning potential on Quipuswap - a decentralized exchange with automated marketmaking in the context of the Proof Of Stake family consensus algo over Tezos protocol, and a proposal to boost the frontrunning resistance of the protocol via the implementation of commit reveal scheme.

Witness hiding proofs require that the verifier cannot find a witness after seeing a proof. The exact round complexity needed for witness hiding proofs has so far remained an open question. In this work, we provide compelling evidence that witness hiding proofs are achievable non-interactively for wide classes of languages. We use non-interactive witness indistinguishable proofs as the basis for all of our protocols. We give four schemes in different settings under different assumptions: – A universal non-interactive proof that is witness hiding as long as any proof system, possibly an inefficient and/or non-uniform scheme, is witness hiding, has a known bound on verifier runtime, and has short proofs of soundness. – A non-uniform non-interactive protocol justified under a worst-case complexity assumption that is witness hiding and efficient, but may not have short proofs of soundness. – A new security analysis of the two-message argument of Pass [Crypto 2003], showing witness hiding for any non-uniformly hard distribution. We propose a heuristic approach to removing the first message, yielding a non-interactive argument. – A witness hiding non-interactive proof system for languages with unique witnesses, assuming the non-existence of a weak form of witness encryption for any language in NP &#8745; coNP.

Non-interactive zero-knowledge proofs or arguments allow a prover to show validity of a statement without further interaction. For non-trivial statements such protocols require a setup assumption in form of a common random or reference string (CRS). Generally, the CRS can only be used for one statement (single-theorem zero-knowledge) such that a fresh CRS would need to be generated for each proof. Fortunately, Feige, Lapidot and Shamir (FOCS 1990) presented a transformation for any non-interactive zero-knowledge proof system that allows the CRS to be reused any polynomial number of times (multi-theorem zero-knowledge). This FLS transformation, however, is only known to work for either computational zero-knowledge or requires a structured, non-uniform common reference string.

In this paper we present FLS-like transformations that work for non-interactive statistical zero-knowledge arguments in the common random string model. They allow to go from single-theorem to multi-theorem zero-knowledge and also preserve soundness, for both properties in the adaptive and non-adaptive case. Our first transformation is based on the general assumption that one-way permutations exist, while our second transformation uses lattice-based assumptions. Additionally, we define different possible soundness notions for non-interactive arguments and discuss their relationships.

We present a bootstrapping procedure for the full-RNS variant of the approximate homomorphic encryption scheme of Cheon et al., CKKS (Asiacrypt 17, SAC 18). Compared to the previously proposed procedures (Eurocrypt 18 & 19, CT-RSA 20), our bootstrapping is simultaneously more precise and more efficient in terms of CPU cost and number of consumed levels. Moreover, unlike the previous approaches, it does not require the use of sparse secret-keys. Hence, to the best of our knowledge, this is the first procedure that enables efficient bootstrapping for parameters that are 128-bit-secure under more recent attacks on sparse R-LWE secrets.

We achieve this by introducing two novel contributions, applicable to the CKKS scheme: (i) We propose a generic algorithm for homomorphic polynomial evaluation that is scale-invariant and optimal in level consumption. (ii) We optimize the key-switch procedure and propose a new technique to perform rotations (``double hoisting'') that significantly reduces the complexity of homomorphic matrix-vector products.

Our scheme improvements and bootstrapping procedure are implemented in the open source Lattigo library (https://github.com/ldsec/lattigo). As an example, bootstrapping a plaintext in $\mathbb{C}^{32768}$ takes 17 seconds, with an output coefficient modulus of 505 bits and a mean precision of 19.2 bits. Hence, we achieve an order of magnitude improvement in bootstrapped throughput (plaintext-bit per second) with respect to the previous best results, while ensuring 128-bit of security.

WAGE is a hardware-oriented authenticated cipher, which has the smallest (unprotected) hardware cost (for 128-bit security level) among the round 2 candidates of the NIST lightweight cryptography (LWC) competition. In this work, we analyze the security of WAGE against the correlation power analysis (CPA) on ARM Cortex-M4F microcontroller. Our attack detects the secret key leakage from power consumption for up to 12 (out of 111) rounds of the WAGE permutation and requires 10,000 power traces to recover the 128-bit secret key. Motivated by the CPA attack and the low hardware cost of WAGE, we propose the first optimized masking scheme of WAGE in the t-strong non-interference (SNI) security model. We investigate different masking schemes for S-boxes by exploiting their internal structures and leveraging the state-of-the-art masking techniques.To practically demonstrate the effectiveness of masking, we perform the test vector leakage assessment on the 1-order masked WAGE. We evaluate the hardware performance of WAGE for 1, 2, and 3-order security and provide a comparison with other NIST LWC round 2 candidates.

Farfalle, a permutation-based construction for building a pseudorandom function (PRF), is really versatile. It can be used for message authentication code, stream cipher, key derivation function, authenticated encryption and so on. Farfalle construction relies on a set of permutations and on so-called rolling functions: it can be split into a compression layer followed by a two-step expansion layer.

As one instance of Farfalle, Xoofff is very efficient on a wide range of platforms from low-end devices to high-end processors by combining the narrow permutation Xoodoo and the inherent parallelism of Farfalle. In this paper, we present key-recovery attacks on reduced-round Xoofff. After identifying a weakness in the expanding rolling function, we first propose practical attacks on Xoofff instantiated with 1-/2-round Xoodoo in the expansion layer. We next extend such attack on Xoofff instantiated with 3-/4-round Xoodoo in the expansion layer by making use of Meet-in-the-Middle algebraic attacks and the linearization technique. All attacks proposed here -- which are independent of the details of the compression and/or middle layer -- have been practically verified (either on the "real" Xoofff or on a toy-version Xoofff with block-size of 96 bits).

As a countermeasure, we discuss how to slightly modified the rolling function for free to reduce the number of attackable rounds.

The aim of white-box cryptography is to protect a secret key in a whitebox environment in which an adversary has full control ability over the computer’s execution process and the running environment. In order to solve the issues of lower security in static white-box algorithm and inconvenient application in traditional dynamic white-box algorithm, it is proposed that a white-box block cipher scheme based on dynamic library named WBCD. In this scheme, look-up tables and affine transformations are used to construct dynamic white-box library, which ensure that the different look-up tables can be used for each round of encryptions. In order to illustrate the effectiveness of WBCD, it is designed a novel white-box mechanism (WBDL) based on dynamic library, ,which adopt MDS matrix. In this mechanism, different round-keys have been employed to implement encryption by randomly selecting look-up tables in each round of operations. According to the analysis, WBDL mechanism can resist differential attack, linear attack, BGE attack and side channel energy attack against SM4. After being calculated and tested, WBDL mechanism requires 466.914KB of memory to store the look-up tables, maximum differential probability(MDP) of each round is 2^&#8722;26, maximum linear probability(MLP) of each round is 2^&#8722;25.61, the encryption speed can reach to 0.273×10^&#8722;3 Gbps, and decryption speed can achieve 0.234×10^&#8722;3 Gbps. Our mechanism has better security and working efficiency, which can be used in mobile communication security and digital payment security.

In the backdoored random-oracle (BRO) model, besides access to a random function $H$, adversaries are provided with a backdoor oracle that can compute arbitrary leakage functions $f$ of the function table of $H$. Thus, an adversary would be able to invert points, find collisions, test for membership in certain sets, and more. This model was introduced in the work of Bauer, Farshim, and Mazaheri (Crypto 2018) and extends the auxiliary-input idealized models of Unruh (Crypto 2007), Dodis, Guo, and Katz (Eurocrypt 2017), Coretti et al. (Eurocrypt 2018), and Coretti, Dodis, and Guo (Crypto 2018). It was shown that certain security properties, such as one-wayness, pseudorandomness, and collision resistance can be re-established by combining two independent BROs, even if the adversary has access to both backdoor oracles.

In this work we further develop the technique of combining two or more independent BROs to render their backdoors useless in a more general sense. More precisely, we study the question of building an indifferentiable and backdoor-free random function by combining multiple BROs. Achieving full indifferentiability in this model seems very challenging at the moment. We however make progress by showing that the xor combiner goes well beyond security against preprocessing attacks and offers indifferentiability as long as the adaptivity of queries to different backdoor oracles remains logarithmic in the input size of the BROs. We even show that an extractor-based combiner of three BROs can achieve indifferentiability with respect to a linear adaptivity of backdoor queries. Furthermore, a natural restriction of our definition gives rise to a notion of indifferentiability with auxiliary input, for which we give two positive feasibility results.

To prove these results we build on and refine techniques by Göös et al. (STOC 2015) and Kothari et al. (STOC 2017) for decomposing distributions with high entropy into distributions with more structure and show how they can be applied in the more involved adaptive settings.