International Association
for Cryptologic Research

Code polymorphism is a way to efficiently address the challenge of automatically applying the hiding of sensitive information leakage, as a way to protect cryptographic primitives against side-channel attacks (SCA) involving layman adversaries. Yet, recent improvements in SCA, involving more powerful threat models, e.g., using deep learning, emphasized the weaknesses of some hiding counter-measures. This raises two questions. On the one hand, the security of code polymorphism against more powerful attackers, which has never been addressed so far, might be affected. On the other hand, using deep learning SCA on code polymorphism would require to scale the state-of-the-art models to much larger traces than considered so far in the literature. Such a case typically occurs with code polymorphism due to the unknown precise location of the leakage from one execution to another. We tackle those questions through the evaluation of two polymorphic implementations of AES, similar to the ones used in a recent paper published in TACO 2019 [6]. We show on our analysis how to efficiently adapt deep learning models used in SCA to scale on traces 32 folds larger than what has been done so far in the literature. Our results show that the targeted polymorphic implementations are broken within 20 queries with the most powerful threat models involving deep learning, whereas 100,000 queries would not be sufficient to succeed the attacks previously investigated against code polymorphism. As a consequence, this paper pushes towards the search of new polymorphic implementations secured against state-of-the-art attacks, which currently remains to be found.

Regev (2005) introduced the learning with errors (LWE) problem and showed a quantum reduction from a worst case lattice problem to LWE. Building on the work of Peikert (2009), a classical reduction from the shortest vector problem to LWE was obtained by Brakerski et al. (2013). A concrete security analysis of Regev's reduction by Chatterjee et al. (2016) identified a huge tightness gap. The present work performs a concrete analysis of the tightness gap in the classical reduction of Brakerski et al. It turns out that the tightness gap in the Brakerski et al. classical reduction is even larger than the tightness gap in the quantum reduction of Regev. This casts doubts on the implication of the reduction to security assurance of practical cryptosystems.

Masking by lookup table randomisation is a well-known technique used to achieve side-channel attack resistance for software implementations, particularly, against DPA attacks. The randomised table technique for first- and second-order security requires about m * 2^n bits of RAM to store an (n, m)-bit masked S-box lookup table. Table compression helps in reducing the amount of memory required, and this is useful for highly resource-constrained IoT devices. Recently, Vadnala (CT-RSA 2017) proposed a randomised table compression scheme for first- and second-order security in the probing leakage model. This scheme reduces the RAM memory required by about a factor of 2^l, where l is a compression parameter. Vivek (Indocrypt 2017) demonstrated an attack against the second-order scheme of Vadnala. Hence achieving table compression at second and higher orders is an open problem.

In this work, we propose a second-order secure randomised table compression scheme which works for any (n, m)-bit S-box. Our proposal is a variant of Vadnala's scheme that is not only secure but also significantly improves the time-memory trade-off. Specifically, we improve the online execution time by a factor of 2^(n-l). Our proposed scheme is proved 2-SNI secure in the probing leakage model. We have implemented our method for AES-128 on a 32-bit ARM Cortex processor. We are able to reduce the memory required to store a randomised S-box table for second-order AES-128 implementation to 59 bytes.

crypto 4-bit substitution boxes or crypto 4-bit S-boxes are used in block ciphers for nonlinear substitution very frequently. If the 16 elements of a 4-bit S-box are unique, distinct and vary between 0 and f in hex then the said 4-bit S-box is called as a crypto 4-bit S-box. There are 16! crypto 4-bit S-boxes available in crypto literature. Other than crypto 4-bit S-boxes there are another type of 4-bit S-boxes exist. In such 4-bit S-boxes 16 elements of the 4-bit S-box are not unique and distinct i.e. at least one element must repeat more than one time. They are called as non-crypto 4-bit S-boxes. There are 16^16-factorial 16 Numbers of non-crypto 4-bit S-boxes can be found in crypto-literature. The non-crypto 4-bit S-boxes can be generated from 4-bit Boolean Functions (BFs) in the same manner as crypto 4-bit S-boxes are generated in [1]. But to generate crypto 4-bit S-boxes the security of the generated 4-bit S-boxes is sacrificed into some extend. Since 12870 4-bit balanced BFs are responsible for factorial 16 crypto 4-bit S-boxes and the nonlinearity of the balanced 4-bit BFs are at most 4. So the 4-bit BFs with highest nonlinearity 6 are left abandoned. These 4-bit BFs are called as 4-bit Bent BFs. Here in this paper we generate non-crypto 4-bit S-boxes from 4-bit Bent BFs. The generated non-crypto 4-bit S-boxes are analyzed with the existing cryptanalysis techniques to prove them much secure 4-bit S-boxes from crypto angle.

The Network and Information Security Group is currently looking for several motivated and talented researchers at all levels (PhD, PostDoc) to contribute to research projects related to applied cryptography, hardware security, security and privacy. The successful candidates will primarily be working on the following topics (but not limited to):

• Differential Privacy;
• Functional Encryption;
• Privacy-Preserving Analytics;
• Privacy-Preserving Machine Learning;
• Searchable Encryption and data structures enabling efficient search operations on encrypted data;
• Processing of encrypted data in outsourced and untrusted environments;
• Applying encrypted search techniques to Trusted Execution Environments;
• Revocable Attribute-Based Encryption schemes and their application to cloud services;
• IoT Security and Applications to Smart Cities;
• Side Channel Analysis (SCA);
• Machine Learning based SCA;
• Embedded security (e.g. ARM-based SoC);
• TEE security and development (e.g. TrustZone, Trusted Applications, etc.).

Programming skills is a must.

The positions are principa research-focused. Activities include:

• Conducting both theoretical and applied research;
• Design of secure and/or privacy-preserving protocols;
• Software development and validation;
• Reading and writing scientific articles;
• Presentation of the research results at seminars and conferences in Finland and abroad;
• Acquiring (or assisting in acquiring) further funding.

Successful candidates will be working in EU and industrial research projects. Topics will be spanning from the theoretical foundations of cryptography to the design and implementation of provable secure communication protocols with direct applications to smart cities, cloud computing and eHealth.

To apply please send the following:

• Your latest CV;
• A research statement (max 2 pages long);
• The three best papers you have co-authored.

Closing date for applications:

Contact:

• Billy Bob Brumley (Hardware Security and SCA): billy.brumley@tuni.fi
• Antonis Michalas (Provable Security and Privacy): antonios.michalas@tuni.fi

More information: https://research.tuni.fi/vision/open-positions-2020/

We initiate the study of encryption schemes where the decryption keys are unclonable quantum objects, which we call single decryptor encryption. We give a number of initial results in this area:

-We formalize the notion of single decryptor encryption. -We show that secret-key single decryptor encryption is possible unconditionally, in the setting where a limited number of ciphertexts are given. However, given an encryption oracle, we show that unconditional security is impossible. -We show how to use a very recent notion of one-shot signatures, together with sufficiently powerful witness encryption, to achieve public key single decryptor encryption. -We demonstrate several extensions of our scheme, achieving a number of interesting properties that are not possible classically.

Internet of Things is developing at a very fast rate. In order to ensure security and privacy, end-devices (e.g. smartphones, smart sensors, or any connected smartcards) shall be protected both against cyber attacks (coming down from the network) and against physical attacks (arising from attacker low-level interaction with the device). In this context, proactive protections shall be put in place to mitigate information theft from either side-channel monitoring or active computation/data corruption. Although both countermeasures have been developing fast and have become mature, there has surprisingly been little research to combine both.

In this article, we tackle this difficult topic and highlight a viable solution. It is shown to be more efficient than mere fault detection by repetition (which is anyway prone to repeated correlated faults). The presented solution leverages the fact that both side-channel protection and fault attack detection are coding techniques. We explain how to both prevent (higher-order) side-channel analyses and detect (higher-order) fault injection attacks. The specificity of this method is that it works ``end-to-end'', meaning that the detection can be delayed until the computation is finished. This simplifies considerably the error management logic as there is a single verification throughout the computation.

The final exponentiation, which is the exponentiation by a fixed large exponent, must be performed in the Tate and (optimal) Ate pairing computation to ensure output uniqueness, algorithmic correctness, and security for pairing-based cryptography. In this paper, we propose a new framework of efficient final exponentiation for pairings over families of elliptic curves. Our framework provides two methods: the first method supports families of elliptic curves with arbitrary embedding degrees, and the second method supports families with specific embedding degrees of providing even faster algorithms. Applying our framework to several Barreto-Lynn-Scott families, we obtain faster final exponentiation than the previous state-of-the-art constructions.

We put forward a new abstraction for achieving forward-secure signatures that are (1) short, (2) have fast update and signing and (3) have small private key size. Prior work that achieved these parameters was pioneered by the pebbling techniques of Itkis and Reyzin (CRYPTO 2001) which showed a process for generating a sequence of roots $h^{1/e_1}, h^{1/e_2}, \dots, h^{1/e_T}$ for a group element $h$ in $\mathbb{Z}_N^*$. However, the current state of the art has limitations.

First, while many works claim that Itkis-Reyzin pebbling can be applied, it is seldom shown how this non-trivial step is concretely done. Second, setting up the pebbling data structure takes $T$ time which makes key generation using this approach expensive. Third, many past works require either random oracles and/or the Strong RSA assumption; we will work in the standard model under the RSA assumption.

We introduce a new abstraction that we call an RSA sequencer. Informally, the job of an RSA sequencer is to store roots of a public key $U$, so that at time period $t$, it can provide $U^{1/e_t}$, where the value $e_t$ is an RSA exponent computed from a certain function. This separation allows us to focus on building a sequencer that efficiently stores such values, in a forward-secure manner and with better setup times than other comparable solutions. Our sequencer abstraction also has certain re-randomization properties that allow for constructing forward-secure signatures with a single trusted setup that takes $T$ time and individual key generation takes $\lg(T)$ time.

We demonstrate the utility of our abstraction by using it to provide concrete forward-secure signature schemes. We first give a random-oracle construction that closely matches the performance and structure of the Itkis-Reyzin scheme with the important exception that key generation is much faster (after the one-time setup). We then move on to designing a standard model scheme. This abstraction and illustration of how to use it may be useful for other future works.

We include a detailed performance evaluation of our constructions, with an emphasis on the time and space costs for large caps on the maximum number of time periods $T$ supported. Our philosophy is that frequently updating forward secure keys should be part of ``best practices'' in key maintenance. To make this practical, even for bounds as high as $T=2^{32}$, we show that after an initial global setup, it takes only seconds to generate a key pair, and only milliseconds to update keys, sign messages and verify signatures. The space requirements for the public parameters and private keys are also a modest number of kilobytes, with signatures being a single element in $\mathbb{Z}_N$ and one smaller value.

Progress in quantum technologies forces the development of new cryptographic primitives that are resistant to attacks of an adversary with a quantum computer. A large number of key establishment schemes have been proposed for two participants, but the area of group post-quantum key establishment schemes has not been studied a lot. Not so long ago, an isogeny-based key agreement scheme was proposed for three participants, based on a gradual increase in the degree of the key. We propose another principle for establishing a key for a group of participants using a tree-structure. The proposed key establishment scheme for four participants uses isogeny of elliptic curves as a mathematical tool.

The side-channel community recently investigated a new approach, based on deep learning, to significantly improve profiled attacks against embedded systems. Compared to template attacks, deep learning techniques can deal with protected implementations, such as masking or desynchronization, without substantial pre-processing. However, important issues are still open. One challenging problem is to adapt the methods classically used in the machine learning field (e.g. loss function, performance metrics) to the specific side-channel context in order to obtain optimal results. We propose a new loss function derived from the learning to rank approach that helps preventing approximation and estimation errors, induced by the classical cross-entropy loss. We theoretically demonstrate that this new function, called Ranking Loss (RkL), maximizes the success rate by minimizing the ranking error of the secret key in comparison with all other hypotheses. The resulting model converges towards the optimal distinguisher when considering the mutual information between the secret and the leakage. Consequently, the approximation error is prevented. Furthermore, the estimation error, induced by the cross-entropy, is reduced by up to 23%. When the ranking loss is used, the convergence towards the best solution is up to 23% faster than a model using the cross-entropy loss function. We validate our theoretical propositions on public datasets.

One-time memories (OTM) are the hardware version of oblivious transfer, and are useful for constructing objects that are impossible with software alone, such as one-time programs. In this work, we consider attacks on OTMs where a quantum adversary can leverage his physical access to the memory to mount quantum ``superposition attacks'' against the memory. Such attacks result in significantly weakened OTMs. For example, in the application to one-time programs, it may appear that such an adversary can always “quantumize” the classical protocol by running it on a superposition of inputs, and therefore learn superpositions of outputs of the protocol.

Perhaps surprisingly, we show that this intuition is false: we construct one-time programs from quantum-accessible one-time memories where the view of an adversary, despite making quantum queries, can be simulated by making only classical queries to the ideal functionality. At the heart of our work is a method of immunizing one-time memories against superposition attacks.

Learning parity with noise (LPN) is a notorious (average-case) hard problem that has been well studied in learning theory, coding theory and cryptography since the early 90's. It further inspires the Learning with Errors (LWE) problem [Regev, STOC 2005], which has become one of the central building blocks for post-quantum cryptography and advanced cryptographic primitives such as fully homomorphic encryption [Gentry, STOC 2009]. Unlike LWE whose hardness can be reducible from worst-case lattice problems, no corresponding worst-case hardness results were known for LPN until very recently. At Eurocrypt 2019, Brakerski et al. [BLVW19] established the first feasibility result that the worst-case hardness of nearest codeword problem (NCP) (on balanced linear code) at the extremely low noise rate $\frac{log^2 n}{n}$ implies the quasi-polynomial hardness of LPN at the extremely high noise rate $1/2-1/poly(n)$. It remained open whether a worst-case to average-case reduction can be established for standard (constant-noise) LPN, ideally with sub-exponential hardness.

In this paper, we carry on the worst-case to average-case reduction for LPN [BLVW19]. We first expand the underlying binary linear codes (of the worst-case NCP) to not only the balanced code considered in [BLVW19] but also to another code (in some sense dual to balanced code). At the core of our reduction is a new variant of smoothing lemma (for both binary codes) that circumvents the barriers (inherent in the underlying worst-case randomness extraction) and admits tradeoffs for a wider spectrum of parameter choices. In addition to the worst-case hardness result obtained in [BLVW19], we show that for any constant $0<c<1$ the constant-noise LPN problem is ($T=2^{\Omega(n^{1-c})},\epsilon=2^{-\Omega(n^{min(c,1-c)})},q=2^{\Omega(n^{min(c,1-c)})}$)-hard assuming that the NCP (on either code) at the low-noise rate $\tau=n^{-c}$ is ($T'={2^{\Omega(\tau n)}}$, $\epsilon'={2^{-\Omega(\tau n)}}$,$m={2^{\Omega(\tau n)}}$)-hard in the worst case, where $T$, $\epsilon$, $q$ and $m$ are time complexity, success rate, sample complexity, and codeword length respectively. Moreover, refuting the worst-case hardness assumption would imply arbitrary polynomial speedups over the current state-of-the-art algorithms for solving the NCP (and LPN), which is a win-win result. Unfortunately, public-key encryptions and collision resistant hash functions would need constant-noise LPN with ($T={2^{\omega(\sqrt{n})}}$, $\epsilon'={2^{-\omega(\sqrt{n})}}$,$q={2^{\sqrt{n}}}$)-hardness (Yu et al., CRYPTO 2016 \& ASIACRYPT 2019), which is almost (up to an arbitrary $\omega(1)$ factor in the exponent) what is reducible from the worst-case NCP when $c= 0.5$. We leave it as an open problem whether the gap can be closed or there is a separation in place.

In this article, we propose an adaptation of the algorithmic reduction theory of lattices to binary codes. This includes the celebrated LLL algorithm (Lenstra, Lenstra, Lovasz, 1982), as well as adaptations of associated algorithms such as the Nearest Plane Algorithm of Babai (1986). Interestingly, the adaptation of LLL to binary codes can be interpreted as an algorithmic version of the bound of Griesmer (1960) on the minimal distance of a code.

Using these algorithms, we demonstrate ---both with a heuristic analysis and in practice--- a small polynomial speed-up over the Information-Set Decoding algorithm of Lee and Brickell (1988) for random binary codes. This appears to be the first such speed-up that is not based on a time-memory trade-off.

The above speed-up should be read as a very preliminary example of the potential of a reduction theory for codes, for example in cryptanalysis. In constructive cryptography, this algorithmic reduction theory could for example also be helpful for designing trapdoor functions from codes.

The primary function of a cryptocurrency is money transfer between individuals. The wallet is the software that facilitates such transfers. Wallets are nowadays ubiquitous in the cryptocurrency space and a cryptocurrency is usually supported by many wallets. Despite that, the functionality of wallets has never been formally defined. Additionally, the mechanisms employed by the many wallets in the wild remain hidden in their respective codebases.

In this work we provide the first definition of a cryptocurrency wallet, which we model as a client to a server, or set of servers. We provide a distinction of wallets in various categories, based on whether they work for transparent or private cryptocurrencies, what trust assumptions they require, their performance and their communication overhead. For each type of wallet we provide a description of its client and server protocols. Additionally, we explore superlight wallets and describe their difference to superlight clients that have appeared in recent literature. We demonstrate how new wallet protocols can be produced by combining concepts from existing protocols. Finally we evaluate the performance and security characteristics of all wallet protocols and compare them.

Recently, many profiling side-channel attacks based on Machine Learning and Deep Learning have been proposed. Most of them focus on reducing the number of traces required for successful attacks by optimizing the modeling algorithms. In previous work, relatively sufficient traces need to be used for training a model. However, in the practical profiling phase, it is difficult or impossible to collect sufficient traces due to the constraint of various resources. In this case, the performance of profiling attacks is inefficient even if proper modeling algorithms are used. In this paper, the main problem we consider is how to conduct more efficient profiling attacks when sufficient profiling traces cannot be obtained. To deal with this problem, we first introduce the Conditional Generative Adversarial Network (CGAN) in the context of side-channel attacks. We show that CGAN can generate new traces to enlarge the size of the profiling set, which improves the performance of profiling attacks. For both unprotected and protected cryptographic algorithms, we find that CGAN can effectively learn the leakage of traces collected in their implementations. We also apply it to different modeling algorithms. In our experiments, the model constructed with the augmented profiling set can reduce the required attack traces by more than half, which means the generated traces can provide useful information as the real traces.

The currently proposed RISC-V True Random Number Generator (TRNG) architecture breaks with previous ISA TRNG practice by splitting the Entropy Source (ES) component away from cryptographic PRNGs into a separate interface, and in its use of polling. We describe the interface, its use in cryptography, and offer additional discussion, background, and rationale for various aspects of it. This design is informed by lessons learned from earlier mainstream ISAs, recently introduced SP 800-90B and FIPS 140-3 entropy audit requirements, AIS 31 and Common Criteria, current and emerging cryptographic needs such as post-quantum cryptography, and the goal of supporting a wide variety of RISC-V implementations and applications. Many of the architectural choices are a result of quantitative observations about random number generators in secure microcontrollers, the Linux kernel, and cryptographic libraries (OpenSSL). We further compare the architecture to some contemporary random number generators and describe a minimalistic TRNG reference implementation that uses the Entropy Source together with RISC-V AES instructions.

We propose Agora, the first blockchain-based data marketplace that enables multiple privacy-concerned parties to get compensated for contributing and exchanging data, without relying on a trusted third party during the exchange. Agora achieves data privacy, output verifiability, and atomicity of payments by leveraging cryptographic techniques, and is designed as a decentralized application via smart contracts. Particularly, data generators provide encrypted data to data brokers who use a functional secret key to learn nothing but the output of a specific, agreed upon, function over the raw data. Data consumers can purchase decrypted outputs from the brokers, accompanied by corresponding proofs of correctness. We implement a working prototype of Agora on Ethereum and experimentally evaluate its performance and deployment costs. As a core building block of Agora, we propose a new functional encryption scheme with additional public parameters that operate as a trust anchor for verifying decrypted results.

In this paper, we propose a new private set intersection (PSI) protocol that computes the following functionality. The two parties ($P_1$ and $P_2$) input two sets of items ($X$ and $Y$, respectively) and one of the parties outputs a function of the intersection ($f(X \cap Y)$). This functionality is generally required when the PSI protocol is used as a part of a larger secure two-party secure computation. Pinkas et al. presented a PSI protocol at Eurocrypt 2019 for this functionality, which has linear complexity only in communication. While there are PSI protocols with linear computation and communication complexities in the classical PSI setting where the intersection itself is revealed to one party, to the best of our knowledge, there is no PSI protocol, which outputs a function of the intersection and satisfies linear complexity in both communication and computation. We present the first PSI protocol that outputs only a function of the intersection with linear communication and computation complexities. While creating the protocol, as a side contribution, we provide a one-time oblivious programmable pseudo-random function based on garbled Bloom filters. We also implemented our protocol and provide performance results.

Contact tracing is an essential component of public health efforts to slow the spread of COVID-19 and other infectious diseases. Automating parts of the contact tracing process has the potential to significantly increase its scalability and efficacy, but also raises an array of privacy concerns, including the risk of unwanted identification of infected individuals and clandestine collection of privacy-invasive data about the population at large.

In this paper, we focus on automating the exposure notification part of contact tracing, which notifies people who have been in close proximity to infected people of their potential exposure to the virus. This work is among the first to focus on the privacy aspects of automated exposure notification. We introduce two privacy-preserving exposure notification schemes based on proximity detection. Both systems are decentralized -- no central entity has access to sensitive data. The first scheme is simple and highly efficient, and provides strong privacy for non-diagnosed individuals and some privacy for diagnosed individuals. The second scheme provides enhanced privacy guarantees for diagnosed individuals, at some cost to efficiency. We provide formal definitions for automated exposure notification and its security, and we prove the security of our constructions with respect to these definitions.