International Association
for Cryptologic Research

In this short note, we show that substantially weaker Low Order assumptions are sufficient to prove the soundness of Pietrzak's protocol for proof of exponentiation in groups of unknown order. This constitutes the first step to a better understanding of the asymptotic computational complexity of breaking the soundness of the protocol. Furthermore, we prove the equivalence of the (weaker) Low Order assumption(s) and the Factoring assumption in RSA groups for a non-negligible portion of moduli. We argue that in practice our reduction applies for a considerable amount of deployed moduli. Our results have cryptographic applications, most importantly in the theory of recently proposed verifiable delay function constructions. Finally, we describe how to certify RSA moduli free of low order elements.

Non-interactive zero-knowledge proofs, and more specifically succinct non-interactive zero-knowledge arguments (zk-SNARKS), have been proven to be the “swiss army knife” of the blockchain and distributed ledger space, with a variety of applications in privacy, interoperability and scalability. Many commonly used SNARK systems rely on a structured reference string, the secure generation of which turns out to be their Achilles heel: If the randomness used for the generation is known, the soundness of the proof system can be broken with devastating consequences for the underlying blockchain system that utilises them. In this work we describe and analyze, for the first time, a blockchain mechanism that produces a secure SRS with the characteristic that security is shown for the exact same conditions under which the blockchain protocol is proven to be secure. Our mechanism makes use of the recent discovery of updateable structure reference strings to perform this secure generation in a fully distributed manner. In this way, the SRS emanates from the normal operation of the blockchain protocol itself without the need of additional security assumptions or off-chain computation and/or verification. We provide concrete guidelines for the parameterisation of this system which allows for the completion of a secure setup in a reasonable period of time. We also provide an incentive scheme that, when paired with the update mechanism, properly incentivises participants into contributing to secure reference string generation.

In an article presented at FDTC 2018, Arribas, De Cnudde, and Sijacic prove under mild conditions that threshold implementations (TIs) are secure against fault sensitivity analysis (FSA). Later in 2018, in the PhD thesis of De Cnudde, additional assumptions were imposed to provably withstand FSA, thereby increasing the required number of random bits. We point out that even under the latter, stronger conditions, the proof remains incorrect.

To help fighting the COVID-19 pandemic, the Pan-European Privacy-Preserving Proximity Tracing (PEPP-PT) project proposed a Decentralized Privacy-Preserving Proximity Tracing (DP3T) system. This helps tracking the spread of SARS-CoV-2 virus while keeping the privacy of individuals safe. In this report, we analyze the security and the privacy protection of DP3T. Without questioning how effective it could be against the pandemic, we show that it may introduce severe risks to society. Furthermore, we argue that some privacy protection measurements by DP3T may have the opposite affect of what they were intended to. Specifically, sick and reported people may be deanonymized, private encounters may be revealed, and people may be coerced to reveal the private data they collect.

Contact tracing is a promising approach to combat the COVID -19 pandemic. Various systems have been proposed to automatise the process. However, user privacy was not a major design goal in most of these systems. Other designs rely heavily on a centralised server or reveal significant amounts of private data to health authorities. We propose CAUDHT, a decentralized peer-to-peer system for contact tracing. The central health authority can focus on providing and operating tests for the disease while contact tracing is done by the system’s users themselves. We use a distributed hash table to build a decentral messaging system for infected patients and their contacts. With blind signatures, we ensure that messages about infections are authentic and unchanged. A strong privacy focus enables data integrity, confidentiality, and privacy.

In this paper, we present all 4-bit S-boxes which are able to support BOGI logic. We exhaustively show that only 2,413 PXE classes of 4-bit S-box are BOGI-applicable among the 142,090,700 PXE classes. We evaluate the whole BOGI-applicable S-boxes in terms of the security and implementation costs. The security evaluation includes security strength of the S-boxes themselves, and how they affect the resistance of GIFT-64 against differential and linear cryptanalysis (DC and LC). The security evaluation shows that all the BOGI-applicable S-boxes fulfill the security criteria of GIFT designers as long as they have the differential uniformity and linearity as 6 and 8, respectively. It will also be shown that the security of GIFT-64 against DC and LC can be improved only by changing the S-box. Moreover, we evaluate the implementation costs of the BOGI-applicable S-boxes by finding their optimal implementation. The results show that GIFT S-box is well-chosen considering existence of fixed-points, and suggest a set of S-boxes providing the same implementation cost as GIFT S-box. Finally, we suggest a set of potentially better S-boxes for GIFT-64 based on our investigations.

In recent years, deep learning-based side-channel attacks have established its position as mainstream. However, most deep learning techniques for cryptanalysis mainly focused on classifying side-channel information in a profiled scenario where attackers can obtain the label of training data. In this paper, we introduce a novel approach with deep learning for improving side-channel attacks, especially in a non-profiling scenario. We also propose a new method that trains autoencoder through the noise from real data using the noise-reduced-label. It notably diminishes the noise in a trace by adapting the autoencoder framework to the signal preprocessing. We show the convincing comparison from our custom dataset, which captured that our works outperform conventional preprocessing methods such as principal component analysis and linear discriminant analysis. Furthermore, we apply the method to realign desynchronized traces that applied hiding countermeasures, and we experimentally validate the performance of the proposal. Also, for masking countermeasures, we experimentally show that we can improve the performance of side-channel analysis by using an existing combining function or proposed method using domain knowledge.

Reductions between problems, the mainstay of theoretical computer science, efficiently map an instance of one problem to an instance of another in such a way that solving the latter allows solving the former. The subject of this work is ``lossy'' reductions, where the reduction loses some information about the input instance. We show that such reductions, when they exist, have interesting and powerful consequences for lifting hardness into ``useful'' hardness, namely cryptography.

Our first, conceptual, contribution is a definition of lossy reductions in the language of mutual information. Roughly speaking, our definition says that a reduction $\mathsf{C}$ is $t$-lossy if, for any distribution $X$ over its inputs, the mutual information $I(X;\mathsf{C}(X)) \leq t$. Our treatment generalizes a variety of seemingly related but distinct notions such as worst-case to average-case reductions, randomized encodings (Ishai and Kushilevitz, FOCS 2000), homomorphic computations (Gentry, STOC 2009), and instance compression (Harnik and Naor, FOCS 2006).

We then proceed to show several consequences of lossy reductions:

1. We say that a language $L$ has an $f$-reduction to a language $L'$ for a Boolean function $f$ if there is a (randomized) polynomial-time algorithm $\mathsf{C}$ that takes an $m$-tuple of strings $X = (x_1,\ldots,x_m)$, with each $x_i\in\{0,1\}^n$, and outputs a string $z$ such that with high probability, \begin{align*} L'(z) = f(L(x_1),L(x_2),\ldots,L(x_m)) \end{align*} 2. Suppose a language $L$ has an $f$-reduction $\mathsf{C}$ to $L'$ that is $t$-lossy. Our first result is that one-way functions exist if $L$ is worst-case hard and one of the following conditions holds: - $f$ is the OR function, $t \leq m/100$, and $L'$ is the same as $L$ - $f$ is the Majority function, and $t \leq m/100$ - $f$ is the OR function, $t \leq O(m\log{n})$, and the reduction has no error

This improves on the implications that follow from combining (Drucker, FOCS 2012) with (Ostrovsky and Wigderson, ISTCS 1993) that result in {\em auxiliary-input} one-way functions.

3. Our second result is about the stronger notion of $t$-compressing $f$-reductions -- reductions that only output $t$ bits. We show that if there is an average-case hard language $L$ that has a $t$-compressing Majority reduction to some language for $t=m/100$, then there exist collision-resistant hash functions.

This improves on the result of (Harnik and Naor, STOC 2006), whose starting point is a cryptographic primitive (namely, one-way functions) rather than average-case hardness, and whose assumption is a compressing OR-reduction of SAT (which is now known to be false unless the polynomial hierarchy collapses).

Along the way, we define a non-standard one-sided notion of average-case hardness, which is the notion of hardness used in the second result above, that may be of independent interest.

We propose a new approach to construct general-purpose indistinguishability obfuscation (iO). Our construction is obtained via a new intermediate primitive that we call split fully-homomorphic encryption (split FHE), which we show to be sufficient for constructing iO. Specifically, split FHE is FHE where decryption takes the following two-step syntactic form: (i) A secret decryption step uses the secret key and produces a hint which is (asymptotically) shorter than the length of the encrypted message, and (ii) a public decryption step that only requires the ciphertext and the previously generated hint (and not the entire secret key), and recovers the encrypted message. In terms of security, the hints for a set of ciphertexts should not allow one to violate semantic security for any other ciphertexts.

Next, we show a generic candidate construction of split FHE based on three building blocks: (i) A standard FHE scheme with linear decrypt-and-multiply (which can be instantiated with essentially all LWE-based constructions), (ii) a linearly homomorphic encryption scheme with short decryption hints (such as the Damgard-Jurik encryption scheme, based on the DCR problem), and (iii) a cryptographic hash function (which can be based on a variety of standard assumptions). Our approach is heuristic in the sense that our construction is not provably secure and makes implicit assumptions about the interplay between these underlying primitives. We show evidence that this construction is secure by providing an argument in an appropriately defined oracle model.

We view our construction as a big departure from the state-of-the-art constructions, and it is in fact quite simple.

We study the problem of secure two-party computation of arithmetic circuits in the presence of active (``malicious'') parties. This problem is motivated by privacy-preserving numerical computations, such as ones arising in the context of machine learning training and classification, as well as in threshold cryptographic schemes.

In this work, we design, optimize, and implement an actively secure protocol for secure two-party arithmetic computation. A distinctive feature of our protocol is that it can make a fully modular black-box use of any passively secure implementation of oblivious linear function evaluation (OLE). OLE is a commonly used primitive for secure arithmetic computation, analogously to the role of oblivious transfer in secure computation for Boolean circuits.

For typical (large but not-too-narrow) circuits, our protocol requires roughly 4 invocations of passively secure OLE per multiplication gate. This significantly improves over the recent TinyOLE protocol (Dottling et al., ACM CCS 2017), which requires 22 invocations of actively secure OLE in general, or 44 invocations of a specific code-based passively secure OLE.

Our protocol follows the high level approach of the IPS compiler (Ishai et al., CRYPTO 2008, TCC 2009), optimizing it in several ways. In particular, we adapt optimization ideas that were used in the context of the practical zero-knowledge argument system Ligero (Ames et al., ACM CCS 2017) to the more general setting of secure computation, and explore the possibility of boosting efficiency by employing a ``leaky'' passively secure OLE protocol. The latter is motivated by recent (passively secure) lattice-based OLE implementations in which allowing such leakage enables better efficiency.

We showcase the performance of our protocol by applying its implementation to several useful instances of secure arithmetic computation. On ``wide'' circuits, such as ones computing a fixed function on many different inputs, our protocol is 5x faster and transmits 4x less data than the state-of-the-art Overdrive (Keller et al., Eurocrypt 2018). Our benchmarks include a general passive-to-active OLE compiler, authenticated generation of ``Beaver triples'', and a system for securely outsourcing neural network classification. The latter is the first actively secure implementation of its kind, strengthening the passive security provided by recent related works (Mohassel and Zhang, IEEE S&P 2017; Juvekar et al., USENIX 2018).

LRBC is a new lightweight block cipher that has been proposed for resource-constrained IoT devices. The cipher is claimed to be secure against differential cryptanalysis and linear cryptanalysis. However, beside short state length which is only 16-bits, the structures of the cipher only use the linear operations, the its s-boxes, and this is a reason why the cipher is completely insecure against the mentioned attacks. we present a few examples to show that. Also, we show that the round function of LRBC has some structural problem and even if we fix them the cipher does not provide complete diffusion. Hence, even with replacement of the cipher s-boxes with proper s-boxes, the problem will not be fixed and it is possible to provide deterministic distinguisher for any number of round of the cipher. In addition, we show that for any fixed key, it is possible to create a full code book for the cipher with the complexity of $2^{n/2}$, which should be compared with $2^{n}$ for any secure $n$-bit block cipher.

The implementation of isogeny-based cryptography mainly use Montgomery curves as they offer fast elliptic curve arithmetic and isogeny compuation. However, although Montgomery curves have efficient 3- and 4-isogenies, it becomes inefficient when recovering the coefficient of the image curve for large degree isogenies. This is the main bottleneck of using a Montgomery curve for CSIDH as it requires odd-degree isogenies up to at least 587. In this paper, we present a new optimization method for faster CSIDH protocols entirely on Montgomery curves. To this end, we present a new parameter for CSIDH in which the rational 2-torsion points are defined over $\mathbb{F}_p$. By using the proposed parameters the CSIDH moves around the surface. The curve coefficient of the image curve can be recovered by a 2-torsion point. We also proved that the CSIDH using the proposed parameter guarantees a free and transitive group action. Additionally, we present the implementation result using our method. We demonstrated that our method is 8.6% faster than the original CSIDH. Our works show that quite higher performance of CSIDH is achieved using only Montgomery curves.

The Franco-Prussian war (1870--1871) was the first major European conflict during which extensive telegraph use enabled fast communication across large distances. Field officers would therefore have to learn how to use secret codes. But training officers also raises the probability that defectors would reveal these codes to the enemy. Practically all known secret codes at the time could be broken if the enemy knew how they worked.

Under Kerckhoffs' impulsion, the French military thus developed new codes, meant to resist even if the adversary knew the encoding and decoding algorithms, but simple enough to be explained and taught to military personnel.

Many of these codes were lost to history. One of the designs however, due to Major H. D. Josse, has been recovered and this article describes the features, history, and role of this particular construction. Josse's code was considered for field deployment and underwent some experimental tests in the late 1800s, the result of which were condensed in a short handwritten report. During World War II, German forces got hold of documents describing Josse's work, and brought them to Berlin to be analyzed. A few years later these documents moved to Russia, where they have resided since.

Encoding an arbitrary bit string, by parceling it out to randomized size subsections, encoding each subsection through a unary alphabet, thereby expressing the original string via a much larger one, which upon transposition projects up to perfect mathematical secrecy. The attraction of TEAM (Transposition Encryption Alphabet Method) is in the fact that it replaces common floating-point complex computational ciphers with the utter simplicity and speed of nothing more than one round of transposition. Also enabling decoy bits, which are recognized as noise by the intended recipient, while presenting a cryptanalytic burden on the attacker. Implemented in hardware TEAM is very battery-friendly, fitting for Internet of Things application. TEAM security is based on equivocation, which classifies it as post quantum cryptography. TEAM’s efficacy may be upgraded unilaterally by the transmitter through increased use of ad-hoc, not pre-shared randomness.

This paper introduces 4 way vectorization of Montgomery ladder on any Montgomery form elliptic curve. Our algorithm takes 2M^4+1S^4 (M^4: A vector of four field multiplications, S^4: A vector of four field squarings) per ladder step for variable-scalar variable-point multiplication. This paper also introduces new formulas for doing arithmetic over GF(2^255-19).

Noisy measurements of a physical unclonable function (PUF) are used to store secret keys with reliability, security, privacy, and complexity constraints. A new set of low-complexity and orthogonal transforms with no multiplication is proposed to obtain bit-error probability results significantly better than all methods previously proposed for key binding with PUFs. The uniqueness and security performance of a transform selected from the proposed set is shown to be close to optimal. An error-correction code with a low-complexity decoder and a high code rate is shown to provide a block-error probability significantly smaller than provided by previously proposed codes with the same or smaller code rates.

While accountability is a well-known concept in distributed systems and cryptography, in the literature on blockchains (and, more generally, distributed ledgers) the formal treatment of accountability has been a blind spot: there does not exist a formalization let alone a formal proof of accountability for any blockchain yet.

Therefore, in this work we put forward and propose a formal treatment of accountability in this domain. Our goal is to formally state and prove that if in a run of a blockchain a central security property, such as consistency, is not satisfied, then misbehaving parties can be identified and held accountable. Accountability is particularly useful for permissioned blockchains where all parties know each other, and hence, accountability incentivizes all parties to behave honestly.

We exemplify our approach for one of the most prominent permissioned blockchains: Hyperledger Fabric in its most common instantiation.

Private intersection-sum with cardinality allows two parties, where each party holds a private set and one of the parties additionally holds a private integer value associated with each element in her set, to jointly compute the cardinality of the intersection of the two sets as well as the sum of the associated integer values for all the elements in the intersection, and nothing beyond that.

We present a new construction for private intersection sum with cardinality that provides malicious security with abort and guarantees that both parties receive the output upon successful completion of the protocol. A central building block for our constructions is a primitive called shuffled distributed oblivious PRF (DOPRF), which is a PRF that offers oblivious evaluation using a secret key shared between two parties, and in addition to this allows obliviously permuting the PRF outputs of several parallel oblivious evaluations. We present the first construction for shuffled DOPRF with malicious security. We further present several new sigma proof protocols for relations across Pedersen commitments, ElGamal encryptions, and Camenisch-Shoup encryptions that we use in our main construction, for which we develop new batching techniques to reduce communication.

We implement and evaluate the efficiency of our protocol and show that we can achieve communication cost that is only 4-5 times greater than the most efficient semi-honest protocol. When measuring monetary cost of executing the protocol in the cloud, our protocol is 25 times more expensive than the semi-honest protocol. Our construction also allows for different parameter regimes that enable trade-offs between communication and computation.

This article discusses a fixed critical security bug in Google Tink's Ed25519 Java implementation. The bug allows remote attackers to extract the private key with only two Ed25519 signatures. The vulnerability comes from the misunderstanding of what "final" in Java programming language means. The bug was discovered during security review before Google Tink was officially released. It reinforces the challenge in writing safe cryptographic code and the importance of the security review process even for the code written by professional cryptographers.

Mines Saint-Etienne, an IMT graduate school under the supervision of the French Ministry of Economy and Finance, is recruiting an assistant professor in Electronics and Embedded Systems at the Centre of Microelectronics in Provence.

The Centre of Microelectronics in Provence (CMP) is one of the 5 research centres and it is located in Gardanne (France, Bouches-du-Rhône). It is composed of 4 research departments including the Secure Architectures and Systems (SAS) department. The SAS department applies research to guarantee the integrity of electronic components and their contents against physical attacks by developing hardware and/or software protection schemes. The SAS department is a common research team with CEA-Tech. This team is composed of 27 persons (14 associate professors or research engineers and 13 PhD students).

The candidate must hold a PhD degree with knowledge of security and/or embedded system design. You must have a track record of research publications and/or industrial experience to contribute to the development of research interests of the SAS department. You will also demonstrate substantial proven experience of delivering teaching, learning and student support at University level.

Complete application including a cover letter, a CV with the most significant teaching and research experience, a list of publications (10 pages maximum), reference letters, a copy of your PhD degree and a copy of your passport ID should be sent to Elodie EXBRAYAT by mail : elodie.exbrayat@emse.fr before the April 30th 2020.

Closing date for applications:

Contact: Jean-Max DUTERTRE by phone + 33 (0)4 42 61 67 36 or Mail : dutertre@emse.fr for further information on the research department project

More information: https://www.mines-stetienne.fr/en/jobs-opportunities/