What a lovely hat

Recent active studies have demonstrated that cryptography without one-way functions (OWFs) could be possible in the quantum world. Many fundamental primitives that are natural quantum analogs of OWFs or pseudorandom generators (PRGs) have been introduced, and their mutual relations and applications have been studied. Among them, pseudorandom function-like state generators (PRFSGs) [Ananth, Qian, and Yuen, Crypto 2022] are one of the most important primitives. PRFSGs are a natural quantum...

In this work, we revisit the Hosoyamada-Iwata (HI) proof for the quantum CPA security of the 4-round Luby-Rackoff construction and identify a gap that appears to undermine the security proof. We emphasize that this is not an attack, and the construction may still achieve the claimed security level. However, this gap raises concerns about the feasibility of establishing a formal security proof for the 4-round Luby-Rackoff construction. In fact, the issue persists even if the number of rounds...

In this article, we propose a generic hybrid encryption scheme providing entity authentication. The scheme is based on lossy trapdoor functions relying on the hardness of the Learning With Errors problem. The construction can be used on a number of different security requirements with minimal reconfiguration. It ensures entity authentication and ciphertext integrity while providing security against adaptive chosen ciphertext attacks in the standard model. As a desired characteristic of...

Security against chosen-ciphertext attacks (CCA) concerns privacy of messages even if the adversary has access to the decryption oracle. While the classical notion of CCA security seems to be strong enough to capture many attack scenarios, it falls short of preserving the privacy of messages in the presence of quantum decryption queries, i.e., when an adversary can query a superposition of ciphertexts. Boneh and Zhandry (CRYPTO 2013) defined the notion of quantum CCA (qCCA) security to...

In this paper, we study the robustness of Kyber, the Learning With Errors (LWE)-based Key Encapsulation Mechanism (KEM) chosen for standardization by NIST, against key mismatch attacks. We demonstrate that Kyber's security levels can be compromised with a few mismatch queries by striking a balance between the parallelization level and the cost of lattice reduction for post-processing. This highlights the imperative need to strictly prohibit key reuse in CPA-secure Kyber. We further...

Targeted Denial-of-Service (DoS) attacks have been a practical concern for permissionless blockchains. Potential solutions, such as random sampling, are adopted by blockchains. However, the associated security guarantees have only been informally discussed in prior work. This is due to the fact that existing adversary models are either not fully capturing this attack or giving up certain design choices (as in the sleepy model or asynchronous network model), or too strong to be...

At EUROCRYPT’23, Castryck and Decru, Maino et al., and Robert present efficient attacks against supersingular isogeny Diffie-Hellman key exchange protocol (SIDH). Drawing inspiration from these attacks, Andrea Basso, Luciano Maino, and Giacomo Pope introduce FESTA, an isogeny-based trapdoor function, along with a corresponding IND-CCA secure public key encryption (PKE) protocol at ASIACRYPT’23. FESTA incorporates either a diagonal or circulant matrix into the secret key to mask torsion...

We focus on the problem of constructing fully homomorphic encryption (FHE) schemes that achieve some meaningful notion of adaptive chosen-ciphertext security beyond CCA1. Towards this, we propose a new notion, called security against verified chosen-ciphertext attack (vCCA). The idea behind it is to ascertain integrity of the ciphertext by imposing a strong control on the evaluation algorithm. Essentially, we require that a ciphertext obtained by the use of homomorphic evaluation must be...

A recent security model for fully homomorphic encryption (FHE), called IND-CPA^D security and introduced by Li and Micciancio [Eurocrypt'21], strengthens IND-CPA security by giving the attacker access to a decryption oracle for ciphertexts for which it should know the underlying plaintexts. This includes ciphertexts that it (honestly) encrypted and those obtained from the latter by evaluating circuits that it chose. Li and Micciancio singled out the CKKS FHE scheme for approximate data...

The polynomial attacks on SIDH by Castryck, Decru, Maino, Martindale and Robert have shown that, while the general isogeny problem is still considered unfeasible to break, it is possible to efficiently compute a secret isogeny when given its degree and image on enough torsion points. A natural response from many researchers has been to propose SIDH variants where one or both of these possible extra pieces of information is masked in order to obtain schemes for which a polynomial attack is...

In this paper we propose a new hash-and-sign digital signature scheme whose security against existential forgery under adaptive chosen message attack is based on the hardness of full-distance syndrome decoding. We propose parameter sets for three security levels (128-bits, 192-bits, and 256-bits) based on concrete estimations for hardness of the syndrome decoding problem and estimate the corresponding sizes of the keys and the signature for each level. The scheme has large public and private...

In this paper, we present a new distinguisher for the Tweak-aNd-Tweak (TNT) tweakable block cipher with $O(2^{n/2})$ complexity. The distinguisher is an adaptive chosen ciphertext distinguisher, unlike previous attacks that are only non-adaptive chosen plaintext attacks. However, the attack contradicts the security claims made by the designers. Given TNT can be seen as the three-round CLRW1 tweakable block cipher, our attack matches its more conservative bound. We provide the distinguisher...

We instantiate the hash-then-evaluate paradigm for pseudorandom functions (PRFs), $\mathsf{PRF}(k, x) := \mathsf{wPRF}(k, \mathsf{RO}(x))$, which builds a PRF $\mathsf{PRF}$ from a weak PRF $\mathsf{wPRF}$ via a public preprocessing random oracle $\mathsf{RO}$. In applications to secure multiparty computation (MPC), only the low-complexity wPRF performs secret-depending operations. Our construction replaces RO by $f(k_H , \mathsf{elf}(x))$, where $f$ is a non-adaptive PRF and the key $k_H$...

Real-world cryptographic implementations nowadays are not only attacked via classical cryptanalysis but also via implementation attacks, including passive attacks (observing side-channel information about the inner computation) and active attacks (inserting faults into the computation). While countermeasures exist for each type of attack, countermeasures against combined attacks have only been considered recently. Masking is a standard technique for protecting against passive side-channel...

Isogeny-based cryptography is one of the candidates for post-quantum cryptography. In 2023, Kani's theorem breaks an isogeny-based scheme SIDH, which was considered a promising post-quantum scheme. Though Kani's theorem damaged isogeny-based cryptography, some researchers have been trying to dig into the applications of this theorem. A FESTA trapdoor function is an isogeny-based trapdoor function that is one trial to apply Kani's theorem to cryptography. This paper claims that there is an...

Can an adversary hack into our computer and steal sensitive data such as cryptographic keys? This question is almost as old as the Internet and significant effort has been spent on designing mechanisms to prevent and detect hacking attacks. Once quantum computers arrive, will the situation remain the same or can we hope to live in a better world? We first consider ubiquitous side-channel attacks, which aim to leak side information on secret system components, studied in the...

A single-leader election (SLE) is a way to elect one leader randomly among the parties in a distributed system. If the leader is secret (i.e., unpredictable) then it is called a secret single leader election (SSLE). In this paper, we model the security of SLE in the universally composable (UC) model. Our model is adaptable to various unpredictability levels for leaders that an SLE aims to provide. We construct an SLE protocol that we call semi-anonymous single leader election (SASLE). We...

The learning with errors (LWE) assumption is a powerful tool for building encryption schemes with useful properties, such as plausible resistance to quantum computers, or support for homomorphic computations. Despite this, essentially the only method of achieving threshold decryption in schemes based on LWE requires a modulus that is superpolynomial in the security parameter, leading to a large overhead in ciphertext sizes and computation time. In this work, we propose a (fully...

This paper introduces new digital signature scheme whose security against existential forgery under adaptive chosen message attack is based on hardness of the Syndrome Decoding Problem. The hardness assumption is quite simple and hence easy to analyze and investigate. The scheme as whole is neat with intuitive security definition and proof in addition to elegant and efficient signing and verifying algorithms. We propose parameter sets for three security levels (128-bits, 192-bits, and 256...

Single Secret Leader Election protocols (SSLE, for short) allow a group of users to select a random leader so that the latter remains secret until she decides to reveal herself. Thanks to this feature, SSLE can be used to build an election mechanism for proof-of-stake based blockchains. In particular, a recent work by Azouvi and Cappelletti (ACM AFT 2021) shows that in comparison to probabilistic leader election methods, SSLE-based proof-of-stake blockchains have significant security gains,...

Side-channel resilience is a crucial feature when assessing whether a post-quantum cryptographic proposal is sufficiently mature to be deployed. In this paper, we propose a generic and efficient adaptive approach to improve the sample complexity (i.e., the required number of traces) of plaintext-checking (PC) oracle-based side-channel attacks (SCAs), a major class of key recovery chosen-ciphertext SCAs on lattice-based key encapsulation mechanisms. This new approach is preferable when the...

We cryptanalyse the isogeny-based public key encryption schemes SHealS and HealS, and the key exchange scheme HealSIDH of Fouotsa and Petit from Asiacrypt 2021.

Is it possible to convert classical reductions into post-quantum ones? It is customary to argue that while this is problematic in the interactive setting, non-interactive reductions do carry over. However, when considering quantum auxiliary input, this conversion results in a non-constructive post-quantum reduction that requires duplicating the quantum auxiliary input, which is in general inefficient or even impossible. This violates the win-win premise of provable cryptography: an attack...

One of the most significant challenges is the secure user authentication. If it becomes breached, confidentiality and integrity of the data or services may be compromised. The most widespread solution for entity authentication is the password-based scheme. It is easy to use and deploy. During password registration typically users create or activate their account along with their password through their verification email, and service providers are authenticated based on their SSL/TLS...

We look at two basic coding theoretic and cryptographic mechanisms developed separately and investigate relationships between them and their implications. The first mechanism is Proactive Secret Sharing (PSS), which allows randomization and repair of shares using information from other shares. PSS enables constructing secure multi-party computation protocols that can withstand mobile dynamic attacks. This self-recovery and the redundancy of uncorrupted shares allows a system to overcome...

(Fully) homomorphic encryption ((F)HE) allows users to publicly evaluate circuits on encrypted data. Although publicly homomorphic evaluation property has various applications, (F)HE cannot achieve security against chosen ciphertext attacks (CCA2) due to its nature. To achieve both the CCA2 security and homomorphic evaluation property, Emura et al. (PKC 2013) introduced keyed-homomorphic public key encryption (KH-PKE) and formalized its security denoted by $\mathsf{KH\textup{-}CCA}$...

In 2016, Galbraith et al. presented an adaptive attack on the SIDH key exchange protocol. In SIKE, one applies a variant of the Fujisaki-Okamoto transform to force Bob to reveal his encryption key to Alice, which Alice then uses to re-encrypt Bob's ciphertext and verify its validity. Therefore, Bob can not reuse his encryption keys. There have been two other proposed countermeasures enabling static-static private keys: k-SIDH and its variant by Jao and Urbanik. These countermeasures are...

Consider an $n$-message coin-tossing protocol between $n$ parties $P_1,\dots,P_n$, in which $P_i$ broadcasts a single message $w_i$ in round $i$ (possibly based on the previously shared messages) and at the end they agree on bit $b$. A $k$-replacing adversary $A_k$ can change up to $k$ of the messages as follows. In every round $i$, the adversary who knows all the messages broadcast so far, as well as a message $w_i$ that is prepared by $P_i$ to be just sent, can can to replace the prepared...

The celebrated Fiat-Shamir transformation turns any public-coin interactive proof into a non-interactive one, which inherits the main security properties (in the random oracle model) of the interactive version. While originally considered in the context of 3-move public-coin interactive proofs, i.e., so-called $\Sigma$-protocols, it is now applied to multi-round protocols as well. Unfortunately, the security loss for a $(2\mu + 1)$-move protocol is, in general, $Q^\mu$, where $Q$ is the...

The SIDH key exchange is the main building block of SIKE, the only isogeny based scheme involved in the NIST standardization process. In 2016, Galbraith et al. presented an adaptive attack on SIDH. In this attack, a malicious party manipulates the torsion points in his public key in order to recover an honest party's static secret key, when having access to a key exchange oracle. In 2017, Petit designed a passive attack (which was improved by de Quehen et al. in 2020) that exploits the...

Our context is anonymous encryption schemes hiding their receiver, but in a setting which allows authorities to reveal the receiver when needed. While anonymous Identity-Based Encryption (IBE) is a natural candidate for such fair anonymity (it gives trusted authority access by design), the de facto security standard (a.k.a. IND-ID-CCA) is incompatible with the ciphertext rerandomizability which is crucial to anonymous communication. Thus, we seek to extend IND-ID-CCA security for IBE to a...

In the last decades, several signcryption schemes have been proposed for different privacy-enhancing purposes. In this paper, we propose a new privacy-enhancing group signcryption scheme that provides: unforgeability, confidentiality, ciphertext and sender anonymity, traceability, unlinkability, exculpability, coalition-resistance, and unforgeable tracing verification. It is important to notice that the proposed scheme allows a signer to anonymously signcryt a message on the group's behalf...

We present a polynomial-time adaptive attack on the genus-2 variant of the SIDH protocol (G2SIDH) and describe an improvement to its secret selection procedure. G2SIDH is a generalisation of the Supersingular Isogeny Diffie--Hellman key exchange into the genus-2 setting which was proposed by Flynn and Ti. G2SIDH is able to achieve the same security as SIDH while using fields a third of the size. We analyze the keyspace of G2SIDH and achieve an improvement to the secret selection by using...

In CRYPTO 2019, Chen et al. have initiated an interesting research direction in designing PRF based on public permutations. They have proposed two beyond the birthday bound secure $n$-bit to $n$-bit PRF constructions, i.e., \textsf{SoEM22} and \textsf{SoKAC21}, which are built on public permutations, where $n$ is the size of the permutation. However, both of their constructions require two independent instances of public permutations. In FSE 2020, Chakraborti et al. have proposed a single...

We present an adaptive key recovery attack on the leveled homomorphic encryption scheme suggested by Li, Galbraith and Ma (Provsec 2016), which itself is a modification of the GSW cryptosystem designed to resist key recovery attacks by using a different linear combination of secret keys for each decryption. We were able to efficiently recover the secret key for a realistic choice of parameters using a statistical attack. In particular, this means that the Li, Galbraith and Ma strategy does...

Should quantum computers become available, they will reduce the effective key length of basic secret-key primitives, such as blockciphers. To address this we will either need to use blockciphers with inherently longer keys or develop key-length extension techniques to amplify the security of a blockcipher to use longer keys. We consider the latter approach and revisit the FX and double encryption constructions. Classically, FX was proven to be a secure key-length extension technique, while...

Smart grid has improved the security, efficiency of the power system and balanced the supply and demand by intelligent management, which enhanced stability and reliability of power grid. The key point to achieve them is real-time data and consume data sharing by using fine-grained policies. But it will bring the leakage of the privacy of the users and losing of control over data for data owners. The reported solutions can not give the best trade-off among the privacy protection, control over...

With every new generation, high-end FPGAs are becoming richer in features and resources, making the usage model of single-user per FPGA decreasingly cost-efficient. Although virtualized FPGAs enable multiple users to share the same FPGA, this multi-tenancy is not employed in practice because of potential security threats, such as voltage attacks. These attacks use power-wasting circuits to exercise excessive switching activity on the target FPGA to cause extreme voltage fluctuations, which...

In this paper we introduce partitioning oracles, a new class of decryption error oracles which, conceptually, take a ciphertext as input and output whether the decryption key belongs to some known subset of keys. We introduce the first partitioning oracles which arise when encryption schemes are not committing with respect to their keys. We detail novel adaptive chosen ciphertext attacks that exploit partitioning oracles to efficiently recover passwords and de-anonymize anonymous...

The random oracle model (ROM) enjoys widespread popularity, mostly because it tends to allow for tight and conceptually simple proofs where provable security in the standard model is elusive or costly. While being the adequate replacement of the ROM in the post-quantum security setting, the quantum-accessible random oracle model (QROM) has thus far failed to provide these advantages in many settings. In this work, we focus on adaptive reprogrammability, a feature of the ROM enabling tight...

Non-zero inner product encryption (NIPE) allows a user to encrypt a message with an attribute vector and a receiver holding a secret-key associated to a predicate vector can recover the message from the ciphertext if the inner product between the attribute and predicate vectors is non-zero. The main focus is to hide messages in most of the existing NIPEs and the associated attribute is trivially included in the ciphertext. In this work, we investigate the design of NIPEs that are capable of...

Lattice-based cryptography, as an active branch of post-quantum cryptography (PQC), has drawn great attention from side-channel analysis researchers in recent years. Despite the various side-channel targets examined in previous studies, detail on revealing the secret-dependent information efficiently is less studied. In this paper, we propose adaptive EM side-channel attacks with carefully constructed ciphertexts on Kyber, which is a finalist of NIST PQC standardization project. We...

Recently, Huang et al. proposed a concept of public key encryption with filtered equality test (PKE-FET) that allows a tester who has a warrant for the selected message set to check equality of messages in ciphertexts that belong to that set (Journal of Computer and System Sciences, 2017). They also presented an instantiation of the PKE-FET that was asserted to achieve the indistinguishability against adaptive chosen ciphertext attacks (IND-CCA2) in the standard model. In this note, we show...

Using a novel class of single bit one-way trapdoor functions we construct a theoretical probabilistic public key encryption scheme that has many interesting properties. These functions are constructed from binary quadratic forms and rational quartic reciprocity laws. They are not based on class group operations nor on universal one-way hash functions. Inverting these functions appears to be as difficult as factoring, and other than factoring, we know of no reductions between this new...

The k-SIDH protocol is a static-static isogeny-based key agreement protocol. At Mathcrypt 2018, Jao and Urbanik introduced a variant of this protocol which uses non-scalar automorphisms of special elliptic curves to improve its efficiency. In this paper, we provide a new adaptive attack on Jao-Urbanik's protocol. The attack is a non-trivial adaptation of Galbraith-Petit-Shani-Ti's attack on SIDH (Asiacrypt 2016) and its extension to k-SIDH by Dobson-Galbraith-LeGrow-Ti-Zobernig (IACR eprint...

It is well known, due to the adaptive attack by Galbraith, Petit, Shani, and Ti (GPST), that plain SIDH is insecure in the static setting. Recently, Kayacan's preprint "A Note on the Static-Static Key Agreement Protocol from Supersingular Isogenies", ePrint 2019/815, presented two possible fixes. Protocol A (also known as 2-SIDH, a low-degree instantiation of the more general k-SIDH) has been broken by Dobson, Galbraith, LeGrow, Ti, and Zobernig. In this short note we will show how to break...

The task of function inversion is central to cryptanalysis: breaking block ciphers, forging signatures, and cracking password hashes are all special cases of the function-inversion problem. In 1980, Hellman showed that it is possible to invert a random function $f\colon [N] \to [N]$ in time $T = \widetilde{O}(N^{2/3})$ given only $S = \widetilde{O}(N^{2/3})$ bits of precomputed advice about $f$. Hellman’s algorithm is the basis for the popular “Rainbow Tables” technique (Oechslin, 2003),...

Multi-proxy multi-signature schemes are useful in distributed networks, where a group of users cooperatively could delegate their administrative rights to the users of another group, who are authorized to generate the proxy signatures cooperatively on behalf of the original signers. In this paper, we aim to propose an ID-based lattice-based multi-proxy multi-signature (ILMPMS) scheme, which enjoys security against quantum computers and efficiency due to ID-based framework, linear operations...

Proof-of-stake (PoS) blockchain protocols are emerging as one of the most promising alternative to the energy-consuming proof-of-work protocols. However, one particularly critical threat in the PoS setting is the well-known long-range attacks caused by secret key leakage (LRSL attack). Specifically, an adversary can attempt to corrupt the secret keys corresponding to accounts possessing substantial stake at some past moment such that double-spend or erase past transactions, violating the...

In this work we investigate the problem of automating the development of adaptive chosen ciphertext attacks on systems that contain vulnerable format oracles. Unlike previous attempts, which simply automate the execution of known attacks, we consider a more challenging problem: to programmatically derive a novel attack strategy, given only a machine-readable description of the plaintext verification function and the malleability characteristics of the encryption scheme. We present a new set...

In this paper, we study the results of the recently proposed exchange attack in an adaptive setting. As expected, it leads to present a better 6-round key-independent distinguisher in terms of data and computational complexities. More specifically, our 6-round adaptive distinguisher requires $2^{83}$ chosen plaintexts and $2^{83}$ adaptively chosen ciphertexts and has a computational cost of $2^{83}$ encryption.

We present a polynomial-time adaptive attack on the 2-SIDH protocol. The 2-SIDH protocol is a special instance of the countermeasure proposed by Azarderakhsh, Jao and Leonardi to perform isogeny-based key exchange with static keys in the presence of an adaptive attack. This countermeasure has also been recently explicitly proposed by Kayacan. Our attack extends the adaptive attack by Galbraith, Petit, Shani and Ti (GPST) to recover a static secret key using malformed points. The extension...

In this work, we present new low-data secret-key distinguishers and key-recovery attacks on reduced-round AES. The starting point of our work is “Mixture Differential Cryptanalysis” recently introduced at FSE/ToSC 2019, a way to turn the “multiple-of-8” 5-round AES secret-key distinguisher presented at Eurocrypt 2017 into a simpler and more convenient one (though, on a smaller number of rounds). By reconsidering this result on a smaller number of rounds, we present as our main contribution...

In this paper we investigate the security of 5-round AES against two different attacks in an adaptive setting. We present a practical key-recovery attack on 5-round AES with a secret s-box that requires $2^{32}$ adaptively chosen ciphertexts, which is as far as we know a new record. In addition, we present a new and practical key-independent distinguisher for 5-round AES which requires $2^{27.2}$ adaptively chosen ciphertexts. While the data complexity of this distinguisher is in the same...

Random sampling is a fundamental primitive in modern algorithms, statistics, and machine learning, used as a generic method to obtain a small yet ``representative'' subset of the data. In this work, we investigate the robustness of sampling against adaptive adversarial attacks in a streaming setting: An adversary sends a stream of elements from a universe $U$ to a sampling algorithm (e.g., Bernoulli sampling or reservoir sampling), with the goal of making the sample ``very unrepresentative''...

We present a practical digital signature scheme built from a cryptographic hash function and a hash-then-publish digital time- stamping scheme. We also provide a simple proof of existential unforgeability against adaptive chosen-message attack (EUF-ACM) in the random oracle (RO) model.

Structure-Preserving Signatures (SPSs) are a useful tool for the design of modular cryptographic protocols. Recent series of works have shown that by limiting the message space of those schemes to the set of Diffie-Hellman (DH) pairs, it is possible to circumvent the known lower bounds in the Type-3 bilinear group setting thus obtaining the shortest signatures consisting of only 2 elements from the shorter source group. It has been shown that such a variant yields efficiency gains for some...

Large-scale quantum computing is a significant threat to classical public-key cryptography. In strong “quantum access” security models, numerous symmetric-key cryptosystems are also vulnerable. We consider classical encryption in a model which grants the adversary quantum oracle access to encryption and decryption, but where the latter is restricted to non-adaptive (i.e., pre-challenge) queries only. We define this model formally using appropriate notions of ciphertext...

At CRYPTO’98, Bleichenbacher published his seminal paper which described a padding oracle attack against RSA implementations that follow the PKCS #1 v1.5 standard. Over the last twenty years researchers and implementors had spent a huge amount of effort in developing and deploying numerous mitigation techniques which were supposed to plug all the possible sources of Bleichenbacher-like leakages. However, as we show in this paper most implementations are still vulnerable to several novel...

Cloud storage enables its users to store confidential information as encrypted files in the cloud. A cloud user (say Alice) can share her encrypted files with another user (say Bob) by availing proxy re-encryption services of the cloud. Proxy Re-Encryption (PRE) is a cryptographic primitive that allows transformation of ciphertexts from Alice to Bob via a semi-trusted proxy, who should not learn anything about the shared message. Typically, the re-encryption rights are enabled only for a...

In 2005, Yen et al. proposed the first $N-1$ attack on the modular exponentiation algorithms such as BRIP and square-and-multiply-always methods. This attack makes use of the ciphertext $N-1$ as a distinguisher of low order to obtain a strong relation between side-channel leakages and secret exponent. The so-called $N-1$ attack is one of the most important order-2 element attacks, as it requires a non-adaptive chosen ciphertext which is considered as a more realistic attack model compared...

Braid group is a very important non-commutative group. It is also an important tool of quantum field theory, and has good topological properties. This paper focuses on the provable security research of cryptosystem over braid group, which consists of two aspects: One, we prove that the Ko's cryptosystem based on braid group is secure against chosen-plaintext-attack which proposed in CRYPTO 2000, while it dose not resist active attack. The other is to propose a new public key cryptosystem...

Private linear key agreement (PLKA) enables a group of users to agree upon a common session key in a broadcast encryption (BE) scenario, while traitor tracing (TT) system allows a tracer to identify conspiracy of a troop of colluding pirate users. This paper introduces a key encapsulation mechanism in BE that provides the functionalities of both PLKA and TT in a unified cost-effective primitive. Our PLKA based traitor tracing offers a solution to the problem of achieving full collusion...

At ACISP 2017, Wu et al. presented an identity-based encryption with equality test (IBEET) that considers to prevent insider attacks. To analyze its security, they proposed a new security notion for IBEET, which is slightly weaker than the indistinguishability under adaptive identity and chosen ciphertext attacks (IND-ID-CCA2) for traditional identity-based encryption. Then, they claimed that their proposed scheme achieves this new security notion under the Bilinear Diffie-Hellman (BDH)...

In Public-Key Encryption, traditionally no security is expected if honest parties use keys provided by an adversary. In this work, we re-examine this premise. While using untrusted keys may seem nonsensical at first glance, we argue the use of providing certain security guarantees even in such situations. We propose Chosen Object Attack (COA) security as a broad generalization of various notions of security that have been considered in the literature, including CCA security, key anonymity...

One of the most efficient post-quantum signature schemes is Rainbow whose harness is based on the multivariate quadratic polynomial (MQ) problem. ELSA, a new multivariate signature scheme proposed at Asiacrypt 2017,has a similar construction to Rainbow. Its advantages, compared to Rainbow, are its smaller secret key and faster signature generation. In addition, its existential unforgeability against an adaptive chosen-message attack has been proven under the hardness of the MQ-problem...

Increasingly connectivity becomes integrated in products and devices that previously operated in a stand-alone setting. This observation holds for many consumer ap- plications in the so-called "Internet of Things" (IoT) as well as for corresponding industry applications (IIoT), such as industrial process sensors. Often the only practicable means for authentication of human users is a password. The security of password-based authentication schemes frequently forms the weakest point of...

In this paper we present new fundamental properties of SPNs. These properties turn out to be particularly useful in the adaptive chosen ciphertext/plaintext setting and we show this by introducing for the first time key-independent yoyo-distinguishers for 3- to 5-rounds of AES. All of our distinguishers beat previous records and require respectively $3, 4$ and $2^{25.8}$ data and essentially zero computation except for observing differences. In addition, we present the first key-independent...

We study the problem of encrypting and authenticating quantum data in the presence of adversaries making adaptive chosen plaintext and chosen ciphertext queries. Classically, security games use string copying and comparison to detect adversarial cheating in such scenarios. Quantumly, this approach would violate no-cloning. We develop new techniques to overcome this problem: we use entanglement to detect cheating, and rely on recent results for characterizing quantum encryption schemes. We...

We investigate the subset-resilience problem, defined in 2002 by Reyzin and Reyzin to analyze their HORS signature scheme. We show that textbook HORS is insecure against adaptive attacks, and present a practical attack based on a greedy algorithm. We also describe weak messages for HORS, that map to smaller subsets than expected, and are thus easier to cover. This leads to an improved attack against HORS and to an improved classical attack against the signature scheme SPHINCS, of complexity...

At CRYPTO 2015, Minaud and Seurin introduced and studied the iterated random permutation problem, which is to distinguish the $r$-th iterate of a random permutation from a random permutation. In this paper, we study the closely related iterated random function problem, and prove the first almost-tight bound in the adaptive setting. More specifically, we prove that the advantage to distinguish the $r$-th iterate of a random function from a random function using $q$ queries is bounded by...

The Bitcoin whitepaper states that security of the system is guaranteed as long as honest miners control more than half of the current total computational power. The whitepaper assumes a static difficulty, thus it is equally hard to solve a cryptographic proof-of-work puzzle for any given moment of the system history. However, the real Bitcoin network is using an adaptive difficulty adjustment mechanism. In this paper we introduce and analyze a new kind of attack on a mining difficulty...

We describe novel, adaptive user interface attacks, where the adversary attaches a small device to the interface that connects user input peripherals to the target system. The device executes the attack when the authorized user is performing safety-, or security-critical operations, by modifying or blocking user input, or injecting new events. Although the adversary fully controls the user input channel, to succeed he needs to overcome a number of challenges, including the inability to...

The Keccak hash function is the winner of the SHA-3 competition and became the SHA-3 standard of NIST in 2015. In this paper, we focus on practical collision attacks against round-reduced Keccak hash function, and two main results are achieved: the first practical collision attacks against 5-round Keccak-224 and an instance of 6-round Keccak collision challenge. Both improve the number of practically attacked rounds by one. These results are obtained by carefully studying the algebraic...

For many cryptographic primitives, it is relatively easy to achieve selective security (where the adversary commits a-priori to some of the choices to be made later in the attack) but appears difficult to achieve the more natural notion of adaptive security (where the adversary can make all choices on the go as the attack progresses). A series of several recent works shows how to cleverly achieve adaptive security in several such scenarios including generalized selective decryption...

We present symbolic analysis techniques for detecting vulnerabilities that are due to adaptive side-channel attacks, and synthesizing inputs that exploit the identified vulnerabilities. We start with a symbolic attack model that encodes succinctly all the side-channel attacks that an adversary can make. Using symbolic execution over this model, we generate a set of mathematical constraints, where each constraint characterizes the set of secret values that lead to the same sequence of...

ID based generalized signcryption can adaptively work as a signature scheme, an encryption scheme or a signcryption scheme and avoid weighty and complicated certificate management like Public Key Infrastructure. It has application in emerging paradigm big data security. Recently,Wei et al proposed a new ID based generalized signcryption scheme to obtain con…dentiality or/and authenticity in big data, and claimed that their scheme is provably secure in standard model. Unfortunately, by...

Real-world applications of authenticated encryption often require the encryption to be computable {online}, e.g. to compute the $i^{\textrm{th}}$ block of ciphertext after having processed the first $i$ blocks of plaintext. A significant line of research was dedicated to identifying security notions for online authenticated encryption schemes, that capture various security goals related to real-life scenarios. Fouque, Joux, Martinet and Valette proposed definitions of privacy and integrity...

In this paper, we put forward the first adaptively secure recipient revocable broadcast encryption (RR-BE) scheme in the standard model. The scheme is adaptively secure against chosen plaintext attack (CPA) under the q-weaker Decisional Augmented Bilinear Diffie-Hellman Exponent (q-wDABDHE) assumption. Our scheme compares well with the only existing RR-BE scheme of Susilo et al. which is selectively secure in the random oracle model. More interestingly, achieving adaptive security in the...

Recently, Nie et al. proposed a certificateless aggregate signature scheme. In the standard security model considered in certificateless cryptography, we are dealing with two types of adversaries. In this paper, we show that Nie et al.'s scheme is insecure against the adversary of the first type. In other words, although they claimed that their proposed scheme is existentially unforgeable against adaptive chosen message attack considering the adversaries in certificateless settings, we prove...

A major open problem is to protect leveled homomorphic encryption from adaptive attacks that allow an adversary to learn the private key. The only positive results in this area are by Loftus, May, Smart and Vercauteren. They use a notion of "valid ciphertexts" and obtain an IND-CCA1 scheme under a strong knowledge assumption, but they also show their scheme is not secure under a natural adaptive attack based on a "ciphertext validity oracle". However, due to recent cryptanalysis their scheme...

The tweakable Even-Mansour construction generalizes the conventional Even-Mansour scheme through replacing round keys by strings derived from a master key and a tweak. Besides providing plenty of inherent variability, such a design builds a tweakable block cipher from some lower level primitive. In the present paper, we evaluate the multi-key security of TEM-1, one of the most commonly used one-round tweakable Even-Mansour schemes (introduced at CRYPTO 2015), which is constructed from a...

In broadcast encryption schemes, a distribution center broadcasts an encrypted message to a subset $ S $ chosen from a universe of receivers and only the intended users are able to decrypt the message. Most broadcast encryption schemes do not provide anonymity and the identities of target receivers are sent in plaintext. However, in several applications, the authorized users' identities has the same sensitivity as the message itself. YRL, is an anonymous attribute-based broadcast encryption...

In this paper, we provide a security analysis of ELmD: a block cipher based Encrypt-Linear-mix-Decrypt authentication mode. As being one of the second-round CAESAR candidate, it is claimed to provide misuse resistant against forgeries and security against block-wise adaptive adversaries as well as 128-bit security against key recovery attacks. We scrutinize ElmD in such a way that we provide universal forgery attacks as well as key recovery attacks. First, based on the collision attacks on...

With the advances of cloud computing, data sharing becomes easier for large-scale enterprises. When deploying privacy and security schemes in data sharing systems, fuzzy-entity data sharing, entity management, and efficiency must take into account, especially when the system is asked to share data with a large number of users in a tree-like structure. (Hierarchical) Identity-Based Encryption is a promising candidate to ensure fuzzy-entity data sharing functionalities while meeting the...

Nakamoto's famous blockchain protocol enables achieving consensus in a so-called \emph{permissionless setting}---anyone can join (or leave) the protocol execution, and the protocol instructions do not depend on the identities of the players. His ingenious protocol prevents ``sybil attacks'' (where an adversary spawns any number of new players) by relying on computational puzzles (a.k.a. ``moderately hard functions'') introduced by Dwork and Naor (Crypto'92). The analysis of the blockchain...

An aggregate signature scheme is the aggregation of multiple signatures into a single compact signature of short string that can convince to any arbitrary verifier participating in the scheme. The aggregate signature scheme is very useful for real-world cryptographic applications such as secure routing, database outsourcing, etc. where the signatures on several distinct messages generated by many distinct users requires to be compact. In this paper, we presented an aggregate signature scheme...

We introduce a novel notion of smooth (-verifier) non-interactive zero-knowledge proofs (NIZK) which parallels the familiar notion of smooth projective hash functions (SPHF). We also show that the recent single group element quasi-adaptive NIZK (QA-NIZK) of Jutla and Roy (CRYPTO 2014) for linear subspaces can be easily extended to be computationally smooth. One important distinction of the new notion from SPHFs is that in a smooth NIZK the public evaluation of the hash on a language...

It is a well-known result that homomorphic encryption is not secure against adaptive chosen ciphertext attacks (CCA2) because of its malleable property. Very recently, however, Gong et al. proposed a construction asserted to be a CCA2-secure additively homomorphic encryption (AHE) scheme; in their construction, the adversary is not able to obtain a correct answer when querying the decryption oracle on a ciphertext obtained by modifying the challenge ciphertext (Theoretical Computer Science,...

Myers and Shelat (FOCS 2009) showed how to convert a chosen ciphertext secure (CCA secure) PKE scheme that can encrypt only $1$-bit plaintexts into a CCA secure scheme that can encrypt arbitrarily long plaintexts (via the notion of key encapsulation mechanism (KEM) and hybrid encryption), and subsequent works improved efficiency and simplicity. In terms of efficiency, the best known construction of a CCA secure KEM from a CCA secure 1-bit PKE scheme, has the public key size $\Omega(k) \cdot...

An important shortcoming of client-side cryptography on consumer devices is the poor protection of secret keys. Encrypting the keys under a human-memorizable password hardly offers any protection when the device is stolen. Trusted hardware tokens such as smart cards can provide strong protection of keys but are cumbersome to use. We consider the case where secret keys are used for digital signatures and propose a password-authenticated server-aided signature Pass2Sign protocol, where...

A Probabilistically Checkable Proof (PCP) allows a randomized verifier, with oracle access to a purported proof, to probabilistically verify an input statement of the form ``$x\in L$'' by querying only few bits of the proof. A zero-knowledge PCP (ZKPCP) is a PCP with the additional guarantee that the view of any verifier querying a bounded number of proof bits can be efficiently simulated given the input $x$ alone, where the simulated and actual views are statistically close. Originating...

We provide a symbolic model for multi-party computation based on linear secret-sharing scheme, and prove that this model is com- putationally sound: if there is an attack in the computational world, then there is an attack in the symbolic (abstract) model. Our original contri- bution is that we deal with the uniformity properties, which cannot be described using a single execution trace, while considering an unbounded number of sessions of the protocols in the presence of active and...

An Attribute-Based Signcryption (ABSC) is a natural extension of Attribute-Based Encryption (ABE) and Attribute-Based Signature (ABS), where we have the message confidentiality and authenticity together. Since the signer privacy is captured in security of ABS, it is quite natural to expect that the signer privacy will also be preserved in ABSC. In this paper, first we propose an ABSC scheme which is \textit{weak existential unforgeable, IND-CCA2} secure in \textit{adaptive-predicates} attack...

We provide a formal treatment of security of digital signatures against subversion attacks (SAs). Our model of subversion generalizes previous work in several directions, and is inspired by the proliferation of software attacks (e.g., malware and buffer overflow attacks), and by the recent revelations of Edward Snowden about intelligence agencies trying to surreptitiously sabotage cryptographic algorithms. The main security requirement we put forward demands that a signature scheme should...

In this paper we present adaptive key recovery attacks on NTRU-based somewhat homomorphic encryption schemes. Among such schemes, we study the proposal by Bos et al [BLLN13] in 2013. Given access to a decryption oracle, the attack allows us to compute the private key for all parameter choices. Such attacks show that one must be very careful about the use of homomorphic encryption in practice. The existence of a key recovery attack means that the scheme is not CCA1-secure. Indeed, almost...

Protecting user data entails providing authenticated users access to their data. The most prevalent and probably also the most feasible approach to the latter is by username and password. With password breaches through server compromise now reaching billions of affected passwords, distributing the password files and user data over multiple servers is not just a good idea, it is a dearly needed solution to a topical problem. Threshold password-authenticated secret sharing (TPASS) protocols...

At Asiacrypt 2014, Hanser and Slamanig presented a new cryptographic primitive called structure-preserving signature scheme on equivalence classes in the message space $(\G_1^*)^\ell $, where $\G_1$ is some additive cyclic group. Based on the signature scheme, they constructed an efficient multi-show attribute-based anonymous credential system that allows to encode an arbitrary number of attributes. The signature scheme was claimed to be existentially unforgeable under the adaptive chosen...

Side channel attacks -- attacks that exploit implementation-dependent information of a cryptosystem -- have been shown to be highly detrimental, and the cryptographic community has recently focused on developing techniques for securing implementations against such attacks. An important model called \emph{Only Computation Leaks} (OCL) [Micali and Reyzin, TCC '04] and its stronger variants were proposed to model a broad class of leakage attacks (a type of side-channel attack). These models...

This report summarizes our results from security analysis covering all 57 competitions for authenticated encryption: security, applicability, and robustness (CAESAR) first-round candidates and over 210 implementations. We have manually identified security issues with three candidates, two of which are more serious, and these ciphers have been withdrawn from the competition. We have developed a testing framework, BRUTUS, to facilitate automatic detection of simple security lapses and...