International Association
for Cryptologic Research

We present a multi-input functional encryption scheme (MIFE) for the inner product functionality based on the k-Linear assumption in prime-order bilinear groups. Our construction works for any polynomial number of encryption slots and achieves security against unbounded collusion, while relying on standard polynomial hardness assumptions. This is the first MIFE scheme for a non-trivial functionality based on standard cryptographic assumptions, as well as the first to achieve polynomial security loss for a super-constant number of slots under falsifiable assumptions. Prior works required stronger non-standard assumptions such as indistinguishability obfuscation or multi-linear maps.

Quantum-mechanical devices have the potential to transform cryptography. Most research in this area has focused either on the information-theoretic advantages of quantum protocols or on the security of classical cryptographic schemes against quantum attacks. In this work, we initiate the study of another relevant topic: the encryption of quantum data in the computational setting.

In this direction, we establish quantum versions of several fundamental classical results. First, we develop natural definitions for private-key and public-key encryption schemes for quantum data. We then define notions of semantic security and indistinguishability, and, in analogy with the classical work of Goldwasser and Micali, show that these notions are equivalent. Finally, we construct secure quantum encryption schemes from basic primitives. In particular, we show that quantum-secure one-way functions imply IND-CCA1-secure symmetric-key quantum encryption, and that quantum-secure trapdoor one-way permutations imply semantically-secure public-key quantum encryption.

In recent work, Bellare, Hoang, and Keelveedhi (CRYPTO 2013) introduced a new abstraction called Universal Computational Extractors (UCEs), and showed how they can replace random oracles (ROs) across a wide range of cryptosystems. We formulate a new framework, called Interactive Computational Extractors (ICEs), that extends UCEs by viewing them as models of ROs under unpredictable (aka. high-entropy) queries. We overcome a number of limitations of UCEs in the new framework, and in particular prove the adaptive RKA and semi-adaptive KDM securities of a highly efficient symmetric encryption scheme using ICEs under key offsets.

We show both negative and positive feasibility results for ICEs. On the negative side, we demonstrate ICE attacks on the HMAC and NMAC constructions. On the positive side we show that: 1) ROs are indeed ICE secure, thereby confirming the structural soundness of our definition and enabling a finer layered approach to protocol design in the RO model; and 2) a modified version of Liskov's Zipper Hash is ICE secure with respect to an underlying fixed- input-length RO, for appropriately restricted classes of adversaries. This brings the first result closer to practice by moving away from variable-input- length ROs. Our security proofs employ techniques from indifferentiability in multi-stage settings.

In this paper, we study the behavior of the XOR count distributions under different bases of finite field. XOR count of a field element is a simplified metric to estimate the hardware implementation cost to compute the finite field multiplication of an element. It is an important criterion in the design of lightweight cryptographic primitives, typically to estimate the efficiency of the diffusion layer in a block cipher. Although several works have been done to find lightweight MDS diffusion matrices, to the best of our knowledge, none has considered finding lightweight diffusion matrices under other bases of finite field apart from the conventional polynomial basis. The main challenge for considering different bases for lightweight diffusion matrix is that the number of bases grows exponentially as the dimension of a finite field increases, causing it to be infeasible to check all possible bases. Through analyzing the XOR count distributions and the relationship between the XOR count distributions under different bases, we find that when all possible bases for a finite field are considered, the collection of the XOR count distribution is invariant to the choice of the irreducible polynomial of the same degree. In addition, we can partition the set of bases into equivalence classes, where the XOR count distribution is invariant in an equivalence class, thus when changing bases within an equivalence class, the XOR count of a diffusion matrix will be the same. This significantly reduces the number of bases to check as we only need to check one representative from each equivalence class for lightweight diffusion matrices. The empirical evidence from our investigation says that the bases which are in the equivalence class of the polynomial basis are the recommended choices for constructing lightweight MDS diffusion matrices.

Our paper suggests a general method to construct a Floating-Point Homomorphic Encryption (FPHE) scheme that allows the floating-point arithmetics of ciphertexts, thus computing encryptions of most signicant bits of m1+m2 and m1m2, given encryptions of floating-point numbers m1 and m2. Our concrete construction of leveled FPHE based on BGV scheme is almost optimal in the sense of noise growth and precision loss. More precisely, given encryptions of d messages with eta bits of precision, our scheme of depth log d securely computes their product with (eta-log d) bits of precision similarly to the case of unencrypted floating-point computation. The required bit size of the largest modulus grows linearly in the depth. We also describe algorithms for evaluating some floating-point arithmetic circuits containing polynomial, multiplicative inverse, and even exponential function, and analyze their complexities and output precisions. With the security parameter 80, our rudimentary implementation takes 315ms and 168ms to compute a product of 16 ciphertexts and a multiplicative inverse of a ciphertext, respectively, when given ciphertexts have 20 bits of precision.

Recently, threshold implementations (TI) with $d + 1$ input shares have been proposed at Crypto 2015. This optimization aims for more lightweight TI designs while keeping the glitch-resistance of the original concept. In this note, we consider such an approach and provide preliminary simulation-based evidence, backed by empirical results, of the existence of $d^{\text{th}}$-order leakages. We conclude that, while for first-order TI designs this solution can be overkill due to the extra randomness requirements, higher-order TIs can still benefit from it.

Walsh-Hadamard transform is used in a wide variety of scientific and engineering applications, including bent functions and cryptanalytic optimization techniques in cryptography. In linear cryptanalysis, it is a key question to find a good linear approximation, which holds with probability $(1+d)/2$ and the bias $d$ is large in absolute value. Lu and Desmedt (2011) take a step toward answering this key question in a more generalized setting and initiate the work on the generalized bias problem with linearly-dependent inputs. In this paper, we give fully extended results. Deep insights on assumptions behind the problem are given. We take an information-theoretic approach to show that our bias problem assumes the setting of the maximum input entropy subject to the input constraint. By means of Walsh transform, the bias can be expressed in a simple form. It incorporates Piling-up lemma as a special case. Secondly, as application, we answer a long-standing open problem in correlation attacks on combiners with memory. We give a closed-form exact solution for the correlation involving the multiple polynomial of any weight \emph{for the first time}. We also give Walsh analysis for numerical approximation. An interesting bias phenomenon is uncovered, i.e., for even and odd weight of the polynomial, the correlation behaves differently. Thirdly, we introduce the notion of weakly biased distribution, and study bias approximation for a more general case by Walsh analysis. We show that for weakly biased distribution, Piling-up lemma is still valid. Our work shows that Walsh analysis is useful and effective to a broad class of cryptanalysis problems.

The study of program obfuscation is seeing great progress in recent years, which is crucially attributed to the introduction of graded encoding schemes by Garg, Gentry and Halevi (Eurocrypt 2013). In such schemes, elements of a ring can be encoded such that the content of the encoding is hidden, but restricted algebraic manipulations, followed by zero-testing, can be performed publicly. This primitive currently underlies all known constructions of general-purpose obfuscators.

However, the security properties of the current candidate graded encoding schemes are not well understood, and new attacks frequently introduced. It is therefore important to assume as little as possible about the security of the graded encoding scheme, and use as conservative security models as possible. This often comes at a cost of reducing the efficiency or the functionality of the obfuscator.

In this work, we present a candidate obfuscator, based on composite-order graded encoding schemes, which obfuscates circuits directly a la Zimmerman (Eurocrypt 2015) and Applebaum-Brakerski (TCC 2015). Our construction requires a graded encoding scheme with only $3$ ``plaintext slots'' (= sub-rings of the underlying ring), which is directly related to the size and complexity of the obfuscated program. We prove that our obfuscator is superior to previous works in two different security models.

1. We prove that our obfuscator is indistinguishability-secure (iO) in the \emph{Unique Representation Generic Graded Encoding} model. Previous works either required a composite-order scheme with polynomially many slots, or were provable in a milder security model. This immediately translates to a polynomial improvement in efficiency, and shows that improved security does not come at the cost of efficiency in this case.

2. Following Badrinarayanan et al.\ (Eurocrypt 2016), we consider a model where finding any ``non-trivial'' encoding of zero breaks the security of the encoding scheme. We show that, perhaps surprisingly, secure obfuscation is possible in this model even for some classes of \emph{non-evasive functions} (for example, any class of conjunctions). We define the property required of the function class, formulate an appropriate (generic) security model, and prove that our aforementioned obfuscator is virtual-black-box (VBB) secure in this model.

In this work we extend the electronic voting scheme introduced by R. Cramer, R. Gennaro and B. Schoenmakers in [CGS97]. In the original paper the privacy of votes is based on the decisional Diffie-Hellman or respectively the higher residuosity assumption. Since both problems can be solved efficiently in the event of quantum computers, a desirable goal is to implement the voting scheme with privacy based on different assumptions. We present the framework and a concrete instantiation for an efficient solution with privacy based on learning with errors over rings. Additionally we show how to achieve privacy assuming hardness of worst-case lattice problems, which are well analyzed and conjectured to be secure against quantum computers.

Reputation systems are a major feature of every modern e-commerce website, helping buyers carefully choose their service providers and products. However, most websites use centralized reputation systems, where the security of the system rests entirely upon a single Trusted Third Party. Moreover, they often disclose the identities of the raters, which may discourage honest users from posting frank reviews due to the fear of retaliation from the ratees. We present a reputation system that is decentralized yet secure and efficient, and could therefore be applied in a practical context. In fact, users are able to retrieve the reputation score of a service provider directly from it in constant time, with assurance regarding the correctness of the information obtained. Additionally, the reputation system is anonymity-preserving, which ensures that users can submit feedback without their identities being associated to it. Despite this anonymity, the system still offers robustness against attacks such as ballot-stuffing and Sybil attacks.

Due to their high efficiency and their strong security properties, lattice-based cryptographic schemes seem to be a very promising post-quantum replacement for currently used public key cryptography. The security of lattice-based schemes has been deeply analyzed mathematically, whereas little effort has been spent on the analysis against implementation attacks. In this paper, we start with the fault analysis of one of the most important cryptographic primitives: signature schemes. We investigate the vulnerability and resistance of the currently most efficient lattice-based signature schemes BLISS (CRYPTO 2013), ring-TESLA (AfricaCrypt 2016), and the GLP scheme (CHES 2012) and their implementations. We consider different kinds of (first-order) randomizing, zeroing, and skipping faults. For each of the signature schemes, we found at least six effective attacks. To increase the security of lattice-based signature schemes, we propose countermeasures for each of the respective attacks.

Key schedules in block ciphers are often highly simplified, which causes weakness that can be exploited in many attacks. At ASIACRYPT 2011, Dunkelman et al. proposed a technique using the weakness in the key schedule of AES, called key-bridging technique, to improve the overall complexity. The advantage of key-bridging technique is that it allows the adversary to deduce some sub-key bits from some other sub-key bits, even though they are separated by many key mixing steps. Although the relations of successive rounds may be easy to see, the relations of two rounds separated by some mixing steps are very hard to find. In this paper, we describe a versatile and powerful algorithm for searching key-bridging technique on word-oriented and bit-oriented block ciphers. To demonstrate the usefulness of our approach, we apply our tool to the impossible differential and multidimensional zero correlation linear attacks on 23-round LBlock, 23-round TWINE-80 and 25-round TWINE-128. To the best of our knowledge, these results are the currently best results on LBlock and TWINE in the single-key setting.

We propose a new suite of algorithms that significantly improve the performance of supersingular isogeny Diffie-Hellman (SIDH) key exchange. Subsequently, we present a full-fledged implementation of SIDH that is geared towards the 128-bit quantum and 192-bit classical security levels. Our library is the first constant-time SIDH implementation and is more than 2.5 times faster than the previous best (non-constant-time) SIDH software. The high speeds in this paper are driven by compact, inversion-free point and isogeny arithmetic and fast SIDH-tailored field arithmetic: on an Intel Haswell processor, generating ephemeral public keys takes 51 million cycles for Alice and 59 million cycles for Bob while computing the shared secret takes 47 million and 57 million cycles, respectively. The size of public keys is only 751 bytes, which is significantly smaller than most of the popular post-quantum key exchange alternatives. Ultimately, the size and speed of our software illustrates the strong potential of SIDH as a post-quantum key exchange candidate and we hope that these results encourage a wider cryptanalytic effort.

Solving a system of multivariate quadratic equations (MQ) is an NP-complete problem whose complexity estimates are relevant to many cryptographic scenarios. In some cases it is required in the best known attack; sometimes it is a generic attack (such as for the multivariate PKCs), and sometimes it determines a provable level of security (such as for the QUAD stream ciphers).

Under reasonable assumptions, the best way to solve generic MQ systems is the XL algorithm implemented with a sparse matrix solver such as Wiedemann's algorithm. Knowing how much time an implementation of this attack requires gives us a good idea of how future cryptosystems related to MQ can be broken, similar to how implementations of the General Number Field Sieve that factors smaller RSA numbers give us more insight into the security of actual RSA-based cryptosystems.

This paper describes such an implementation of XL using the block Wiedemann algorithm. In 5 days we are able to solve a system with 32 variables and 64 equations over $\mathbb{F}_{16}$ (a computation of about $2^{60.3}$ bit operations) on a small cluster of 8 nodes, with 8 CPU cores and 36 GB of RAM in each node. We do not expect system solvers of the F$_4$/F$_5$ family to accomplish this due to their much higher memory demand. Our software also offers implementations for $\mathbb{F}_{2}$ and $\mathbb{F}_{31}$ and can be easily adapted to other small fields. More importantly, it scales nicely for small clusters, NUMA machines, and a combination of both.

Polymorphic encryption and Pseudonymisation, abbreviated as PEP, form a novel approach for the management of sensitive personal data, especially in health care. Traditional encryption is rather rigid: once encrypted, only one key can be used to decrypt the data. This rigidity is becoming an every greater problem in the context of big data analytics, where different parties who wish to investigate part of an encrypted data set all need the one key for decryption.

Polymorphic encryption is a new cryptographic technique that solves these problems. Together with the associated technique of polymorphic pseudonymisation new security and privacy guarantees can be given which are essential in areas such as (personalised) healthcare, medical data collection via self-measurement apps, and more generally in privacy-friendly identity management and data analytics.

The key ideas of polymorphic encryption are: 1. Directly after generation, data can be encrypted in a `polymorphic' manner and stored at a (cloud) storage facility in such a way that the storage provider cannot get access. Crucially, there is no need to a priori fix who gets to see the data, so that the data can immediately be protected.

For instance a PEP-enabled self-measurement device will store all its measurement data in polymorphically encrypted form in a back-end data base.

2. Later on it can be decided who can decrypt the data. This decision will be made on the basis of a policy, in which the data subject should play a key role.

The user of the PEP-enabled device can, for instance, decide that doctors $X,Y,Z$ may at some stage decrypt to use the data in their diagnosis, or medical researcher groups $A, B, C$ may use it for their investigations, or third parties $U,V,W$ may use it for additional services, etc.

3. This `tweaking' of the encrypted data to make it decryptable by a specific party can be done in a blind manner. It will have to be done by a trusted party who knows how to tweak the ciphertext for whom.

This PEP technology can provide the necessary security and privacy infrastructure for big data analytics. People can entrust their data in polymorphically encrypted form, and each time decide later to make (parts of) it available (decryptable) for specific parties, for specific analysis purposes. In this way users remain in control, and can monitor which of their data is used where by whom for which purposes.

The polymorphic encryption infrastructure can be supplemented with a pseudonymisation infrastructure which is also polymorphic, and guarantees that each individual will automatically have different pseudonyms at different parties and can only be de-pseudonymised by participants (like medical doctors) who know the original identity.

This white paper provides an introduction to Polymorphic Encryption and Pseudonymisation (PEP), at different levels of abstraction, focusing on health care as application area. It contains a general description of PEP, explaining the basic functionality for laymen, supplemented by a clarification of the legal framework provided by the upcoming General Data Protection Regulation (GDPR) of the European Union. The paper also contains a more advanced, mathematically oriented description of PEP, including the underlying cryptographic primitives, key and pseudonym managment, interaction protocols, etc. This second part is aimed at readers with a background in computer security and cryptography. The cryptographic basis for PEP is ElGamal public key encryption, which is well-known since the mid 1980s. It is the way in which this encryption is used --- with re-randomisation, re-keying and re-shuffling --- that is new.

The PEP framework is currently elaborated into an open design and open source (prototype) implementation at Radboud University in Nijmegen, The Netherlands. The technology will be used and tested in a real-life medical research project at the Radboud University Medical Center.

Passionate about PKI, algorithms, ciphers and security systems to encrypt sensitive information? We have a vacancy for a code maker/breaker, the professional who ensures that data regarding finance, health, national security and other important worlds are hidden from hungry hackers...

You will be working on software for mobile platforms, mobile devices like iOS, Android, Windows and connected devices. Your projects are designing and implementing cryptography in our software solutions that are resilient against real world attacks. This will include the analysis of cryptographic implementations embedded in AET’s solutions under evaluation. You will also provide technical expertise in applied cryptography.

What you bring

We’re looking for an Applied Cryptographer / PKI developer who is passionate (like us) about software development and not afraid to pioneer new approaches, techniques and technologies. The ideal candidate will have a passion for implementing solutions to complex security problems with a keen understanding of information security challenges and an up-to-date awareness of information security threats.

You will need to have the following qualifications and experience:

• Has a Bachelor or Master degree in IT, Math or other related degree,
• Deep knowledge of applied cryptography and PKI,
• Ability to combine market and technology topics to find technical solutions in complex environments.

Other areas of knowledge and experience that would be considered key assets:

• Programming languages: C/C++, Java,
• An understanding of modern computer architectures and information technology architectures including cloud computing,
• Platforms like iOS, Android, Windows or Linux,
• Smart cards, sims and/or HSMs,

If you are interested in this opportunity and feel that you have the relevant skills, qualifications and experience as a Applied Cryptographer / PKI developer please send your resume to hrm (at) aeteurope.com

Closing date for applications: 31 December 2017

Contact: We can understand you want to know more about the job, your colleagues or the company of AET. Don’t hesitate to give us a call at +31 26 365 3350. Ask for Bert Smit, Development Manager.

We are looking forward to getting to know you!

More information: https://www.aeteurope.com

We are looking for a research scientist or post-doc in cryptography to work on novel cryptographic concepts for emerging ICT domains (e.g. cloud computing or cyber physical systems). Ideally you have experience in fields like modern public-key cryptography, distributed cryptography, privacy enhancing technologies, or multi-party computation. You will be involved in EU research projects and advance/improve cryptography for secure and privacy preserving cloud based systems. Ideally you have also experience in software development and prototyping.

Further infos:

• Direct job posting: http://www.ait.ac.at/fileadmin/inserate/Jobs/Science/Scientist_for_Applied_Crypthography.pdf
• AIT Digital Safety & Security Department: http://www.ait.ac.at/departments/digital-safety-security

Closing date for applications: 30 June 2016

Contact:

• Thomas Loruenser, Department Digital Safety & Security, AIT Austrian Institute of Technology, or
• Maria Leonhard-Maurer, Head of Human Resources, E-Mail: maria.leonhard-maurer (at) ait.ac.at

More information: http://www.ait.ac.at/fileadmin/inserate/Jobs/Science/Scientist_for_Applied_Crypthography.pdf

Secure Internet communications face conflicting demands: advances in (quantum) computers require stronger, quantum-resistant algorithms, while at the same time the Internet of Things demands better-performing protocols; and finally, communication links usually depend on a single root-of-trust, e.g., a certification authority, a single point-of-failure that is too big of a risk for future systems. This paper proposes a hybrid infrastructure that combines a quantum-resistant HIMMO key pre-distribution scheme based on multiple Trusted Third Parties with public-key cryptography to address these problems. During operation, any pair of devices can use HIMMO key material and public-keys to establish a secure link, and public-keys are then certified by multiple TTPs. The solution is resilient to the capture of individual roots of trust, without affecting performance, while public keys can provide features such as forward secrecy. Combining HIMMO identities with public-keys enables secure certification of public keys and distribution of HIMMO key material from multiple TTPs, without requiring an out-of-band channel. The infrastructure can be tuned to fit Internet of Things scenarios benefiting from an efficient, non-interactive and authenticated key exchange, or to fit use cases where the use of multiple TTPs provides privacy safe-guards when lawful interception is required. As proof-of-concept we show how TLS can benefit from these ideas with minimal extensions, while exhibiting good security features and performance compared with solutions based on public-key cryptography only.

We propose the first adaptation of Matsui's algorithm for finding the best differential and linear trails to the class of ARX ciphers. It is based on a branch-and-bound search strategy, does not use any heuristics and returns optimal results. The practical application of the new algorithm is demonstrated on reduced round variants of block ciphers from the \textsc{Speck} family. More specifically, we report the probabilities of the best differential trails for up to 10, 9, 8, 7, and 7 rounds of \textsc{Speck32}, \textsc{Speck48}, \textsc{Speck64}, \textsc{Speck96} and \textsc{Speck128} respectively, together with the exact number of differential trails that have the best probability. The new results are used to compute bounds, under the Markov assumption, on the security of \textsc{Speck} against single-trail differential cryptanalysis. Finally, we propose two new ARX primitives with provable bounds against single-trail differential and linear cryptanalysis -- a long standing open problem in the area of ARX design.

Bitcoin as deployed today does not scale. Scalability research has focused on two directions: 1) redesigning the Blockchain protocol, and 2) facilitating `off-chain transactions' and only consulting the Blockchain if an adjudicator is required. In this paper we focus on the latter and provide an overview of Bitcoin payment networks. These consist of two components: payment channels to facilitate off-chain transactions between two parties, and the capability to fairly exchange bitcoins across multiple channels. We compare Duplex Micropayment Channels and Lightning Channels, before discussing Hashed Time Locked Contracts which enable Bitcoin-based payment networks. Finally, we highlight challenges for route discovery in these networks.