International Association
for Cryptologic Research

We study information-theoretic multiparty computation (MPC) protocols over rings $\mathbb{Z}/p^k \mathbb{Z}$ that have good asymptotic communication complexity for a large number of players. An important ingredient for such protocols is arithmetic secret sharing, i.e., linear secret-sharing schemes with multiplicative properties. The standard way to obtain these over fields is with a family of linear codes $C$, such that $C$, $C^\perp$ and $C^2$ are asymptotically good (strongly multiplicative). For our purposes here it suffices if the square code $C^2$ is not the whole space, i.e., has codimension at least 1 (multiplicative).

Our approach is to lift such a family of codes defined over a finite field $\mathbb F$ to a Galois ring, which is a local ring that has $\mathbb F$ as its residue field and that contains $\mathbb{Z}/p^k \mathbb{Z}$ as a subring, and thus enables arithmetic that is compatible with both structures. Although arbitrary lifts preserve the distance and dual distance of a code, as we demonstrate with a counterexample, the multiplicative property is not preserved. We work around this issue by showing a dedicated lift that preserves \emph{self-orthogonality} (as well as distance and dual distance), for $p \geq 3$. Self-orthogonal codes are multiplicative, therefore we can use existing results of asymptotically good self-dual codes over fields to obtain arithmetic secret sharing over Galois rings. For $p = 2$ we obtain multiplicativity by using existing techniques of secret-sharing using both $C$ and $C^\perp$, incurring a constant overhead. As a result, we obtain asymptotically good arithmetic secret-sharing schemes over Galois rings.

With these schemes in hand, we extend existing field-based MPC protocols to obtain MPC over $\mathbb{Z}/p^k \mathbb{Z}$, in the setting of a submaximal adversary corrupting less than a fraction $1/2 - \varepsilon$ of the players, where $\varepsilon > 0$ is arbitrarily small. We consider 3 different corruption models. For passive and active security with abort, our protocols communicate $O(n)$ bits per multiplication. For full security with guaranteed output delivery we use a preprocessing model and get $O(n)$ bits per multiplication in the online phase and $O(n \log n)$ bits per multiplication in the offline phase. Thus, we obtain true linear bit complexities, without the common assumption that the ring size depends on the number of players.

This paper considers multivariate polynomial equation systems over GF(2) that have a small number of solutions. This paper gives a new method EGHAM2 for solving such systems of equations that uses the properties of the Boolean quotient ring to potentially reduce memory and time complexity relative to existing XL-type or Groebner basis algorithms applied in this setting. This paper also establishes a direct connection between solving such a multivariate polynomial equation system over GF(2), an MQ problem, and an instance of the LPN problem.

This paper closes the question of the possibility of two-round MPC protocols achieving different security guarantees with and without the availability of broadcast in any given round. Cohen et al. [CGZ20] study this question in the dishonest majority setting; we complete the picture by studying the honest majority setting. In the honest majority setting, given broadcast in both rounds, it is known that the strongest guarantee — guaranteed output delivery — is achievable [GLS15]. We show that in this setting, given broadcast in the first round only, guaranteed output delivery is still achievable. Given broadcast in the second round only, identifiable abort and all weaker guarantees are achievable, but fairness — and thus guaranteed output delivery — are not. Finally, using only peer-to-peer channels, for corruption thresholds $t > 1$ we show that the weakest guarantee — selective abort — is the only one achievable. For $t = 1$ and $n \geq 4$, it is known [IKP10,IKKP15] that guaranteed output delivery (and thus all weaker guarantees) are possible. We show that for $t = 1$ and $n = 3$ the strongest achievable guarantee is selective abort, resolving the question of best achievable guarantees in two-round secure computation protocols.

In this paper we present a new representation of the AES key schedule, with some implications to the security of AES-based schemes. In particular, we show that the AES-128 key schedule can be split into four independent parallel computations operating on 32 bits chunks, up to linear transformation. Surprisingly, this property has not been described in the literature after more than 20 years of analysis of AES. We show two consequences of our new representation, improving previous cryptanalysis results of AES-based schemes. First, we observe that iterating an odd number of key schedule rounds results in a function with short cycles. This explains an observation of Khairallah on mixFeed, a second-round candidate in the NIST lightweight competition. Our analysis actually shows that his forgery attack on mixFeed succeeds with probability 0.44 (with data complexity 220GB), breaking the scheme in practice. The same observation also leads to a novel attack on ALE, another AES-based AEAD scheme. Our new representation also gives efficient ways to combine information from the first sub-keys and information from the last sub-keys, in order to reconstruct the corresponding master keys. In particular we improve previous impossible-differential attacks against AES-128.

The chair of IT Security at the Brandenburg University of Technology Cottbus-Senftenberg is currently seeking a highly motivated Junior Researcher / PhD Student (limited to 3 years, full time, with possibility for extension).

Tasks:
– Research in the area of intrusion detection systems (IDS) for critical infrastructures, secure cyber-physical systems, and artificial intelligence / machine learning for traffic analysis
– Implementation and evaluation of new algorithms and methods
– Cooperation and knowledge transfer with industrial partners
– Publication of scientific results
– Assistance with teaching

The employment takes place with the goal of doctoral graduation (obtaining a PhD degree).

Requirements:
– Master’s degree (or equivalent) in Computer Science or related disciplines
– Interest in IT security and/or networking and distributed systems
– Knowledge of at least one programming language (C++, Java, etc.) and one scripting language (Perl, Python, etc.) or willingness to quickly learn new programming languages
– Linux/Unix skills
– Knowledge of data mining, machine learning, statistics and result visualization concepts is of advantage
– Excellent working knowledge of English; German is of advantage
– Communication skills

For more information about the vacant position please contact Prof. A. Panchenko (E-Mail: itsec-jobs.informatik@lists.b-tu.de).

We value diversity and therefore welcome all applications. Applicants with disabilities will be given preferential treatment if they are equally qualified.

Applications containing:
– A detailed Curriculum Vitae
– Transcript of records from your Master studies
– An electronic version of your Master thesis, if possible
should be sent in a single PDF file by 26.10.2020 at itsec-jobs.informatik@lists.b-tu.de.

Closing date for applications:

Contact: Prof. Andriy Panchenko (itsec-jobs.informatik@lists.b-tu.de)

More information: https://www.b-tu.de/en/fg-it-sicherheit

Located at the heart of the future Green City of Benguerir, Mohammed VI Polytechnic University (UM6P), a higher education institution with an international standard, is established to serve Morocco and the African continent. Its vision is honed around research and innovation at the service of education and development. This unique nascent university, with its state-of-the-art campus and infrastructure, has woven a sound academic and research network, and its recruitment process is seeking high quality academics and professionals in order to boost its quality-oriented research environment in the metropolitan area of Marrakech. The School of Computer and Communication Sciences at Mohammed VI Polytechnic University (UM6P), Benguerir, Morocco is currently looking for motivated and talented Postdoctoral researchers in applied cryptography, and Information security. The successful candidates will primarily be working on the following topics (but not limited to): • Threshold Cryptography • Blockchains and Cryptocurrencies • Secure Multi Party Computation • Cloud Computing Security • Lightweight Cryptography for IoT The ideal candidates should have a PhD degree in cryptography (or related field) from a leading university, and a proven record of publications in top cryptography/security/TCS venues. We offer competitive salary (the net salary per month is 2000 USD), a budget for conference travel and research visit, and membership in a young and vibrant team with several international contacts (for more see: https://www.um6p.ma/en). Submit your application via email including • full CV, • sample publications, • a detailed research proposal, • and 2-3 reference letters sent directly by the referees. There is no specific deadline for this call, but we will start looking at the applications from Oct 15th, 2020. Contact: Assoc. Prof. Mustapha Hedabou (mustapha.hedabou@um6p.ma) https://career2.successfactors.eu/sfcareer/jobreqcareer?jobId=1339&company=ump

Closing date for applications:

Contact: Assoc. Prof. Mustapha Hedabou (mustapha.hedabou@um6p.ma)

More information: https://career2.successfactors.eu/sfcareer/jobreqcareer?jobId=1339&company=ump

The School of Cyber Science and Engineering (formerly known as the School of Information Security Engineering) of Shanghai Jiao Tong University was founded in October 2000. It was the first school-level training base for high-level information security professionals in China and was jointly established by the Ministry of Education of China, the Ministry of Science and Technology of China, and the Shanghai Municipal People’s Government. The undergraduate and postgraduate students of the school mainly come from the top 100 key high schools and 985/double first-class universities in China. The school is ranked among the best cyberspace security nationwide every year. The school has a solid foundation and strength in the field of academic research and technological innovation on cyberspace security. The school is committed to building a world-class academic research center, cultivating the talents of the country and society. The school is in great demand of a number of world renowned professors, outstanding young researchers, full-time research fellows and post-doctors. The school now has about 20 positions available at the rank of tenure-track Assistant Professors, tenure-track Associate Professors, or tenured Full Professors in theory and practice of cyberspace security. Applicants should have (a) a doctoral degree in Computer Science, Electronic Engineering, Communication, Mathematics or Statistics; (b) an established track record in research and scholarship; (c) expertise in the cryptographic and security research areas; and (d) a demonstrated commitment to excellence in teaching. The school will provide highly competitive remuneration packages and assist applicants to apply for various national, provincial and ministerial level talent programs such as “1000 Youth Talents Program”, Shanghai “Oriental Scholar Program”,etc. We will also assist on employment of spouses, schooling for children and medical care.

Closing date for applications:

Contact: Chaoping Xing, emial: xingcp@sjtu.edu.cn Linjie Li, email: lilinjie@sjtu.edu.cn

A Leakage Resilient Secret Sharing (LRSS) is a secure secret sharing scheme, even when the adversary obtains some (bounded) leakage on honest shares. Ideally, such schemes must be secure against adaptive and joint leakage queries - i.e., the adversary can make a sequence of adaptive leakage queries where each query can be a joint function of many of the shares. The most important parameters of interest are the rate (= $\frac{|secret|}{|longest share|}$) and the leakage rate (ratio of the total allowable leakage from a single leakage query to the size of a share). None of the prior works tolerating such adaptive and joint leakage could attain a constant rate and constant leakage rate, even for the threshold access structure. An LRSS is non-malleable (LRNMSS) when an adversary cannot tamper shares in a way that the reconstructed secret is related to the original secret. Similar to LRSSs, none of the prior LRNMSS schemes in the information theoretic setting could attain a constant rate, even for the threshold access structure.

In this work, we provide the first constant rate LRSS (for the general access structure) and LRNMSS (for the threshold access structure) schemes that tolerate such joint and adaptive leakage in the information-theoretic setting. We show how to make use of our constructions to also provide constant rate constructions of leakage-resilient (and non-malleable) secure message transmission.

We obtain our results by introducing a novel object called Adaptive Extractors. Adaptive extractors can be seen as a generalization of the notion of exposure-resilient extractors (Zimand, CCC 2006). Such extractors provide security guarantees even when an adversary obtains leakage on the source of the extractor after observing the extractor output. We make a compelling case for the study of such extractors by demonstrating their critical use for obtaining adaptive leakage and believe that such an object will be of independent interest.

In this paper, various quantitative information-theoretic security reductions which correlate statistical difference between two probability distributions with security level’s gap between two cryptographic schemes are proposed. Security is the most important prerequisite for cryptographic primitives. In general, there are two kinds of security; one is computational security, and the other is information-theoretic security. We focus on latter one in this paper, especially the view point of bit security which is a convenient notion to indicate the quantitative security level. We propose tighter and more generalized version of information-theoretic security reductions than those of the previous works [1,2]. More specifically, we obtain about 2.5-bit tighter security reduction than that in previous work [2], and we devise a further generalized version of security reduction in the previous work [1] by relaxing the constraint on the upper bound of the information-theoretic measure, that is, λ-efficient. Through this work, we propose the methodology to estimate the affects on security level when κ-bit secure original scheme is implemented on p-bit precision system. (Here, p can be set to any value as long as certain condition is satisfied.) In the previous work [1], p was fixed as κ/2, but our result is generalized to make it possible to security level κ and precision p variate independently. Moreover, we provide diverse types of security reduction formulas for the five kinds of information-theoretic measures. We are expecting that our results could provide an information-theoretic guideline for how much the two identical cryptographic schemes (i.e., the only difference is probability distribution) may show the difference in their security level when extracting their randomness from two different probability distributions. Especially, our results can be used to obtain the quantitative estimation of how much the statistical difference between the ideal distribution and the real distribution affects the security level.

We present a signature scheme for Hamming metric random linear codes via the Schnorr-Lyubashevsky framework that employs the rejection sampling on appropriate probability distributions instead of using trapdoors. Such an approach has been widely believed to be more challenging for linear codes as compared to lattices with Gaussian distributions. We prove that our signature scheme achieves EUF-CMA security under the assumption of the decoding one out of many problem or achieves strong EUF-CMA security under the assumption of the codeword finding problem under relaxed parameters. We provide an instantiation of the signature scheme based on Ring-LPN instances as well as quasi-cyclic codes and present some concrete parameters. In addition, a proof of concept implementation of the scheme is provided. We compare our scheme with previous unsuccessful similar attempts and provide a rigorous security analysis of our scheme.

Our construction primarily relies on an efficient rejection sampling lemma for binary linear codes with respect to suitably defined variants of the binomial distribution. Essentially, the rejection sampling lemma indicates that adding a small weight vector to a large weight vector has no significant effect on the distribution of the large weight vector. Concretely, we prove that if the large weight is at least the square of the small weight and the large weight vector admits binomial distribution, the sum distribution of the two vectors can be efficiently adjusted to a binomial distribution via the rejection step and independent from the small weight vector. As a result, our scheme outputs a signature distribution that is independent of the secret key.

Compared to two existing code based signature schemes, namely Durandal and Wave, the security of our scheme is reduced to full-fledged hard coding problems i.e., codeword finding problem and syndrome decoding problem for random linear codes. By contrast, the security of the Durandal and Wave schemes is reduced to newly introduced product spaces subspaces indistinguishability problem and the indistinguishability of generalized $(U,U+V)$ codes problem, respectively. We believe that building our scheme upon the more mature hard coding problems provides stronger confidence to the security of our signature scheme.

Adversaries in cryptography have traditionally been modeled as either semi-honest or malicious. Over the years, however, several lines of work have investigated the design of cryptographic protocols against rational adversaries. The most well-known example are covert adversaries in secure computation (Aumann & Lindell, TCC '07) which are adversaries that wish to deviate from the protocol but without being detected. To protect against such adversaries, protocols secure in the covert model guarantee that deviations are detected with probability at least $\varepsilon$ which is known as the deterrence factor.

In this work, we initiate the study of contracts in cryptographic protocol design. We show how to design, use and analyze contracts between parties for the purpose of incentivizing honest behavior from rational adversaries. We refer to such contracts as adversarial level agreements (ALA). The framework we propose can result in more efficient protocols and can enforce deterrence in covert protocols; meaning that one can guarantee that a given deterrence factor will deter the adversary instead of assuming it.

We show how to apply our framework to two-party protocols, including secure two-party computation (2PC) and proofs of storage (PoS). In the 2PC case, we integrate ALAs to publicly-verifiable covert protocols and show, through a game-theoretic analysis, how to set the parameters of the ALA to guarantee honest behavior. We do the same in the setting of PoS which are two-party protocols that allow a client to efficiently verify the integrity of a file stored in the cloud.

Private information retrieval (PIR) lets a client retrieve an entry from a database held by a server, without the server learning which entry was retrieved. Here we study a weaker variant that we call *random-index PIR* (RPIR). It differs from standard PIR in that the retrieved index is an output rather than an input of the protocol, and it is chosen at random.

Our motivation for studying RPIR comes from a recent work of Benhamouda et al. (TCC'20) about maintaining secret values on public blockchains. Their solution involves choosing a small anonymous committee from among a large universe, and here we show that RPIR can be used for that purpose.

The RPIR client must be implemented via secure MPC for this use case, stressing the need to make it as efficient as can be. Combined with recent techniques for secure-MPC with stateless parties, our results yield a new secrets-on-blockchain construction (and more generally large-scale MPC). Our solution tolerates any fraction $f \lneq 1/2$ of corrupted parties, solving an open problem left from the work of Benhamouda et al.

Considering RPIR as a primitive, we show that it is in fact equivalent to PIR when there are no restrictions on the number of communication rounds. On the other hand, RPIR can be implemented in a ``noninteractive'' setting, which is clearly impossible for PIR. We also study batch RPIR, where multiple indexes are retrieved at once. Specifically we consider a weaker security guarantee than full RPIR, which is still good enough for our motivating application. We show that this weaker variant can be realized more efficiently than standard PIR or RPIR, and we discuss one protocol in particular that may be attractive for practical implementations.

We propose a new doubly efficient interactive proof protocol for general arithmetic circuits. The protocol generalizes the doubly efficient interactive proof for layered circuits proposed by Goldwasser, Kalai and Rothblum to arbitrary circuits while preserving the optimal prover complexity that is strictly linear to the size of the circuits. The proof size remains succinct for low depth circuits and the verifier time is sublinear for structured circuits. We then construct a new zero knowledge argument scheme for general arithmetic circuits using our new interactive proof protocol together with polynomial commitments.

Not only does our new protocol achieve optimal prover complexity asymptotically, but it is also efficient in practice. Our experiments show that it only takes 1 second to generate the proof for a circuit with 600,000 gates, which is 7 times faster than the original interactive proof protocol on the corresponding layered circuit. The proof size is 229 kilobytes and the verifier time is 0.56 second. Our implementation can take general arithmetic circuits generated by existing tools directly, without transforming them to layered circuits with high overhead on the size of the circuits.

We show that noisy leakage can be simulated in the information-theoretic setting using a single query of bounded leakage, up to a small statistical simulation error and a slight loss in the leakage parameter. The latter holds true in particular for one of the most used noisy-leakage models, where the noisiness is measured using the conditional average min-entropy (Naor and Segev, CRYPTO'09 and SICOMP'12).

Our reductions between noisy and bounded leakage are achieved in two steps. First, we put forward a new leakage model (dubbed the dense leakage model) and prove that dense leakage can be simulated in the information-theoretic setting using a single query of bounded leakage, up to small statistical distance. Second, we show that the most common noisy-leakage models fall within the class of dense leakage, with good parameters. We also provide a complete picture of the relationships between different noisy-leakage models, and prove lower bounds showing that our reductions are nearly optimal.

Our result finds applications to leakage-resilient cryptography, where we are often able to lift security in the presence of bounded leakage to security in the presence of noisy leakage, both in the information-theoretic and in the computational setting. Additionally, we show how to use lower bounds in communication complexity to prove that bounded-collusion protocols (Kumar, Meka, and Sahai, FOCS'19) for certain functions do not only require long transcripts, but also necessarily need to reveal enough information about the inputs.

We introduce a new m-entwined ROS problem that tweaks a random inhomogeneities in an overdetermined solvable system of linear equations (ROS) problem in a scalar field using an associated group. We prove hardness of the 2-entwined ROS-like problem in AGM plus ROM, assuming DLOG hardness in the associated group.

Assuming AGM plus ROM plus KOSK and OMDL, we then prove security for a two-round trip Schnorr multi-signature protocol DWMS that creates its witness aka nonce by delinearizing two pre-witnesses supplied by each signer.

At present, DWMS and MuSig-DN are the only known provably secure two-round Schnorr multi-signatures, or equivalently threshold Schnorr signatures.

This paper analyses security of concrete instantiations of EdDSA by identifying exploitable inconsistencies between standardization recommendations and Ed25519 implementations. We mainly focus on current ambiguity regarding signature verification equations, binding and malleability guarantees, and incompatibilities between randomized batch and single verification. We give a formulation of Ed25519 signature scheme that achieves the highest level of security, explaining how each step of the algorithm links with the formal security properties. We develop optimizations to allow for more efficient secure implementations. Finally, we designed a set of edge-case test-vectors and run them by some of the most popular Ed25519 libraries. The results allowed to understand the security level of those implementations and showed that most libraries do not comply with the latest standardization recommendations. The methodology allows to test compatibility of different Ed25519 implementations which is of practical importance for consensus-driven applications.

The unbalanced oil and vinegar signature scheme (UOV) is a multivariate signature scheme that has essentially not been broken for over 20 years. However, it requires the use of a large public key, so various methods have been proposed to reduce its size. In this paper, we propose a new variant of UOV with the public key represented by block matrices whose components are represented as an element of a quotient ring. We discuss how the irreducibility of the polynomial used to generate the quotient ring affects the security of our proposed scheme. Furthermore, we propose parameters for our proposed scheme and discuss their security against currently known and possible attacks. We show that our proposed scheme can reduce the public key size without significantly increasing the signature size compared with other UOV variants. For example, the public key size of our proposed scheme is 66.7 KB for NIST's Post-Quantum Cryptography Project (security level 3), while that of cyclic Rainbow is 252.3 KB, where Rainbow is a variant of UOV and one of the third round finalists of NIST PQC project.

In this paper, we reevaluate the security of GIFT against differential cryptanalysis under both single-key scenario and related-key scenario. Firstly, we apply Matsui's algorithm to search related-key differential trails of GIFT. We add three constraints to limit the search space and search the optimal related-key differential trails on the limited search space. We obtain related-key differential trails of GIFT-64/128 for up to 15/14 rounds, which are the best results on related-key differential trails of GIFT so far. Secondly, we propose an automatic algorithm to increase the probability of the related-key boomerang distinguisher of GIFT by searching the clustering of the related-key differential trails utilized in the boomerang distinguisher. We find a 20-round related-key boomerang distinguisher of GIFT-64 with probability 2^-58.557. The 25-round related-key rectangle attack on GIFT-64 is constructed based on it. This is the longest attack on GIFT-64. We also find a 19-round related-key boomerang distinguisher of GIFT-128 with probability 2^-109.626. We propose a 23-round related-key rectangle attack on GIFT-128 utilizing the 19-round distinguisher, which is the longest related-key attack on GIFT-128. The 24-round related-key rectangle attack on GIFT-64 and 22-round related-key boomerang attack on GIFT-128 are also presented. Thirdly, we search the clustering of the single-key differential trails. We increase the probability of a 20-round single-key differential distinguisher of GIFT-128 from 2^-121.415 to 2^-120.245. The time complexity of the 26-round differential attack on GIFT-128 is improved from 2^124:415 to 2^123:245.

Differential power analysis (DPA) is a form of side-channel analysis (SCA) that performs statistical analysis on the power traces of cryptographic computations. DPA is applicable to many cryptographic primitives, including block ciphers, stream ciphers and even hash-based message authentication code (HMAC). At COSADE 2017, Dobraunig~et~al. presented a DPA on the fresh re-keying scheme Keymill to extract the bit relations of neighbouring bits in its shift registers, reducing the internal state guessing space from 128 to 4 bits. In this work, we generalise their methodology and combine with differential analysis, we called it differential analysis aided power attack (DAPA), to uncover more bit relations and take into account the linear or non-linear functions that feedback to the shift registers (i.e. LFSRs or NLFSRs). Next, we apply our DAPA on LR-Keymill, the improved version of Keymill designed to resist the aforementioned DPA, and breaks its 67.9-bit security claim with a 4-bit internal state guessing. We experimentally verified our analysis. In addition, we improve the previous DPA on Keymill by halving the amount of data resources needed for the attack. We also applied our DAPA to Trivium, a hardware-oriented stream cipher from the eSTREAM portfolio and reduces the key guessing space from 80 to 14 bits.

We introduce a new signature scheme, SQISign, (for Short Quaternion and Isogeny Signature) from isogeny graphs of supersingular elliptic curves. The signature scheme is derived from a new one-round, high soundness, interactive identification protocol. Targeting the post-quantum NIST-1 level of security, our implementation results in signatures of $204$ bytes, secret keys of $16$ bytes and public keys of $64$ bytes. In particular, the signature and public key sizes combined are an order of magnitude smaller than all other post-quantum signature schemes. On a modern workstation, our implementation in C takes 0.6s for key generation, 2.5s for signing, and 50ms for verification.

While the soundness of the identification protocol follows from classical assumptions, the zero-knowledge property relies on the second main contribution of this paper. We introduce a new algorithm to find an isogeny path connecting two given supersingular elliptic curves of known endomorphism rings. A previous algorithm to solve this problem, due to Kohel, Lauter, Petit and Tignol, systematically reveals paths from the input curves to a `special' curve. This leakage would break the zero-knowledge property of the protocol. Our algorithm does not directly reveal such a path, and subject to a new computational assumption, we prove that the resulting identification protocol is zero-knowledge.