International Association
for Cryptologic Research

For more than two decades, proving or refuting the following statement has remained a challenging open problem in the theory of secret sharing schemes (SSSs): every ideal access structure admits an ideal perfect multi-linear SSS. We consider a weaker statement in this paper asking if: every ideal access structure admits an ideal perfect group-characterizable (GC) SSS. Since the class of GC SSSs is known to include the multi-linear ones (as well as several classes of non-linear schemes), it might turn out that the second statement is not only true but also easier to tackle. Unfortunately, our understanding of GC SSSs is still too basic to tackle the weaker statement. As a first attempt, it is natural to ask if every ideal perfect SSS is equivalent to some GC scheme. The main contribution of this paper is to construct counterexamples using tools from theory of Latin squares and some recent results developed by the present authors for studying GC SSSs.

By associating Fermat's Little Theorem based $GF(2^n)$ inversion algorithms with the multiplicative Norm function, we present an additive Trace based $GF(2^n)$ inversion algorithm. For elements with Trace value 0, it needs 1 less multiplication operation than Fermat's Little Theorem based algorithms in some $GF(2^n)$s.

Due to growing commercial applications like Blockchain, the performance of large-integer arithmetic is the focus of both academic and industrial research. IBM introduced a new integer fused multiply-add instruction in z14, called VMSL, to accelerate such workloads. Unlike their floating-point counterparts, there are a variety of integer fused multiply-add instruction designs. VMSL multiplies two pairs of radix $2^{56}$ inputs, sums the two results together with an additional 128-bit input, and stores the resulting 128-bit value in a vector register. In this paper, we will describe the unique features of VMSL, the ways in which it is inherently more efficient than alternative specifications, in particular by enabling multiple carry strategies. We will then look at the issues we encountered implementing Montgomery Modular Multiplication for Elliptic Curve Cryptography on z14, including radix choice, mixed radices, instruction selection to trade instruction count for latency, and VMSL-specific optimizations for Montgomery-friendly moduli. The best choices resulted in a 20% increase in throughput.

This study is an attempt in quest of the fastest hardware algorithms for the computation of the verifiable delay function (VDF), $a^{2^T} \bmod N$, proposed for use in various distributed protocols, in which no party is assumed to compute it significantly faster than other participants. To this end, we propose a class of modular squaring algorithms suitable for low-latency ASIC implementations. The proposed algorithms aim to achieve highest levels of parallelization that have not been explored in previous works in the literature, which usually pursue more balanced optimization of speed and area. For this, we utilize redundant representations of integers and introduce three modular squaring algorithms that work with integers in redundant forms: i) Montgomery algorithm, ii) memory-based algorithm and iii) direct reduction algorithm for fixed moduli. All algorithms enable $O(\log k)$ depth circuit implementations, where $k$ is the bit-size of the modulus $N$ in the VDF function. We analyze and compare gate level-circuits of the proposed algorithms and provide estimates for their critical path delay and gate count.

In this work, we propose a slightly stronger variant of witness pseudorandom function (WPRF) defined by Zhandry (TCC 2016), that we call puncturable witness pseudorandom function (pWPRF). It is capable of generating a pseudorandom value corresponding to every statement of an NP language. We utilize the punctured technique to extend applications of WPRF. Specifically, we construct a semi-adaptively secure offline witness encryption (OWE) scheme using a pWPRF, an indistinguishability obfuscation (iO) and a symmetric-key encryption (SKE), which enables us to encrypt messages along with NP statements. We show that replacing iO with extractability obfuscation, the OWE turns out to be an extractable offline witness encryption scheme. To gain finer control over data, we further demonstrate how to convert our OWEs into offline functional witness encryption (OFWE) and extractable OFWE. The ciphertext size of current available OWEs grows polynomially with the size of messages, whereas all of our OWEs produce optimal size ciphertexts. Finally, we show that the WPRF of Pal et al. (ACISP 2019) can be extended to a pWPRF and an extractable pWPRF.

In a recent work, Kumar, Meka, and Sahai (FOCS 2019) introduced the notion of bounded collusion protocols (BCPs), in which $N$ parties wish to compute some joint function $f:(\{0,1\}^n)^N\to\{0,1\}$ using a public blackboard, but such that only $p$ parties may collude at a time. This generalizes well studied models in multiparty communication complexity, such as the number-in-hand (NIH) and number-on-forehead (NOF) models, which are just endpoints on this rich spectrum. We construct explicit hard functions against this spectrum, and achieve a tradeoff between collusion and complexity. Using this, we obtain improved leakage-resilient secret sharing schemes against bounded collusion protocols.

Our main tool in obtaining hard functions against BCPs are explicit constructions of leakage resilient extractors against BCPs for a wide range of parameters. Kumar et al. (FOCS 2019) studied such extractors and called them cylinder intersection extractors. In fact, such extractors directly yield correlation bounds against BCPs. We focus on the following setting: the input to the extractor consists of $N$ independent sources of length $n$, and the leakage function Leak $:(\{0,1\}^n)^N\to\{0,1\}^\mu\in\mathcal{F}$ is a BCP with some collusion bound $p$ and leakage (output length) $\mu$. While our extractor constructions are very general, we highlight some interesting parameter settings:

1. In the case when the input sources are uniform, and $p=0.99N$ parties collude, our extractor can handle $n^{\Omega(1)}$ bits of leakage, regardless of the dependence between $N,n$. The best NOF lower bound (i.e., $p=N-1$) on the other hand requires $N<\log n$ even to handle $1$ bit of leakage.

2. Next, we show that for the same setting as above, we can drop the entropy requirement to $k=$polylog $n$, while still handling polynomial leakage for $p=0.99N$. This resolves an open question about cylinder intersection extractors raised by Kumar et al. (FOCS 2019), and we find an application of such low entropy extractors in a new type of secret sharing.

We also provide an explicit compiler that transforms any function with high NOF (distributional) communication complexity into a leakage-resilient extractor that can handle polylogarithmic entropy and substantially more leakage against BCPs. Thus any improvement of NOF lower bounds will immediately yield better leakage-resilient extractors.

Using our extractors against BCPs, we obtain improved $N$-out-of-$N$ leakage-resilient secret sharing schemes. The previous best scheme from Kumar et al. (FOCS 2019) required share size to grow exponentially in the collusion bound, and thus cannot efficiently handle $p=\omega(\log N)$. Our schemes have no dependence of this form, and can thus handle collusion size $p=0.99N$.

In this work we first provide a framework for defining a large subset of pairing-based digital signature schemes which we call Partially Structure-Preserving Signature (PSPS) schemes. PSPS schemes are similar in nature to structure-preserving signatures with the exception that in these schemes messages are scalars from $\Z^n_p$ instead of being source group elements. This class encompasses various existing schemes which have a number of desirable features which makes them an ideal building block for many privacy-preserving cryptographic protocols. They include the widely-used schemes of Camenisch-Lysyanskaya (CRYPTO 2004) and Pointcheval-Sanders (CT-RSA 2016). We then provide various impossibility and lower bound results for variants of this class. Our results include bounds for the signature and verification key sizes as well as lower bounds for achieving strong unforgeability. We also give a generic framework for transforming variants of PSPS schemes into structure-preserving ones. As part of our contribution, we also give a number of optimal PSPS schemes which may be of independent interest. Our results aid in understanding the efficiency of pairing-based signature schemes and show a connection between this class of signature schemes and structure-preserving ones.

The widespread adoption of decentralized cryptocurrencies, such as Bitcoin or Ethereum, is currently hindered by their inherently limited transaction rate. One of the most prominent proposals to tackle this scalability issue are payment channels which allow mutually distrusted parties to exchange an arbitrary number of payments in the form of off-chain authenticated messages while posting only a limited number of transactions onto the blockchain. Specifically, two transactions suffice, unless a dispute between these parties occurs, in which case more on-chain transactions are required to restore the correct balance. Unfortunately, popular constructions, such as the Lightning network for Bitcoin, suffer from heavy communication complexity both off-chain and on-chain in case of dispute. Concretely, the communication overhead grows exponentially and linearly, respectively, in the number of applications that run in the channel. In this work, we introduce and formalize the notion of generalized channels for Bitcoin-like cryptocurrencies. Generalized channels significantly extend the concept of payment channels so as to perform off-chain any operation supported by the underlying blockchain. Besides the gain in expressiveness, generalized channels outperform state-of-the-art payment channel constructions in efficiency, reducing the communication complexity and the on-chain footprint in case of disputes to linear and constant, respectively. We provide a cryptographic instantiation of generalized channels that is compatible with Bitcoin, leveraging adaptor signatures -- a cryptographic primitive already used in the cryptocurrency literature but formalized as a standalone primitive in this work for the first time. We formally prove the security of our construction in the Universal Composability framework. Furthermore, we conduct an experimental evaluation, demonstrating the expressiveness and performance of generalized channels when used as building blocks for popular off-chain applications, such as channel splitting and payment-channel networks.

This paper provides a theoretical background for a new consensus model called Proof of Review (PoR), which extends Algorand’s blockchain consensus model and reproduces the human mechanism for analyzing reviews through analysis and reputation. Our protocol derives the trustworthiness of a participant’s reputation through a consensus of these reviews.

In this new protocol, we combined concepts from proof of stake and proof of reputation to ensure a blockchain system comes to consensus on an honest (non-malicious) congruent review. Additionally, we formally prove this protocol provides further security by using a reputation-based stake instead of token-based, using theorems and proofs. We introduce new concepts in using reputation as a stake, where reputation must be earned and can never be purchased, spent, or traded. The stake is calculated based on the reputation -- not tokens -- of a user in the system proportional to the total reputation in the system at the beginning of each round. A round is a set of steps that conclude in a block being added to the blockchain. We also introduce blacklisting as a decisive action where, after a vote, an honest user will blacklist a leader (the participant elected with their proposed block) or reviewer for some egregious maliciousness, preventing further participation.

Five steps are defined that overlay Algorand’s steps: (1) Evaluation of reviews; (2) Selection of the round’s leader and their associated block containing reviews; (3) Re-evaluation of reviews; (4) Block of reviews agreement (block decision); (5) Block addition to the ledger and reputation adjustment. At every step, verifiers are selected randomly for evaluating the reviews and are anonymous to each other. We provided properties related to reputation and formally proved (Honest Leader, Blacklisting Liveliness and Correctness, Evaluation of the Evaluator’s Confidence, Gradual Gain, and Swift Loss of Reputation). Finally, we discuss several types of attacks that are common for Proof of Stake and Reputation systems, and how our Proof of Review model (in extending Algorand) addresses those attacks. Furthermore, PoR mitigates several kinds of fake reviews (e.g. spam, trolling, etc.) through analysis.

Preliminary experimental results show that payment transactions have similar completion times, regardless of the stake being tokens or reputation, the mechanism for adjusting reputation reflects expected behavior, and the accuracy of the review evaluation (using sentimental analysis) is substantiated for the dataset given. With this new model, we let the technology evaluate a review and secure it on a blockchain using a reputation-based stake.

Proof of Review also provides third party access to reviewer’s reputation along with their respective evaluated reviews, a functionality that could benefit numerous industries including retail, academia, hospitality, corporate, and more. Applications could expedite and validate many different types of processes that rely on a form of review and the analysis of that review.

In CRYPTO'18, Groth et al. introduced the $\textit{updatable}$ CRS model that allows bypassing the trust in the setup of NIZK arguments. Zk-SNARKs are the well-known family of NIZK arguments that are ubiquitously deployed in practice. In applications that achieve $\textit{universal composability}$, e.g. Hawk [S&P'16], Gyges [CCS'16], Ouroboros Crypsinous [S&P'19], the underlying SNARK is lifted by the $\texttt{COCO}$ framework [Kosba et al.,2015] to achieve Black-Box Simulation Extractability (BB-SE). The $\texttt{COCO}$ framework is designed in the standard CRS model, consequently, all BB-SE NIZK arguments built with it need a trusted setup phase. In a promising research direction, recently subversion-resistant and updatable SNARKs are proposed that can eliminate/bypass the needed trust in schemes. However, none of the available subversion-resistant/updatable schemes can achieve BB-SE, as Bellare et al.'s result from ASIACRYPT'16 shows that achieving simultaneously Sub-ZK (ZK without trusting a third party) and BB extractability is impossible. In this paper, we propose $\texttt{Tiramisu}$, as construction to build BB-SE NIZK arguments in the $\textit{updatable}$ CRS model. Similar to the $\texttt{COCO}$, $\texttt{Tiramisu}$ is suitable for modular use in larger cryptographic systems and allows building BB-SE NIZK arguments, but with $\textit{updatable}$ parameters. Our results show that one can bypass the impossibility of achieving Sub-ZK and BB extractability in the updatable CRS model. In new constructions, in the cost of updating, all parties can eliminate the trust on a third-party and the protocol satisfies ZK and BB-SE. Meanwhile, we define public-key cryptosystems with updatable keys and present an efficient construction based on the El-Gamal cryptosystem which can be of independent interest. We instantiate $\texttt{Tiramisu}$ and present efficient BB-SE zk-SNARKs with updatable parameters that can be used in protocols like Hawk, Gyges, Ouroboros Crypsinous while allowing the end-users to update the parameters and eliminate the needed trust.

In this work we study bounded collusion protocols (BCPs) recently introduced in the context of secret sharing by Kumar, Meka, and Sahai (FOCS 2019). These are multi-party communication protocols on $n$ parties where in each round a subset of $p$-parties (the collusion bound) collude together and write a function of their inputs on a public blackboard.

BCPs interpolate elegantly between the well-studied number-in-hand (NIH) model ($p=1$) and the number-on-forehead (NOF) model ($p=n-1$). Motivated by questions in communication complexity, secret sharing, and pseudorandomness we investigate BCPs more thoroughly, answering several questions about them.

* We prove a polynomial (in the input-length) lower bound for an explicit function against BCPs where any constant fraction of players can collude. Previously, nontrivial lower bounds were known only when the collusion bound was at most logarithmic in the input-length (owing to bottlenecks in NOF lower bounds). * For all $t \leq n$, we construct efficient $t$-out-of-$n$ secret sharing schemes where the secret remains hidden even given the transcript of a BCP with collusion bound $O(t/\log t)$. Prior work could only handle collusions of size $O(\log n)$. Along the way, we construct leakage-resilient schemes against disjoint and adaptive leakage, resolving a question asked by Goyal and Kumar (STOC 2018).

* An explicit $n$-source cylinder intersection extractor whose output is close to uniform even when given the transcript of a BCP with a constant fraction of parties colluding. The min-entropy rate we require is $0.3$ (independent of collusion bound $p \ll n$).

Our results rely on a new class of exponential sums that interpolate between the ones considered in additive combinatorics by Bourgain (Geometric and Functional Analysis 2009) and Petridis and Shparlinski (Journal d'Analyse Mathématique 2019).

Directed Acyclic Graph (DAG) is becoming an intriguing direction for distributed ledger structure due to its great potential in improving the scalability of distributed ledger systems. Among existing DAG-based ledgers, one promising category is transaction DAG, namely, treating each transaction as a graph vertex. In this paper, we propose Haootia, a novel two-layer framework of consensus, with a ledger in the form of a transaction DAG built on top of a delicately designed PoW-based backbone chain. By elaborately devising the principle of transaction linearizations, we achieve a secure and scalable DAG-based consensus. By implementing Haootia, we conclude that, with a rotating committee of size 46 and a confirmation latency around 20 seconds, Haootia achieves a throughput around 7500 TPS which is overwhelming compared with all formally analyzed DAG-based consensus schemes to date and all existing non-DAG-based ones to our knowledge.

In this work, we prove that Interpose PUF is learnable in the PAC model. First, we show that Interpose PUF can be approximated by a Linear Threshold Function~(LTF), assuming the interpose bit to be random. We translate the randomness in the interpose bit to classification noise of the hypothesis. Using classification noise model, we prove that the resultant LTF can be learned with number of labelled examples~(challenge response pairs) polynomial in the number of stages and PAC model parameters.

Event date: 26 August to 28 August 2020
Submission deadline: 8 May 2020
Notification: 12 June 2020

Event date: 23 October to 25 October 2020
Submission deadline: 25 June 2020
Notification: 25 July 2020

Event date: 25 August to 28 August 2020
Submission deadline: 1 May 2020
Notification: 5 June 2020

Industrial systems are often used to monitor and control a physical process such as energy production and distribution, water cleaning or transport systems. They are often simply called Supervisory Control And Data Acquisition (SCADA) systems. Due to their interaction withthe real world, the safety of these systems is critical and any incident can potentially harm humans and the environment. One of the main research axis in cybersecurity of industrial systems deals with combination of safety and security properties. Safety relates to applicative properties of the system (e.g. chemical properties for a chemical factory); while security properties take into account how an intruder can harm the system. As show in [3], combining safety and security is a challenging topic as these properties can be either dependent, strengthening, antagonist or independent. currently no tool is able to handle both aspects at the same time. In this context, we propose a Ph.D thesis revolving around modeling of industrial systems taking into account both safety properties of the physical process and security properties. Besides the definition of an accurate, yet automatically analyzable modeling framework/language, many aspects can be part of the subject. For instance, programmable automata (PLC) configuration files could be generated from this model in order to only deploy programs validated beforehand. PLC vulnerabilities could be studied (firmware reverse engineering, protocol fuzzing) in order to test the technical feasibility of found attacks. Finally, in a certification context, security analyzes on the model could include requirements from standards such as IEC 62443 [5] to help evaluation process

Closing date for applications:

Contact: Maxime Puys

As a consequence of the rapid development of the Internet of Things (IoT), where devices are massively interconnected, security breaches are discovered daily. The growing threat of physical attacks, on which connected objects are widely exposed, forces chipmakers to increase the security of their products. True Random Number Generators are the cornerstone of device security; they are required for running cryptographic algorithms and fully integrated into encryption engines. The security level of the system directly depends on the randomness of the bits generated. Furthermore, IoT chips are facing harsh constraints in terms of price and power consumption. In order to be integrated into these chips, TRNG must offer an efficient tradeoff between cost and security. In this perspective, TRNGs based on already integrated components, such as RRAM memories, is a promising lead.

Closing date for applications:

Contact: Florian Pebay-Peyroula

This study is focused on the security of embedded systems and in particular asymmetric cryptography against horizontal attacks and Template attacks. Recent studies, applied to symmetric cryptography, have made it possible to build new techniques for side channel attacks. By improving the effectiveness of Template attacks, these new attacks make it easier to bypass masking countermeasures. It seems appropriate to study these new tools in depth in the context of Template and horizontal attacks against asymmetric cryptography, especially for elliptic curves. The use of machine learning in the context of side channel attacks. The main purpose of the thesis is to evaluate the security properties of ECCs against the most advanced Template and Horizontal attacks that use machine learning. Depending on the results obtained, new countermeasures will have to be constructed in order to address any new weaknesses.

Closing date for applications:

Contact: Antoine Loiseau

Since its inception, the web has grown substantially and websites have turned into rich client-side experience customized for the user where third parties supply a considerable amount of content. The increasing reliance on third parties has brought a number of privacy issues to the web with web tracking being at the top of that list. With cookies and browser fingerprinting, users are on the losing side of privacy as they can be tracked across the domains they are visiting. To regain control, browser vendors like Mozilla and Apple have added in their own browsers a tracking protection mechanism (called Enhanced Tracking Protection for Firefox and Intelligent Tracking Protection for Safari) aimed at preventing track- ing on the web. Yet, essential functionality of a website is sometimes so intertwined with tracking code that using these protective mechanisms can transitively “break” a webpage. We define “page breakage” as an undesirable behavior on a webpage and it includes, but is not limited to, page slowdowns, page freezes, page crashes, page errors and page display issues. In order to push online privacy forward, there is a real need today to identify and block properly tracking entities on the web without the current usability costs associated with it.

Closing date for applications:

Contact: Pierre Laperdrix

More information: https://amiunique.org/phd-proposal-blocking.pdf