International Association
for Cryptologic Research

In this paper, we study the security of the Legendre PRF against quantum attackers, given classical queries only, and without quantum random-access memories. We give two algorithms that recover the key of a shifted Legendre symbol with unknown shift, with a complexity smaller than exhaustive search of the key. The first one is a quantum variant of the table-based collision algorithm. The second one uses Kuperberg's abelian hidden shift algorithm in an offline manner. We show that the latter, although asymptotically promising, is not currently the most efficient against practical parameters.

Development of signature schemes providing short signatures is a quite relevant non-trivial challenge for cryptographers. Since the late 1980’s many short signature schemes have been proposed. The most perspective schemes are multivariate schemes and schemes based on Weil pairing. Unfortunately, the cryptographic tools used in these schemes are still not supported by most cryptographic software that complicates their effortless use in practice.

In the current paper we investigate the opportunity of shortening the standard ElGamal-type signatures. We propose three methods of shortening signatures (for any ElGamal-type schemes such as ECDSA, GOST and SM2) and analyze how applying these methods affects the security. Applying all three methods to the GOST signature scheme with elliptic curve subgroup order $q$, $2^{255} < q < 2^{256}$, can reduce the signature size from $512$ to $320$ bits. The modified scheme provides sufficient security and acceptable (for non-interactive protocols) signing and verifying time.

Although there have been many successes in verifying proofs of non-interactive cryptographic primitives such as encryption and signatures, formal verification of interactive cryptographic protocols is still a nascent area. While in principle, it seems possible to extend general frameworks such as Easycrypt to encode proofs for more complex, interactive protocols, a big challenge is whether the human effort would be scalable enough for proof mechanization to eventually acquire mainstream usage among the cryptography community. We work towards closing this gap by introducing a simple framework, Interactive Probabilistic Dependency Logic (IPDL), for reasoning about a certain well-behaved subset of cryptographic protocols. A primary design goal of IPDL is for formal cryptographic proofs to resemble their on-paper counterparts. To this end, IPDL includes an equational logic to reason about approximate observational equivalence (i.e., computational indistinguishability) properties between protocols. IPDL adopts a channel-centric core logic, which decomposes the behavior of the protocol into the behaviors along each communication channel. IPDL supports straight-line programs with statically bounded loops. This design allows us to capture a broad class of protocols encountered in the cryptography literature, including multi-party, reactive, and/or inductively-defined protocols; meanwhile, the logic can track the runtime of the computational reduction in security proofs, thus ensuring computational soundness. We demonstrate the use of IPDL by a number of case studies, including a multi-use, secure message communication protocol, a multi-party coin toss with abort protocol, several oblivious transfer constructions, as well as the two-party GMW protocol for securely evaluating general circuits. We provide a mechanization of the IPDL proof system and our case studies in Coq, and our code is open sourced at https://github.com/ipdl/ipdl.

With an eye towards applications in cryptography, we consider the problem of evaluating boolean functions through affine-linear arithmetic functionals. We show that each subset of the discrete unit cube admits an exact covering by affine hyperplanes (over a sufficiently large prime field). We study the complexity class consisting of boolean functions whose on-sets and off-sets admit coverings by polynomially many hyperplanes. This extends and improves upon a framework of Ishai and Kushilevitz (FOCS '00). We also investigate a number of concrete examples.

We moreover study the concrete construction of compact coverings, and provide new geometric algorithms. Our logic synthesizer constructs affine coverings of cube subsets using a recursive backtracking procedure, and minimizes the total number of flats used; it may be of independent interest. This represents a new paradigm in boolean logic minimization. We relate this paradigm to classical logic synthesis.

Applying our paradigm, we present a general protocol for commitment-consistent secure two-party computation with an untrusted third party, generalizing a construction of Wagh, Gupta, and Chandran (PETS '19). Our generalization supports the secure evaluation of arbitrary boolean functionalities; we also add commitment-consistency and malicious security under one corruption. We report on a highly efficient implementation of a specialization of this general protocol to a certain natural boolean function.

In the past few years blockchains have been a major focus for security research, resulting in significant progress in the design, formalization, and analysis of blockchain protocols. However, the more general class of distributed ledgers, which includes not just blockchains but also prominent non-blockchain protocols, such as Corda and OmniLedger, cannot be covered by the state-of-the-art in the security literature yet. These distributed ledgers often break with traditional blockchain paradigms, such as block structures to store data, system-wide consensus, or global consistency.

In this paper, we close this gap by proposing the first framework for defining and analyzing the security of general distributed ledgers, with an ideal distributed ledger functionality, called $\mathcal{F}_\text{ledger}$, at the core of our contribution. This functionality covers not only classical blockchains but also non-blockchain distributed ledgers in a unified way.

To illustrate $\mathcal{F}_\text{ledger}$, we first show that the prominent ideal blockchain functionalities $\mathcal{G}_\text{ledger}$ and $\mathcal{G}_\text{PL}$ realize (suitable instantiations of) $\mathcal{F}_\text{ledger}$, which precisely captures their security properties. This immediately implies that their respective implementations, including Bitcoin, Ouroboros Genesis, and Ouroboros Crypsinous, realize $\mathcal{F}_\text{ledger}$ as well. Secondly, we demonstrate that $\mathcal{F}_\text{ledger}$ is capable of precisely modeling also non-blockchain distributed ledgers by performing the first formal security analysis of such a distributed ledger, namely the prominent Corda protocol. Due to the wide spread use of Corda in the industry, in particular the financial sector, this analysis is of independent interest.

These results also illustrate that $\mathcal{F}_\text{ledger}$ not just generalizes the modular treatment of blockchains to distributed ledgers, but moreover helps to unify existing results.

Alongside the development of cloud computing and Internet of Things(IoT), cloud-based RFID is receiving more attention nowadays. Cloud-based RFID system is specifically developed to providing real-time data that can be fed to the cloud for easy access and instant data interpretation. Security and privacy of constrained devices in these systems is a challenging issue for many applications. To deal with this problem, we propose \(\chi\)perbp, a lightweight authentication protocol based on \(\chi\)per component. \(\chi\)per is a hardware/software friendly component that can be implemented using bit-wise operations. To evaluate the performance efficiency of our proposed scheme, we implement the \(\chi\)perbp scheme on a FPGA module Xilinx Kintex-7 using the hardware description language VHDL. Our security and cost analysis of the proposed protocol shows that the proposed protocol provides desired security against various attacks, in a reasonable cost. Also, formal security evaluation using BAN logic and Scyther tool indicates its security correctness. Besides, we analyse the security of a related protocol which has been recently proposed by Fan \textit{et al.} It is a cloud-based lightweight mutual authentication protocol for RFID devices in an IoT system. Although they have claimed security against active and passive adversaries, however, our detailed security analysis in this paper demonstrates major drawbacks of this protocol. More precisely, the proposed attack disclose the tag's secrets efficiently. Given the tag's secrets, any other attack will be trivial.

Centrum Wiskunde & Informatica (CWI) has a vacancy in the Cryptology Group for a talented PhD student, on the subject of Post-Quantum Secure Cryptographic Protocols.

The successful candidate will be working with Lisa Kohl, within the NWO Gravitation project QSC.

Candidates are required to have a master’s degree in Computer Science, Mathematics or a related discipline, ideally with a specialization in Cryptology.

All applications should include a detailed resume, motivation letter, list of MSc courses and grades, copy of master’s thesis and list of publications (if applicable). Please send your application in a single PDF file (with master's thesis as separate attachement).

The application deadline is March 31st, 2021. Review of applications will start immediately until the position is filled.

Closing date for applications:

Contact: Lisa Kohl (l.m.kohl (at) cwi.nl)

Horizen Labs is a blockchain technology company that designs, develops and delivers powerful, scalable and reliable distributed ledger solutions for business. Our Core Engineering Team is based in Milan, Italy. It’s an innovative and collaborative group of technical developers who are dedicated to the design and development of world-class blockchain-based products.

We are now looking for a junior cryptographer, or applied cryptographer, to join our Cryptography Team and develop cutting-edge SNARK-based proof-composition models and software.

The Role

• Help the team, to develop practical applications using both advanced SNARK-based protocols and conventional cryptographic tools
• Keep up to date on emerging capabilities in the fast-growing Zero-Knowledge area and identify where and how new capabilities can be applied
• Identify and recommend technologies and cryptographic solutions to solve technical challenges
• Participate in standards setting, perform collaborative research into open source solutions and assist technical colleagues in their development work

Requirements

• MS/Ph.D. in Mathematics, Computer Science, Computer Programming, or Computer Engineering
• Core understanding of classical crypto primitives (symmetric and public key cryptography)
• Base principles of Elliptic Curve Cryptography, Zero-knowlegde proofs and SNARGs

• Foundations of blockchain technology, and experience developing in Rust and/or C++, is a plus.

Closing date for applications:

Contact: Maurizio Binello

More information: https://horizenlabs.io/

Funded 3-year (full-time) PhD in secure multi-party computation. The aims of the project include (but are not limited to):
1) Improving efficiency and cryptographic assumptions of multi-party computation protocols.
2) Studying new communication models for real-world applications, to obtain protocols with improved performance and security features.
3) Proposing new security definitions and realistic trusted assumptions to overcome current impossibility results.

Closing date for applications:

Contact: Michele Ciampi (michele.ciampi [at] ed.ac.uk)

More information: https://www.ed.ac.uk/informatics/postgraduate/fees/research-scholarships/research-grant-funding/phd-secure-multi-party-computation

The IT University of Copenhagen invites highly motivated individuals to apply for a Postdoc position starting in May 2021 or soon thereafter for a duration of 2 years. The position is in the context of the project “Enabling User-Accountable Mechanisms for Decision Systems”, which looks at ways to provide dispute resolution capabilities to decision systems (e.g. voting protocols) by combining cryptographic techniques for human senses with advanced cryptographic protocols. Candidates should apply here: https://candidate.hr-manager.net/ApplicationInit.aspx?cid=119&ProjectId=181269&DepartmentId=3439&MediaId=1282

Closing date for applications:

Contact: Rosario Giustolisi (rosg@itu.dk) or Carsten Schuermann (carsten@itu.dk)

More information: https://candidate.hr-manager.net/ApplicationInit.aspx?cid=119&ProjectId=181269&DepartmentId=3439&MediaId=1282

The position requires expertise and skills in:

• Architectures and design methods of digital circuits/embedded systems for both hardware and low-level software.
• Theory and practice in the security/safety of electronic circuits and on-board systems.

Circuit and embedded system expertise as well as skills in modeling and quantifying risks are essential for the position. The design a circuit with effective protections against attacks and validation methods should be mastered.
The position requires significant publications in leading journals and conferences. Initiating and participating to national, international and industrial research projects is expected. Higher education experience as well as fluency in written and oral English are required.
Other types of competencies that could serve for the position are listed below:

• Experience in developing embedded systems with hardware and / or software protections.
• Culture of cyber-physical threats and protection principles.
• In-depth knowledge of microprocessor architectures and associated software development tools.
• Methods and architectures of integrated circuits and embedded systems.
• Experimental data generation and analysis.
• Knowledge in modeling, signal processing and machine learning methods.

Detailed informations and submission can be found at:

https://institutminestelecom.recruitee.com/l/en/o/maitre-de-conferences-en-securite-et-surete-des-systemes-embarques-a-telecom-paris-cdi

Closing date for applications:

Contact: jean-luc.danger@telecom-paris.fr

More information: https://institutminestelecom.recruitee.com/l/en/o/maitre-de-conferences-en-securite-et-surete-des-systemes-embarques-a-telecom-paris-cdi