Accountable ring signature (ARS), introduced by Xu and Yung (CARDIS 2004), combines many useful properties of ring and group signatures. In particular, the signer in an ARS scheme has the flexibility of choosing an ad hoc group of users, and signing on their behalf (like a ring signature). Furthermore, the signer can designate an opener who may later reveal his identity, if required (like a group signature). In 2015, Bootle et al. (ESORICS 2015) formalized the notion and gave an efficient construction for ARS with signature-size logarithmic in the size of the ring. Their scheme is proven to be secure in the random oracle model. Recently, Russell et al. (ESORICS 2016) gave a construction with constant signature-size that is secure in the standard model. Their scheme is based on $q$-type assumptions ($q$-SDH). In this paper, we give a new construction for ARS having the following properties: signature is constant-sized, secure in the standard model, and based on indistinguishability obfuscation iO and one-way functions. To the best of our knowledge, this is the first iO-based ARS scheme. Independent of this, our work can be viewed as a new application of puncturable programming and hidden sparse trigger techniques introduced by Sahai and Waters (STOC 2014) to design iO-based deniable encryption.

A cryptosystem which supports both addition and multiplication (thereby preserving the ring structure of the plaintexts) is known as fully homomorphic encryption (FHE) and is very powerful. Using such a scheme, any circuit can be homomorphically evaluated, effectively allowing the construction of programs which may be run on ciphertexts of their inputs to produce a ciphertext of their output. Since such a program never decrypts its input, it can be run by an untrusted party without revealing its inputs and internal state. The existence of an efficient and fully homomorphic cryptosystem would have great practical implications in the outsourcing of private computations, for instance, in the context of cloud computing. In previous work I proposed the fully homomorphic public-key encryption scheme with the size of ciphertext which is not small enough. In this paper the size of ciphertext is one-eighth of the size in the previously proposed scheme. Because proposed scheme adopts the medium text with zero norm, it is immune from the the “p and -p attack”. As the proposed scheme is based on computational difficulty to solve the multivariate algebraic equations of high degree, it is immune from the Gröbner basis attack, the differential attack, rank attack and so on.

We present a semantically secure somewhat homomorphic public-key cryptosystem working in sub-groups of $\mathbb{Z}_{n}^{*}$ of prime power order. Our scheme introduces a novel threshold homomorphic property, which we use to build a two-party protocol for secure integer comparison. In contrast to related work which encrypts and acts on each bit of the input separately, our protocol compares multiple input bits simultaneously within a single ciphertext. Compared to the related protocol of Damgård et al.~we present results showing this approach to be both several times faster in computation and lower in communication complexity.

This work introduces XMSS-T, a new hash-based signature scheme with tight security. Previous hash-based signature schemes are facing a loss of security, linear in performance parameters like the total tree height. Our new scheme can use hash functions with a smaller output length at the same security level, immediately leading to a smaller signature size. XMSS-T is stateful, however, the same techniques also apply directly to the recent stateless hash-based signature scheme SPHINCS (Eurocrypt 2015), and the signature size is improved as a result. Being a little more specific and technical, the tight security stems from new multi-target notions of hash-function properties which we define and analyze. We give precise complexity for breaking these security properties under both classical and quantum generic attacks, thus establishing a reliable estimate for the quantum security of XMSS-T. Especially, we prove quantum upper and lower bounds for the query complexity tailored for cryptographic applications, whereas standard techniques in quantum query complexity have limitations such as they usually only consider worst-case complexity. Our proof techniques may be useful elsewhere. We also implement XMSS-T and compare its performance to that of the most recent stateful hash-based signature scheme XMSS (PQCrypto 2011).

A recent paper by Derler, Ramacher, and Slamanig (IEEE EuroS&P 2018) constructs double-authentication preventing signatures ("DAP signatures", a specific self-enforcement enabled variant of signatures where messages consist of an address and a payload) that have---if the supported address space is not too large---keys and signatures that are considerably more compact than those of prior work. We embark on their approach to restrict attention to small address spaces and construct novel DAP schemes that beat their signature size by a factor of five and reduce the signing key size from linear to constant (the verification key size remains almost the same). We construct our DAP signatures generically from identification protocols, using a transform similar to but crucially different from that of Fiat and Shamir. We use random oracles. We don't use pairings.

Double-authentication-preventing signatures (DAPS) are signatures designed with the aim that signing two messages with an identical first part (called address) but different second parts (called payload) allows to publicly extract the secret signing key from two such signatures. A prime application for DAPS is disincentivizing and/or penalizing the creation of two signatures on different payloads within the same address, such as penalizing double spending of transactions in Bitcoin by the loss of the double spender's money. So far DAPS have been constructed from very specific signature schemes not used in practice and using existing techniques it has proved elusive to construct DAPS schemes from signatures widely used in practice. This, unfortunately, has prevented practical adoption of this interesting tool so far. In this paper we ask whether one can construct DAPS from signature schemes used in practice. We affirmatively answer this question by presenting novel techniques to generically construct provably secure DAPS from a large class of discrete logarithm based signatures. This class includes schemes like Schnorr, DSA, EdDSA, and, most interestingly for practical applications, the widely used ECDSA signature scheme. The resulting DAPS are highly efficient and the shortest among all existing DAPS schemes. They are nearly half of the size of the most efficient factoring based schemes (IACR PKC'17) and improve by a factor of 100 over the most efficient discrete logarithm based ones (ACM CCS'15). Although this efficiency comes at the cost of a reduced address space, i.e., size of keys linear in the number of addresses, we will show that this is not a limitation in practice. Moreover, we generalize DAPS to any N>2, which we denote as N-times-authentication-preventing signatures (NAPS). Finally, we also provide an integration of our ECDSA-based DAPS into the OpenSSL library and perform an extensive comparison with existing approaches.

In this work we seek to construct collusion-resistant traitor tracing systems with small ciphertexts from standard assumptions that also move toward practical efficiency. In our approach we will hold steadfast to the principle of collusion resistance, but relax the requirement on catching a traitor from a successful decoding algorithm. We define a $f$-risky traitor tracing system as one where the probability of identifying a traitor is $f(\lambda,n)$ times the probability a successful box is produced. We then go on to show how to build such systems from prime order bilinear groups with assumptions close to those used in prior works. Our core system achieves, for any $k > 0$, $f(\lambda,n) \approx \frac{k}{n + k - 1}$ where ciphertexts consists of $(k + 4)$ group elements and decryption requires $(k + 3)$ pairing operations. At first glance the utility of such a system might seem questionable since the $f$ we achieve for short ciphertexts is relatively small. Indeed an attacker in such a system can more likely than not get away with producing a decoding box. However, we believe this approach to be viable for four reasons: 1. A risky traitor tracing system will provide deterrence against risk averse attackers. In some settings the consequences of being caught might bear a high cost and an attacker will have to weigh his utility of producing a decryption $D$ box against the expected cost of being caught. 2. Consider a broadcast system where we want to support low overhead broadcast encrypted communications, but will periodically allow for a more expensive key refresh operation. We refer to an adversary produced algorithm that maintains the ability to decrypt across key refreshes as a persistent decoder. We show how if we employ a risky traitor tracing systems in this setting, even for a small $f$, we can amplify the chances of catching such a ``persistent decoder'' to be negligibly close to 1. 3. In certain resource constrained settings risky traitor tracing provides a best tracing effort where there are no other collusion-resistant alternatives. For instance, suppose we had to support 100K users over a radio link that had just 10KB of additional resources for extra ciphertext overhead. None of the existing $\sqrt N$ bilinear map systems can fit in these constraints. On the other hand a risky traitor tracing system provides a spectrum of tracing probability versus overhead tradeoffs and can be configured to at least give some deterrence in this setting. 4. Finally, we can capture impossibility results for differential privacy from $\frac{1}{n}$-risky traitor tracing. Since our ciphertexts are short ($O(\lambda)$), we get the negative result which matches what one would get plugging in the obfuscation based tracing system Boneh-Zhandry (CRYPTO 2014) solution into the prior impossibility result of Dwork et al. (STOC 2009).

The Rényi divergence is a measure of closeness of two probability distributions. We show that it can often be used as an alternative to the statistical distance in security proofs for lattice-based cryptography. Using the Rényi divergence is particularly suited for security proofs of primitives in which the attacker is required to solve a search problem (e.g., forging a signature). We show that it may also be used in the case of distinguishing problems (e.g., semantic security of encryption schemes), when they enjoy a public sampleability property. The techniques lead to security proofs for schemes with smaller parameters, and sometimes to simpler security proofs than the existing ones.

The Fiat-Shamir transform is a technique for combining a hash function and an identification scheme to produce a digital signature scheme. The resulting scheme is known to be secure in the random oracle model (ROM), which does not, however, imply security in the scenario where the adversary also has quantum access to the oracle. The goal of this current paper is to create a generic framework for constructing tight reductions in the QROM from underlying hard problems to Fiat-Shamir signatures. Our generic reduction is composed of two results whose proofs, we believe, are simple and natural. We first consider a security notion (UF-NMA) in which the adversary obtains the public key and attempts to create a valid signature without accessing a signing oracle. We give a tight reduction showing that deterministic signatures (i.e., ones in which the randomness is derived from the message and the secret key) that are UF-NMA secure are also secure under the standard chosen message attack (UF-CMA) security definition. Our second result is showing that if the identification scheme is “lossy”, as defined in (Abdalla et al. Eurocrypt 2012), then the security of the UF-NMA scheme is tightly based on the hardness of distinguishing regular and lossy public keys of the identification scheme. This latter distinguishing problem is normally exactly the definition of some presumably-hard mathematical problem. The combination of these components gives our main result. As a concrete instantiation of our framework, we modify the recent lattice-based Dilithium digital signature scheme (Ducas et al., TCHES 2018) so that its underlying identification scheme admits lossy public keys. The original Dilithium scheme, which is proven secure in the classical ROM based on standard lattice assumptions, has 1.5KB public keys and 2.7KB signatures. The new scheme, which is tightly based on the hardness of the Module-LWE problem in the QROM using our generic reductions, has 7.7KB public keys and 5.7KB signatures for the same security level. Furthermore, due to our proof of equivalence between the UF-NMA and UF-CMA security notions of deterministic signature schemes, we can formulate a new non-interactive assumption under which the original Dilithium signature scheme is also tightly secure in the QROM.

An ECDSA modification with signing equation $s=rk+hd$ has the properties that the signer avoids modular inversion and that passive universal forgery is equivalent to inverting a sum of two functions with freely independent inputs. Let $\sigma:s\mapsto sG$ and $\rho:R\mapsto -rR$ where $r$ is an integer representation of the point $R$. The free sum of $\rho$ and $\sigma$ is $\nu: (R,s) \mapsto \rho(R)+\sigma(s)$. A RKHD signature $(R,s)$ verifies if and only if $\nu(R,s) = hQ$, where $h$ is the hash of the message and $Q$ is the public key. So RKHD security relies upon, among other things, the assumption that free sum $\nu$ is 1-way (or unforgoable, to be precise). Other free sums are 1-way under plausible assumptions: elliptic curve discrete logs, integer factoring, and secure small-key Wegman--Carter--Shoup authentication. Yet other free sums of 1-way functions (integer-factoring based) fail to be 1-way. The ease with which these free sums arise hints at the ease determining RKHD security. RKHD signatures are very similar to ECGDSA (an elliptic curve version Agnew--Mullin--Vanstone signatures): variable-$G$ forgers of the two schemes are algorithmically equivalent. But ECGDSA requires the signer to do one modular inversion, a small implementation security risk.

This paper presents two non-generic and practically efficient private key multi-input functional encryption (MIFE) schemes for the multi-input version of the inner product functionality that are the first to achieve simultaneous message and function privacy, namely, the full-hiding security for a non-trivial multi-input functionality under well-studied cryptographic assumptions. Our MIFE schemes are built in bilinear groups of prime order, and their security is based on the standard $k$-Linear ($k$-LIN) assumption (along with the existence of semantically secure symmetric key encryption and pseudorandom functions). Our constructions support polynomial number of encryption slots (inputs) without incurring any super-polynomial loss in the security reduction. While the number of encryption slots in our first scheme is apriori bounded, our second scheme can withstand an arbitrary number of encryption slots. Prior to our work, there was no known MIFE scheme for a non-trivial functionality, even without function privacy, that can support an unbounded number of encryption slots without relying on any heavy-duty building block or little-understood cryptographic assumption.

This paper extends the leveled homomorphic encryption scheme for an approximate arithmetic of Cheon et al. (ASIACRYPT 2017) to a fully homomorphic encryption, i.e., we propose a new technique to refresh low-level ciphertexts based on Gentry's bootstrapping procedure. The modular reduction operation is the main bottleneck in the homomorphic evaluation of the decryption circuit. We exploit a scaled sine function as an approximation of the modular reduction operation and present an efficient evaluation strategy. Our method requires only one homomorphic multiplication for each of iterations and so the total computation cost grows linearly with the depth of the decryption circuit. We also show how to recrypt packed ciphertexts on the RLWE construction with an open-source implementation. For example, it takes 139.8 seconds to refresh a ciphertext that encrypts 128 numbers with 12 bits of precision, yielding an amortized rate of 1.1 seconds per slot.

We propose a new reaction attack on the public-key cryptosystem LEDApkc. The adversary uses the decoding failure rate (DFR) analysis to learn information about the secret masking matrix $Q$. Provided the adversary learns information about $Q$ within $10^4\times \text{DFR}^{-1}$ decryptions (as prescribed by LEDApkc design to thwart previously known attacks), the adversary builds a small set of candidates for $Q$. Using these candidates, the adversary obtains candidates for a generator matrix of the secret LDPC code. Afterwards, the adversary applies Stern's algorithm to recover the secret matrix $H$, thus recovering the full private key. Provided the adversary can learn information about the matrix $Q$, the complexity of the attack is below $2^{99}$ for a parameter set for 128-bit security. In order to study whether the adversary can learn information about $Q$ from $10^4\times \text{DFR}^{-1}$ decryptions, we conducted experiments with a modified parameter set. The parameter set was modified only in order to increase the DFR, and thus make experiments less computationally expensive. We show that with the modified parameter set it is indeed possible to learn the required information about the matrix $Q$.

In this paper, we describe a new Las Vegas algorithm to solve the elliptic curve discrete logarithm problem. The algorithm depends on a property of the group of rational points of an elliptic curve and is thus not a generic algorithm. The algorithm that we describe has some similarities with the most powerful index-calculus algorithm for the discrete logarithm problem over a finite field.

In 2014, Smart and Vercauteren introduced a packing technique for homomorphic encryption schemes by decomposing the plaintext space using the Chinese Remainder Theorem. This technique allows to encrypt multiple data values simultaneously into one ciphertext and execute Single Instruction Multiple Data operations homomorphically. In this paper we improve and generalize their results by introducing a flexible Laurent polynomial encoding technique and by using a more fine-grained CRT decomposition of the plaintext space. The Laurent polynomial encoding provides a convenient common framework for all conventional ways in which input data types can be represented, e.g. finite field elements, integers, rationals, floats and complex numbers. Our methods greatly increase the packing capacity of the plaintext space, as well as one’s flexibility in optimizing the system parameters with respect to efficiency and/or security.

Bootstrapping is a crucial operation in Gentry's breakthrough work on fully homomorphic encryption (FHE), where a homomorphic encryption scheme evaluates its own decryption algorithm. There has been a couple of implementations of bootstrapping, among which HElib arguably marks the state-of-the-art in terms of throughput, ciphertext/message size ratio and support for large plaintext moduli. In this work, we apply a family of "lowest digit removal" polynomials to improve homomorphic digit extraction algorithm which is crucial part in bootstrapping for both FV and BGV schemes. If the secret key has 1-norm $h=l_1(s)$ and the plaintext modulus is $t = p^r$, we achieved bootstrapping depth $\log h + \log( \log_p(ht))$ in FV scheme. In case of the BGV scheme, we bring down the depth from $\log h + 2 \log t$ to $\log h + \log t$. We implemented bootstrapping for FV in the SEAL library. Besides the regular mode, we introduce another "slim mode'", which restrict the plaintexts to batched vectors in $\mathbb{Z}_{p^r}$. The slim mode has similar throughput as the regular mode, while each individual run is much faster and uses much smaller memory. For example, bootstrapping takes $6.75$ seconds for 7 bit plaintext space with 64 slots and $1381$ seconds for $GF(257^{128})$ plaintext space with 128 slots. We also implemented our improved digit extraction procedure for the BGV scheme in HElib.

Recent progress on NFS imposed a new estimation of the security of pairings. In this work we study the best attacks against some of the most popular pairings and propose new key sizes using an analysis which is more precise than the analysis in a recent article of Menezes, Sarkar and Singh. We also select pairing-friendly curves for standard security levels.

The field size $8^{91}+5$ for elliptic curve cryptography offers simplicity, security, and efficiency.

We present simpler and improved constructions of unbounded attribute-based encryption (ABE) schemes with constant-size public parameters under static assumptions in bilinear groups. Concretely, we obtain: - a simple and adaptively secure unbounded ABE scheme in composite-order groups, improving upon a previous construction of Lewko and Waters (Eurocrypt '11) which only achieves selective security; - an improved adaptively secure unbounded ABE scheme based on the $k$-linear assumption in prime-order groups with shorter ciphertexts and secret keys than those of Okamoto and Takashima (Asiacrypt '12); - the first adaptively secure unbounded ABE scheme for arithmetic branching programs under static assumptions. At the core of all of these constructions is a "bilinear entropy expansion" lemma that allows us to generate any polynomial amount of entropy starting from constant-size public parameters; the entropy can then be used to transform existing adaptively secure "bounded" ABE schemes into unbounded ones.

In this work we analyze the security of cubic cryptographic constructions with respect to rank weakness. We detail how to extend the big field idea from quadratic to cubic, and show that the same rank defect occurs. We extend the min-rank problem and propose an algorithm to solve it in this setting. We show that for fixed small rank, the complexity is even lower than for the quadratic case. However, the rank of a cubic polynomial in $n$ variables can be larger than $n$, and in this case the algorithm is very inefficient. We show that the rank of the differential is not necessarily smaller, rendering this line of attack useless if the rank is large enough. Similarly, the algebraic attack is exponential in the rank, thus useless for high rank.

We investigate the security of a public-key encryption scheme, the Indeterminate Equation Cryptosystem (IEC), introduced by Akiyama, Goto, Okumura, Takagi, Nuida, and Hanaoka at SAC 2017 as postquantum cryptography. They gave two parameter sets PS1 (n,p,deg X,q) = (80,3,1,921601) and PS2 (n,p,deg X,q) = (80,3,2,58982400019). The paper gives practical key-recovery and message-recovery attacks against those parameter sets of IEC through lattice basis-reduction algorithms. We exploit the fact that n = 80 is composite and adopt the idea of Gentry's attack against NTRU-Composite (EUROCRYPT2001) to this setting. The summary of our attacks follows: * On PS1, we recover 84 private keys from 100 public keys in 30–40 seconds per key. * On PS1, we recover partial information of all message from 100 ciphertexts in a second per ciphertext. * On PS2, we recover partial information of all message from 100 ciphertexts in 30 seconds per ciphertext. Moreover, we also give message-recovery and distinguishing attacks against the parameter sets with prime n, say, n = 83. We exploit another subring to reduce the dimension of lattices in our lattice-based attacks and our attack succeeds in the case of deg X = 2. * For PS2’ (n,p,deg X,q) = (83,3,2,68339982247), we recover 7 messages from 10 random ciphertexts within 61,000 seconds \approx 17 hours per ciphertext. * Even for larger n, we can fnd short vector from lattices to break the underlying assumption of IEC. In our experiment, we can found such vector within 330,000 seconds \approx 4 days for n = 113.

Ciphertext-policy attribute-based encryption (CP-ABE) is an access control mechanism where a data provider encrypts a secret message and then sends the ciphertext to the receivers according to the access policy which she/he decides. If the attributes of the receivers match the access policy, then they can decrypt the ciphertext. This paper shows a relation between ABE and identity-based encryption (IBE), and presents a bi-directional conversion between an access structure and identities. By the proposed conversion, the ABE scheme constructed from an IBE scheme will inherit the features, such as constant-size ciphertexts and anonymity, from the IBE scheme, and vice versa. It turns out that the proposed conversion also gives the first ABE achieving access structures with wildcard and constant-size ciphertexts/private keys.

By allowing a large number of users to behave as readers or writers, Multi-User Searchable Encryption (MUSE) raises new security and performance challenges beyond the typical requirements of Symmetric Searchable Encryption (SSE). In this paper we identify two core mandatory requirements of MUSE protocols being privacy in face of users colluding with the CSP and low complexity for the users, pointing that no existing MUSE protocol satisfies these two requirements at the same time. We then come up with the first MUSE protocol that satisfies both of them. The design of the protocol also includes new constructions for a secure variant of Bloom Filters (BFs) and multi-query Oblivious Transfer (OT).

In previous work I proposed a fully homomorphic encryption without bootstrapping which has the large size of ciphertext. This tme I propose the fully homomorphic public-key encryption scheme on non-associative octonion ring over finite field with the small size of ciphertext. In this scheme the size of ciphertext is one-third of the size in the scheme proposed before. Because proposed scheme adopts the medium text with zero norm, it is immune from the “p and -p attack”. As the proposed scheme is based on computational difficulty to solve the multivariate algebraic equations of high degree, it is immune from the Gröbner basis attack, the differential attack, rank attack and so on.

Proxy re-encryption (PRE) and Proxy re-signature (PRS) were introduced by Blaze, Bleumer and Strauss [Eurocrypt '98]. Basically, PRE allows a semi-trusted proxy to transform a ciphertext encrypted under one key into an encryption of the same plaintext under another key, without revealing the underlying plaintext. Since then, many interesting applications have been explored, and many constructions in various settings have been proposed, while PRS allows a semi-trusted proxy to transform Alice's signature on a message into Bob's signature on the same message, but the proxy cannot produce new valid signature on new messages for either Alice or Bob. Recently, for PRE related progress, Cannetti and Honhenberger [CCS '07] defined a stronger notion -- CCA-security and construct a bi-directional PRE scheme. Later on, several work considered CCA-secure PRE based on bilinear group assumptions. Very recently, Kirshanova [PKC '14] proposed the first single-hop CCA1-secure PRE scheme based on learning with errors (LWE) assumption. For PRS related progress, Ateniese and Hohenberger [CCS'05] formalized this primitive and provided efficient constructions in the random oracle model. At CCS 2008, Libert and Vergnaud presented the first multi-hop uni-directional proxy re-signature scheme in the standard model, using assumptions in bilinear groups. In this work, we first point out a subtle but serious mistake in the security proof of the work by Kirshanova. This reopens the direction of lattice-based CCA1-secure constructions, even in the single-hop setting. Then we construct a single-hop PRE scheme that is proven secure in our new tag-based CCA-PRE model. Next, we construct the first multi-hop PRE construction. Lastly, we also construct the first PRS scheme from lattices that is proved secure in our proposed unified security model

If quantum computers were built, they would pose concerns for public key cryptography as we know it. Among other cryptographic techniques, they would jeopardize the use of PKI X.509 certificates (RSA, ECDSA) used today for authentication. To overcome the concern, new quantum secure signature schemes have been proposed in the literature. Most of these schemes have significantly larger public key and signature sizes than the ones used today. Even though post-quantum signatures could work well for some usecases like software signing, there are concerns about the effect their size and processing cost would have on technologies using X.509 certificates. In this work, we investigate the viability of post-quantum signatures in X.509 certificates and protocols that use them (e.g. TLS, IKEv2). We prove that, in spite of common concerns, they could work in today's protocols and could be a viable solution to the emergence of quantum computing. We also quantify the overhead they introduce in protocol connection establishment and show that even though it is significant, it is not detrimental. Finally, we formalize the areas of further testing necessary to conclusively establish that the signature schemes standardized in NIST's PQ Project can work with X.509 certs in a post-quantum Internet.

Aggarwal, Joux, Prakash and Santha recently introduced a new potentially quantum-safe public-key cryptosystem, and suggested that a brute-force attack is essentially optimal against it. They consider but then dismiss both Meet-in-the-Middle attacks and LLL-based attacks. Very soon after their paper appeared, Beunardeau et al.\ proposed a practical LLL-based technique that seemed to significantly reduce the security of the AJPS system. In this paper we do two things. First, we show that a Meet-in-the-Middle attack can also be made to work against the AJPS system, using locality-sensitive hashing to overcome the difficulty that Aggarwal et al.\ saw for such attacks. We also present a quantum version of this attack. Second, we give a more precise analysis of the attack of Beunardeau et al., confirming and refining their results.

In this work we construct efficient aggregate signatures from the RSA assumption in the synchronized setting. In this setting, the signing algorithm takes as input a (time) period $t$ as well the secret key and message. A signer should sign at most once for each $t$. A set of signatures can be aggregated so long as they were all created for the same period $t$. Synchronized aggregate signatures are useful in systems where there is a natural reporting period such as log and sensor data, or for signatures embedded in a blockchain protocol where the creation of an additional block is a natural synchronization event. We design a synchronized aggregate signature scheme that works for a bounded number of periods $T$ that is given as a parameter to a global system setup. The big technical question is whether we can create solutions that will perform well with the large $T$ values that we might use in practice. For instance, if one wanted signing keys to last up to ten years and be able to issue signatures every second, then we would need to support a period bound of upwards of $2^{28}$. We build our solution in stages where we start with an initial solution that establishes feasibility, but has an impractically large signing time where the number of exponentiations and prime searches grows linearly with $T$. We prove this scheme secure in the standard model under the RSA assumption with respect to honestly-generated keys. We then provide a tradeoff method where one can tradeoff the time to create signatures with the space required to store private keys. One point in the tradeoff is where each scales with $\sqrt{T}$. Finally, we reach our main innovation which is a scheme where both the signing time and storage scale with $\lg{T}$ which allows for us to keep both computation and storage costs modest even for large values of $T$. Conveniently, our final scheme uses the same verification algorithm, and has the same distribution of public keys and signatures as the first scheme. Thus we are able to recycle the existing security proof for the new scheme. We also show how to extend our results to the identity-based setting in the random oracle model, which can further reduce the overall cryptographic overhead. We conclude with a detailed evaluation of the signing time and storage requirements for various practical settings of the system parameters.

During the last years public-key encryption schemes based on the hardness of ring-LWE have gained significant popularity. For real-world security applications assuming strong adversary models, a number of practical issues still need to be addressed. In this work we thus present an instance of ring-LWE encryption that is protected against active attacks (i.e., adaptive chosen-ciphertext attacks) and equipped with countermeasures against side-channel analysis. Our solution is based on a postquantum variant of the Fujisaki-Okamoto (FO) transform combined with provably secure first-order masking. To protect the key and message during decryption, we developed a masked binomial sampler that secures the re-encryption process required by FO. Our work shows that CCA2-secured RLWE-based encryption can be achieved with reasonable performance on constrained devices but also stresses that the required transformation and handling of decryption errors implies a performance overhead that has been overlooked by the community so far. With parameters providing 233 bits of quantum security, our implementation requires 4,176,684 cycles for encryption and 25,640,380 cycles for decryption with masking and hiding countermeasures on a Cortex-M4F. The first-order security of our masked implementation is also practically verified using the non-specific t-test evaluation methodology.

The provably secure Schnorr signature scheme is popular and efficient. However, each signature requires a fresh modular exponentiation, which is typically a costly operation. As the increased uptake in connected devices revives the interest in resource-constrained signature algorithms, we introduce a variant of Schnorr signatures that mutualises exponentiation efforts. Combined with precomputation techniques (which would not yield as interesting results for the original Schnorr algorithm), we can amortise the cost of exponentiation over several signatures: these signatures share the same nonce. Sharing a nonce is a deadly blow to Schnorr signatures, but is not a security concern for our variant. Our Scheme is provably secure, asymptotically-faster than Schnorr when combined with efficient precomputation techniques, and experimentally $2$ to $6$ times faster than Schnorr for the same number of signatures when using 1\,MB of static storage.

In this paper, we report on our implementation of a lattice-based Key-Policy Attribute-Based Encryption (KP-ABE) scheme, which uses short secret keys. The particular KP-ABE scheme can be used directly for Attribute-Based Access Control (ABAC) applications, as well as a building block in more involved applications and cryptographic schemes such as audit log encryption, targeted broadcast encryption, functional encryption, and program obfuscation. We adapt a recently proposed KP-ABE scheme [1] based on the Learning With Errors (LWE) problem to a more efficient scheme based on the Ring Learning With Errors (RLWE) problem, and demonstrate an implementation that can be used in practical applications. Our state-of-the-art implementation on graphics processing units (GPUs) shows that the homomorphic public key and ciphertext evaluation operations, which dominate the execution time of the KP-ABE scheme, can be performed in a reasonably short amount of time. Our practicality results also hold when scaled to a relatively large number of attributes. To the best of our knowledge, this is the first KP-ABE implementation that supports both ciphertext and public key homomorphism and the only experimental practicality results reported in the literature.

We construct two identity-based encryption (IBE) schemes. The first one is IBE satisfying key dependent message (KDM) security for user secret keys. The second one is IBE satisfying simulation-based receiver selective opening (RSO) security. Both schemes are secure against adaptive-ID attacks and do not have any a-priori bound on the number of challenge identities queried by adversaries in the security games. They are the first constructions of IBE satisfying such levels of security. Our constructions of IBE are very simple. We construct our KDM secure IBE by transforming KDM secure secret-key encryption using IBE satisfying only ordinary indistinguishability against adaptive-ID attacks (IND-ID-CPA security). Our simulation-based RSO secure IBE is based only on IND-ID-CPA secure IBE. We also demonstrate that our construction technique for KDM secure IBE is used to construct KDM secure public-key encryption. More precisely, we show how to construct KDM secure public-key encryption from KDM secure secret-key encryption and public-key encryption satisfying only ordinary indistinguishability against chosen plaintext attacks.

*Constrained* pseudorandom functions allow for delegating ``constrained'' secret keys that let one compute the function at certain authorized inputs---as specified by a constraining predicate---while keeping the function value at unauthorized inputs pseudorandom. In the *constraint-hiding* variant, the constrained key hides the predicate. On top of this, *programmable* variants allow the delegator to explicitly set the output values yielded by the delegated key for a particular set of unauthorized inputs. Recent years have seen rapid progress on applications and constructions of these objects for progressively richer constraint classes, resulting most recently in constraint-hiding constrained PRFs for arbitrary polynomial-time constraints from Learning With Errors~(LWE) [Brakerski, Tsabary, Vaikuntanathan, and Wee, TCC'17], and privately programmable PRFs from indistinguishability obfuscation (iO) [Boneh, Lewi, and Wu, PKC'17]. In this work we give a unified approach for constructing both of the above kinds of PRFs from LWE with subexponential $\exp(n^{\varepsilon})$ approximation factors. Our constructions follow straightforwardly from a new notion we call a *shift-hiding shiftable function*, which allows for deriving a key for the sum of the original function and any desired hidden shift function. In particular, we obtain the first privately programmable PRFs from non-iO assumptions.

We present several optimizations to SPHINCS, a stateless hash-based signature scheme proposed by Bernstein et al. in 2015: PORS, a more secure variant of the HORS few-time signature scheme used in SPHINCS; secret key caching, to speed-up signing and reduce signature size; batch signing, to amortize signature time and reduce signature size when signing multiple messages at once; mask-less constructions to reduce the key size and simplify the scheme; and Octopus, a technique to eliminate redundancies from authentication paths in Merkle trees. Based on a refined analysis of the subset resilience problem, we show that SPHINCS' parameters can be modified to reduce the signature size while retaining a similar security level and computation time. We then propose Gravity-SPHINCS, our variant of SPHINCS embodying the aforementioned tricks. Gravity-SPHINCS has shorter keys (32 and 64 bytes instead of $\approx1$ KB), shorter signatures ($\approx30$ KB instead of 41 KB), and faster signing and verification for a same security level as SPHINCS.

Witness encryption (WE) is a recent powerful encryption paradigm, which allows to encrypt a message using the description of a hard problem (a word in an NP-language) and someone who knows a solution to this problem (a witness) is able to efficiently decrypt the ciphertext. Recent work thereby focuses on constructing WE for NP complete languages (and thus NP). While this rich expressiveness allows flexibility w.r.t. applications, it makes existing instantiations impractical. Thus, it is interesting to study practical variants of WE schemes for subsets of NP that are still expressive enough for many cryptographic applications. We show that such WE schemes can be generically constructed from smooth projective hash functions (SPHFs). In terms of concrete instantiations of SPHFs (and thus WE), we target languages of statements proven in the popular Groth-Sahai (GS) non-interactive witness-indistinguishable/zero-knowledge proof framework. This allows us to provide a novel way to encrypt. In particular, encryption is with respect to a GS proof and efficient decryption can only be done by the respective prover. The so obtained constructions are entirely practical. To illustrate our techniques, we apply them in context of privacy-preserving exchange of information.

qDSA is a high-speed, high-security signature scheme that facilitates implementations with a very small memory footprint, a crucial requirement for embedded systems and IoT devices, and that uses the same public keys as modern Diffie--Hellman schemes based on Montgomery curves (such as Curve25519) or Kummer surfaces. qDSA resembles an adaptation of EdDSA to the world of Kummer varieties, which are quotients of algebraic groups by \(\pm1\). Interestingly, qDSA does not require any full group operations or point recovery: all computations, including signature verification, occur on the quotient where there is no group law. We include details on four implementations of qDSA, using Montgomery and fast Kummer surface arithmetic on the 8-bit AVR {ATmega} and 32-bit ARM Cortex~M0 platforms. We find that qDSA significantly outperforms state-of-the-art signature implementations in terms of stack usage and code size. We also include an efficient compression algorithm for points on fast Kummer surfaces, reducing them to the same size as compressed elliptic curve points for the same security level.

In delegated computing, prominent in the context of cloud computing, guaranteeing both the correctness and authenticity of computations is of critical importance. Homomorphic signatures can be used as cryptographic solutions to this problem. In this paper we solve the open problem of constructing a linearly homomorphic signature scheme that is secure against an active adversary under standard assumptions. We provide a construction based on the DL and CDH assumption. Furthermore we show how our scheme can be combined with homomorphic encryption under the framework of Linearly Homomorphic Authenticated Encryption with Public Verifiability. This way we can provide the first such scheme that is context hiding. Furthermore our solution even allows verification in constant time (in an amortized sense).

Key-encapsulation mechanisms (KEMs) are a common stepping stone for constructing public-key encryption. Secure KEMs can be built from diverse assumptions, including ones related to integer factorization, discrete logarithms, error correcting codes, or lattices. In light of the recent NIST call for post-quantum secure PKE, the zoo of KEMs that are believed to be secure continues to grow. Yet, on the question of which is the most secure KEM opinions are divided. While using the best candidate might actually not seem necessary to survive everyday life situations, placing a wrong bet can actually be devastating, should the employed KEM eventually turn out to be vulnerable. We introduce KEM combiners as a way to garner trust from different KEM constructions, rather than relying on a single one: We present efficient black-box constructions that, given any set of `ingredient' KEMs, yield a new KEM that is (CCA) secure as long as at least one of the ingredient KEMs is. As building blocks our constructions use cryptographic hash functions and blockciphers. Some corresponding security proofs require idealized models for these primitives, others get along on standard assumptions.

We initiate the study of public-key encryption (PKE) schemes and key-encapsulation mechanisms (KEMs) that retain security even when public parameters (primes, curves) they use may be untrusted and subverted. We define a strong security goal that we call ciphertext pseudo-randomness under parameter subversion attack (CPR-PSA). We also define indistinguishability (of ciphertexts for PKE, and of encapsulated keys from random ones for KEMs) and public-key hiding (also called anonymity) under parameter subversion attack, and show they are implied by CPR-PSA, for both PKE and KEMs. We show that hybrid encryption continues to work in the parameter subversion setting to reduce the design of CPR-PSA PKE to CPR-PSA KEMs and an appropriate form of symmetric encryption. To obtain efficient, elliptic-curve-based KEMs achieving CPR-PSA, we introduce efficiently-embeddable group families and give several constructions from elliptic-curves.

Certain RSA-based protocols, for instance in the domain of group signatures, require a prover to convince a verifier that a set of RSA parameters is well-structured (e.g., that the modulus is the product of two distinct primes and that the exponent is co-prime to the group order). Various corresponding proof systems have been proposed in the past, with different levels of generality, efficiency, and interactivity. This paper proposes two new proof systems for a wide set of properties that RSA and related moduli might have. The protocols are particularly efficient: The necessary computations are simple, the communication is restricted to only one round, and the exchanged messages are short. While the first protocol is based on prior work (improving on it by reducing the number of message passes from four to two), the second protocol is novel. Both protocols require a random oracle.

How to efficiently search over encrypted data is an important and interesting problem in the cloud era. To solve it, Boneh et al. introduced the notion of public key encryption with keyword search (PEKS), in 2004. However, in almost all the PEKS schemes an inside adversary may recover the keyword from a given trapdoor by exhaustively guessing the keywords offline. How to resist the inside keyword guessing attack in PEKS remains a hard problem. In this paper we propose introduce the notion of Public-key Authenticated Encryption with Keyword Search (PAEKS) to solve the problem, in which the data sender not only encrypts a keyword, but also authenticates it, so that a verifier would be convinced that the encrypted keyword can only be generated by the sender. We propose a concrete and efficient construction of PAEKS, and prove its security based on simple and static assumptions in the random oracle model under the given security models. Experimental results show that our scheme enjoys a comparable efficiency with Boneh et al.'s scheme.

Recently, Wang (2016) introduced a random linear code based quantum resistant public key encryp- tion scheme RLCE which is a variant of McEliece encryption scheme. In this paper, we introduce a revised version of the RLCE encryption scheme. The revised RLCE schemes are more efficient than the original RLCE scheme. Specifically, it is shown that RLCE schemes have smaller public key sizes com- pared to binary Goppa code based McEliece encryption schemes for corresponding security levels. The paper further proposes message padding schemes for RLCE to achieve IND-CCA2 security. Practical RLCE parameters for the security levels of 128, 192, and 256 bits and for the quantum security levels of 80, 110, and 144 are recommended. The implementation of the RLCE encryption scheme and software packages for analyzing the security strength of RLCE parameters are available at http://quantumca.org/

Supersingular isogeny Diffie-Hellman (SIDH) is a proposal for a quantum-resistant key exchange. The state-of-the-art implementation works entirely with Montgomery curves and basically can be divided into elliptic curve arithmetic and isogeny arithmetic. It is well known that twisted Edwards curves can provide a more efficient elliptic curve arithmetic. Therefore it was hinted by Costello and Hisil, that by using only Edwards curves for isogeny and curve arithmetic, or a hybrid scheme, that uses Edwards curve arithmetic and switches between the models whenever needed, a speedup in the computation may be gained. Following the latter case, we investigated how to efficiently switch between Montgomery and twisted Edwards curves in SIDH, and how to insert Edwards arithmetic in the current state-of-the-art implementation. We did not gain a speedup compared to the results of Costello, Longa, and Naehrig, but in some cases the performance of Edwards arithmetic is almost equally fast. Thus, we suppose that a hybrid scheme does not improve the performance of SIDH, but still can be interesting for platforms having special hardware acceleration for Edwards curves. However, a full Edwards SIDH version may give a speedup, if fast Edwards isogeny formulas can be found.

We present here new multivariate schemes that can be seen as HFE generalization having a property called `Two-Face'. Particularly, we present five such families of algorithms named `Dob', `Simple Pat', `General Pat', `Mac', and `Super Two-Face'. These families have connections between them, some of them are refinements or generalizations of others. Notably, some of these schemes can be used for public key encryption, and some for public key signature. We introduce also new multivariate quadratic permutations that may have interest beyond cryptography.

A new unconditionally secure multi-party quantum commitment is proposed in this paperby encoding the committed message to the phase of a quantum state. Multi-party means that there are more than one recipient in our scheme. We show that our quantum commitment scheme is unconditional hiding and binding, and hiding is perfect. Our technique is based on the interference of phase-encoded coherent states of light. Its security proof relies on the no-cloning theorem of quantum theory and the properties of quantum information.

This paper designs and analyzes a quantum algorithm to solve a system of $m$ quadratic equations in $n$ variables over a finite field ${\bf F}_q$. In the case $m=n$ and $q=2$, under standard assumptions, the algorithm takes time $2^{(t+o(1))n}$ on a mesh-connected computer of area $2^{(a+o(1))n}$, where $t\approx 0.45743$ and $a\approx 0.01467$. The area-time product has asymptotic exponent $t+a\approx 0.47210$. For comparison, the area-time product of Grover's algorithm has asymptotic exponent $0.50000$. Parallelizing Grover's algorithm to reach asymptotic time exponent $0.45743$ requires asymptotic area exponent $0.08514$, much larger than $0.01467$.

Scalar multiplication on Legendre form elliptic curves can be speeded up in two ways. One can perform the bulk of the computation either on the associated Kummer line or on an appropriate twisted Edwards form elliptic curve. This paper provides details of moving to and from between Legendre form elliptic curves and associated Kummer line and moving to and from between Legendre form elliptic curves and related twisted Edwards form elliptic curves. Further, concrete twisted Edwards form elliptic curves are identified which correspond to known Kummer lines at the 128-bit security level which provide very fast scalar multiplication on modern architectures supporting SIMD operations.

The Camenisch-Lysyanskaya (CL) signature is a very popular tool in cryptography, especially among privacy-preserving constructions. Indeed, the latter benefit from their numerous features such as randomizability. Following the evolution of pairing-based cryptography, with the move from symmetric pairings to asymmetric pairings, Pointcheval and Sanders (PS) proposed at CT-RSA '16 an alternative scheme which improves performances while keeping the same properties. Unfortunately, CL and PS signatures raise concerns in the cryptographic community because they both rely on interactive assumptions that essentially state their EUF-CMA security. This lack of precise security assessment is obviously a barrier to a widespread use of these signatures and a reason for preferring other constructions, such as the ones relying on $q$-type assumptions. In this paper, we study more thoroughly the security of these signatures and prove that it actually relies, for both constructions, on simple variants of the $\textsf{SDH}$ assumption, assuming a slight modification of the original constructions. Our work thus shows that the CL and PS signature schemes offer similar security guarantees as those provided by several other constructions using bilinear groups, and so that one can benefit from their interesting features without jeopardizing security.

A chameleon-hash function is a hash function that involves a trapdoor the knowledge of which allows one to find arbitrary collisions in the domain of the function. In this paper, we introduce the notion of chameleon-hash functions with ephemeral trapdoors. Such hash functions feature additional, i.e., ephemeral, trapdoors which are chosen by the party computing a hash value. The holder of the main trapdoor is then unable to find a second pre-image of a hash value unless also provided with the ephemeral trapdoor used to compute the hash value. We present a formal security model for this new primitive as well as provably secure instantiations. The first instantiation is a generic black-box construction from any secure chameleon-hash function. We further provide three direct constructions based on standard assumptions. Our new primitive has some appealing use-cases, including a solution to the long-standing open problem of invisible sanitizable signatures, which we also present.

Many web hosts are still vulnerable to one of the oldest attacks against RSA in TLS. We show that Bleichenbacher’s RSA vulnerability from 1998 is still very prevalent in the Internet and affects almost a third of the top 100 domains in the Alexa Top 1 Million list, among them Facebook and Paypal. We identified vulnerable products from at least eight different vendors and open source projects, among them F5, Citrix, Radware, Cisco, Erlang, Bouncy Castle, and WolfSSL. Further we have demonstrated practical exploitation by signing a message with the private key of facebook.com’s HTTPS certificate. Finally, we discuss countermeasures against Bleichenbacher attacks in TLS and recommend to deprecate the RSA encryption key exchange in TLS and the PKCS #1 v1.5 standard.

Multivariate Public Key Cryptography is a leading option for security in a post quantum society. In this paper we propose a new encryption scheme, EFLASH, and analyze its efficiency and security.

Following the emergence of Kim and Barbulescu's new number field sieve (exTNFS) algorithm at CRYPTO'16 [21] for solving discrete logarithm problem (DLP) over the finite field; pairing-based cryptography researchers are intrigued to find new parameters that confirm standard security levels against exTNFS. Recently, Barbulescu and Duquesne have suggested new parameters [3] for well-studied pairing-friendly curves i.e., Barreto-Naehrig (BN) [5], Barreto-Lynn-Scott (BLS-12) [4] and Kachisa-Schaefer-Scott (KSS-16) [19] curves at 128-bit security level (twist and sub-group attack secure). They have also concluded that in the context of Optimal-Ate pairing with their suggested parameters, BLS-12 and KSS-16 curves are more efficient choices than BN curves. Therefore, this paper selects the atypical and less studied pairing-friendly curve in literature, i.e., KSS-16 which offers quartic twist, while BN and BLS-12 curves have sextic twist. In this paper, the authors optimize Miller's algorithm of Optimal-Ate pairing for the KSS-16 curve by deriving efficient sparse multiplication and implement them. Furthermore, this paper concentrates on the Miller's algorithm to experimentally verify Barbulescu et al.'s estimation. The result shows that Miller's algorithm time with the derived pseudo 8-sparse multiplication is most efficient for KSS-16 than other two curves. Therefore, this paper defends Barbulescu and Duquesne's conclusion for 128-bit security.

Public-key solutions based on number theory, including RSA, ECC, and Diffie-Hellman, are subject to various quantum attacks, which makes such solutions less attractive long term. Certain group theoretic constructs, however, show promise in providing quantum-resistant cryptographic primitives because of the infinite, non-cyclic, non-abelian nature of the underlying mathematics. This paper introduces Kayawood Key Agreement protocol (Kayawood, or Kayawood KAP), a new group-theoretic key agreement protocol, that leverages the known NP-Hard shortest word problem (among others) to provide an Elgamal-style, Diffie-Hellman-like method. This paper also (i) discusses the implementation of and behavioral aspects of Kayawood, (ii) introduces new methods to obfuscate braids using Stochastic Rewriting, and (iii) analyzes and demonstrates Kayawood's security and resistance to known quantum attacks.

4-bit Linear Relations play an important role in Cryptanalysis of 4-bit Bijective Crypto S-boxes. 4-bit finite differences also a major part of cryptanalysis of 4-bit substitution boxes. Count of existence of all 4-bit linear relations, for all of 16 input and 16 output 4-bit bit patterns of 4-bit bijective crypto S-boxes said as S-boxes has been reported in Linear Cryptanalysis of 4-bit S-boxes. Count of existing finite differences from each element of output S-boxes to distant output S-boxes have been noted in Differential Cryptanalysis of S-boxes. In this paper a brief review of these cryptanalytic methods for 4-bit S-boxes has been introduced in a very lucid and conceptual manner. Two new Analysis Techniques, one to search for the existing Linear Approximations among the input Boolean Functions (BFs) and output BFs of a particular 4-bit S-Box has also been introduced in this paper. The search is limited to find the existing linear relations or approximations in the contrary to count the number existent linear relations among all 16 4-bit input and output bit patterns within all possible linear approximations. Another is to find number of balanced 4-bit BFs in difference output S-boxes. Better the number of Balanced BFs, Better the security.

We present a practical cryptanalysis of WalnutDSA, a digital signature algorithm trademarked by SecureRF. WalnutDSA uses techniques from permutation groups, matrix groups, and braid groups, and is designed to provide post-quantum security in lightweight IoT device contexts. The attack given in this paper bypasses the E-Multiplication and cloaked conjugacy search problems at the heart of the algorithm and forges signatures for arbitrary messages in approximately two minutes. We also discuss potential countermeasures to the attack.

Recently, Tao et al. presented a new simple and efficient multivariate pubic key encryption scheme based on matrix multiplica- tion, which is called Simple Matrix Scheme or ABC. Using linearization method, we propose a polynomial time algorithm, which directly solves an equivalent private key from the public key of ABC. Furthermore, our attack can also be applied to the variants of ABC since these variants have the same algebraic structure as the ABC scheme. Therefore, the ABC cryptosystem and its variants are insecure.

We perform a concrete security treatment of digital signature schemes obtained from canonical identification schemes via the Fiat-Shamir transform. If the identification scheme is rerandomizable and satisfies the weakest possible security notion (key-recoverability), then the implied signature scheme is unforgeability against chosen-message attacks in the multi-user setting in the random oracle model. The reduction loses a factor of roughly Qh, the number of hash queries. Previous security reductions incorporated an additional multiplicative loss of N, the number of users in the system. As an important application of our framework, we obtain a concrete security treatment for Schnorr signatures. Our analysis is done in small steps via intermediate security notions, and all our implications have relatively simple proofs. Furthermore, for each step we show the optimality of the given reduction via a meta-reduction.

Ciphertext-Policy Attribute-Based Encryption (CP-ABE) has been proposed to implement fine-grained access control. Data owners encrypt data with a certain access policy so that only data users whose attributes satisfy the access policy can decrypt the ciphertext. A user can be automatically assigned an access privilege based on whether his/her attributes satisfying a given access policy described by attributes and their logical relations. In order to provide more flexible policy-based access control, attribute-based revocation approaches had been proposed to provide the NOT logic on attributes to allow attribute-based revocation. However, previous solutions increase the attribute management overhead when considering each user’s ID as an attribute for more precise revocations at the individual user-level. To address this issue, in this paper, an ID-ABE scheme is presented, where a user’s ID is incorporated into the key generation procedure allowing user-ID-based revocation. In addition to ID-based revocation, ID-ABE also presents a hierarchical identity structure to build a delegation framework to enable group-based revocation. In the end, we also evaluate the performance of the proposed scheme in terms of computation, storage and communication overhead, which shows the practical value of the solution for secure data sharing applications.

Ciphertext Policy Attribute-Based Encryption (CP- ABE) has been proposed to implement the attribute-based access control model. In CP-ABE, data owners encrypt the data with a certain access policy such that only data users whose attributes satisfy the access policy could obtain the corresponding private decryption key from a trusted authority. Therefore, CP-ABE is considered as a promising fine-grained access control mechanism for data sharing where no centralized trusted third party exists, for example, cloud computing, mobile ad hoc networks (MANET), Peer-to-Peer (P2P) networks, information centric networks (ICN), etc.. As promising as it is, user revocation is a cumbersome problem in CP-ABE, thus impeding its application in practice. To solve this problem, we propose a new scheme named HIR-CP-ABE, which implements hierarchical identity- based user revocation from the perceptive of encryption. In particular, the revocation is implemented by data owners directly without any help from any third party. Compared with previous attribute-based revocation solutions, our scheme provides the following nice properties. First, the trusted authority could be offline after system setup and key distribution, thus making it applicable in mobile ad hoc networks, P2P networks, etc., where the nodes in the network are unable to connect to the trusted authority after system deployment. Second, a user does not need to update the private key when user revocation occurs. Therefore, key management overhead is much lower in HIR-CP-ABE for both the users and the trusted authority. Third, the revocation mechanism enables to revoke a group of users affiliated with the same organization in a batch without influencing any other users. To the best of our knowledge, HIR-CP-ABE is the first CP-ABE scheme to provide affiliation-based revocation functionality for data owners. Through security analysis and performance evaluation, we show that the proposed scheme is secure and efficient in terms of computation, communication and storage.

Ciphertext-Policy Attribute-Based Encryp- tion (CP-ABE) is an access control mechanism over encrypted data and well suited for secure group-based communication. However, it also suffers from the fol- lowing problem, i.e., it is impossible to build all de- sired groups. For example, if two group members have exactly the same attributes, how to construct a group including only one of the two members? Obviously, at- tributes alone cannot distinguish these two members, therefore existing CP-ABE solutions do not work. To address this issue, in this paper, we present a new CP-ABE scheme (called IR-CP-ABE) that incorporates an Identity-based Revocation capability. With IR-CP-ABE, an access policy will be constructed by not only group members’ attributes but also their identities. To build a group, first, build a candidate group based on all de- sired group members’ attributes; second, remove unde- sired members by revoking their identities. By evaluat- ing the security and efficiency of a proposed construc- tion, we show that the IR-CP-ABE scheme is secure and efficient for practical applications.

The HFEv- signature scheme is one of the most studied multivariate schemes and one of the major candidates for the upcoming standardization of post-quantum digital signature schemes. In this paper, we propose three new attack strategies against HFEv-, each of them using the idea of projection. Especially our third attack is very effective and is, for some parameter sets, the most efficient known attack against HFEv-. Furthermore, our attack requires much less memory than direct and rank attacks. By our work, we therefore give new insights in the security of the HFEv- signature scheme and restrictions for the parameter choice of a possible future standardized HFEv- instance.

This paper studies ways to backdoor lattice-based systems following Young and Yung's work on backdooring RSA and discrete-log based systems. For the NTRU encryption scheme we show how to build a backdoor and to change the system so that each ciphertext leaks information about the plaintext to the owner of the backdoor. For signature schemes the backdoor leaks information about the signing key to the backdoor owner. As in Young and Yung's work the backdoor uses the freedom that random selections offer in the protocol to hide a secret message encrypted to the backdoor owner. The most interesting and very different part though is how to hide and retrieve the hidden messages.

The HFEv- signature scheme is one of the most promising candidates for post-quantum digital signatures. Most notably here is the short signature size of the scheme. It has long been known that direct attacks against HFEv- systems work more efficiently than against random systems. The reason for this was found by Jintai Ding et al., who proved an upper bound on the degree of regularity of these systems. However, not much is known about the efficiency of the hybrid approach against the HFEv- scheme. In order to find suitable parameter sets for HFEv- for higher levels of security, this topic has to be studied in more detail. In this article we consider this question by performing a large number of computer experiments. As our experiments show, guessing variables does not help to speed up direct attacks against HFEv- systems. Therefore, in the parameter selection of these schemes, we do not have to consider the hybrid approach. Furthermore, we develop in this article a simple formula to estimate the degree of regularity of a determined HFEv- system. Together with our results on the behavior of the hybrid approach, this formula gives us an easy way to estimate the complexity of direct attacks against HFEv- systems.

Higher-level cryptographic privacy-enhancing protocols such as anonymous credentials, voting schemes, and e-cash are often constructed by suitably combining signature, commitment, and encryption schemes with zero-knowledge proofs. Indeed, a large body of protocols have been constructed in that manner from Camenisch-Lysyanskaya signatures and generalized Schnorr proofs. In this paper, we build a similar framework for lattice-based schemes by presenting a signature and commitment scheme that are compatible with Lyubashevsky's Fiat-Shamir proofs with abort, currently the most efficient zero-knowledge proofs for lattices. To cope with the relaxed soundness guarantees of these proofs, we define corresponding notions of relaxed signature and commitment schemes. We demonstrate the flexibility and efficiency of our new primitives by constructing a new lattice-based anonymous attribute token scheme and providing concrete parameters to securely instantiate this scheme.

Quantum computing poses challenges to public key signatures as we know them today. LMS and XMSS are two hash based signature schemes that have been proposed in the IETF as quantum secure. Both schemes are based on well-studied hash trees, but their similarities and differences have not yet been discussed. In this work, we attempt to compare the two standards. We compare their security assumptions and quantify their signature and public key sizes. We also address the computation overhead they introduce. Our goal is to provide a clear understanding of the schemes’ similarities and differences for implementers and protocol designers to be able to make a decision as to which standard to chose.

This article appeared as Chapter 9 of the book "Topics in Computational Number Theory inspired by Peter L. Montgomery", edited by Joppe W. Bos and Arjen K. Lenstra and published by Cambridge University Press. See https://www.cambridge.org/9781107109353.

NTRUEncrypt is a fast lattice-based cryptosystem and a probable alternative of the existing public key schemes. The existing provable-secure NTRUEncrypts are limited by the cyclotomic field it works on - the prime-power cyclotomic field. This is worth worrying, due to the subfield attack methods proposed in $2016$. Also, the module used in computation and security parameters rely heavily on the choice of plaintext space. These disadvantages restrict the applications of NTRUEncrypt. In this paper, we give a new provable secure NTRUEncrypt in standard model under canonical embedding over any cyclotomic field. We give an reduction from a simple variant of RLWE - an error distribution discretized version of RLWE, hence from worst-case ideal lattice problems, to our NTRUEncrypt. In particular, we get a union bound for reduction parameters and module for all choices of plaintext space, so that our NTRUEncrypt can send more encrypted bits in one encrypt process with higher efficiency and stronger security. Furthermore, our scheme's decryption algorithm succeeds with probability $1-n^{\o(\sqrt{n\log n})}$ comparing with the previous works' $1-n^{-\o(1)}$, making our scheme more practical in theory.

This chapter describes the developments since 1970 in general purpose integer factoring and highlights the contributions of Peter L. Montgomery. This article appeared as Chapter 5 of the book "Topics in Computational Number Theory inspired by Peter L. Montgomery", edited by Joppe W. Bos and Arjen K. Lenstra and published by Cambridge University Press. See www.cambridge.org/9781107109353.

The KMOV scheme is a public key cryptosystem based on an RSA modulus $n=pq$ where $p$ and $q$ are large prime numbers with $p\equiv q\equiv 2\pmod 3$. It uses the points of an elliptic curve with equation $y^2\equiv x^3+b\pmod n$. In this paper, we propose a generalization of the KMOV cryptosystem with a prime power modulus of the form $n=p^{r}q^{s}$ and study its resistance to the known attacks.

Let $N=pq$ be an RSA modulus with unknown factorization. Some variants of the RSA cryptosystem, such as LUC, RSA with Gaussian primes and RSA type schemes based on singular elliptic curves use a public key $e$ and a private key $d$ satisfying an equation of the form $ed- k\left(p^2-1\right)\left(q^2-1\right)=1$. In this paper, we consider the general equation $ex-\left(p^2-1\right)\left(q^2-1\right)y=z$ and present a new attack that finds the prime factors $p$ and $q$ in the case that $x$, $y$ and $z$ satisfy a specific condition. The attack combines the continued fraction algorithm and Coppersmith's technique and can be seen as a generalization of the attacks of Wiener and Blömer-May on RSA.

In this paper we introduce NewHope-Simple, a variant of the NewHope Ring-LWE-based key exchange that is using a straight-forward transformation from Ring-LWE encryption to a passively secure KEM (or key-exchange scheme). The main advantage of NewHopeLP-Simple over NewHope is simplicity. In particular, it avoids the error-reconciliation mechanism originally proposed by Ding. The explanation of his method, combined with other tricks, like unbiasing the key following Peikert's tweak and using the quantizer $D_4$ to extract one key bit from multiple coefficients, takes more than three pages in the NewHope-Simple paper. The price for that simplicity is small: one of the exchanged messages increases in size by $6.25\%$ from $2048$ bytes to $2176$ bytes. The security of NewHopeLP is the same as the security of NewHope; the performance is very similar.

At EUROCRYPT 2013, Garg, Gentry and Halevi proposed a candidate construction (later referred as GGH13) of cryptographic multilinear map (MMap). Despite weaknesses uncovered by Hu and Jia (EUROCRYPT 2016), this candidate is still used for designing obfuscators. The naive version of the GGH13 scheme was deemed susceptible to averaging attacks, i.e., it could suffer from a statistical leak (yet no precise attack was described). A variant was therefore devised, but it remains heuristic. Recently, to obtain MMaps with low noise and modulus, two variants of this countermeasure were developed by Döttling et al. (EPRINT:2016/599). In this work, we propose a systematic study of this statistical leak for all these GGH13 variants. In particular, we confirm the weakness of the naive version of GGH13. We also show that, among the two variants proposed by Döttling et al., the so-called conservative method is not so effective: it leaks the same value as the unprotected method. Luckily, the leak is more noisy than in the unprotected method, making the straightforward attack unsuccessful. Additionally, we note that all the other methods also leak values correlated with secrets. As a conclusion, we propose yet another countermeasure, for which this leak is made unrelated to all secrets. On our way, we also make explicit and tighten the hidden exponents in the size of the parameters, as an effort to assess and improve the efficiency of MMaps.

As an important cryptographic primitive in cloud computing and outsourced computation, fully homomorphic encryption (FHE) is an animated area of modern cryptography. However, the efficiency of FHE has been a bottleneck that impeding its application. According to Gentry’s blueprint, bootstrapping, which is used to decrease ciphertext errors, is the most important process in FHE. However, bootstrapping is also the most expensive process that affecting the efficiency of the whole system. Firstly, we notice that, hundreds of serial homomorphic additions take most of the time of bootstrapping. We made use of the properties of Boolean circuit to reduce the number of serial homomorphic additions by two-thirds, and thus constructed an efficient FHE scheme with bootstrapping in 10ms. Secondly, the most expensive parts in our bootstrapping, EHCM and addition operations of multiple matrices, can be accelerated by parallel. This parallel may accelerate the bootstrapping. At last, we found a set of more efficient combination of parameters. As a result, our security parameter level is 128 bits and the correctness is elevated, compared with TFHE scheme in ASIACRYPT 2016. Experiments show that the running time of our bootstrapping is 10ms, which is only 52 percent of TFHE, and is less than CGGI17.

An identity-based encryption scheme enables the efficient distribution of keys in a multi-user system. Such schemes are particularly attractive in resource constrained environments where critical resources such as processing power, memory and bandwidth are severely limited. This research examines the first pragmatic lattice-based IBE scheme pre- sented by Ducas, Lyubashevsky and Prest in 2014 and brings it into the realm of practicality for use on small devices. This is the first standalone ANSI C implementation of all the software elements of the scheme with improved performance. User Key Extraction demonstrates a 180% speed increase and Encrypt and Decrypt demonstrate increases of over 500% and 1200% respectively for 80-bit security on an Intel Core i7-6700 CPU at 4.0 GHz, with similar accelerations for 192-bit security, compared with Prest’s NTL proof-of-concept implementation on an Intel Core i5-3210M CPU at 2.5GHz. In addition, we provide a range of suggestions to further enhance performance.

We give precise quantum resource estimates for Shor's algorithm to compute discrete logarithms on elliptic curves over prime fields. The estimates are derived from a simulation of a Toffoli gate network for controlled elliptic curve point addition, implemented within the framework of the quantum computing software tool suite LIQ$Ui|\rangle$. We determine circuit implementations for reversible modular arithmetic, including modular addition, multiplication and inversion, as well as reversible elliptic curve point addition. We conclude that elliptic curve discrete logarithms on an elliptic curve defined over an $n$-bit prime field can be computed on a quantum computer with at most $9n + 2\lceil\log_2(n)\rceil+10$ qubits using a quantum circuit of at most $448 n^3 \log_2(n) + 4090 n^3$ Toffoli gates. We are able to classically simulate the Toffoli networks corresponding to the controlled elliptic curve point addition as the core piece of Shor's algorithm for the NIST standard curves P-192, P-224, P-256, P-384 and P-521. Our approach allows gate-level comparisons to recent resource estimates for Shor's factoring algorithm. The results also support estimates given earlier by Proos and Zalka and indicate that, for current parameters at comparable classical security levels, the number of qubits required to tackle elliptic curves is less than for attacking RSA, suggesting that indeed ECC is an easier target than RSA.

Fully Homomorphic Encryption (FHE) schemes allow arbitrary computations on encrypted data, making them a promising tool for numerous use cases that require outsourcing computation on private data to untrusted parties. FHE schemes operate over finite fields while many use cases call for real numbers, requiring appropriate encoding of the data into the scheme's plaintext space. However, the choice of encoding can tremendously impact the computational effort on the encrypted data. Although the question of selecting the encoding arises immediately in practice, users are mostly left alone in choosing it. In this work, we investigate this question for applications that operate over integers and rational numbers using $p$-adic encoding and the extensions $p$'s Complement and Sign-Magnitude, based on three natural metrics: the number of finite field additions, multiplications, and the multiplicative depth. Our results are partly constructive and partly negative: For the first two metrics, an optimal choice exists and we state it explicitly. However, for multiplicative depth the optimum depends on the use-case and does not exist globally. We do show how to choose this best encoding depending on the use-case.

A watermarking scheme for a public-key cryptographic functionality enables the embedding of a mark in the instance of the secret-key algorithm such that the functionality of the original scheme is maintained, while it is infeasible for an adversary to remove the mark (unremovability) or mark a fresh object without the marking key (unforgeability). Cohen et al. [STOC'16] has provided constructions for watermarking arbitrary cryptographic functionalities; the resulting schemes rely on indistinguishability obfuscation (iO) and leave two important open questions: (i) the realization of both unremovability and unforgeability, and (ii) schemes the security of which reduces to simpler hardness assumptions than iO. In this paper we provide a new definitional framework that distinguishes between watermarking cryptographic functionalities and implementations (think of ElGamal encryption being an implementation of the encryption functionality), while at the same time provides a meaningful relaxation of the watermarking model that enables both unremovability and unforgeability under minimal hardness assumptions. In this way we can answer questions regarding the ability to watermark a given implementation of a cryptographic functionality which is more refined compared to the question of whether a watermarked implementation functionality exists. Taking advantage of our new formulation we present the first constructions for watermarking public key encryption that achieve both unremovability and unforgeability under minimal hardness assumptions. Our first construction enables the watermarking of any public-key encryption implementation assuming only the existence of one-way functions for private key detection. Our second construction is at the functionality level and uses a stronger assumption (existence of identity-based encryption (IBE)) but supports public detection of the watermark.

Asymptotically, the best known algorithms for solving the Shortest Vector Problem (SVP) in a lattice of dimension $n$ are sieve algorithms, which have heuristic complexity estimates ranging from $(4/3)^{n+o(n)}$ down to $(3/2)^{n/2 +o(n)}$ when Locality Sensitive Hashing techniques are used. Sieve algorithms are however outperformed by pruned enumeration algorithms in practice by several orders of magnitude, despite the larger super-exponential asymptotical complexity $2^{\Theta(n \log n)}$ of the latter. In this work, we show a concrete improvement of sieve-type algorithms. Precisely, we show that a few calls to the sieve algorithm in lattices of dimension less than $n-d$ solves SVP in dimension $n$, where $d = \Theta(n/\log n)$. Although our improvement is only sub-exponential, its practical effect in relevant dimensions is quite significant. We implemented it over a simple sieve algorithm with $(4/3)^{n+o(n)}$ complexity, and it outperforms the best sieve algorithms from the literature by a factor of $10$ in dimensions $70$-$80$. It performs less than an order of magnitude slower than pruned enumeration in the same range. By design, this improvement can also be applied to most other variants of sieve algorithms, including LSH sieve algorithms and tuple-sieve algorithms. In this light, we may expect sieve-techniques to outperform pruned enumeration in practice in the near future.

This paper suggests to use rounded Gaussians in place of dis- crete Gaussians in rejection-sampling-based lattice signature schemes like BLISS. We show that this distribution can efficiently be sampled from while additionally making it easy to sample in constant time, systematically avoiding recent timing-based side-channel attacks on lattice-based signatures. We show the effectiveness of the new sampler by applying it to BLISS, prove analogues of the security proofs for BLISS, and present an implementation that runs in constant time. Our implementation needs no precomputed tables and is twice as fast as the variable-time CDT sampler posted by the BLISS authors with precomputed tables.

Direct Anonymous Attestation (DAA) is a complex cryptographic protocol that has been widely deployed in practice, with more than 500 million machines in the market that are already equipped with its hardware, the so-called Trusted Module Platform (TPM). While formalizing the right security model for such a complex protocol has triggered a dense line of research, all the proposed DAA schemes so far are based on number-theoretic problems that are known to be vulnerable to quantum computer attacks. In this paper, we propose the first lattice-based DAA scheme that is secure w.r.t. the most up-to-date security model proposed by Camenisch et al. More precisely, our lattice-based DAA scheme is secure in the Universally Composable (UC) security model. Furthermore, we give (amongst others) the first lattice-based DAA scheme providing user controlled linkability that is realized by means of a new lattice-based MAC/TAG construction which could be of independent interest.

Current widely-used key exchange (KE) mechanisms will be vulnerable to quantum attacks when sufficiently strong quantum computers become available. Therefore, devising quantum-resistant replacements that combine efficiency with solid security guarantees is an important and challenging task. This paper proposes several contributions towards this goal. First, we introduce CAKE, a key encapsulation algorithm based on the QC-MDPC McEliece encryption scheme, with two major improvements: a) the use of ephemeral keys that defeats a recent reaction attack against MDPC decoding of the corresponding encryption scheme and b) a highly efficient key generation procedure for QC-MDPC-based cryptosystems. Then, we present an authenticated key exchange protocol based on CAKE, which is suitable for the Internet Key Exchange (IKE) standard. We prove that CAKE is IND-CPA secure, that the protocol is SK-Secure, and suggest practical parameters. Compared to other post-quantum schemes, we believe that CAKE is a promising candidate for post-quantum key exchange standardization.

We provide an alternative method for constructing lattice-based digital signatures which does not use the ``hash-and-sign'' methodology of Gentry, Peikert, and Vaikuntanathan (STOC 2008). Our resulting signature scheme is secure, in the random oracle model, based on the worst-case hardness of the $\tilde{O}(n^{1.5})-SIVP$ problem in general lattices. The secret key, public key, and the signature size of our scheme are smaller than in all previous instantiations of the hash-and-sign signature, and our signing algorithm is also much simpler, requiring just a few matrix-vector multiplications and rejection samplings. We then also show that by slightly changing the parameters, one can get even more efficient signatures that are based on the hardness of the Learning With Errors problem. Our construction naturally transfers to the ring setting, where the size of the public and secret keys can be significantly shrunk, which results in the most practical to-date provably secure signature scheme based on lattices.

In this paper, we will study some possible generalizations of the famous Diffie-Hellman algorithm. As we will see, at the end, most of these generalizations will not be secure or will be equivalent to some classical schemes. However, these results are not always obvious and moreover our analysis will present some interesting connections between the concepts of commutativity, associativity, and public key cryptography.

Many digital signature schemes rely on random numbers that are unique and non-predictable per signature. Failures of random number generators may have catastrophic effects such as compromising private signature keys. In recent years, many widely-used cryptographic technologies adopted deterministic signature schemes because they are presumed to be safer to implement. In this paper, we analyze the security of deterministic ECDSA and EdDSA signature schemes and show that the elimination of random number generators in these schemes enables new kinds of fault attacks. We formalize these attacks and introduce practical attack scenarios against EdDSA using the Rowhammer fault attack. EdDSA is used in many widely used protocols such as TLS, SSH and IPSec, and we show that these protocols are not vulnerable to our attack. We formalize the necessary requirements of protocols using these deterministic signature schemes to be vulnerable, and discuss mitigation strategies and their effect on fault attacks against deterministic signature schemes.

Hash Proof Systems or Smooth Projective Hash Functions (SPHFs) are a form of implicit arguments introduced by Cramer and Shoup at Eurocrypt'02. They have found many applications since then, in particular for authenticated key exchange or honest-verifier zero-knowledge proofs. While they are relatively well understood in group settings, they seem painful to construct directly in the lattice setting. Only one construction of an SPHF over lattices has been proposed in the standard model, by Katz and Vaikuntanathan at Asiacrypt'09. But this construction has an important drawback: it only works for an ad-hoc language of ciphertexts. Concretely, the corresponding decryption procedure needs to be tweaked, now requiring $q$ many trapdoor inversion attempts, where $q$ is the modulus of the underlying Learning With Errors (LWE) problem. Using harmonic analysis, we explain the source of this limitation, and propose a way around it. We show how to construct SPHFs for standard languages of LWE ciphertexts, and explicit our construction over a tag-IND-CCA2 encryption scheme à la Micciancio-Peikert (Eurocrypt'12). We then improve our construction and our analysis in the case where the tag is known in advance or fixed (in the latter case, the scheme is only IND-CPA) with a super-polynomial modulus, to get a stronger type of SPHF, which was never achieved before for any language over lattices. Finally, we conclude with applications of these SPHFs: password-based authenticated key exchange, honest-verifier zero-knowledge proofs, and a relaxed version of witness encryption.

Current signature and encryption schemes secure against continual leakage fail completely if the key in any time period is fully exposed. We suggest forward security as a second line of defense, so that in the event of full exposure of the current secret key, at least uses of keys prior to this remain secure, a big benefit in practice. (For example if the signer is a certificate authority, full exposure of the current secret key would not invalidate certificates signed under prior keys.) We provide definitions for signatures and encryption that are forward-secure under continual leakage. Achieving these definitions turns out to be challenging, and we make initial progress with some constructions and transforms.

Deterministic signature schemes are becoming more popular, as illustrated by the deterministic variant of ECDSA and the popular EdDSA scheme, since eliminating the need for high-quality randomness might have some advantages in certain use-cases. In this paper we outline a range of differential fault attacks and a differential power analysis attack against such deterministic schemes. This shows, contrary to some earlier works, that such signature schemes are not naturally protected against such advanced attacks. We discuss different countermeasures and propose to include entropy for low-cost protection against these attacks in scenarios where these attack vectors are a real threat: this does not require to change the key generation or the verification methods and results in a signature scheme which offers high performance and security for a wide range of use-cases.

Ed25519 is an instance of the Elliptic Curve based signature scheme EdDSA that was recently introduced to solve an inconvenience of the more established ECDSA. Namely, both schemes require the generation of a random value (scalar of the ephemeral key pair) during the signature generation process and the secrecy of this random value is critical for security: knowledge of one such a random value, or partial knowledge of a series of them, allows reconstructing the signer's private key. In ECDSA it is not specified how to generate this random value and hence implementations critically rely on the quality of random number generators and are challenging to implement securely. EdDSA removes this dependence by deriving the secret deterministically from the message and a long-term auxiliary key using a cryptographic hash function. The feature of determinism has received wide support as enabling secure implementations and in particular deployment of Ed25519 is spectacular. Today Ed25519 is used in numerous security protocols, networks and both software and hardware security products e.g. OpenSSH, Tor, GnuPG etc. In this paper we show that in use cases where power or electromagnetic leakage can be exploited, exactly the mechanism that makes EdDSA deterministic complicates its secure implementation. In particular, we break an Ed25519 implementation in WolfSSL, which is a suitable use case for IoT applications. We apply differential power analysis (DPA) on the underlying hash function, SHA-512, requiring only 4000 traces. Finally, we present a tweak to the EdDSA protocol that is cheap and effective against the described attack while keeping the claimed advantage of EdDSA over ECDSA in terms of featuring less things that can go wrong e.g. the required high-quality randomness. However, we do argue with our countermeasure that some randomness (that need not be perfect) might be hard to avoid.

Attribute-based encryption (ABE) is a cryptographic primitive which supports fine-grained access control on encrypted data, making it an appealing building block for many applications. In this paper, we propose, implement, and evaluate fully automated methods for proving security of ABE in the Generic Bilinear Group Model (Boneh, Boyen, and Goh, 2005, Boyen, 2008), an idealized model which admits simpler and more efficient constructions, and can also be used to find attacks. Our method is applicable to Rational-Fraction Induced ABE, a large class of ABE that contains most of the schemes from the literature, and relies on a Master Theorem, which reduces security in the GGM to a (new) notion of symbolic security, which is amenable to automated verification using constraint- based techniques. We relate our notion of symbolic security for Rational-Fraction Induced ABE to prior notions for Pair Encodings. Finally, we present several applications, including automated proofs for new schemes.

Indistinguishability obfuscation (iO) is a powerful cryptographic tool often employed to construct a variety of core cryptographic primitives such as public key encryption and signatures. In this paper, we focus on the employment of iO in order to construct short signatures with strong security guarantees (i.e., adaptive security) that provide a very efficient signing process for resource constrained devices. Sahai and Waters (SW) (STOC 2014) initially explored the construction of iO-based short signature schemes but their proposal provides selective security. Ramchen and Waters (RW) (CCS 2014) attempted to provide stronger security guarantees (i.e., adaptive security) but their proposal is much more computationally expensive than the SW proposal. In this work, we propose an iO-based short signature scheme that provides adaptive security, fast signing for resource-constrained devices and is much more cost-efficient than the RW signature scheme. More precisely, we employ a puncturable PRF with a fixed length input to get a fast and adaptively secure signature scheme without any additional hardness assumption as in the SW signature scheme. To achieve this goal, we employ the technique of Hofheinz et al. called "delayed backdoor programming" using a random oracle, which allows to embed an execution thread that will only be invoked by special inputs generated using secret key information. Furthermore, we compare the cost of our signature scheme in terms of the cost of the underlying PRG used by the puncturable PRF. Our scheme has a much lower cost than the RW scheme, while providing strong security guarantees (i.e., adaptive security).

In anonymous identity-based encryption (IBE), ciphertexts not only hide their corresponding messages, but also their target identity. We construct an anonymous IBE scheme based on the Computational Diffie-Hellman (CDH) assumption in general groups (and thus, as a special case, based on the hardness of factoring Blum integers). Our approach extends and refines the recent tree-based approach of Cho et al. (CRYPTO '17) and Döttling and Garg (CRYPTO '17). Whereas the tools underlying their approach do not seem to provide any form of anonymity, we introduce two new building blocks which we utilize for achieving anonymity: blind garbled circuits (which we construct based on any one-way function), and blind batch encryption (which we construct based on CDH). We then further demonstrate the applicability of our newly-developed tools by showing that batch encryption implies a public-key encryption scheme that is both resilient to leakage of a $(1-o(1))$-fraction of its secret key, and KDM secure (or circular secure) with respect to all linear functions of its secret key (which, in turn, is known to imply KDM security for bounded-size circuits). These yield the first high-rate leakage-resilient encryption scheme and the first KDM-secure encryption scheme based on the CDH or Factoring assumptions. Finally, relying on our techniques we also construct a batch encryption scheme based on the hardness of the Learning Parity with Noise (LPN) problem, albeit with very small noise rate $\Omega(\log^2(n)/n)$. Although this batch encryption scheme is not blind, we show that it still implies standard (i.e., non-anonymous) IBE, leakage resilience and KDM security. IBE and high-rate leakage resilience were not previously known from LPN, even with extremely low noise.

We introduce Multi Tree XMSS (XMSS^MT), a hash-based signature scheme that can be used to sign a virtually unlimited number of messages. It is provably forward and hence EU-CMA secure in the standard model and improves key and signature generation times compared to previous schemes. XMSS^MT has --- like all practical hash-based signature schemes --- a lot of parameters that control different trade-offs between security, runtimes and sizes. Using linear optimization, we show how to select provably optimal parameter sets for different use cases.

We present WOTS+, a Winternitz type one-time signature scheme (WOTS). We prove that WOTS+ is strongly unforgeable under chosen message attacks in the standard model. Our proof is exact and tight. The first property allows us to compute the security of the scheme for given parameters. The second property allows for shorter signatures than previous proposals without lowering the security. This improvement in signature size directly carries over to all recent hash-based signature schemes. I.e. we can reduce the signature size by more than 50% for XMSS+ at a security level of 80 bits. As the main drawback of hash-based signature schemes is assumed to be the signature size, this is a further step in making hash-based signatures practical.

We formally define and give the first construction of (leveled) threshold fully homomorphic encryption for any access structure induced by a monotone boolean formula and in particular for the threshold access structure. Our construction is based on the learning with errors assumption and can be instantiated with any existing homomorphic encryption scheme that satisfies fairly general conditions, such as Gentry, Sahai, Waters (CRYPTO 2013) and Brakerski, Gentry, Vaikuntanathan (ITCS 2012). From threshold homomorphic encryption, we construct function secret sharing and distributed pseudorandom functions for the aforementioned access structures. No such constructions were known prior to this work.

We develop a general approach to thresholdizing a large class of (non-threshold) cryptographic schemes. We show how to add threshold functionality to CCA-secure public-key encryption (PKE), signature schemes, pseudorandom functions, and others primitives. To do so, we introduce a general tool, called a universal thresholdizer, from which many threshold systems are possible. The tool builds upon a lattice-based fully-homomorphic encryption (FHE) system. Applying the tool to a (non-threshold) lattice-based signature, gives the first single-round threshold signature from the learning with errors problem (LWE). Applying the tool to a (non-threshold) lattice-base CCA-secure PKE, gives a single-round lattice-based threshold CCA-secure PKE.

We show that the Winternitz one-time signature scheme is existentially unforgeable under adaptive chosen message attacks when instantiated with a family of pseudo random functions. Compared to previous results, which require a collision resistant hash function, our result provides significantly smaller signatures at the same security level. We also consider security in the strong sense and show that the Winternitz one-time signature scheme is strongly unforgeable assuming additional properties of the pseudo random function. In this context we formally define several key-based security notions for function families and investigate their relation to pseudorandomness. All our reductions are exact and in the standard model and can directly be used to estimate the output length of the hash function required to meet a certain security level.

GGH13, CLT13 and GGH15 of multilinear maps suffer from zeroizing attacks. In this paper, we present a new construction of multilinear maps using a variant of ring-LWE (vRLWE). Furthermore, we also present two new variants of vRLWE, which respectively support the applications of multipartite key exchange and witness encryption. At the same time, we also present a new variant of GGH13 using matrix form. The security of our construction depends upon new hardness assumptions.

In contrast to classical signature schemes, such as RSA or ECDSA signatures, the lattice-based signature scheme ring-TESLA is expected to be resistant even against quantum adversaries. Due to a recent key recovery from a lattice-based implementation, it becomes clear that cache side channels are a serious threat for lattice-based implementations. In this article, we analyze an existing implementation of ring-TESLA against cache side channels. To reduce the effort for manual code inspection, we selectively employ automated program analysis. The leakage bounds we compute with program analysis are sound overapproximations of cache-side-channel leakage. We detect four cache-side-channel vulnerabilities in the implementation of ring-TESLA. Since two vulnerabilities occur in implementations of techniques common to lattice-based schemes, they are also interesting beyond ring-TESLA. Finally, we show how the detected vulnerabilities can be mitigated effectively.

Keeping correct and informative log files is crucial for system maintenance, security and forensics. Cryptographic logging schemes offer integrity checks that protect a log file even in the case where an attacker has broken into the system. A relatively recent feature of these schemes is resistance against truncations, i.e. the deletion and/or replacement of the end of the log file. This is especially relevant as system intruders are typically interested in manipulating the later log entries that point towards their attack. However, there are not many schemes that are resistant against truncating the log file. Those that are have at least one of the following disadvantages: They are memory intensive (they store at least one signature per log entry), or fragile (i.e. a single error in the log renders the signature invalid and useless in determining where the error occurred). We obtain a publicly-verifiable secure logging scheme that is simultaneously robust, space-efficient and truncation secure with provable security under simple assumptions. Our generic construction uses forward-secure signatures, in a plain and a sequential aggregate variant, where the latter is additionally fault-tolerant, as recently formalized by Hartung et al. (PKC 2016). Fault-tolerant schemes can cope with a number of manipulated log entries (bounded a priori) and offer strong robustness guarantees while still retaining space efficiency. Our implementation and the accompanying performance measurements confirm the practicality of our scheme.

Abstract: Reducing the Learning with Errors problem (LWE) to the Unique-SVP problem and then applying lattice reduction is a commonly relied-upon strategy for estimating the cost of solving LWE-based constructions. In the literature, two different conditions are formulated under which this strategy is successful. One, widely used, going back to Gama & Nguyen's work on predicting lattice reduction (Eurocrypt 2008) and the other recently outlined by Alkim et al. (USENIX 2016). Since these two estimates predict significantly different costs for solving LWE parameter sets from the literature, we revisit the Unique-SVP strategy. We present empirical evidence from lattice-reduction experiments exhibiting a behaviour in line with the latter estimate. However, we also observe that in some situations lattice-reduction behaves somewhat better than expected from Alkim et al.'s work and explain this behaviour under standard assumptions. Finally, we show that the security estimates of some LWE-based constructions from the literature need to be revised and give refined expected solving costs.