International Association
for Cryptologic Research

The breakthrough of blockchain in many decentralized cryptocurrencies has reactivated studies on consensus under network synchrony, which has better security than a consensus under network asynchrony but has been considered to be impractical and only theoretical so far. One of the biggest concerns is the speed of transaction processing. To solve this concern, transactions can be processed responsively, i.e., without reliance on synchrony. Another approach is to minimize reliance on synchrony to achieve optimal synchronous latency. In this paper, we consider answering the question ”Can we achieve both responsiveness and optimal synchronous latency?”. To do this, we first show some theoretical possibilities and impossibilities in achieving both responsiveness and optimal synchronous latency, and then we present a practical blockchain or state machine replication protocol we call Hybrid-BFT. Hybrid-BFT can process transactions responsively under normal situation, i.e., small number of faults, while it can achieve optimal synchronous latency even under worst situation. Furthermore, Hybrid-BFT achieves responsive leader change, making it completely free from synchronous delay under normal situation.

Modern electronic voting systems (e-voting systems) are designed to provide not only vote privacy but also (end-to-end) verifiability. Several verifiable e-voting systems have been proposed in the literature, with Helios being one of the most prominent ones.

Almost all such systems, however, reveal not just the voting result but also the full tally, consisting of the exact number of votes per candidate or even all single votes. There are several situations where this is undesirable. For example, in elections with only a few voters (e.g., boardroom or jury votings), revealing the complete tally leads to a low privacy level, possibly deterring voters from voting for their actual preference. In other cases, revealing the complete tally might unnecessarily embarrass some candidates. Often, the voting result merely consists of a single winner or a ranking of candidates, so revealing only this information but not the complete tally is sufficient. This property is called tally-hiding and it offers completely new options for e-voting.

In this paper, we propose the first provably secure end-to-end verifiable tally-hiding e-voting system, called Ordinos. We instantiated our system with suitable cryptographic primitives, including an MPC protocol for greater-than tests, implemented the system, and evaluated its performance, demonstrating its practicality. Moreover, our work provides a deeper understanding of tally-hiding in general, in particular in how far tally-hiding affects the levels of privacy and verifiability of e-voting systems.

In this work we develop a rewarding framework that can be used as a building block in crowd-sensing applications. Although a core requirement of such systems is user engagement, people may be reluctant to participate as sensitive information about them may be leaked or inferred from submitted data. Thus monetary incentives could help attract a large number of participants, thereby increasing not only the amount but also the quality of sensed data. Our first contribution in this work is to ensure that users can submit data and obtain Bitcoin payments in a privacy-preserving manner, preventing curious providers from linking the data or the payments back to the user. At the same time, we thwart malicious user behavior such as double-redeeming attempts where a user tries to obtain rewards for multiple submissions of the same data. More importantly, we ensure the fairness of the exchange in a completely trustless manner; by relying on the Blockchain, we eliminate the trust placed on third parties in traditional fair exchange protocols. Finally, our system is highly efficient as most of the protocol steps do not utilize the Blockchain network. When they do, we only rely on simple Bitcoin transactions as opposed to prior works that are based on the use of highly complex smart contracts.

Chameleon-hash functions, introduced by Krawczyk and Rabin at NDSS 2000, are trapdoor collision-resistant hash-functions parametrized by a public key. If the corresponding secret key is known, arbitrary collisions for the hash function can be efficiently found. Chameleon-hash functions have prominent applications in the design of cryptographic primitives, such as lifting non-adaptively secure signatures to adaptively secure ones. Recently, this primitive also received a lot of attention as a building block in more complex cryptographic applications ranging from editable blockchains to advanced signature and encryption schemes.

We observe that in latter applications various different notions of collision-resistance are used, and it is not always clear if the respective notion does really cover what seems intuitively required by the application. Therefore, we revisit existing collision-resistance notions in the literature, study their relations, and - using the example of the recent redactable blockchain proposals - discuss which practical impact different notions of collision-resistance might have. Moreover, we provide a stronger, and arguably more desirable, notion of collision-resistance than what is known from the literature. Finally, we present a surprisingly simple and efficient black-box construction of chameleon-hash functions achieving this strong notion.

As part of our planned expansion in the area of Cybersecurity, the Department of Mathematics and Computer Science at the University of Southern Denmark, Odense, invites applications for an assistant professor position in Computer Science. We interpret the area cybersecurity broadly: the ideal applicant is a computer scientist with a strong theoretical background, conducting research on cybersecurity or research that has cybersecurity as a direct application. We would like to expand on our current security research efforts within Cryptology, Formal Methods, Information Security, Security in DevOps, and Data-driven approaches, so these topics are of particular interest. Application deadline: 30 May 2020.

Closing date for applications:

Contact: Jacopo Mauro mauro@imada.sdu.dk or Joan Boyar joan@imada.sdu.dk

More information: https://www.sdu.dk/da/service/ledige_stillinger/1098235

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).