International Association
for Cryptologic Research

A cryptographic function with a fixed-length output, such as a block cipher, hash function, or message authentication code (MAC), should behave as a random mapping. The mapping's randomness can be evaluated with statistical tests. Statistical test suites typically used to evaluate cryptographic functions, such as the NIST test suite, are not well-suited for testing fixed-output-length cryptographic functions. Also, these test suites employ a frequentist approach, making it difficult to obtain an overall evaluation of the mapping's randomness. This paper describes CryptoStat, a test suite that overcomes the aforementioned deficiencies. CryptoStat is specifically designed to test the mappings of fixed-output-length cryptographic functions, and CryptoStat employs a Bayesian approach that quite naturally yields an overall evaluation of the mappings' randomness. Results of applying CryptoStat to reduced-round and full-round versions of the AES block ciphers and the SHA-1 and SHA-2 hash functions are reported; the results are analyzed to determine the algorithms' randomness margins.

Pairing-based cryptography is now a mature science. However implementation of a pairing-based protocol can be challenging, as the efficient computation of a pairing is difficult, and the existing literature on implementation might not match with the requirements of a particular application. Furthermore developments in our understanding of the true security of pairings render much of the existing literature redundant. Here we take a fresh look and develop a simpler three-stage algorithm for calculating pairings, as they arise in real applications.

White-box cryptography is the last security barrier for a cryptographic software implementation deployed in an untrusted environment. The principle of internal encodings is a commonly used white-box technique to protect block cipher implementations. It consists in representing an implementation as a network of look-up tables which are then encoded using randomly generated bijections (the internal encodings). When this approach is implemented based on nibble (i.e. 4-bit wide) encodings, the protected implementation has been shown to be vulnerable to differential computation analysis (DCA). The latter is essentially an adaptation of differential power analysis techniques to computation traces consisting of runtime information, e.g., memory accesses, of the target software. In order to thwart DCA, it has then been suggested to use wider encodings, and in particular byte encodings, at least to protect the outer rounds of the block cipher which are the prime targets of DCA.

In this work, we provide an in-depth analysis of when and why DCA works. We pinpoint the properties of the target variables and the encodings that make the attack (in)feasible. In particular, we show that DCA can break encodings wider than 4-bit, such as byte encodings. Additionally, we propose new DCA-like attacks inspired from side-channel analysis techniques. Specifically, we describe a collision attack particularly effective against the internal encoding countermeasure. We also investigate mutual information analysis (MIA) which naturally applies in this context. Compared to the original DCA, these attacks are also passive and they require very limited knowledge of the attacked implementation, but they achieve significant improvements in terms of trace complexity. All the analyses of our work are experimentally backed up with various attack simulation results. We also verified the practicability of our analyses and attack techniques against a publicly available white-box AES implementation protected with byte encodings --which DCA has failed to break before-- and against a ``masked'' white-box AES implementation --which intends to resist DCA.

Event date: 9 July to 11 July 2019
Submission deadline: 10 March 2019
Notification: 15 April 2019

The Security and Cryptography Group at Microsoft Research, led by Brian LaMacchia, is looking for research interns.

The researchers and engineers in the MSR Security and Cryptography team pursue both theoretical and applied research in our field that will have impact for Microsoft, Microsoft’s customers, and the industry at large. Our current projects include the design and development of quantum-resistant public-key cryptographic algorithms and protocols, high-performance post-quantum cryptographic libraries, quantum cryptanalysis, and end-to-end verifiable election technology.

We are interested in applicants with expertise in one or more of the following: isogeny-based cryptography, lattice-based cryptography, classical and quantum cryptanalysis, and the design of key exchange and digital signature primitives with post-quantum security.

Closing date for applications: 30 June 2019

Contact: Dr. Brian LaMacchia, CryptoIntern (at) microsoft.com

More information: https://careers.microsoft.com/us/en/job/573172/Research-Intern-MSR-Security-and-Cryptography

The CISPA-Stanford Center for Cybersecurity was established as a joint program by the Helmholtz Center for Information Security (CISPA) and Stanford University in 2016 and is supported by the German Federal Ministry of Education and Research (BMBF).

The Elite Research Career Program intends to offer the very best postdoctoral cybersecurity researchers a unique career path at two of the leading cybersecurity institutes in the world. The program consists of three consecutive phases:

- a preparatory 1-2 year postdoctoral phase (Phase P) at CISPA, followed by

- a 2-year appointment at Stanford University (Phase I) as a visiting assistant professor, followed by

- a 3-year position at CISPA as an independent research group leader (Phase II).

Applicants to the program must have completed a distinguished PhD and demonstrated their potential to become future leaders in their field of research. After their return from Stanford candidates are invited to apply for CISPA Tenure Track Faculty Positions and will be considered for fast track.

Closing date for applications: 31 January 2019

Contact: Dr. Sandra Strohbach, Mail: application (at) cispa-stanford.org

More information: https://www.cispa-stanford.org/application.html

Positions are available for talented and passionate software engineers in the Decentralized and Distributed Systems (DEDIS) lab at EPFL led by Prof. Bryan Ford in Lausanne, Switzerland. The DEDIS lab focuses on building secure, scalable, and privacy-preserving decentralized systems, including next-generation blockchain or distributed ledger technology.

The ideal candidate is ready to scale their code from proof-of-concept to production, likes to build real software for real people to use, and believes their code can change the world for the better. A deep understanding of distributed systems, networking, and applied cryptography is a major bonus.

Closing date for applications: 28 February 2019

Contact: Jeff R. Allen

More information: https://stackoverflow.com/jobs/232489/security-privacy-software-engineer-dedis-lab-at-epfl

NewHope is a suite of two efficient Ring-Learning-With-Error based key encapsulation mechanisms (KEMs) that has been proposed to the NIST call for proposals for post-quantum standardization. In this paper, we study the security of NewHope when an active adversary accesses a key establishment and is given access to an oracle, called key mismatch oracle, which indicates whether her guess of the shared key value derived by the party targeted by the attack is correct or not. This attack model turns out to be relevant in key reuse situations since an attacker may then be able to access such an oracle repeatedly with the same key either directly or using faults or side channels, depending on the considered instance of NewHope. Following this model we show that, by using NewHope recommended parameters, several thousands of queries are sufficient to recover the full private key with high probability. This result has been experimentally confirmed using Magma CAS implementation. While the presented key mismatch oracle attacks do not break any of the designers’ security claims for the NewHope KEMs, they provide better insight into the resilience of these KEMs against key reuse. In the case of the CPA-KEM instance of NewHope, they confirm that key reuse (e.g. key caching at server side) should be strictly avoided, even for an extremely short duration. In the case of the CCA-KEM instance of NewHope, they allow to point out critical steps inside the CCA transform that should be carefully protected against faults or side channels in case of potential key reuse.

Many implementations of secure computation use fixed-key AES (modeled as a random permutation); this results in substantial performance benefits due to existing hardware support for~AES and the ability to avoid recomputing the AES key schedule. Surveying these implementations, however, we find that most utilize AES in a heuristic fashion; in the best case this leaves a gap in the security proof, but in many cases we show it allows for explicit attacks.

Motivated by this unsatisfactory state of affairs, we initiate a comprehensive study of how to use fixed-key block ciphers for secure computation---in particular for OT extension and circuit garbling---efficiently and securely. Specifically:

- We consider several notions of pseudorandomness for hash functions (e.g., correlation robustness), and show provably secure schemes for OT extension, garbling, and other applications based on hash functions satisfying these notions.

- We provide provably secure constructions, in the random-permutation model, of hash functions satisfying the different notions of pseudorandomness we consider.

Taken together, our results provide end-to-end security proofs for implementations of secure-computation protocols based on fixed-key block ciphers (modeled as random permutations). Perhaps surprisingly, at the same time our work also results in noticeable performance improvements over the state-of-the-art.

With the large scale adoption of the Radio Frequency Identification (RFID) technology, a variety of security and privacy risks need to be addressed. Arguably, the most general and used RFID security and privacy model is the one proposed by Vaudenay. It considers concurrency, corruption (with or without destruction) of tags, and the possibility to get the result of a protocol session on the reader side. Security in Vaudenay's model embraces two forms, unilateral (tag) authentication and mutual (tag and reader) authentication, while privacy is very flexible and dependent on the adversary class. The construction of destructive private RFID schemes in Vaudenay's model was left open when the model was initially proposed. It was solved three years later in the context of unilateral authentication.

In this paper we propose a destructive private and mutual authentication RFID scheme in Vaudenay's model. The security and privacy of our scheme are rigorously proved. We also show that the only two RFID schemes proposed so far that claimed to achieve destructive privacy and mutual authentication are not even narrow forward private. Thus, our RIFD scheme is the first one to achieve this kind of privacy and security. The paper also points out some privacy proof flaws that have been met in previous constructions.

The Zerocoin protocol is a set of cryptographic algorithms which embedded in a cryptocurrency provide anonymous swap of tokens in a mathematically provable way by using cryptographic accumulators. Functionally it can be described as a black box where an actor can introduce an arbitrary number of coins, and later withdraw them without leaving evidence of connection between both actions. The withdrawing step admits a destination for the coins different from the original minter, but unconditionally requires a previous mint action and does not accept the transfer of coins without leaving the accumulator, thus exposing the traceability of the coins. We propose an alternative design which for the first time combines the virtues of Zerocoin with those of Confidential Transactions offering fully-featured anonymous transactions between individuals with private amounts.

As data outsourcing becomes popular, oblivious algorithms have raised extensive attentions since their control flow and data access pattern appear to be independent of the input data they compute on and thus are especially suitable for secure processing in outsourced environments. In this work, we focus on oblivious shuffling algorithms that aim to shuffle encrypted data blocks outsourced to the cloud server without disclosing the permutation of blocks to the server. Existing oblivious shuffling algorithms suffer from issues of heavy communication and client computation costs when blocks have a large size because all outsourced blocks must be downloaded to the client for shuffling or peeling off extra encryption layers. To help eliminate this void, we introduce the ``repeatable oblivious shuffling'' notation that restricts the communication and client computation costs to be independent of the block size. We present an efficient construction of repeatable oblivious shuffling using additively homomorphic encryption schemes. The comprehensive evaluation of our construction shows its effective usability in practice for shuffling large-sized blocks.

Mining pools in Proof-of-Work cryptocurrencies allow miners to pool their computational resources as a means of reducing payout variance. In Ethereum, uncle blocks are valid Proof-of-Work solutions which do not become the head of the blockchain, yet yield rewards if later referenced by main chain blocks. Mining pool operators are faced with the non-trivial task of fairly distributing rewards for both block types among pool participants. Inspired by empirical observations, we formally reconstruct a Sybil attack exploiting the uncle block distribution policy in a queue-based mining pool. To ensure fairness of the queue-based payout scheme, we propose a mitigation. We examine the effectiveness of the attack strategy under the current and the proposed policy via a discrete-event simulation. Our findings show that the observed attack can indeed be obviated by altering the current reward scheme.

In this work we show that the sponge construction can be used to construct quantum-secure pseudorandom functions. As our main result we prove that random sponges are quantum indistinguishable from random functions. In this setting the adversary is given superposition access to the input-output behavior of the construction but not to the internal function. Our proofs hold under the assumption that the internal function is a random function or permutation. We then use this result to obtain a quantum-security version of a result by Andreeva, Daemen, Mennink, and Van Assche (FSE'15) which shows that a sponge that uses a secure PRP or PRF as internal function is a secure PRF. This result also proves that the recent attacks against CBC-MAC in the quantum-access model by Kaplan, Leurent, Leverrier, and Naya-Plasencia (Crypto'16) and Santoli, and Schaffner (QIC'16) can be prevented by introducing a state with a non-trivial inner part.

The proof of our main result is derived by analyzing the joint distribution of any $q$ input-output pairs. Our method analyzes the statistical behavior of the considered construction in great detail. The used techniques might prove useful in future analysis of different cryptographic primitives considering quantum adversaries. Using Zhandry's PRF/PRP switching lemma we then obtain that quantum indistinguishability also holds if the internal block function is a random permutation.

Randomness is an essential part of any secure cryptosystem, but many constructions rely on distributions that are not uniform. This is particularly true for lattice based cryptosystems, which more often than not make use of discrete Gaussian distributions over the integers. For practical purposes it is crucial to evaluate the impact that approximation errors have on the security of a scheme to provide the best possible trade-off between security and performance. Recent years have seen surprising results allowing to use relatively low precision while maintaining high levels of security. A key insight in these results is that sampling a distribution with low relative error can provide very strong security guarantees. Since floating point numbers provide guarantees on the relative approximation error, they seem a suitable tool in this setting, but it is not obvious which sampling algorithms can actually profit from them. While previous works have shown that inversion sampling can be adapted to provide a low relative error (Pöppelmann et al., CHES 2014; Prest, ASIACRYPT 2017), other works have called into question if this is possible for other sampling techniques (Zheng et al., Eprint report 2018/309). In this work, we consider all sampling algorithms that are popular in the cryptographic setting and analyze the relationship of floating point precision and the resulting relative error. We show that all of the algorithms either natively achieve a low relative error or can be adapted to do so.

In the classical kleptographic business models, the manufacturer of a device $D$ is paid either in advance or in installments by a malicious entity to backdoor $D$. Unfortunately, these models have an inherent high risk for the manufacturer. This translates in high costs for clients. To address this issue, we introduce a subscription based business model and tackle some of the technical difficulties that arise.

A proof system is publicly verifiable, if anyone, by looking at the transcript of the proof, can be convinced that the corresponding theorem is true. Public verifiability is important in many applications since it allows to compute a proof only once while convincing an unlimited number of verifiers. Popular interactive proof systems (e.g., $\Sigma$-protocols) protect the witness through various properties (e.g., witness indistinguishability (WI) and zero knowledge (ZK)) but typically they are not publicly verifiable since such proofs are convincing only for those verifiers who contributed to the transcripts of the proofs. The only known proof systems that are publicly verifiable rely on a non-interactive (NI) prover, through trust assumptions (e.g., NIZK in the CRS model), heuristic assumptions (e.g., NIZK in the random oracle model),specific number-theoretic assumptions on bilinear groups or relying on obfuscation assumptions (obtaining NIWI with no setups). In this work we construct publicly verifiable witness-indistinguishable proof systems from any $\Sigma$-protocol, based {\em only} on the existence of a very generic blockchain. The novelty of our approach is in enforcing a non-interactive verification (thus guaranteeing public verifiability) while allowing the prover to be interactive and talk to the blockchain (this allows us to circumvent the need of strong assumptions and setups). This opens interesting directions for the design of cryptographic protocols leveraging on blockchain technology.

We want to design and analyze protocols in a modular way by combining idealized components that we realize individually. While this is in principle possible using security frameworks that provide generic composition theorems, we notice that actually applying this methodology in practical protocols is far from trivial and, worse, is sometimes not even possible. As an example, we use a natural combination of zero-knowledge proofs with signature and commitment schemes, where the goal to have a party prove in zero-knowledge that it knows a signature on a committed message, i.e., prove knowledge of a witness to a statement involving algorithms of the signature and commitment scheme. We notice that, unfortunately, the composition theorem of the widely used UC framework does allow one to modularly prove the security of this example protocol. We then describe a new variant of the UC framework, multi-protocol UC, and show a composition theorem that generalizes the one from the standard framework. We use this new framework to provide a modular analysis of a practical protocol that follows the above structure and is based on discrete-logarithm-based primitives. Besides the individual security proofs of the protocol components, we also describe a new methodology for idealizing them as components that can then be composed.

Group signatures are signatures providing signer anonymity where signers can produce signatures on behalf of the group that they belong to. Although such anonymity is quite attractive considering privacy issues, it is not trivial to check whether a signer has been revoked or not. Thus, how to revoke the rights of signers is one of the major topics in the research on group signatures. In particular, scalability, where the signing and verification costs and the signature size are constant in terms of the number of signers N, and other costs regarding signers are at most logarithmic in N, is quite important.

In this paper, we propose a revocable group signature scheme which is currently more efficient compared to previous all scalable schemes. Moreover, our revocable group signature scheme is secure under simple assumptions (in the random oracle model), whereas all scalable schemes are secure under q-type assumptions. We implemented our scheme by employing Barreto-Lynn-Scott curves of embedding degree 12 over a 455-bit prime field (BLS-12-455), and Barreto-Naehrig curves of embedding degree 12 over a 382-bit prime field (BN-12-382), respectively, by using the RELIC library. We showed that the online running times of our signing algorithm were approximately 14 msec (BLS-12-455) and 11 msec (BN-12-382), and those of our verification algorithm were approximately 20 msec (BLS-12-455) and 16 msec (BN-12-382), respectively. Finally, we showed that our scheme is applied to an identity management system proposed by Isshiki et al.

With the recent emergence of efficient zero-knowledge (ZK) proofs for general circuits, while efficient zero-knowledge proofs of algebraic statements have existed for decades, a natural challenge arose to combine algebraic and non-algebraic statements. Chase et al. (CRYPTO 2016) proposed an interactive ZK proof system for this cross-domain problem. As a use case they show that their system can be used to prove knowledge of a RSA/DSA signature on a message m with respect to a publicly known Pedersen commitment g^m h^r . One drawback of their system is that it requires interaction between the prover and the verifier. This is due to the interactive nature of garbled circuits, which are used in their construction. Subsequently, Agrawal et al. (CRYPTO 2018) proposed an efficient non-interactive ZK (NIZK) proof system for cross-domains based on SNARKs, which however require a trusted setup assumption.

In this paper, we propose a NIZK proof system for cross-domains that requires no trusted setup and is efficient both for the prover and the verifier. Our system constitutes a combination of Schnorr based ZK proofs and ZK proofs for general circuits by Giacomelli et al. (USENIX 2016). The proof size and the running time of our system are comparable to the approach by Chase et al. Compared to Bulletproofs (SP 2018), a recent NIZK proofs system on committed inputs, our techniques achieve asymptotically better performance on prover and verifier, thus presenting a different trade-off between the proof size and the running time.