Here you can see all recent updates to the IACR webpage. These updates are also available:

16
September
2018

We apply Scholten's construction to give explicit isogenies between the Weil restriction of supersingular Montgomery curves with full rational 2-torsion over $GF(p^2)$ and corresponding abelian surfaces over $GF(p)$. Subsequently, we show that isogeny-based public key cryptography can exploit the fast Kummer surface arithmetic that arises from the theory of theta functions. In particular, we show that chains of 2-isogenies between elliptic curves can instead be computed as chains of Richelot (2,2)-isogenies between Kummer surfaces. This gives rise to new possibilities for efficient supersingular isogeny-based cryptography.

14
September
2018

ePrint Report
Improved (Almost) Tightly-Secure Simulation-Sound QA-NIZK with Applications
Masayuki Abe, Charanjit S. Jutla, Miyako Ohkubo, Arnab Roy

We construct the first (almost) tightly-secure unbounded-simulation-sound quasi-adaptive non-interactive
zero-knowledge arguments (USS-QA-NIZK) for linear-subspace languages with compact (number of group elements independent of the security parameter)
common reference string (CRS) and compact proofs under standard assumptions in bilinear-pairings groups.
In particular, under the SXDH assumption, the USS-QA-NIZK proof size is only seventeen group elements with
a factor $O(\log{Q})$ loss in security reduction to SXDH. The USS-QA-NIZK primitive has many applications,
including structure-preserving signatures (SPS), CCA2-secure publicly-verifiable public-key encryption (PKE), which in turn have applications
to CCA-anonymous group signatures, blind signatures and unbounded simulation-sound Groth-Sahai NIZK proofs.
We show that the almost tight security of our USS-QA-NIZK translates into constructions of all of the above applications
with (almost) tight-security to standard assumptions such as SXDH and, more generally, $\mathcal D_k$-MDDH. Thus, we
get the first publicly-verifiable (almost) tightly-secure multi-user/multi-challenge CCA2-secure PKE with practical efficiency under standard bilinear assumptions. Our (almost) tight SPS construction is also improved in the signature size over previously known constructions.

ePrint Report
A Universally Composable Framework for the Privacy of Email Ecosystems
Pyrros Chaidos, Olga Fourtounelli, Aggelos Kiayias, Thomas Zacharias

Email communication is amongst the most prominent online activities, and as such, can put sensitive information at risk.
It is thus of high importance that internet email applications are designed in a privacy-aware manner and analyzed under a rigorous threat model.
The Snowden revelations (2013) suggest that such a model should feature a global adversary, in light of the observational tools available.
Furthermore, the fact that protecting metadata can be of equal importance as protecting the communication context implies
that end-to-end encryption may be necessary, but it is not sufficient.

With this in mind, we utilize the Universal Composability framework [Canetti, 2001] to introduce an expressive cryptographic model for email ``ecosystems'' that can formally and precisely capture various well-known privacy notions (unobservability, anonymity, unlinkability, etc.), by parameterizing the amount of leakage an ideal-world adversary (simulator) obtains from the email functionality.

Equipped with our framework, we present and analyze the security of two email constructions that follow different directions in terms of the efficiency vs. privacy tradeoff. The first one achieves optimal security (only the online/offline mode of the users is leaked), but it is mainly of theoretical interest; the second one is based on parallel mixing [Golle and Juels, 2004] and is more practical, while it achieves anonymity with respect to users that have similar amount of sending and receiving activity.

With this in mind, we utilize the Universal Composability framework [Canetti, 2001] to introduce an expressive cryptographic model for email ``ecosystems'' that can formally and precisely capture various well-known privacy notions (unobservability, anonymity, unlinkability, etc.), by parameterizing the amount of leakage an ideal-world adversary (simulator) obtains from the email functionality.

Equipped with our framework, we present and analyze the security of two email constructions that follow different directions in terms of the efficiency vs. privacy tradeoff. The first one achieves optimal security (only the online/offline mode of the users is leaked), but it is mainly of theoretical interest; the second one is based on parallel mixing [Golle and Juels, 2004] and is more practical, while it achieves anonymity with respect to users that have similar amount of sending and receiving activity.

ePrint Report
Realizing Chosen Ciphertext Security Generically in Attribute-Based Encryption and Predicate Encryption
Venkata Koppula, Brent Waters

We provide generic and black box transformations from any chosen plaintext secure Attribute-Based Encryption (ABE) or One-sided Predicate Encryption system into a chosen ciphertext secure system.
Our transformation requires only the IND-CPA security of the original ABE scheme coupled with a pseudorandom generator (PRG) with a special security property.

In particular, we consider a PRG with an $n$ bit input $s \in {0,1}^n$ and $n\cdot \ell$ bit output $y_1, ..., y_n$ where each $y_i$ is an $\ell$ bit string. Then for a randomly chosen $s$ the following two distributions should be computationally indistinguishable. In the first distribution $r_{i,s_i} = y_i$ and $r_{i, \bar{s}_i}$ is chosen randomly for $i \in [n]$. In the second distribution all $r_{i,b}$ are chosen randomly for $i \in [n], b \in {0,1}$.

In particular, we consider a PRG with an $n$ bit input $s \in {0,1}^n$ and $n\cdot \ell$ bit output $y_1, ..., y_n$ where each $y_i$ is an $\ell$ bit string. Then for a randomly chosen $s$ the following two distributions should be computationally indistinguishable. In the first distribution $r_{i,s_i} = y_i$ and $r_{i, \bar{s}_i}$ is chosen randomly for $i \in [n]$. In the second distribution all $r_{i,b}$ are chosen randomly for $i \in [n], b \in {0,1}$.

ePrint Report
Strong Leakage Resilient Encryption by Hiding Partial Ciphertext
Jia Xu, Jianying Zhou

Leakage-resilient encryption is a powerful tool to protect data confidentiality against side channel attacks. In this work, we introduce a new and strong leakage setting to counter
backdoor (or trojan horse) plus covert channel attack, by relaxing the restrictions on leakage.
We allow bounded leakage (e.g. 10000 bits) at anytime and anywhere and over anything.
Our leakage threshold could be much larger than typical secret key (e.g. AES key or RSA private key) size.
Under such a strong leakage setting, we propose an efficient encryption scheme which is semantic secure in standard setting (i.e. without leakage) and can tolerate strong continuous leakage.
We manage to construct such a secure scheme under strong leakage setting, by hiding partial (e.g. $1\%$) ciphertext as secure as we hide the secret key using a small amount of more secure hardware resource, so that it is almost equally difficult for any adversary to steal information regarding this well-protected partial ciphertext or the secret key. We remark that, the size of such well-protected small portion of ciphertext is chosen to be much larger than the leakage threshold.
We provide concrete and practical examples of such more secure hardware resource for data communication and data storage.
We also introduce a new notion of computational entropy, as a sort of computational version of Kolmogorov complexity.
Our quantitative analysis shows that, hiding partial ciphertext is a powerful countermeasure, which enables us to achieve higher security level than existing approaches in case of backdoor plus covert channel attacks. We also show the relationship between our new notion of computational entropy and existing relevant concepts, including Shannon-Entropy, Yao-Entropy, Hill-Entropy, All-or-Nothing Transform, and Exposure Resilient Function. This new computation entropy formulation may have independent interests.

ePrint Report
A Framework for Achieving KDM-CCA Secure Public-Key Encryption
Fuyuki Kitagawa, Keisuke Tanaka

We propose a framework for achieving a public-key encryption (PKE) scheme that satisfies key dependent message security against chosen ciphertext attacks (KDM-CCA security) based on projective hash function. Our framework can be instantiated under the decisional diffie-hellman (DDH), quadratic residuosity (QR), and decisional composite residuosity (DCR) assumptions. The constructed schemes are KDM-CCA secure with respect to affine functions and compatible with the amplification method shown by Applebaum (EUROCRYPT 2011). Thus, they lead to PKE schemes satisfying KDM-CCA security for all functions computable by a-priori bounded size circuits. They are the first PKE schemes satisfying such a security notion in the standard model using neither non-interactive zero knowledge proof nor bilinear pairing.

The above framework based on projective hash function captures only KDM-CCA security in the single user setting. However, we can prove the KDM-CCA security in the multi user setting of our concrete instantiations by using their algebraic structures explicitly. Especially, we prove that our DDH based scheme satisfies KDM-CCA security in the multi user setting with the same parameter setting as in the single user setting.

The above framework based on projective hash function captures only KDM-CCA security in the single user setting. However, we can prove the KDM-CCA security in the multi user setting of our concrete instantiations by using their algebraic structures explicitly. Especially, we prove that our DDH based scheme satisfies KDM-CCA security in the multi user setting with the same parameter setting as in the single user setting.

ePrint Report
Simulatable Channels: Extended Security that is Universally Composable and Easier to Prove
Jean Paul Degabriele, Marc Fischlin

Ever since the foundational work of Goldwasser and Micali, simulation has proven to be a powerful and versatile construct for formulating security in various areas of cryptography. However security definitions based on simulation are generally harder to work with than game based definitions, often resulting in more complicated proofs. In this work we challenge this viewpoint by proposing new simulation-based security definitions for secure channels that in many cases lead to simpler proofs of security. We are particularly interested in definitions of secure channels which reflect real-world requirements, such as, protecting against the replay and reordering of ciphertexts, accounting for leakage from the decryption of invalid ciphertexts, and retaining security in the presence of ciphertext fragmentation. Furthermore we show that our proposed notion of channel simulatability implies a secure channel functionality that is universally composable. To the best of our knowledge, we are the first to study universally composable secure channels supporting these extended security goals. We conclude, by showing that the Dropbear implementation of SSH-CTR is channel simulatable in the presence of ciphertext fragmentation, and therefore also realises a universally composable secure channel. This is intended, in part, to highlight the merits of our approach over prior ones in admitting simpler security proofs in comparable settings.

ePrint Report
Concretely Efficient Large-Scale MPC with Active Security (or, TinyKeys for TinyOT)
Carmit Hazay, Emmanuela Orsini, Peter Scholl, Eduardo Soria-Vazquez

In this work we develop a new theory for concretely efficient, large-scale MPC with active security. Current practical techniques are mostly in the strong setting of all-but-one corruptions, which leads to protocols that scale badly with the number of parties. To work around this issue, we consider a large-scale scenario where a small minority out of many parties is honest and design scalable, more efficient MPC protocols for this setting. Our results are achieved by introducing new techniques for information-theoretic MACs with short keys and extending the work of Hazay et al. (CRYPTO 2018), which developed new passively secure MPC protocols in the same context. We further demonstrate the usefulness of this theory in practice by analyzing the concrete communication overhead of our protocols, which improve upon the most efficient previous works.

ePrint Report
Attribute-Based Signatures for Unbounded Languages from Standard Assumptions
Yusuke Sakai, Shuichi Katsumata, Nuttapong Attrapadung, Goichiro Hanaoka

Attribute-based signature (ABS) schemes are advanced signature schemes
that simultaneously provide fine-grained authentication while protecting
privacy of the signer. Previously known expressive ABS schemes support
either the class of deterministic finite automata and circuits from
standard assumptions or Turing machines from the existence of
indistinguishability obfuscations.

In this paper, we propose the first ABS scheme for a very general policy class, all deterministic Turin machines, from a standard assumption, namely, the Symmetric External Diffie-Hellman (SXDH) assumption. We also propose the first ABS scheme that allows nondeterministic finite automata (NFA) to be used as policies. Although the expressiveness of NFAs are more restricted than Turing machines, this is the first scheme that supports nondeterministic computations as policies.

Our main idea lies in abstracting ABS constructions and presenting the concept of history of computations; this allows a signer to prove possession of a policy that accepts the string associated to a message in zero-knowledge while also hiding the policy, regardless of the computational model being used. With this abstraction in hand, we are able to construct ABS for Turing machines and NFAs using a surprisingly weak NIZK proof system. Essentially we only require a NIZK proof system for proving that a (normal) signature is valid. Such a NIZK proof system together with a base signature scheme are, in turn, possible from bilinear groups under the SXDH assumption, and hence so are our ABS schemes.

In this paper, we propose the first ABS scheme for a very general policy class, all deterministic Turin machines, from a standard assumption, namely, the Symmetric External Diffie-Hellman (SXDH) assumption. We also propose the first ABS scheme that allows nondeterministic finite automata (NFA) to be used as policies. Although the expressiveness of NFAs are more restricted than Turing machines, this is the first scheme that supports nondeterministic computations as policies.

Our main idea lies in abstracting ABS constructions and presenting the concept of history of computations; this allows a signer to prove possession of a policy that accepts the string associated to a message in zero-knowledge while also hiding the policy, regardless of the computational model being used. With this abstraction in hand, we are able to construct ABS for Turing machines and NFAs using a surprisingly weak NIZK proof system. Essentially we only require a NIZK proof system for proving that a (normal) signature is valid. Such a NIZK proof system together with a base signature scheme are, in turn, possible from bilinear groups under the SXDH assumption, and hence so are our ABS schemes.

ePrint Report
Building Quantum-One-Way Functions from Block Ciphers: Davies-Meyer and Merkle-Damgård Constructions
Akinori Hosoyamada, Kan Yasuda

We present hash functions that are almost optimally one-way in the quantum setting.
Our hash functions are based on the Merkle-Damgård construction iterating a Davies-Meyer compression function, which is built from a block cipher. The quantum setting that we use is a natural extention of the classical ideal cipher model.
Recent work has revealed that symmetric-key schemes using a block cipher or a public permutation, such as CBC-MAC or the Even-Mansour cipher, can get completely broken with quantum superposition attacks, in polynomial time of the block size.
Since many of the popular schemes are built from a block cipher or a permutation, the recent findings motivate us to study such schemes that are provably secure in the quantum setting.
Unfortunately, no such schemes are known, unless one relies on certain algebraic assumptions.
In this paper we present hash constructions that are provably one-way in the quantum setting without algebraic assumptions, solely based on the assumption that the underlying block cipher is ideal.
To do this, we reduce one-wayness to a problem of finding a fixed point and then bound its success probability with a distinguishing advantage.
We develop a generic tool that helps us prove indistinguishability of two quantum oracle distributions.

We put forward the notion of universal proxy re-encryption (UPRE). A UPRE scheme enables us to convert a ciphertext under a (delegator) public key of any existing public-key encryption (PKE) scheme into another ciphertext under a (delegatee) public key of any existing PKE scheme (possibly different from the delegator one). Such a conversion is executed by a third party called proxy that has a re-encryption key generated from the delegator's secret key and the delegatee public key. Proxy re-encryption is a related notion, but it can neither convert ciphertexts into ones of possibly different PKE schemes nor treat general PKE schemes.

Our contributions are twofold. One is a definitional work. We define the syntax and security of UPRE. The other is showing the feasibility of UPRE. More precisely, we present three generic constructions of UPRE. One is a UPRE based on probabilistic indistinguishability obfuscation (PIO). It can re-encrypt ciphertexts polynomially many times. Another is a relaxed variant of UPRE based on function secret sharing (FSS). It can re-encryption ciphertexts constant times. The relaxed variant means that decryption algorithms for re-encrypted ciphertext are slightly modified though we use only original delegatee secret keys for decryption. The other is the relaxed variant of UPRE based on oblivious transfer and garbled circuits. It can re-encryption ciphertexts polynomially many times.

The supported PKE schemes by the first and second generic constructions vary in the underlying hard problems or cryptographic tools. The third generic construction supports any CPA-secure PKE. The security levels of our UPRE schemes vary in the underlying hard problems or cryptographic tools that they rely on.

Our contributions are twofold. One is a definitional work. We define the syntax and security of UPRE. The other is showing the feasibility of UPRE. More precisely, we present three generic constructions of UPRE. One is a UPRE based on probabilistic indistinguishability obfuscation (PIO). It can re-encrypt ciphertexts polynomially many times. Another is a relaxed variant of UPRE based on function secret sharing (FSS). It can re-encryption ciphertexts constant times. The relaxed variant means that decryption algorithms for re-encrypted ciphertext are slightly modified though we use only original delegatee secret keys for decryption. The other is the relaxed variant of UPRE based on oblivious transfer and garbled circuits. It can re-encryption ciphertexts polynomially many times.

The supported PKE schemes by the first and second generic constructions vary in the underlying hard problems or cryptographic tools. The third generic construction supports any CPA-secure PKE. The security levels of our UPRE schemes vary in the underlying hard problems or cryptographic tools that they rely on.

6
September
2018

ePrint Report
On Kummer Lines With Full Rational 2-torsion and Their Usage in Cryptography
Huseyin Hisil, Joost Renes

A paper by Karati and Sarkar at Asiacrypt'17 has pointed out the potential for Kummer lines in genus one, by observing that its SIMD-friendly arithmetic is competitive with the status quo. A more recent preprint explores the connection with (twisted) Edwards curves. In this paper we extend this work and significantly simplify their treatment. We show that their Kummer line is the x-line of a Montgomery curve translated by a point of order two, and exhibit a natural isomorphism to a twisted Edwards curve. Moreover, we show that the Kummer line presented by Gaudry and Lubicz can be obtained via the action of a point of order two on the y-line of an Edwards curve. The maps connecting these curves and lines are all very simple. As an example, we present the first implementation of the qDSA signature scheme based on the squared Kummer line. Finally we present close estimates on the number of isomorphism classes of Kummer lines.

ePrint Report
(Tightly) QCCA-Secure Key-Encapsulation Mechanism in the Quantum Random Oracle Model
Keita Xagawa, Takashi Yamakawa

This paper shows the security against quantum chosen-ciphertext attacks (QCCA security) of the KEM in Saito, Yamakawa, and Xagawa (EUROCRYPT 2018) in the QROM. The proof is very similar to that for the CCA security in the QROM, easy to understand, and as tight as the original proof.

ePrint Report
Constructing Ideal Secret Sharing Schemes based on Chinese Remainder Theorem
Yu Ning, Fuyou Miao, Wenchao Huang, Keju Meng, Yan Xiong, Xingfu Wang

Since $(t,n)$-threshold secret sharing (SS) was initially proposed by Shamir and Blakley separately in 1979, it has been widely used in many aspects. Later on, Asmuth and Bloom presented a $(t,n)$-threshold SS scheme based on the Chinese Remainder Theorem(CRT) for integers in 1983. However, compared with the most popular Shamir's $(t,n)$-threshold SS scheme, existing CRT based schemes have a lower information rate, moreover, they are harder to construct. To overcome these shortcomings of the CRT based scheme, 1) we first propose a generalized $(t,n)$-threshold SS scheme based on the CRT for the polynomial ring over a finite field. We show that our scheme is ideal, i.e., it is perfect in security and has the information rate 1. By comparison, we show that our scheme has a better information rate and is easier to construct compared with existing threshold SS schemes based on the CRT for integers. 2) We show that Shamir's scheme, which is based on the Lagrange interpolation polynomial, is a special case of our scheme. Therefore, we establish the connection among threshold schemes based on the Lagrange interpolation, schemes based on the CRT for integers and our scheme. 3) As a natural extension of our threshold scheme, we present a weighted threshold SS scheme based on the CRT for polynomial rings, which inherits the above advantages of our threshold scheme over existing weighted schemes based on the CRT for integers.

ePrint Report
Pitchforks in Cryptocurrencies: Enforcing rule changes through offensive forking- and consensus techniques
Aljosha Judmayer, Nicholas Stifter, Philipp Schindler, Edgar Weippl

The increasing number of cryptocurrencies, as well as the rising number of actors within each single cryptocurrency, inevitably leads to tensions between the respective communities.
As with open source projects, (protocol) forks are often the result of broad disagreement.
Usually, after a permanent fork both communities ``mine'' their own business and the conflict is resolved.
But what if this is not the case?
In this paper, we outline the possibility of malicious forking and consensus techniques that aim at destroying the other branch of a protocol fork.
Thereby, we illustrate how merged mining can be used as an attack method against a permissionless PoW cryptocurrency, which itself involuntarily serves as the parent chain for an attacking merge mined branch of a hard fork.

ePrint Report
Fully-Featured Anonymous Credentials with Reputation System
Kai Bemmann, Johannes Bl\"{o}mer, Jan Bobolz, Henrik Br\"{o}cher, Denis Diemert, Fabian Eidens, Lukas Eilers, Jan Haltermann, Jakob Juhnke, Burhan Otour, Laurens Porzenheim, Simon Pukrop, Erik Schilli

We present $\mathsf{CLARC}$ (Cryptographic Library for Anonymous Reputation and Credentials), an anonymous credentials system (ACS) combined with an anonymous reputation system.

Using $\mathsf{CLARC}$, users can receive attribute-based credentials from issuers. They can efficiently prove that their credentials satisfy complex (access) policies in a privacy-preserving way. This implements anonymous access control with complex policies.

Furthermore, $\mathsf{CLARC}$ is the first ACS that is combined with an anonymous reputation system where users can anonymously rate services. A user who gets access to a service via a credential, also anonymously receives a review token to rate the service. If a user creates more than a single rating, this can be detected by anyone, preventing users from spamming ratings to sway public opinion.

To evaluate feasibility of our construction, we present an open-source prototype implementation.

Using $\mathsf{CLARC}$, users can receive attribute-based credentials from issuers. They can efficiently prove that their credentials satisfy complex (access) policies in a privacy-preserving way. This implements anonymous access control with complex policies.

Furthermore, $\mathsf{CLARC}$ is the first ACS that is combined with an anonymous reputation system where users can anonymously rate services. A user who gets access to a service via a credential, also anonymously receives a review token to rate the service. If a user creates more than a single rating, this can be detected by anyone, preventing users from spamming ratings to sway public opinion.

To evaluate feasibility of our construction, we present an open-source prototype implementation.

ePrint Report
Identity-based Encryption Tightly Secure under Chosen-ciphertext Attacks
Dennis Hofheinz, Dingding Jia, Jiaxin Pan

We propose the first identity-based encryption (IBE) scheme that is (almost) tightly secure against chosen-ciphertext attacks. Our scheme is efficient, in the sense that its ciphertext overhead is only seven group elements, three group elements more than that of the state-of-the-art passively (almost) tightly secure IBE scheme. Our scheme is secure in a multi-challenge setting, i.e., in face of an arbitrary number of challenge ciphertexts. The security of our scheme is based upon the standard symmetric external Diffie-Hellman assumption in pairing-friendly groups, but we also consider (less efficient) generalizations under weaker assumptions.

ePrint Report
Improved Inner-product Encryption with Adaptive Security and Full Attribute-hiding
Jie Chen, Junqing Gong, Hoeteck Wee

In this work, we propose two IPE schemes achieving both adaptive security and full attribute-hiding in the prime-order bilinear group, which improve upon the unique existing result satisfying both features from Okamoto and Takashima [Eurocrypt '12] in terms of efficiency.

- Our first IPE scheme is based on the standard $k$-Lin assumption and has shorter master public key and shorter secret keys than Okamoto and Takashima's IPE under weaker DLIN=$2$-lin assumption.

- Our second IPE scheme is adapted from the first one; the security is based on the XDLIN assumption (as Okamoto and Takashima's IPE) but now it also enjoys shorter ciphertexts.

Technically, instead of starting from composite-order IPE and applying existing transformation, we start from an IPE scheme in a very restricted setting but already in the prime-order group, and then gradually upgrade it to our full-fledged IPE scheme. This method allows us to integrate Chen et al.'s framework [Eurocrypt '15] with recent new techniques [TCC '17, Eurocrypt '18] in an optimized way.

- Our first IPE scheme is based on the standard $k$-Lin assumption and has shorter master public key and shorter secret keys than Okamoto and Takashima's IPE under weaker DLIN=$2$-lin assumption.

- Our second IPE scheme is adapted from the first one; the security is based on the XDLIN assumption (as Okamoto and Takashima's IPE) but now it also enjoys shorter ciphertexts.

Technically, instead of starting from composite-order IPE and applying existing transformation, we start from an IPE scheme in a very restricted setting but already in the prime-order group, and then gradually upgrade it to our full-fledged IPE scheme. This method allows us to integrate Chen et al.'s framework [Eurocrypt '15] with recent new techniques [TCC '17, Eurocrypt '18] in an optimized way.

ePrint Report
Lightweight and Side-channel Secure 4x4 S-Boxes from Cellular Automata Rules
Ashrujit Ghoshal, Rajat Sadhukhan, Sikhar Patranabis, Nilanjan Datta, Stjepan Picek, Debdeep Mukhopadhyay

This work focuses on side-channel resilient design strategies for symmetric-key cryptographic primitives targeting lightweight applications. In light of NIST's lightweight cryptography project, design choices for block ciphers must consider not only security against traditional cryptanalysis, but also side-channel security, while adhering to low area and power requirements. In this paper, we explore design strategies for substitution-permutation network (SPN)-based block ciphers that make them amenable to low-cost threshold implementations (TI) - a provably secure strategy against side-channel attacks. The core building blocks for our strategy are cryptographically optimal 4x4 S-Boxes, implemented via repeated iterations of simple cellular automata~(CA) rules. We present highly optimized TI circuits for such S-Boxes, that consume nearly 40% less area and power as compared to popular lightweight S-Boxes such as PRESENT and GIFT. We validate our claims via implementation results on ASIC using 180nm technology. We also present a comparison of TI circuits for two popular lightweight linear diffusion layer choices - bit permutations and MixColumns using almost-maximum-distance-separable (almost-MDS) matrices. We finally illustrate design paradigms that combine the aforementioned TI circuits for S-Boxes and diffusion layers to obtain fully side-channel secure SPN block cipher implementations with low area and power requirements.

RaCoSS is a signature scheme based on the syndrome decoding problem over the random linear code and proposed by Fukushima, Roy, Xu, Kiyomoto, Morozov, and Takagi. This scheme is cryptanalyzed Bernstein, Hülsing, Lange, and Panny (pqc-forum on 23 Dec. 2017).

Roy, Morozov, Fukushima, Kiyomoto, and Takagi recently gave a patch and call the patched scheme as RaCoSS-R (ISEC Conf. on 25 Jul. 2018).

This short note describes how to break RaCoSS-R by modifying the forgery attack against RaCoSS.

Roy, Morozov, Fukushima, Kiyomoto, and Takagi recently gave a patch and call the patched scheme as RaCoSS-R (ISEC Conf. on 25 Jul. 2018).

This short note describes how to break RaCoSS-R by modifying the forgery attack against RaCoSS.

The success rate is the most common evaluation metric for measuring the performance of a particular side channel attack scenario. We improve on an analytic formula for the success rate.

ePrint Report
Information-Theoretic Broadcast with Dishonest Majority for Long Messages
Wutichai Chongchitmate, Rafail Ostrovsky

Byzantine broadcast is a fundamental primitive for secure computation. In a setting with $n$ parties in the presence of an adversary controlling at most $t$ parties,
while a lot of progress in optimizing communication complexity has been made for $t < n/2$, little progress has been made for the general case $t<n$, especially for information-theoretic security. In particular, all information-theoretic secure broadcast protocols for $\ell$-bit messages and $t<n$ and optimal round complexity $\mathcal{O}(n)$ have, so far, required a communication complexity of $\mathcal{O}(\ell n^2)$. A broadcast extension protocol allows a long message to be broadcast more efficiently using a small number of single-bit broadcasts. Through broadcast extension, so far, the best achievable round complexity for $t<n$ setting with the optimal communication complexity
of $\mathcal{O}(\ell n)$ is $\mathcal{O}(n^4)$ rounds.

In this work, we construct a new broadcast extension protocol for $t<n$ with information-theoretic security. Our protocol improves the round complexity to $\mathcal{O}(n^3)$ while maintaining the optimal communication complexity for long messages. Our result shortens the gap between the information-theoretic setting and the computational setting, and between the optimal communication protocol and the optimal round protocol in the information-theoretic setting for $t<n$.

In this work, we construct a new broadcast extension protocol for $t<n$ with information-theoretic security. Our protocol improves the round complexity to $\mathcal{O}(n^3)$ while maintaining the optimal communication complexity for long messages. Our result shortens the gap between the information-theoretic setting and the computational setting, and between the optimal communication protocol and the optimal round protocol in the information-theoretic setting for $t<n$.

ePrint Report
Aurora: Transparent Succinct Arguments for R1CS
Eli Ben-Sasson, Alessandro Chiesa, Michael Riabzev, Nicholas Spooner, Madars Virza, Nicholas P. Ward

We design, implement, and evaluate a zero knowledge succinct non-interactive argument (SNARG) for Rank-1 Constraint Satisfaction (R1CS), a widely-deployed NP language undergoing standardization. Our SNARG has a transparent setup, is plausibly post-quantum secure, and uses lightweight cryptography. A proof attesting to the satisfiability of $n$ constraints has size $O(\log^2 n)$; it can be produced with $O(n \log n)$ field operations and verified with $O(n)$. At 128 bits of security, proofs are less than 250kB even for several million constraints, more than 10x shorter than prior SNARGs with similar features.

A key ingredient of our construction is a new Interactive Oracle Proof (IOP) for solving a univariate analogue of the classical sumcheck problem [LFKN92], originally studied for multivariate polynomials. Our protocol verifies the sum of entries of a Reed--Solomon codeword over any subgroup of a field.

We also provide libiop, a library for writing IOP-based arguments, in which a toolchain of transformations enables programmers to write new arguments by writing simple IOP sub-components. We have used this library to specify our construction and prior ones, and plan to open-source it.

A key ingredient of our construction is a new Interactive Oracle Proof (IOP) for solving a univariate analogue of the classical sumcheck problem [LFKN92], originally studied for multivariate polynomials. Our protocol verifies the sum of entries of a Reed--Solomon codeword over any subgroup of a field.

We also provide libiop, a library for writing IOP-based arguments, in which a toolchain of transformations enables programmers to write new arguments by writing simple IOP sub-components. We have used this library to specify our construction and prior ones, and plan to open-source it.

ePrint Report
Practical Strategy-Resistant Privacy-Preserving Elections
Sébastien Canard, David Pointcheval, Quentin Santos, Jacques Traoré

Recent advances in cryptography promise to let us run complex algorithms in the
encrypted domain. However, these results are still mostly theoretical since the
running times are still much larger than their equivalents in the plaintext
domain. In this context, Majority Judgment is a recent proposal for a new voting system with
several interesting practical advantages, but which implies a more involved tallying process than
first-past-the-post voting. To protect voters' privacy, such a process needs to be done by only manipulating encrypted data.

In this paper, we then explore the possibility of computing the (ordered) winners in the Majority Judgment election without leaking any other information, using homomorphic encryption and multiparty computation. We particularly focus on the practicality of such a solution and, for this purpose, we optimize both the algorithms and the implementations of several cryptographic building blocks. Our result is very positive, showing that this is as of now possible to attain practical running times for such a complex privacy-protecting tallying process, even for large-scale elections.

In this paper, we then explore the possibility of computing the (ordered) winners in the Majority Judgment election without leaking any other information, using homomorphic encryption and multiparty computation. We particularly focus on the practicality of such a solution and, for this purpose, we optimize both the algorithms and the implementations of several cryptographic building blocks. Our result is very positive, showing that this is as of now possible to attain practical running times for such a complex privacy-protecting tallying process, even for large-scale elections.

ePrint Report
Simple and More Efficient PRFs with Tight Security from LWE and Matrix-DDH
Tibor Jager, Rafael Kurek, Jiaxin Pan

We construct efficient and tightly secure pseudorandom functions (PRFs) with only logarithmic security loss and short secret keys. This yields very simple and efficient variants of well-known constructions, including those of Naor-Reingold (FOCS 1997) and Lewko-Waters (ACM CCS 2009). Most importantly, in combination with the construction of Banerjee, Peikert and Rosen (EUROCRYPT 2012) we obtain the currently most efficient LWE-based PRF from a weak LWE-assumption with a much smaller modulus than the original construction. In comparison to the only previous construction with this property, which is due to Doettling and Schroeder (CRYPTO 2015), we use a modulus of similar size, but only a single instance of the underlying PRF, instead of $\lambda \cdot \omega(\log \lambda)$ parallel instances, where $\lambda$ is the security parameter. Like Doettling and Schroeder, our security proof is only almost back-box, due to the fact that the number of queries made by the adversary and its advantage must be known a-priori.

Technically, we introduce all-prefix universal hash functions (APUHFs), which are hash functions that are (almost-)universal, even if any prefix of the output is considered. We give simple and very efficient constructions of APUHFs, and show how they can be combined with the augmented cascade of Boneh et al. (ACM CCS 2010) to obtain our results. Along the way, we develop a new and more direct way to prove security of PRFs based on the augmented cascade.

Technically, we introduce all-prefix universal hash functions (APUHFs), which are hash functions that are (almost-)universal, even if any prefix of the output is considered. We give simple and very efficient constructions of APUHFs, and show how they can be combined with the augmented cascade of Boneh et al. (ACM CCS 2010) to obtain our results. Along the way, we develop a new and more direct way to prove security of PRFs based on the augmented cascade.

ePrint Report
Low Randomness Masking and Shuffling: An Evaluation Using Mutual Information
Kostas Papagiannopoulos

Side-channel countermeasure designers often face severe performance
overheads when trying to protect a device. Widely applied countermeasures such as masking and shuffling entail generating a large amount of random numbers, which can result in a computational bottleneck. To mitigate the randomness cost, this work evaluates low-randomness versions of both masking and shuffling, namely Recycled
Randomness Masking (RRM) and Reduced Randomness Shuffling (RRS). These countermeasures employ memory units to store generated random numbers and reuse them in subsequent computations,making them primarily suitable for implementation on devices with sufficient memory. Both RRM and RRS are evaluated using the MI-based framework in the context of horizontal attacks.
The evaluation exhibits the tradeoff between the randomness cost and the noisy leakage security level offered by the countermeasures, enabling the designer to fine-tune a masking or shuffling scheme and maximize the security level achieved for a certain cost.

ePrint Report
SeaSign: Compact isogeny signatures from class group actions
Luca De Feo, Steven D. Galbraith

We give a new signature scheme for isogenies that combines the class group actions of CSIDH with the notion of Fiat-Shamir with aborts. Our techniques allow to have signatures of size less than one kilobyte at the 128-bit security level, even with tight security reduction (to a non-standard problem) in the quantum random oracle model. Hence our signatures are potentially shorter than lattice signatures, but signing and verification are currently very expensive.

ePrint Report
The Security of Lazy Users in Out-of-Band Authentication
Moni Naor, Lior Rotem, Gil Segev

Faced with the threats posed by man-in-the-middle attacks, messaging platforms rely on "out-of-band'' authentication, assuming that users have access to an external channel for authenticating one short value. For example, assuming that users recognizing each other's voice can authenticate a short value, Telegram and WhatApp ask their users to compare $288$-bit and $200$-bit values, respectively. The existing protocols, however, do not take into account the plausible behavior of users who may be "lazy'' and only compare parts of these values (rather than their entirety).

Motivated by such a security-critical user behavior, we study the security of lazy users in out-of-band authentication. We start by showing that both the protocol implemented by WhatsApp and the statistically-optimal protocol of Naor, Segev and Smith (CRYPTO '06) are completely vulnerable to man-in-the-middle attacks when the users consider only a half of the out-of-band authenticated value. In this light, we put forward a framework that captures the behavior and security of lazy users. Our notions of security consider both statistical security and computational security, and for each flavor we derive a lower bound on the tradeoff between the number of positions that are considered by the lazy users and the adversary's forgery probability.

Within our framework we then provide two authentication protocols. First, in the statistical setting, we present a transformation that converts any out-of-band authentication protocol into one that is secure even when executed by lazy users. Instantiating our transformation with a new refinement of the protocol of Naor et al. results in a protocol whose tradeoff essentially matches our lower bound in the statistical setting. Then, in the computational setting, we show that the computationally-optimal protocol of Vaudenay (CRYPTO '05) is secure even when executed by lazy users -- and its tradeoff matches our lower bound in the computational setting.

Motivated by such a security-critical user behavior, we study the security of lazy users in out-of-band authentication. We start by showing that both the protocol implemented by WhatsApp and the statistically-optimal protocol of Naor, Segev and Smith (CRYPTO '06) are completely vulnerable to man-in-the-middle attacks when the users consider only a half of the out-of-band authenticated value. In this light, we put forward a framework that captures the behavior and security of lazy users. Our notions of security consider both statistical security and computational security, and for each flavor we derive a lower bound on the tradeoff between the number of positions that are considered by the lazy users and the adversary's forgery probability.

Within our framework we then provide two authentication protocols. First, in the statistical setting, we present a transformation that converts any out-of-band authentication protocol into one that is secure even when executed by lazy users. Instantiating our transformation with a new refinement of the protocol of Naor et al. results in a protocol whose tradeoff essentially matches our lower bound in the statistical setting. Then, in the computational setting, we show that the computationally-optimal protocol of Vaudenay (CRYPTO '05) is secure even when executed by lazy users -- and its tradeoff matches our lower bound in the computational setting.

ePrint Report
LWE Without Modular Reduction and Improved Side-Channel Attacks Against BLISS
Jonathan Bootle, Claire Delaplace, Thomas Espitau, Pierre-Alain Fouque, Mehdi Tibouchi

This paper is devoted to analyzing the variant of Regev's learning with
errors (LWE) problem in which modular reduction is omitted: namely, the
problem (ILWE) of recovering a vector $\vec s\in\mathbb{Z}^n$ given polynomially many
samples of the form $(\vec a,\langle\vec a,\vec s\rangle + e)\in\mathbb{Z}^{n+1}$
where $\vec a$ and $e$ follow fixed distributions. Unsurprisingly, this
problem is much easier than LWE: under mild conditions on the
distributions, we show that the problem can be solved efficiently as long
as the variance of $e$ is not superpolynomially larger than that of $\vec
a$. We also provide almost tight bounds on the number of samples needed
to recover $\vec s$.

Our interest in studying this problem stems from the side-channel attack against the BLISS lattice-based signature scheme described by Espitau et al. at CCS 2017. The attack targets a quadratic function of the secret that leaks in the rejection sampling step of BLISS. The same part of the algorithm also suffers from a linear leakage, but the authors claimed that this leakage could not be exploited due to signature compression: the linear system arising from it turns out to be noisy, and hence key recovery amounts to solving a high-dimensional problem analogous to LWE, which seemed infeasible. However, this noisy linear algebra problem does not involve any modular reduction: it is essentially an instance of ILWE, and can therefore be solved efficiently using our techniques. This allows us to obtain an improved side-channel attack on BLISS, which applies to 100% of secret keys (as opposed to ~7% in the CCS paper), and is also considerably faster.

Our interest in studying this problem stems from the side-channel attack against the BLISS lattice-based signature scheme described by Espitau et al. at CCS 2017. The attack targets a quadratic function of the secret that leaks in the rejection sampling step of BLISS. The same part of the algorithm also suffers from a linear leakage, but the authors claimed that this leakage could not be exploited due to signature compression: the linear system arising from it turns out to be noisy, and hence key recovery amounts to solving a high-dimensional problem analogous to LWE, which seemed infeasible. However, this noisy linear algebra problem does not involve any modular reduction: it is essentially an instance of ILWE, and can therefore be solved efficiently using our techniques. This allows us to obtain an improved side-channel attack on BLISS, which applies to 100% of secret keys (as opposed to ~7% in the CCS paper), and is also considerably faster.

ePrint Report
Side-channel Assisted Existential Forgery Attack on Dilithium - A NIST PQC candidate
Prasanna Ravi, Mahabir P. Jhanwar, James Howe, Anupam Chattopadhyay, Shivam Bhasin

The recent lattice-based signature scheme Dilithium, submitted as part of the CRYSTALS (Cryptographic Suite for Algebraic Lattices) package, is one of a number of strong candidates submitted for the NIST standardisation process of post-quantum cryptography. The Dilithium signature scheme is based on the Fiat-Shamir paradigm and can be seen as a variant of the Bai-Galbraith scheme (BG) combined with several improvements from previous ancestor lattice-based schemes like GLP and BLISS signature schemes. One of the main features of Dilithium is the compressed public-key, which is a rounded version of the LWE instance. This implies that Dilithium is not breakable with the knowledge of only the secret or the error of the LWE instance, unlike its ancestor lattice-based signature schemes. In this paper, we investigate the security of Dilithium against a combination of side-channel and classical attacks. Side-channel attacks on schoolbook and optimised polynomial multiplication algorithms in the signing procedure are shown to extract the secret component of the LWE instance, which is just one among the multiple components of the secret-key of Dilithium. We then propose an alternative signing procedure, through which it is possible to forge signatures with only the extracted portion of the secret-key, without requiring the knowledge of all its elements. Thus showing that Dilithium too breaks on just knowing the secret portion of the LWE instance, similar to previous lattice-based schemes.