International Association
for Cryptologic Research

With Attribute-based Signatures (ABS) users can simultaneously sign messages and prove compliance of their attributes, issued by designated attribute authorities, with some verification policy. Neither signer's identity nor possessed attributes are leaked during the verification process, making ABS schemes a handy tool for applications requiring privacy-preserving authentication. Earlier ABS schemes lacked support for hierarchical delegation of attributes (across tiers of attribute authorities down to the signers), a distinct property that has made traditional PKIs more scalable and widely adoptable.

This changed recently with the introduction of Hierarchical ABS (HABS) schemes, where support for attribute delegation was proposed in combination with stronger privacy guarantees for the delegation paths (path anonymity) and new accountability mechanisms allowing a dedicated tracing authority to identify these paths (path traceability) and the signer, along with delegated attributes, if needed. Yet, current HABS construction is generic with inefficient delegation process resulting in sub-optimal signature lengths of order $O(k^{2}|\Psi|)$ where $\Psi$ is the policy size and $k$ the height of the hierarchy.

This paper proposes a direct HABS construction in bilinear groups that significantly improves on these bounds and satisfies the original security and privacy requirements. At the core of our HABS scheme is a new delegation process based on the length-reducing homomorphic trapdoor commitments to group elements for which we introduce a new delegation technique allowing step-wise commitments to additional elements without changing the length of the original commitment and its opening. While also being of independent interest, this technique results in shorter HABS keys and achieves the signature-length growth of $O(k|\Psi|)$ which is optimal due to the path-traceability requirement.

Cube attacks are an important type of key recovery attacks against stream ciphers. In particular, it is shown to be powerful against Trivium-like ciphers. Traditional cube attacks are experimental attacks which could only exploit cubes of size less than 40. At CRYPTO 2017, division property based cube attacks were proposed by Todo et al., and an advantage of introducing the division property to cube attacks is that large cube sizes which are beyond the experimental range could be explored, and so powerful theoretical attacks were mounted to many lightweight stream ciphers.

In this paper, we revisit the division property based cube attacks. There is an important assumption, called Weak Assumption, proposed in division property based cube attacks to support the effectiveness of key recovery. Todo et al. in CRYPTO 2017 said that the Weak Assumption was expected to hold for theoretically recovered superpolies of Trivium according to some experimental results on small cubes. In this paper, based on some new techniques to remove invalid division trails, some best key recovery results given at CRYPTO 2017 and CRYPTO 2018 on Trivium are proved to be distinguishers. First, we build a relationship between the bit-based division property and the algebraic degree evaluation on a set of active variables. Second, based on our algebraic point of view, we propose a new variant of division property which incorporates the distribution of active variables. Third, a new class of invalid division trails are characterized and new techniques based on MILP models to remove them are proposed. Hopefully this paper could give some new insights on accurately evaluating the propagation of the bit-based division property and also attract some attention on the validity of division property based cube attacks against stream ciphers.

It is known that information-theoretically secure computation can be done by using a deck of physical cards. In card-based protocols, shuffles, which covertly rearrange the order of cards according to a permutation chosen randomly, are the heaviest operations. Due to this, the number of shuffles in a protocol is desired to be small. However, as far as we know, there are no general-purpose protocols with a constant number of shuffles. In this paper, we construct a general-purpose protocol with a constant number of shuffles; surprisingly, just one (somewhat complicated) shuffle. This is achieved by introducing the garbled circuit methodology. Moreover, to make our shuffle simpler, we also develop a novel technique for aggregating several pile-scramble shuffles (which are efficiently implementable) into one pile-scramble shuffle. Consequently, we also construct a general-purpose protocol with two pile-scramble shuffles. Both techniques may lead to many other applications in this area.

We construct efficient, unconditional non-malleable codes that are secure against tampering functions computed by decision trees of depth $d = n^{1/4-o(1)}$. In particular, each bit of the tampered codeword is set arbitrarily after adaptively reading up to $d$ arbitrary locations within the original codeword. Prior to this work, no efficient unconditional non-malleable codes were known for decision trees beyond depth $O(\log^2 n)$.

Our result also yields efficient, unconditional non-malleable codes that are $\exp(-n^{\Omega(1)})$-secure against constant-depth circuits of $\exp(n^{\Omega(1)})$-size. Prior work of Chattopadhyay and Li (STOC 2017) and Ball et al. (FOCS 2018) only provide protection against $\exp(O(\log^2n))$-size circuits with $\exp(-O(\log^2n))$-security.

We achieve our result through simple non-malleable reductions of decision tree tampering to split-state tampering. As an intermediary, we give a simple and generic reduction of leakage-resilient split-state tampering to split-state tampering with improved parameters. Prior work of Aggarwal et al. (TCC 2015) only provides a reduction to split-state non-malleable codes with decoders that exhibit particular properties.

We introduce pRate, a novel reputation management scheme with strong security and privacy guarantees for the users and their reputation scores. The reputation scores are computed based on the (aggregated) number(s) of stars that users receive from their raters. pRate allows users to advertise privacy-friendly statements about their reputation when searching for potential transaction partners. Ratings can only be submitted by partners who have been initially authorised by the ratee and issued a rating token. The scheme is managed by a possibly untrusted reputation manager who can register users and assist ratees in updating their reputation scores, yet without learning these scores. In addition to ensuring the secrecy of the ratings, a distinctive feature of pRate over prior proposals, is that it hides the identities of raters and ratees from each other during the transaction and rating stages. The scheme is built from a number of efficient cryptographic primitives; its security is formally modeled and proven to hold under widely used assumptions on bilinear groups.

We prove an $\Omega(d \lg n/ (\lg\lg n)^2)$ lower bound on the dynamic cell-probe complexity of statistically $\mathit{oblivious}$ approximate-near-neighbor search ($\mathsf{ANN}$) over the $d$-dimensional Hamming cube. For the natural setting of $d = \Theta(\log n)$, our result implies an $\tilde{\Omega}(\lg^2 n)$ lower bound, which is a quadratic improvement over the highest (non-oblivious) cell-probe lower bound for $\mathsf{ANN}$. This is the first super-logarithmic $\mathit{unconditional}$ lower bound for $\mathsf{ANN}$ against general (non black-box) data structures. We also show that any oblivious $\mathit{static}$ data structure for decomposable search problems (like $\mathsf{ANN}$) can be obliviously dynamized with $O(\log n)$ overhead in update and query time, strengthening a classic result of Bentley and Saxe (Algorithmica, 1980).

We present a practical solution to design a secure logging system that provides confidentiality, integrity, completeness, and non-repudiation. To the best of our knowledge, our solution is the first practical implementation of a logging system that brings all the above security aspects together. Our proposed library makes use of a Dynamic Searchable Symmetric Encryption (DSSE) scheme to provide keyword search operations through encrypted logs without decryption. This helps us to keep each log confidential, preventing unauthorized users from decrypting the encrypted logs. Moreover, we deploy a set of new features such as log sequence generation and digital signatures on top of the DSSE scheme, which makes our library a complete proof of concept solution for a secure logging system, providing all the necessary security assurances. We also analyze the library's performance on a real setting, bootstrapping with 10,000 lines of logs. Based on our observation, the entire search operation for a keyword takes about 10 milliseconds. Although SELL v1.0 is developed purely in Python without any low level optimization, the benchmarks show promising timing results for all the operations.

Trick-Taking Games (TTGs) are card games in which each player plays one of his cards in turn according to a given rule. The player with the highest card then wins the trick, i.e., he gets all the cards that have been played during the round. For instance, Spades is a famous TTG proposed by online casinos, where each player must play a card that follows the leading suit when it is possible. Otherwise, he can play any of his cards. In such a game, a dishonest user can play a wrong card even if he has cards of the leading suit. Since his other cards are hidden, there is no way to detect the cheat. Hence, the other players realize the problem later, i.e., when the cheater plays a card that he is not supposed to have. In this case, the game is biased and is canceled. Our goal is to design protocols that prevent such a cheat for TTGs. We give a security model for secure Spades protocols, and we design a scheme called SecureSpades. This scheme is secure under the Decisional Diffie-Hellman assumption in the random oracle model. Our model and our scheme can be extended to several other TTGs, such as Belotte, Whist, Bridge, etc.

SNEIK is a permutation at the core of a submission to the NIST lightweight cryptography project. In this note, we exhibit an iterated probability 1 differential in this permutation. However, it is still unclear if this differential can be used to construct attacks against the permutation in a mode, e.g., against the hash function SNEIKHA.

We also suggest a simple fix: adding a 32-bit rotation in one tap prevents this issue.

We propose Lelantus, a new anonymous payment system which ensures both transaction confidentiality and anonymity with small proof sizes, short verification times and without requiring a trusted setup.

Inspired by the Zerocoin protocol, Lelantus extends the original Zerocoin functionality to support confidential transactions while also significantly improving on the protocol performance. Lelantus proof sizes are almost 17 times smaller compared to the original Zerocoin proof sizes. Moreover, we show how to support efficient aggregation of the transaction proofs, so that the proof verification, while asymptotically linear, is very efficient in practice.

Lelantus builds on the techniques of Confidential Transactions, Zerocoin and One-out-of-Many proofs and its efficiency is particularly well-suited for enabling private blockchain transactions with minimal trust required while employing well-studied cryptographic assumptions.

The IACR and PKC Steering Committee are pleased to announce a new Test-of-Time award for papers published PKC.

PKC is the International Conference on Practice and Theory in Public Key Cryptography, which was founded in 1998 and became an official IACR event in 2003. The new Test-of-Time award recognizes outstanding papers, published in PKC about 15 years ago, making a significant contribution to the theory and practice of public key cryptography, preferably with influence either on foundations or on the practice of the field.

The inaugural award will be given next week at PKC 2019 in Beijing, for papers published in the conference's initial years of early 2000s and late 1990s. In the first few years a number of papers from a few different initial years of PKC can be recognized. Thereafter, the award will typically recognize one year at a time with one or two papers.

The recipients of the 2019 award are:

• How to Enhance the Security of Public-Key Encryption at Minimum Cost by Eiichiro Fujisaki, and Tatsuaki Okamoto, PKC 1999.
• Selecting Cryptographic key Sizes by Arjen K. Lenstra and Eric R. Verheul, PKC 2000 (later Journal of Cryptography 2000).
• The Gap-Problems: A New Class of Problems for the Security of Cryptographic Schemes by Tatsuaki Okamoto, and David Pointcheval, PKC 2001.

Congratulations to these authors for their impactful work! More information about the award can be found at https://iacr.org/meetings/pkc/test_of_time_award/

Online Social Networks (OSNs) offer free storage and social networking services through which users can communicate personal information with one another. The personal information of the users collected by the OSN provider comes with privacy problems when being monetized for advertising purposes. To protect user privacy, existing studies propose utilizing data encryption that immediately prevents OSNs from monetizing users data, and hence leaves secure OSNs with no convincing commercial model. To address this problem, we propose Privado as a privacy-preserving group-based advertising mechanism to be integrated into secure OSNs to re-empower monetizing ability. Privado is run by N servers, each provided by an independent provider. User privacy is protected against an active malicious adversary controlling N -1 providers, all the advertisers, and a large fraction of the users. We base our design on the group-based advertising notion to protect user privacy, which is not possible in the personalized variant. Our design also delivers advertising transparency; the procedure of identifying target customers is operated solely by the OSN servers without getting users and advertisers involved. We carry out experiments to examine the advertising running time under a various number of servers and group sizes. We also argue about the optimum number of servers with respect to user privacy and advertising running time.

We propose a generic construction of linkable ring signature from any compatible ring signature scheme and one-time signature scheme. Our construction has both theoretical and practical interest. In theory, our construction gives the first generic transformation from ring signature to linkable ring signature, which brings at least two main benefits: first, the transformation achieves the lowest bound of the complexity that constructing linkable ring signature schemes. Second, ours preserve the anonymity of underlying ring signature schemes. In practice, our transformation incurs a very small overhead in size and running time. By instantiating our construction using the ring signature scheme [ESS+ 18] and the one-time signature scheme [DLL+ 17], we obtain a lattice-based linkable ring signature scheme whose signature size is logarithmic in the number of ring members. This scheme is practical, especially the signature size is very short: for $2^30$ ring members and security level of 100-bit, our signature size is only 4MB. In addition, we give a new proof approach in proving the linkability, which might be of independent interest towards the proof in the random oracle model.

We initiate the study of indifferentiability for public key encryption and other public key primitives. Our main results are definitions and constructions of public key cryptosystems that are indifferentiable from ideal cryptosystems, in the random oracle model. Cryptosystems include Public key encryption, Digital signatures, Non-interactive key agreement. Our schemes are based on standard public key assumptions. By being indifferentiable from an ideal object, our schemes satisfy any security property that can be represented as a single-stage game and can be composed to operate in higher-level protocols.

Recently Budaghyan, Calderini and Villa (2018) introduced a procedure for investigating if CCZ-equivalence can be more general than EA-equivalence together with inverse transformation (when applicable). In this paper, we show of it is possible to use this procedure for classifying, up to EA-equivalence, all known APN functions in dimension 6. We also give some discussion for dimension 7, 8 and 9. In particular, in these cases it is possible to give an upper bound on the EA-classes contained in the CCZ-classes of the known APN functions.

Proxy Re-Encryption (PRE), introduced by Bellare et. al, allows a ciphertext encrypted using a key pki to be re-encrypted by a third party so that it is an encryption of the same message under a new key pkj , without revealing the message. Post-Compromise Security (PCS) was first introduced for messaging protocols, and ensures that a ciphertext remains confidential even when past keys have been corrupted. We define PCS in the context of PRE, which ensures that an adversary cannot distinguish which ciphertext a re-encryption was created from even given the old secret key, potential old ciphertexts and update token used to perform the re-encryption. We argue that this formal notion accurately captures the most intuitive form of PCS. We give separating examples demonstrating how our definition is stronger than existing ones, before showing that PCS can be met using a combination of existing security definitions from the literature. In doing so, we show that there are existing PRE schemes that satisfy PCS. We also show that natural modifications of more practical PRE schemes can be shown to be PCS without relying on this combination of existing security definitions. Finally, we discuss the relationship between PCS with selective versus adaptive key corruptions, giving a theorem that shows how adaptive security can be met for certain re-encryption graphs.

As messaging applications are becoming increasingly popular, it is of utmost importance to analyze their security and mitigate existing weaknesses. This paper focuses on one of the most acclaimed messaging applications: Signal. Signal is a protocol that provides end-to-end channel security, forward secrecy, and post-compromise security. These features are achieved thanks to a key-ratcheting mechanism that updates the key material at every message. Due to its high security impact, Signal's key-ratcheting has recently been formalized, along with an analysis of its security. In this paper, we revisit Signal, describing some attacks against the original design and proposing SAID: Signal Authenticated and IDentity-based. As the name indicates, our protocol relies on an identity-based setup, which allows us to dispense with Signal's centralized server. We use the identity-based long-term secrets to obtain persistent and explicit authentication, such that SAID achieves higher security guarantees than Signal. We prove the security of SAID not only in the "Authenticated Key Exchange" (AKE) model (as done by previous work), but also in the "Authenticated and Confidential Channel Establishment" (ACCE) model, which we adapted and redefined for SAID and asynchronous messaging protocols in general into a model we call identity-based Multistage Asynchronous Messaging (iMAM). We believe our model to be more faithful in particular to the true security of Signal, whose use of the message keys prevents them from achieving the composable guarantee claimed by previous analysis.

Cryptographic libraries often feature multiple implementations of primitives to meet both the security needs of handling private information and the performance requirements of modern services when the handled information is public. OpenSSL, the de-facto standard free and open source cryptographic library, includes mechanisms to differentiate the confidential data and its control flow, including runtime flags, designed for hardening against timing side-channels, but repeatedly accidentally mishandled in the past. To analyze and prevent these accidents, we introduce Triggerflow, a tool for tracking execution paths that, assisted by source annotations, dynamically analyzes the binary through the debugger. We validate this approach with case studies demonstrating how adopting our method in the development pipeline would have promptly detected such accidents. We further show-case the value of the tooling by presenting two novel discoveries facilitated by Triggerflow: one leak and one defect.

Attribute-based Encryption (ABE), first introduced by [SW05,GPSW06], is a public key encryption system that can support multiple users with varying decryption permissions. One of the main properties of such schemes is the supported function class of policies. While there are fully secure constructions from bilinear maps for a fairly large class of policies, the situation with lattice-based constructions is less satisfactory and many efforts were made to close this gap. Prior to this work the only known fully secure lattice construction was for the class of point functions (also known as IBE).

In this work we construct for the first time a lattice-based (ciphertext-policy) ABE scheme for the function class $t$-CNF, which consists of CNF formulas where each clause depends on at most $t$ bits of the input, for any constant $t$. This class includes NP-verification policies, bit-fixing policies and $t$-threshold policies. Towards this goal we also construct a fully secure single-key constrained PRF from OWF for the same function class, which might be of independent interest.

For $1\leq m \leq n$, we consider a natural $m$-out-of-$n$ multi-instance scenario for a public-key encryption (PKE) scheme. An adversary, given $n$ independent instances of PKE, wins if he breaks at least $m$ out of the $n$ instances. In this work, we are interested in the scaling factor of PKE schemes, $\mathrm{SF}$, which measures how well the difficulty of breaking $m$ out of the $n$ instances scales in $m$. That is, a scaling factor $\mathrm{SF}=\ell$ indicates that breaking $m$ out of $n$ instances is at least $\ell$ times more difficult than breaking one single instance. A PKE scheme with small scaling factor hence provides an ideal target for mass surveillance. In fact, the Logjam attack (CCS 2015) implicitly exploited, among other things, an almost constant scaling factor of ElGamal over finite fields (with shared group parameters).

For Hashed ElGamal over elliptic curves, we use the generic group model to argue that the scaling factor depends on the scheme's granularity. In low granularity, meaning each public key contains its independent group parameter, the scheme has optimal scaling factor $\mathrm{SF}=m$; In medium and high granularity, meaning all public keys share the same group parameter, the scheme still has a reasonable scaling factor $\mathrm{SF}=\sqrt{m}$. Our findings underline that instantiating ElGamal over elliptic curves should be preferred to finite fields in a multi-instance scenario.

As our main technical contribution, we derive new generic-group lower bounds of $\Omega(\sqrt{m p})$ on the difficulty of solving both the $m$-out-of-$n$ Gap Discrete Logarithm and the $m$-out-of-$n$ Gap Computational Diffie-Hellman problem over groups of prime order $p$, extending a recent result by Yun (EUROCRYPT 2015). We establish the lower bound by studying the hardness of a related computational problem which we call the search-by-hypersurface problem.