International Association
for Cryptologic Research

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.

This paper presents the first attribute-based signature (ABS) scheme in which the correspondence between signers and signatures is captured in an arithmetic model of computation. Specifically, we design a fully secure, i.e., adaptively unforgeable and perfectly signer-private ABS scheme for signing policies realizable by arithmetic branching programs (ABP), which are a quite expressive model of arithmetic computations. On a more positive note, the proposed scheme places no bound on the size and input length of the supported signing policy ABP’s, and at the same time, supports the use of an input attribute for an arbitrary number of times inside a signing policy ABP, i.e., the so called unbounded multi-use of attributes. The size of our public parameters is constant with respect to the sizes of the signing attribute vectors and signing policies available in the system. The construction is built in (asymmetric) bilinear groups of prime order, and its unforgeability is derived in the standard model under (asymmetric version of) the well-studied decisional linear (DLIN) assumption coupled with the existence of standard collision resistant hash functions. Due to the use of the arithmetic model as opposed to the boolean one, our ABS scheme not only excels significantly over the existing state-of-the-art constructions in terms of concrete efficiency, but also achieves improved applicability in various practical scenarios. Our principal technical contributions are (a) extending the techniques of Okamoto and Takashima [PKC 2011, PKC 2013], which were originally developed in the context of boolean span programs, to the arithmetic setting; and (b) innovating new ideas to allow unbounded multi-use of attributes inside ABP’s, which themselves are of unbounded size and input length.

Blockchain technology has immense potential. At the same time, it is not always possible to scale blockchains. State Channels solve the problem of scalability while increasing the blockchain's speed and efficiency. State Channels present a workaround to current blockchains' TPS (transaction per second) bottleneck. We used State Channels as a foundation and created Game Channels. We built it around the needs of the gambling market. We also developed Signidice PRNG as well as a dispute resolution mechanism. Signidice uses unique digital signatures and is also described below. The potential use of Game Channels technology is not only gambling; some types of online gaming may also be able to use it.

Nearly all secret sharing schemes studied so far are linear or multi-linear schemes. Although these schemes allow to implement any monotone access structure, the share complexity may be suboptimal -- the gap between the best known lower bounds and best known upper bounds is exponential for some access structures. There is growing evidence in the literature, that non-linear schemes can improve share complexity for some access structures - with the work of Beimel and Ishai (CCC 01') being among the first to demonstrate it. This motivates further study of non linear schemes.

We initiate a systematic study of polynomial secret sharing schemes, where shares are (multi-variate polynomials) of secret and randomness vectors over some finite field. Our main hope is that the nice algebraic structure of polynomials would help obtain better lower bounds than those known for the general setting, extending over the class of multi-linear schemes.

Some of the concrete new results we prove in this work are as follows.\\ \textbf{On share complexity of polynomial schemes.}\\ First we studied degree 1 in randomness (where the degree of secret is unlimited). We have shown that a large subclass of these schemes are equivalent to multi-linear schemes, in the sense that for any such scheme, there exists an equivalent multi-linear scheme with very similar share complexity. Also, we have shown that the class of schemes of polynomials of degree exactly 2 in r, without degree 1 in r monomials, is very weak, and can implement only trivial access structures where the minterms consist of single parties.\\ Another observation we make refers to the share complexity (per bit) of multi linear schemes (polynomial schemes of total degree 1). We observe that the scheme by Liu et. al obtaining share complexity $O(2^{0.994n})$ can be transformed into a multi-linear scheme with similar share complexity per bit, for sufficiently long secrets. It is interesting to check, whether similar ideas could be applied to the recent improvement of Beimel et al. with share complexity $O(2^{0.862n})$ for general schemes, transforming it into a . \textbf{On the randomness complexity of polynomial schemes.}\\ We prove that for every degree 2 polynomial secret sharing scheme, there exists an equivalent degree-2 scheme with identical share complexity with randomness complexity bounded by $O(2^{2^n})$. For general polynomial secret sharing schemes, randomness complexity can be bounded by $SC^{O(SC)^2}$, where $SC$ is the share complexity of the original scheme. So far, bounds on randomness complexity were known only for multi linear schemes, demonstrating that $RC \leq SC$ is always achievable. Our bounds are not nearly as practical, and may be viewed as a proof of concept. One nice application of low (say polynomial) randomness complexity is transforming polynomial schemes with polynomial (in $n$) algebraic formulas $C(s,r)$, into a degree-3 scheme with only polynomial blowup in share complexity (using standard randomizing polynomials constructions).

Blockchains have the potential to revolutionize markets and services, yet, currently exhibit high latencies and fail to handle loads comparable to those managed by traditional custodian financial systems. Layer-two protocols, built on top of (layer-one) blockchains, avoid disseminating every transaction to the whole network by sending transactions off-chain and instead utilize the blockchain only as a recourse for disputes. The promise of layer-two protocols is to complete transactions in sub-seconds, reduce fees, and allow blockchains to scale. With this Systematization of Knowledge, we are the first to structure the complete rich and multifaceted body of research on layer-two transactions. Categorizing the research into payment and state channels as well as commit-chains, we provide a comparison of the protocols and their properties. We contribute a systematization of the associated synchronization and routing protocols along with their privacy and security aspects. Contrary to common belief in the blockchain community, we show that layer-two can scale blockchains; that layer-two protocols are secure without full collateralization; that privacy of layer-two transaction is not granted by default; and that fees depend on the transmitted transaction value. The SoK clears the layer-two fog, highlights the potential of layer-two solutions and identifies their unsolved challenges and promising avenues of future work.

We present new secure protocols for approximate $k$-nearest neighbor search ($k$-NNS) over the Euclidean distance in the semi-honest model. Our implementation is able to handle massive datasets efficiently. On the algorithmic front, we show a new circuit for the approximate top-$k$ selection from $n$ numbers that is built from merely $O(n + \mathrm{poly}(k))$ comparators. Using this circuit as a subroutine, we design new approximate $k$-NNS algorithms and two corresponding secure protocols: 1) optimized linear scan; 2) clustering-based sublinear time algorithm.

Our secure protocols utilize a combination of additively-homomorphic encryption, garbled circuit and Oblivious RAM. Along the way, we introduce various optimizations to these primitives, which drastically improve concrete efficiency.

We evaluate the new protocols empirically and show that they are able to handle datasets that are significantly larger than in the prior work. For instance, running on two standard Azure instances within the same availability zone, for a dataset of 96 dimensional descriptors of 10000000 images, we can find 10 nearest neighbors with average accuracy 0.9 in under 10 seconds improving upon prior work by at least two orders of magnitude.

Profiling attacks, especially those based on machine learning proved as very successful techniques in recent years when considering side-channel analysis of block ciphers implementations. At the same time, the results for implementations public-key cryptosystems are very sparse. In this paper, we consider several machine learning techniques in order to mount a power analysis attack on EdDSA using the curve Curve25519 as implemented in WolfSSL. The results show all considered techniques to be viable and powerful options. The results with convolutional neural networks (CNNs) are especially impressive as we are able to break the implementation with only a single measurement in the attack phase while requiring less than 500 measurements in the training phase. Interestingly, that same convolutional neural network was recently shown to perform extremely well for attacking the AES cipher. Our results show that some common grounds can be established when using deep learning for profiling attacks on distinct cryptographic algorithms and their corresponding implementations.