International Association
for Cryptologic Research

This paper introduces a new approach to reduce end-to-end costs in large-scale replicated systems built under a Byzantine fault model. Specifically, our approach transforms a given replicated state machine (RSM) to another RSM where nodes incur lower costs by delegating state machine execution: an untrusted prover produces succinct cryptographic proofs of correct state transitions along with state changes, which nodes in the transformed RSM verify and apply respectively.

To realize our approach, we build Piperine, a system that makes the proof machinery profitable in the context of RSMs. Specifically, Piperine reduces the costs of both proving and verifying the correctness of state machine execution while retaining liveness—a distinctive requirement in the context of RSMs. Our experimental evaluation demonstrates that, for a payment service, employing Piperine is more pro table than naive reexecution of transactions as long as there are $>10^4$ nodes. When we apply Piperine to ERC-20 transactions in Ethereum (a real-world RSM with up to $10^5$ nodes), it reduces per-transaction costs by $5.4\times$ and network costs by $2.7\times$.

In this work, we present:

- the first adaptively secure ABE for DFA from the k-Lin assumption in prime-order bilinear groups; this resolves one of open problems posed by Waters [CRYPTO'12];

- the first ABE for NFA from the k-Lin assumption, provided the number of accepting paths is smaller than the order of the underlying group; the scheme achieves selective security;

- the first compact adaptively secure ABE (supporting unbounded multi-use of attributes) for branching programs from the k-Lin assumption, which generalizes and simplifies the recent result of Kowalczyk and Wee for boolean formula (NC1) [EUROCRYPT'19].

Our adaptively secure ABE for DFA relies on a new combinatorial mechanism avoiding the exponential security loss in the number of states when naively combining two recent techniques from CRYPTO'19 and EUROCRYPT'19. This requires us to design a selectively secure ABE for NFA; we give a construction which is sufficient for our purpose and of independent interest. Our ABE for branching programs leverages insights from our ABE for DFA.

We present a 2-party private set intersection (PSI) protocol which provides security against malicious participants, yet is almost as fast as the fastest known semi-honest PSI protocol of Kolesnikov et al. (CCS 2016).

Our protocol is based on a new approach for two-party PSI, which can be instantiated to provide security against either malicious or semi-honest adversaries. The protocol is unique in that the only difference between the semi-honest and malicious versions is an instantiation with different parameters for a linear error-correction code. It is also the first PSI protocol which is concretely efficient while having linear communication and security against malicious adversaries, while running in the OT-hybrid model (assuming a non-programmable random oracle).

State of the art semi-honest PSI protocols take advantage of cuckoo hashing, but it has proven a challenge to use cuckoo hashing for malicious security. Our protocol is the first to use cuckoo hashing for malicious-secure PSI. We do so via a new data structure, called a probe-and-XOR of strings (PaXoS), which may be of independent interest. This abstraction captures important properties of previous data structures, most notably garbled Bloom filters. While an encoding by a garbled Bloom filter is larger by a factor of $O(\lambda)$ than the original data, we describe a significantly improved PaXoS based on cuckoo hashing that achieves constant rate while being no worse in other relevant efficiency measures.

Homomorphic signature is an extremely important public key cryptographic technique for network coding to defend against pollution attacks. As a public key cryptographic primitive, it also encounters the same problem that how to confirm the relationship between some public key pk and the identity ID of its owner. In the setting of network coding, the intermediate and destination nodes need to use source node S’s public key to check the validity of vector-signature pairs. Therefore, the binding of S and its corresponding public key becomes crucial. The popular and traditional solution is based on certificates which is issued by a trusted certification authority (CA) center. However, the generation and management of certificates is extremely cumbersome. Hence, in recent work [20], Lin et al. proposed a new notion of identity-based homomorphic signature, which intends to avoid using certificates. But the key escrow problem is inevitable for identity-based primitives. In this paper, we propose another new notion (for network coding): certificateless homomorphic signature (CLHS), which is a compromise for the above two techniques. In particular, we first describe the definition and security model of certificateless homomorphic signature. Then based on bilinear map and the computational Diffie-Hellman (CDH) assumption, give a concrete implementation and detailedly analyze its security. Finally, performance analysis illustrates that our construction is practical.

We propose a candidate Ciphertext-Policy Attribute Based Encryption (CP-ABE) scheme for circuits, with ciphertext size that depends only on the depth of the policy circuit (and not its size). This, in particular, gives us a Broadcast Encryption (BE) scheme where all parameters (in particular, the size of the keys and ciphertexts) have a poly-logarithmic dependence on the number of users, a task that was only known to be achievable assuming ideal multilinear maps or indistinguishability obfuscation. Our construction relies on techniques from lattice-based (and in particular LWE-based) cryptography, but we are unable to provide a security proof. We analyze some attempts at cryptanalysis.

Blockchain-based payment systems utilize an append-only log of transactions whose correctness can be verified by any observer. In almost all of today’s implementations, verification costs grow linearly in either the number of transactions or blocks in the blockchain (often both). We propose a new distributed payment system which uses Incrementally Verifiable Computation (IVC) to enable constant-time verification. Since generating the succinct proofs needed to verify correctness is more expensive, we introduce the notion of Proof of Necessary Work (PoNW), in which proof generation is an integral part of the proof-of-work used in Nakamoto consensus, effectively producing proofs using energy that would otherwise be wasted. We implement and benchmark a prototype of our system using recent recursive SNARK-based constructions, enabling stateless “light” clients to efficiently verify the entire blockchain history in about 40 milliseconds.

We study the communication complexity of unconditionally secure MPC with guaranteed output delivery over point-to-point channels for corruption threshold t < n/2, assuming the existence of a public broadcast channel. We ask the question: “is it possible to construct MPC in this setting s.t. the communication complexity per multiplication gate is linear in the number of parties?” While a number of works have focused on reducing the communication complexity in this setting, the answer to the above question has remained elusive until now. We also focus on the concrete communication complexity of evaluating each multiplication gate. We resolve the above question in the affirmative by providing an MPC with communication complexity O(Cn\phi) bits (ignoring fixed terms which are independent of the circuit) where \phi is the length of an element in the field, C is the size of the (arithmetic) circuit, n is the number of parties. This is the first construction where the asymptotic communication complexity matches the best-known semi-honest protocol. This represents a strict improvement over the previously best-known communication complexity of O(C(n\phi+\kappa)+D_Mn^2\kappa) bits, where \kappa is the security parameter and D_M is the multiplicative depth of the circuit. Furthermore, the concrete communication complexity per multiplication gate is 5.5 field elements per party in the best case and 7.5 field elements in the worst case when one or more corrupted parties have been identified. This also roughly matches the best-known semi-honest protocol, which requires 5.5 field elements per gate.

The security and performance of many integrity proof systems like SNARKs, STARKs and Bulletproofs highly depend on the underlying hash function. For this reason several new proposals have recently been developed. These primitives obviously require an in-depth security evaluation, especially since their implementation constraints have led to less standard design approaches. This work compares the security levels offered by two recent families of such primitives, namely GMiMC and HadesMiMC. We exhibit low-complexity distinguishers against the GMiMC and HadesMiMC permutations for most parameters proposed in recently launched public challenges for STARK-friendly hash functions. In the more concrete setting of the sponge construction corresponding to the practical use in the ZK-STARK protocol, we present a practical collision attack on a round-reduced version of GMiMC and a preimage attack on some instances of HadesMiMC. To achieve those results, we adapt and generalize several cryptographic techniques to fields of odd characteristic.

In light of the emerging threat of powerful quantum computers appearing in the near future, we investigate the potential attacks on Bitcoin available to a quantum-capable adversary. In particular, we illustrate how Shor’s quantum algorithm can be used to forge ECDSA based signatures, allowing attackers to hijack transactions. We then propose a simple commit–delay reveal protocol, which allows users to securely move their funds from non-quantum-resistant outputs to those adhering to a quantum-resistant digital signature scheme. In a previous paper, we presented a similar scheme with a long fixed delay. Here we improve on our previous work, by allowing each user to choose their preferred delay – long for a low risk of attack, or short if a higher risk is acceptable to that user. As before, our scheme requires modifications to the Bitcoin protocol, but once again these can be implemented as a soft fork.

With the advances in quantum computing taking place over the last few years, researchers have started considering the implications on cryptocurrencies. As most digital signature schemes would be impacted, it is somewhat reassuring that transition schemes to quantum resistant signatures are already being considered for Bitcoin. In this work, we stress the danger of public key reuse, as it prevents users from recovering their funds in the presence of a quantum enabled adversary despite any transition scheme the developers decide to implement. We emphasise this threat by quantifying the damage a functional quantum computer could inflict on Bitcoin (and Bitcoin Cash) by breaking exposed public keys.

The design of glitch-resistant higher-order masking schemes is an important challenge in cryptographic engineering. A recent work by Moos et al. (CHES 2019) showed that most published schemes (and all efficient ones) exhibit local or composability flaws at high security orders, leaving a critical gap in the literature on hardware masking. In this paper, we first extend the simulatability framework of Belaïd et al. (EUROCRYPT 2016) and prove that a compositional strategy that is correct without glitches remains valid with glitches. We then use this extended framework to prove the first masked gadgets that enable trivial composition with glitches at arbitrary orders. We show that the resulting "Hardware Private Circuits'' approach the implementation efficiency of previous (flawed) schemes. We finally investigate how trivial composition can serve as a basis for a tool that allows verifying full masked hardware implementations (e.g., of complete block ciphers) at any security order. The tool checks that a synthesized HDL code fulfills the topological requirements of the composability theorems. As side products, we improve the randomness complexity of the best published refreshing gadgets, show that some S-box representations allow latency reductions and confirm practical claims based on implementation~results.

We construct a privacy-preserving, distributed and decentralized marketplace where parties can exchange data for tokens. In this market, buyers and sellers make transactions in a blockchain and interact with a third party, called notary, who has the ability to vouch for the authenticity and integrity of the data.

We introduce a protocol for the data-token exchange where neither party gains more information than what it is paying for, and the exchange is fair: either both parties gets the other's item or neither does. No third party involvement is required after setup, and no dispute resolution is needed.

We generalize a protocol by Yu for comparing two integers with relatively small difference in a secure multiparty computation setting. Yu's protocol is based on the Legendre symbol. A prime number $p$ is found for which the Legendre symbol in $\mathbb{F}_p$ agrees with the sign function for integers in a certain range $\{-N, \ldots, N\}$. This can then be computed efficiently.

We generalize this idea to higher residue symbols in cyclotomic rings $\mathbb{Z}[\zeta_r]$ for $r$ a small odd prime. We present a way to determine a prime number $p$ such that the $r$-th residue symbol agrees with a desired function $f\colon A \to \{\zeta_r^0, \ldots, \zeta_r^{r - 1}\}$ on a given small subset $A \subset \mathbb{Z}[\zeta_r]$, when this is possible. We also explain how to efficiently compute the $r$-th residue symbol in a secret shared setting.

Algebraically simple PRFs, ciphers, or cryptographic hash functions are becoming increasingly popular, for example due to their attractive properties for MPC and new proof systems (SNARKs, STARKs, among many others). In this paper, we focus on the algebraically simple construction MiMC which became an attractive cryptanalytic target due to its simplicity, but also due to its use as a baseline in an ongoing competition for more recent designs exploring this design space.

For the first time, we are able to describe key-recovery attacks on all full-round versions of MiMC over GF(2^n), requiring half the codebook. Recovering the key from this data for the n-bit version of MiMC takes the equivalent of less than 2^(n-log_2(n)+1) calls to MiMC and negligible amounts of memory.

The attack procedure is a generalization of higher-order differential cryptanalysis, and it is based on two main ingredients: First, a zero-sum distinguisher which exploits the fact that the algebraic degree of MiMC grows much slower than originally believed. Second, an approach to turn the zero-sum distinguisher into a key-recovery attack without needing to guess the full subkey.

The attack has been practically verified on toy versions of MiMC. Note that our attack does not affect the security of MiMC over prime fields.

Event date: 21 March to 25 March 2021
Submission deadline: 2 March 2020
Notification: 1 May 2020

Starting with the CHES conference in 2020 the CHES Test-of-Time Award is given yearly. An award will be given in year X to honor a paper published at (T)CHES in years X-21 to X-19 which has had a lasting impact on the field with respect to academia and/or industry.

Nominations for the 2020 award (for papers published in 1999-2001) are welcomed by the selection committee. Deadline for nomination is May 3, 2020 23:59 AoE.

The proceedings of the relevant conferences can be found here:
CHES 1999
CHES 2000
CHES 2001

In order to nominate please send an email to the chair of selection committee with the following contents:

1. email subject line: ches test of time award nomination
2. mention: paper title and publication year
3. provide short justification why the paper should receive the award by providing number of citations, describing influence in industry, etc. in a max. 2 pages document or text in the email body

More information about the CHES Test-of-Time award can be found here: https://ches.iacr.org/testoftime.shtml

The 2020 Selection Committee:

• Benedikt Gierlichs (chair)
• Helena Handschuh
• Marc Joye
• Christof Paar
• Pankaj Rohatgi

Event date: 10 May 2020
Submission deadline: 6 March 2020
Notification: 16 March 2020

The Faculty of Electrical Engineering, Computer Science and Mathematics has two full-time research assistant positions in the area of System Security.

Our group provides a relaxed and inspiring working atmosphere allowing you to address challenging research problems or to develop new cool attacks on well-used cryptographic implementations.

Your profile:

• Academic degree in Informatics, Mathematics, or a related area; ideally (but not mandatory) with a specialization in the area of IT security or cryptography
• High interest in research in IT security or applied cryptography
• Solid know-how in at least one of these areas:
  • Applied cryptography (e. g., protocols like TLS or SSH)
  • System security (e. g., fuzzing, reverse engineering or microarchitectural attacks)
  • Web security

Deadline: 2nd March 2020. More information at: https://www.uni-paderborn.de/fileadmin/zv/4-4/stellenangebote/Kennziffer4190Englisch.pdf

Closing date for applications:

Contact: For further details about the position, you can contact Juraj Somorovsky.

More information: https://www.uni-paderborn.de/fileadmin/zv/4-4/stellenangebote/Kennziffer4190Englisch.pdf

Singapore University of Technology and Design (SUTD) is a young university which was established in collaboration with MIT. iTrust is a Cyber Security Research Center with 10+ multi-discipline faculty members from SUTD. It has the world’s best facilities in cyber-physical systems (CPS).

I am looking for postdocs & research fellows with expertise on cyber-physical system security. The candidates should have track record of strong R&D capability, be a good team player, and also have good written/oral communication skills. The positions are available immediately, and will provide an excellent opportunity to perform both basic and translational research in close collaboration with industry. Successful candidates will be offered internationally competitive remuneration, and enjoy high-quality living and low tax rates in Singapore.

Interested candidates please send your CV with a research statement to Prof. Jianying Zhou. Only short-listed candidates will be contacted for interview.

Closing date for applications:

Contact: Prof. Jianying Zhou (jianying_zhou@sutd.edu.sg)

More information: http://jianying.space/

Télécom Paris, one of the top four engineering schools in France for training general engineers and PhDs, invites application for a tenured position of Professor in Cryptography. The successful candidate will join the Computer Science and Networks department of the school and will be at the center of a unique innovation ecosystem on the Paris-Saclay Campus.

Details about this job offer can be found on :

https://www.telecom-paris.fr/job-offer-professor-cryptography

The closing date for applications is April 12, 2020.

Informal enquiries may be made to Bertrand Meyer (bertrand.meyer@telecom-paris.fr)

Closing date for applications:

Contact: Bertrand Meyer bertrand.meyer@telecom-paris.fr

More information: https://www.telecom-paris.fr/job-offer-professor-cryptography