International Association
for Cryptologic Research

Auxiliary-input idealized models, such as the auxiliary-input random oracle model and the auxiliary-input random permutation model, play a critical role in assessing non-uniform security of symmetric-key and hash-function constructions. However, obtaining security bounds in these models are often much more challenging than in traditional idealized models.

The presampling technique, introduced by Unruh (CRYPTO' 07), generically reduces security proofs in the auxiliary-input models to a much simpler bit-fixing models. This technique has been further optimized by Coretti, Dodis, Guo, Steinberger (EUROCRYPT' 18), and generalized by Coretti, Dodis, Guo (CRYPTO' 18), resulting in powerful tools for proving non-uniform security bounds in various idealized models, including random oracle models (ROM), random permutation models (RPM), ideal cipher models (ICM) and generic group models (GGM). We study the possibility of unifying and leveraging the presampling technique to the quantum world. To this end,

* We show that such leveraging will resolve a major open problem in quantum computing, which is closely related with the famous Aaronson-Ambainis conjecture (ITCS' 11).

* Faced with this barrier, we give a new but equivalent bit-fixing model and a simple proof of presampling techniques for arbitrary oracle distribution and access in the classical setting, including AI-ROM and AI-RPM. Our security loss matches the security loss of the best known presampling technique by Coretti et al. (EUROCRYPT' 18) for both indistinguishability and unpredictability applications. Our new proof unifies previous results by Coretti et al. (EUROCRYPT' 18) and Coretti et al. (CRYPTO' 18).

* We leverage our new classical presampling techniques to a novel ``quantum bit-fixing version'' of presampling. The security loss of our quantum bit-fixing presampling also matches the optimal security loss of the classical presampling. Using our techniques, we give the first post-quantum non-uniform security bounds for salted Merkle-Damgard hash functions.

We introduce the notion of Deniable Fully Homomorphic Encryption and provide constructions based on the circular-secure Learning With Errors polynomial hardness assumption. Deniable fully homomorphic encryption offers a compelling upgrade of deniable public key encryption suitable for the motivating applications of deniability, such as prevention of vote-buying in electronic voting schemes where encrypted votes can be tallied without decryption, or storing encrypted data in the cloud, to be processed securely, in a deniable way. Our constructions enjoy deniability compactness, namely both the size of the public key and the size of the ciphertext of our schemes can be bounded by a fixed polynomial, independent of the level of deniability (or faking probability) achieved by the scheme. Additionally, our constructions support large message spaces and are well suited to an online-offline model of encryption, where the bulk of computation is independent of the message and may be performed in an offline pre-processing phase. This leads to a very efficient online phase, whose running time is independent of the faking probability, whereas the offline encryption run-time grows with the inverse of the faking probability.

In contrast, all prior constructions even in the context of deniable public key encryption without homomorphic properties, encoded large messages bit by bit, where the ciphertext for each bit grew inversely with the faking probability. Indeed, all previous constructions from polynomial hardness assumptions have both the public key and ciphertext size that grows with the inverse of the faking probability achieved by the scheme. This limitation dates back to the seminal work of Canetti, Dwork, Naor and Ostrovsky (CRYPTO 1997) which introduced the notion of deniable encryption, and has been inherited by all subsequent work (excepting one by Sahai and Waters (STOC 2013) which is based on indistinguishability obfuscation. Indeed Canetti et al. argued that this dependence ``seems inherent''. Our constructions imply deniable public key encryption with deniability compactness, showing that this dependence is not inherent. However, the running time of our encryption algorithm does depend on the inverse of the faking probability, thus falling short of achieving simultaneously negligible deniability and polynomial encryption time.

At the heart of our constructions is a new way to use bootstrapping to obliviously generate FHE ciphertexts so that it supports faking under coercion.

We initiate a study, when $F$ is a general APN function, of the Boolean function $\gamma_F$ related to the differential spectrum of $F$ (which is known to be bent if and only if $F$ is almost bent). We first list many open questions about it. We study its algebraic normal form and its bivariate representation. We characterize its linear structures and specify nonexistence cases; we show, for $n$ even, their relation with bent components $v\cdot F$, $v\neq 0_n$, of $F$. We pose three related open problems. We characterize further in terms of $\gamma_F$ the fact that a component function of $F$ is bent and study if the number of bent components can be optimal. We consider in particular two classes, one of which is that of APN power functions. We study more deeply the relation between the Walsh transform of $\gamma_F$ and the Walsh transform of $F$. By applying the Titsworth relation to the Walsh transform $W_{\gamma_F}$, we deduce a very simple new relation satisfied by $W_F^2$. From this latter relation, we deduce, for a sub-class of APN functions, a lower bound on the nonlinearity, that is significantly stronger than $nl(F)>0$ (the only general known bound). This sub-class of APN functions includes all known APN functions. The question (which is another open problem that we state) arises whether this sub-class equals that of all APN functions, but our bound provides at least a beginning of explanation why all known APN functions have non-weak nonlinearity. We finally show how the nonlinearities of $\gamma_F$ and $F$ are related by a simple formula; this leads to a last open problem.

The programming languages community, the cryptography community, and others rely on translating programs in high-level source languages (e.g., C) to logical constraint representations. Unfortunately, building compilers for this task is difficult and time consuming. In this work, we show that all of these communities can build upon a shared compiler infrastructure, because they all share a common abstraction: stateless, non-deterministic computations that we call existentially quantified circuits, or EQCs.

To make our approach concrete we create CirC, an infrastructure for building compilers to EQCs. CirC makes it easy to add support for new EQCs: we build support for two, one used by the PL community and one used by the cryptography community, in $\approx$2000 LOC. It’s also easy to extend CirC to support new source languages: we build a feature complete compiler for a cryptographic language in one week and $\approx$700 LOC, whereas the reference compiler for the same language took years to write, comprises $\approx$24000 LOC, and produces worse-performing output than our compiler. Finally, CirC enables novel applications that combine multiple EQCs. For example, we build the first pipeline that (1) automatically identifies bugs in programs, then (2) automatically constructs cryptographic proofs of the bugs’ existence.

Semi-regular sequences over $\mathbb{F}_2$ are sequences of homogeneous elements of the algebra $ B^{(n)}=\mathbb{F}_2[X_1,...,X_n]/(X_1^2,...,X_n^2) $, which have a given Hilbert series and can be thought of as having as few relations between them as possible. It is believed that most such systems are semi-regular and this property has important consequences for understanding the complexity of Grobner basis algorithms such as F4 and F5 for solving such systems. We investigate the case where the sequence has length two and give an almost complete description of the number of semi-regular sequences for each $n$.

The potential development of large-scale quantum computers is raising concerns among IT and security research professionals due to their ability to solve (elliptic curve) discrete logarithm and integer factorization problems in polynomial time. All currently used, public-key cryptography algorithms would be deemed insecure in a post-quantum setting. In response, the United States National Institute of Standards and Technology has initiated a process to standardize quantum-resistant cryptographic algorithms, focusing primarily on their security guarantees. Additionally, the Internet Engineering Task Force has published two quantum-secure signature schemes and has been looking into adding quantum-resistant algorithms in protocols. In this work, we investigate two post-quantum, hash-based signature schemes published by the Internet Engineering Task Force and submitted to the National Institute of Standards and Technology for use in secure boot. We evaluate various parameter sets for the use-cases in question and we prove that post-quantum signatures would not have material impact on image signing. We also study the hierarchical design of these signatures in different scenarios of hardware secure boot.

We propose HERMES, a scalable, secure, and privacy-enhancing system, which allows users to share and access vehicles. HERMES outsources the vehicle access token generation to a set of untrusted servers, utilizing several cryptographic primitives with secure multi-party computation efficiently. It conceals the vehicle secret keys and transaction details from the servers such as vehicle booking details, access token information, and user-vehicle identities. It also provides user accountability in case of disputes. We prove that HERMES meets its security and privacy requirements. Moreover, we demonstrate that HERMES scales for a large number of users and vehicles, making it practical for real-world deployments. To achieve high-performance computations, we evaluate HERMES over two different multiparty computation protocols for Boolean and arithmetic circuits. We provide a detailed comparison of their performance, together with other state-of-the-art access provision protocols. Through a proof-of-concept implementation, our performance analysis demonstrates that HERMES requires only approx 61ms for a single-vehicle access provision. At the same time, it handles 546 and 84 access token generations per second from a single-vehicle owner and large branches of rental companies with over a thousand vehicles, respectively.

Bit permutations are efficient linear functions often used for lightweight cipher designs. However, they have low diffusion effects, compared to word-oriented binary and MDS matrices. Thus, the security of bit permutation-based ciphers is significantly affected by differential and linear branch numbers (DBN and LBN) of nonlinear functions. In this paper, we introduce a widely applicable method for constructing S-boxes with high DBN and LBN. Our method exploits constructions of S-boxes from smaller S-boxes and it derives/proves the required conditions for smaller S-boxes so that the DBN and LBN of the constructed S-boxes are at least 3. These conditions enable us to significantly reduce the search space required to create such S-boxes. In order to make cryptographically good and efficient S-boxes, we propose a unbalanced-Bridge structure that accepts one 3-bit and two 5-bit S-boxes, and produces 8-bit S-boxes. Using the proposed structure, we develop a variety of new lightweight S-boxes that provide not only both DBN and LBN of at least 3 but also efficient bitsliced implementations including at most 11 nonlinear bitwise operations. The new S-boxes are the first that exhibit these characteristics. Moreover, we propose a block cipher PIPO based on one of the new S-boxes, which supports a 64-bit plaintext and a 128 or 256-bit key. Our implementations demonstrate that PIPO outperforms existing block ciphers (for the same block and key lengths) in both side-channel protected and unprotected environments, on an 8-bit AVR. The security of PIPO has been scrutinized with regards to state-of-the-art cryptanalysis.

Recently, Li and Micciancio (ePrint 2020/1533) have proposed a passive attack on the CKKS approximate homomorphic encryption (HE) scheme, which allows an adversary to query decryption on valid ciphertexts. In this paper, we discuss for which applications such attack is applicable, and introduce an extension of the HEaaN library. In addition, we investigate the mitigation strategies of other HE libraries that support the CKKS scheme including HElib, PALISADE, Lattigo and SEAL.

State machine replication protocols have reached a crucial juncture in their widespread deployment. Tokenised state machine replication protocols, which utilise an internal token for rewarding player participation, have brought about major advances in the areas of finance, internet of things, supply chain, legal systems, and data storage, to name but a few. However, the viability of these protocols as replacements for their centralised alternatives requires guarantees of player actions at all times which at present do not exist. Current standards for player characterisation in tokenised state machine replication protocols allow for honest players who will always follow the protocol, regardless of possible token increases for deviating. Given the ever-increasing market capitalisation of these tokenised protocols, honesty is becoming more expensive and more unrealistic. As such, this out-dated player characterisation must be removed to provide true guarantees of safety and liveness in a major stride towards universal trust in state machine replication protocols and a new scale of adoption. As all current state machine replication protocols are built on these legacy standards, it is imperative that a new player model is identified and utilised to reflect the true nature of players in tokenised protocols, now and into the future. To this effect, we propose the ByRa player model for state machine replication protocols. In the ByRa model, players either attempt to maximise their tokenised rewards, or behave adversarially. This merges the fields of game theory and distributed systems, an intersection in which tokenised state machine replication protocols exist, but on which little formalisation has been carried out. In the ByRa model, we identify the properties of strong incentive compatibility in expectation and fairness that all protocols must satisfy in order to achieve state machine replication. We then provide FAIRSICAL, a protocol which provably satisfies these properties, and by doing so, achieves state machine replication in the ByRa model.

Image is a visual representation of a certain fact and can be used as proof of events. As the utilization of the image increases, it is required to prove its authenticity with the protection of its sensitive personal information. In this paper, we propose a new efficient verifiable image redacting scheme based on zk-SNARKs, a commitment, and a digital signature scheme. We adopt a commit-and-prove SNARK scheme which takes commitments as inputs, in which the authenticity can be quickly verified outside the circuit. We also specify relations between the original and redacted images to guarantee the redacting correctness. Our experimental results show that the proposed scheme is superior to the existing works in terms of the key size and proving time without sacrificing the other parameters. The security of the proposed scheme is proven formally.

This paper presents an IND-CCA2 attack against the 1st- and 2nd-round versions of NTS-KEM, i.e., the versions before the update in December 2019. Our attack works against the 1st- and 2nd-round specifications, with a number of decapsulation queries upper-bounded by n − k and an advantage lower-bounded by roughly 0.5(n − k)t/n^2 , where n, k, and t stand for the code length, code dimension, and the designed decoding capacity, for all the three parameter sets of NTS-KEM. We found that the non-reference implementations are also vulnerable to our attack, even though there are bugs. There are also bugs in the reference implementations, but in a way invulnerable to our attack.

Secure multi-party computation has seen significant performance advances and increasing use in recent years. Techniques based on secret sharing offer attractive performance and are a popular choice for privacy-preserving machine learning applications. Traditional techniques operate over a field, while designing equivalent techniques for a ring can boost performance. In this work we develop a suit of multi-party techniques for a ring in the honest majority setting starting from elementary operations to more complex with the goal of supporting general-purpose computation. We demonstrate through empirical evaluation that our techniques can be several times faster than their field-based equivalents and up to two orders of magnitudes faster for certain operations such as matrix multiplication. We also evaluate our techniques on machine learning applications and show that the resulting performance is on par with that of most recent custom protocols for these applications.

Secure computation is a promising privacy enhancing technology, but it is often not scalable enough for data intensive applications. On the other hand, the use of sketches has gained popularity in data mining, because sketches often give rise to highly efficient and scalable sub-linear algorithms. It is natural to ask: what if we put secure computation and sketches together? We investigated the question and the findings are interesting: we can get security, we can get scalability, and somewhat unexpectedly, we can also get differential privacy -- for free. Our study started from building a secure computation protocol based on the Flajolet-Martin (FM) sketches, for solving the Private Distributed Cardinality Estimation (PDCE) problem, which is a fundamental problem with applications ranging from crowd tracking to network monitoring. The state of art protocol for PDCE (Fenske et al. CCS'17) is computationally expensive and not scalable enough to cope with big data applications, which prompted us to design a better protocol. Our further analysis revealed that if the cardinality to be estimated is large enough, our protocol can achieve $(\epsilon,\delta)$-differential privacy automatically, without requiring any additional manipulation of the output. The result signifies a new approach for achieving differential privacy that departs from the mainstream approach (i.e. adding noise to the result). Free differential privacy can be achieved because of two reasons: secure computation minimizes information leakage, and the intrinsic estimation variance of the FM sketch makes the output of our protocol uncertain. We further show that the result is not just theoretical: the minimal cardinality for differential privacy to hold is only $10^2-10^4$ for typical parameters.

Sigfox is a popular communication and security protocol which allows setting up low-power wide-area networks for the Internet of Things. Currently, Sigfox networks operate in 72 countries, and cover 1.3 billion people. In this paper, we make an extensive analysis of the security mechanisms used to protect the radio interface. We describe news attacks against data authenticity, which is the only mandatory security property in Sigfox. Namely we describe how to replay frames, and how to compute forgeries. In addition, we highlight a flaw in the (optional) data encryption procedure. Our attacks do not exploit implementation or hardware bugs, nor do they imply a physical access to any equipment (e.g., legitimate end-device). They rely only on the peculiarities of the Sigfox security protocol. Our analysis is supported by practical experiments made in interaction with the Sigfox back-end network. These experiments validate our findings. Finally, we present efficient counter-measures which are likely straightforward to implement.

Event date: 20 May to 22 May 2021
Submission deadline: 3 March 2021

Event date: to
Submission deadline: 8 March 2021

[Number of Openings]: 1 [Area of Specialization]: Theoretical Computer Science, Theory and Practice of Cybersecurity, Theory of Cryptography, Theory of Algorithms, Theory of Computational Complexity, Programming Theory, Software Verification Theory, Blockchain Technology, Network Security, etc. [Job Description]: Research and education at Department of Mathematical and Computing Science. Assigned tasks on the management of the department. [Qualifications]: - Applicants must have a PhD degree or be expected to obtain the degree by the start of the employment in the specialized area given above or related areas. - Applicants must have ability to be in charge of exercises of undergraduate courses in computer science. - Applicants must be highly motivated on research and education. [Location]: Ookayama Campus (Nearest station: Ookayama Station (Tokyu Line)) [Term]: Fixed-term appointments will be for up to 5 years. Reappointment may be possible for one additional term of up to 5 years. The total term is limited to a maximum of 10 years from the original date of employment. [Proposed Start Date]: April 1st, 2021, or the earliest possible date thereafter [Closing Date for Application]: Applications must be received by January 17th, 2021 [Selection Process]: Selection will be based on a comprehensive review of applications and interviews. Interviews will be done remotely. Selected applicants may be asked to have interviews and/or give presentations and lectures. [How to Submit an Application]: Combine all of the required documents into a single PDF file, and send it via JREC-IN Portal Web application system. (https://jrecin.jst.go.jp/seek/SeekJorDetail?id=D120120992&ln_jor=1)

Closing date for applications:

Contact: Keisuke Tanaka, Professor, Chair of Department of Mathematical and Computing Science, School of Computing (Email: keisuke@is.titech.ac.jp)

More information: https://jrecin.jst.go.jp/seek/SeekJorDetail?id=D120120992&ln_jor=1

[Number of Openings]: 1 [Area of Specialization]: Theoretical Computer Science, Theory and Practice of Cybersecurity, Theory of Computational Complexity, Theory of Algorithms, Theory of Cryptography, Programming Theory, Software Verification Theory, Blockchain Technology, Network Security, etc. [Job Description]: - Designing and conducting graduate and undergraduate courses related to mathematical and computing science. - Managing a laboratory (research group) and supervising graduate and undergraduate students. - Research activities leading international research communities of the specialized area given above or related areas. - Tasks related to the management of the department and the institute. [Qualifications]: Applicants must have a PhD degree in the specialized area given above or related areas. [Location]: Ookayama Campus (Nearest station: Ookayama Station (Tokyu Line)) [Term]: Permanent Position (The Institute has mandatory retirement, requiring employees to retire at age 65.) [Proposed Start Date]: April 1st, 2021, or the earliest possible date thereafter [Closing Date for Application]: Applications must be received by January 17th, 2021 [Selection Process]: Selection will be based on a comprehensive review of applications and interviews. Interviews will be done remotely. Selected applicants may be asked to have interviews and to give presentations and lectures. [How to Submit an Application]: Combine all of the required documents into a single PDF file, and send it via JREC-IN Portal Web application system. (https://jrecin.jst.go.jp/seek/SeekJorDetail?id=D120120988&ln_jor=1)

Closing date for applications:

Contact: Keisuke Tanaka, Professor, Chair of Department of Mathematical and Computing Science, School of Computing (Email: keisuke@is.titech.ac.jp)

More information: https://jrecin.jst.go.jp/seek/SeekJorDetail?id=D120120988&ln_jor=1

ABOUT POLE LEONARD DE VINCI : The Leonard de Vinci Pole is made up of three higher education institutions offering recognized degree programs that cover complementary academic fields, particularly in the digital sector: a business school, EMLV (Leonard de Vinci Business School); an engineering school, ESILV (Leonard de Vinci Engineering School), and a digital/multimedia school, IIM (Institute of Internet and Multimedia). The schools share a common research laboratory: De Vinci Research Center (DVRC). The "De Vinci Research Center - DVRC" includes all the researchers from the two schools of the Leonard De Vinci Association: the School of Management (EMLV) and the School of Engineering (ESILV). The research, focused on innovation and digital technology, is structured within four research groups and a partnership research unit. CONTEXT: Through the Pôle Léonard de Vinci, DVRC is a member of the “Moneytrack” project on blockchain scalability, together with INRIA and Truffle Capital. Topic: The ambition of the Lightning Network is to provide a second layer to the Bitcoin network to enable transactions confirmed instantly, securely and anonymously with a world scale capacity using a decentralized protocol. However, some of the current propositions and implementations present some difficulties in anonymity, scaling and decentralization. The Ant Routing algorithm for the Lightning Network solves several problems such as channel information update and centralization by beacon nodes. It requires no landmark, no knowledge on the topology. The decentralization of the algorithm is achieved by making every node play exactly the same role in the routing process and using only knowledge about its neighbors. Routing tables are not required and transactions are completed instantaneously and anonymously. The algorithm is inspired by the behavior of ants. Although each ant individually seems to follow a random motion, their collective behavior finds efficiently the shortest path from their nest to a food source. This is achieved through a “stygmergic” communication of the ants with their environment through pheromones. See https://arxiv.org/abs/2002.0

Closing date for applications:

Contact: APPLICATION PROCEDURE: Please provide your CV and a cover letter describing your research activities. Qualified candidates need to send their application package by email to recrutement@devinci.fr. Contacts: - Cyril Grunspan (cyril.grunspan@devinci.fr) - Jean Rohmer (jean.rohmer@devinci.fr)

More information: https://www.devinci.fr/