IACR News
Updates on the COVID-19 situation are on the
Announcement channel.
Here you can see all recent updates to the IACR webpage. These updates are also available:
17 October 2019
The 2019 Election for Board positions is now open.
You may vote as often as you wish now through November 15th 23:00 UTC using the Helios cryptographically verifiable election
system, but only your last vote will be counted.
Abdur Rehman Razaz, Khawir Mahmoodx , Muhammad Faisal Amjad, Haider Abbas, Mehreen Afzal
Lightweight block ciphers are primarily designed for resource constrained devices. However, due to service requirements of large-scale IoT networks and systems, the need for efficient software implementations can not be ruled out. A number of studies have compared software implementations of different lightweight block ciphers on a specific platform but to the best of our knowledge, this is the first attempt to benchmark various software implementations of a single lightweight block cipher across different programming languages and platforms in the cloud architecture. In this paper, we defined six lookup-table based software implementations for lightweight block ciphers with their characteristics ranging from memory to throughput optimized variants. We carried out a thorough analysis of the two costs associated with each implementation (memory and operations) and discussed possible trade-offs in detail. We coded all six types of implementations for three key settings (64, 80, 128 bits) of LED (a lightweight block cipher) in four programming languages (Java, C#, C++, Python). We highlighted the impact of choice relating to implementation type, programming language, and platform by benchmarking the seventy-two implementations for throughput and software efficiency on 32 & 64-bit platforms for two major operating systems (Windows & Linux) on Amazon Web Services Cloud. The results showed that these choices can affect the efficiency of a cryptographic primitive by a factor as high as 400.
Ashutosh Dhar Dwivedi
The internet has the main advantage of transparent and sharing, but on the other hand, it has a disadvantage that digital contents are not protected. Due to the online environment, it is not easy to achieve a well protected Digital Rights Management System. Any digital content that is freely allowed to spread online have zero value. The content provider only gets a one-time profit when they upload their work to a platform and transfer the right of the production to the platform. Now the platform is assumed to hold the right. But due to the online availability of content, anyone can download it and can make various copies. After this, the value of the digital content becomes zero, because the value can only be determined by the difficulty of access to the content. There is no way to track the leakage or copyright to the spread of digital material. Anyone is allowed to use it for their purpose. In this paper, we propose a distributed media transaction framework for digital rights management(DRM) scheme based on digital watermarking and scalable blockchain network model. The first generation of blockchain technology is suffering from high latency, low throughput, high transaction cost, high energy and high computational power consumption as well as centralization due to mining pools. In this paper, we mainly focus on removing or improving all these issues from the original blockchain system to make it suitable for our digital rights management model. Our model allows only authorized user to use online contents and provide original multimedia contents. The DRM also take care of digital contents and keep track records of required content modification, copyright transfer or other transaction trails related to multimedia data. We use digital watermarking to reclaim the uniqueness and copyright ownership of the off-line content once it is leaked.
Wei-Zhu Yeoh, Je Sen Teh, Jiageng Chen
Differential cryptanalysis of block ciphers requires the identification of differential characteristics with high probability. For block ciphers that have a large block size and a large number of rounds, identifying these differential trails is a computationally intensive task. Matsui first proposed a branch-and-bound algorithm to search for differential trails in 1994. There have been numerous improvements made to the branch-and-bound algorithm since then, such as improving its efficiency by bounding the number of active s-boxes, incorporating a meet-in-the-middle approach, and adapting it to different block cipher architectures like ARX. Although mixed-integer linear programming (MILP) technique has been widely used recently to evaluate the differential resistance of block ciphers, MILP is still an inefficient technique for clustering differential trails (also known as the differential effect). The branch-and-bound method is still a tool better suited for the task of trail clustering. However, it still requires enhancements before being feasible for block ciphers with large block sizes, especially for a large number of rounds. Motivated by the need for a more efficient branch-and-bound algorithm to search for block cipher differential clusters, we propose a GPU-accelerated branch-and-bound approach. The proposed GPU-accelerated algorithm substantially increases the performance of the differential cluster search. We were able to derive a branch enumeration and evaluation kernel that is 5.95 times faster than its CPU counterpart. Then to showcase the practicality of the proposed approach, it is applied on TRIFLE-BC, a 128-bit block cipher. By utilizing the proposed GPU kernel together the incorporation of a meet-in-the-middle approach, we were able to improve the performance of the algorithm by approximately 60 times the original recursive algorithm based on a 20-round TRIFLE-BC. Also, differential clusters with sizes of approximately 2 million for 43 rounds were constructed, leading to slight improvements to the overall differential probabilities. This result depicts the practicality of the proposed GPU framework in constructing clusters consisting of millions of differential trails, which could be used to improve cryptanalytic findings against other block ciphers in the future.
Sanaz Taheri Boshrooyeh, Alptekin Küpçü, Öznur Özkasap
In invitation-based systems, a new user can register upon having a certain number of invitations (i.e., t) issued by the existing members. The newcomer hands his invitations to the system administrator to be authenticated, who verifies that the invitations are issued by legitimate members. This causes the administrator being aware of who is invited by whom. However, the inviter-invitee relationship is privacy-sensitive information whose exposure can lead to an inference attack where the invitee's profile (e.g., political view or location) can be extracted through the profiles of his inviters. Addressing this problem, we propose Anonyma, an anonymous invitation-based system where a corrupted administrator who may even collude with a subset of existing members is not able to figure out who is invited by whom. We formally define and prove the inviter anonymity and unforgeability of invitations against a malicious adversary. Our design only incurs constant cost to authenticate a new registration. This is significantly better than the similar works where the generation of invitations and verification of new registration cause an overhead linear in the total number of existing members. Besides, Anonyma is efficiently scalable in the sense that once a user joins the system, the administrator can instantly, and without re-keying the existing members, issue credential for the newcomer to be able to act as an inviter. We additionally design AnonymaX, an anonymous cross-network invitation-based system where the invitations issued by the members of one system can be used for registering to another system.
Farokhlagha Moazami , Masoumeh Safkhani
In systems equipped with radio frequency identification (RFID) technology, several security concerns may arise when the ownership of a tag should be transferred from one owner to another, e.g., the confidentiality of information related to the old owner or the new owner. Therefore, this transfer is usually done via a security protocol called the ownership transfer protocol. If the ownership of several things together transmitted from one owner to another during a single session, the protocol is referred to as the group ownership transfer protocol.
Lee et al. recently proposed a new group ownership transfer protocol by using cloud server, as a trusted third-party, and based on homomorphic encryption and quadratic residue. In this paper, at first, we explain some important security attacks against this recently proposed RFID group ownership transfer protocol. The success probability of any attack that is presented in this paper is $1$ and the complexity is just a run of the protocol. Zhu et al. also in order to provide simultaneous transfer of group of tags in multi-owner environment proposed a lightweight anonymous group ownership transfer protocol. In this paper, we show that it suffers from desynchronization attack. The success probability of this attack is "1" and its complexity is only five runs of group ownership transfer protocol.
In addition, to overcome the Lee \textit{et al.} protocol security weaknesses, we present a new group ownership transfer protocol which is resistant against all known active and passive attacks, including the attacks presented in this paper. The provided security proof through informal methods and also formal methods such as Barrows-Abadi-Needham logic and Scyther tool show the proposed protocol's security correctness.
Lee et al. recently proposed a new group ownership transfer protocol by using cloud server, as a trusted third-party, and based on homomorphic encryption and quadratic residue. In this paper, at first, we explain some important security attacks against this recently proposed RFID group ownership transfer protocol. The success probability of any attack that is presented in this paper is $1$ and the complexity is just a run of the protocol. Zhu et al. also in order to provide simultaneous transfer of group of tags in multi-owner environment proposed a lightweight anonymous group ownership transfer protocol. In this paper, we show that it suffers from desynchronization attack. The success probability of this attack is "1" and its complexity is only five runs of group ownership transfer protocol.
In addition, to overcome the Lee \textit{et al.} protocol security weaknesses, we present a new group ownership transfer protocol which is resistant against all known active and passive attacks, including the attacks presented in this paper. The provided security proof through informal methods and also formal methods such as Barrows-Abadi-Needham logic and Scyther tool show the proposed protocol's security correctness.
16 October 2019
Fatih Balli, Subhadeep Banik
Recently the ForkAES construction was proposed by Andreeva et al. for efficiently performing authenticated encryption of very short messages on next generation IoT devices. The ForkAES tweakable block cipher uses around one and a half AES encryption calls to produce a pair of ciphertexts for any given plaintext. However the only downside of the construction is that it needs to store an extra state of 128 bits in addition with the storage elements required to perform AES encryption. Thus a hardware implementation of ForkAES would require additional circuit area to accommodate the extra state.
In this paper, we first show that it is possible to implement ForkAES without any additional storage elements other than those required to implement AES, if the AES circuit can additionally perform decryption. Such an implementation naturally requires more clock cycles to perform ForkAES operations. We extend the recently proposed Atomic AES v2.0 architecture to realize ForkAES and compare the area-latency trade-offs incurred with and without an additional storage. The area of the most compact ForkAES design takes about 1.2 times that of AES.
In the second part of the paper we look at another important parameter of lightweight efficiency, i.e. energy. It is well known that round based constructions for AES are the most energy efficient ones. We extend the so-called S3K2 construction of Banik et al. (IEEE HOST 17) to realize ForkAES in an energy-preserving manner, and compare the effects of some design choices. The energy consumption of our best ForkAES design takes about 2 times that of AES. From lightweight design perspective, our results hence demonstrate that although ForkAES lives up to its promise (of being roughly 1.5 times that of AES) in terms of its area, the same does not hold for its energy consumption.
In this paper, we first show that it is possible to implement ForkAES without any additional storage elements other than those required to implement AES, if the AES circuit can additionally perform decryption. Such an implementation naturally requires more clock cycles to perform ForkAES operations. We extend the recently proposed Atomic AES v2.0 architecture to realize ForkAES and compare the area-latency trade-offs incurred with and without an additional storage. The area of the most compact ForkAES design takes about 1.2 times that of AES.
In the second part of the paper we look at another important parameter of lightweight efficiency, i.e. energy. It is well known that round based constructions for AES are the most energy efficient ones. We extend the so-called S3K2 construction of Banik et al. (IEEE HOST 17) to realize ForkAES in an energy-preserving manner, and compare the effects of some design choices. The energy consumption of our best ForkAES design takes about 2 times that of AES. From lightweight design perspective, our results hence demonstrate that although ForkAES lives up to its promise (of being roughly 1.5 times that of AES) in terms of its area, the same does not hold for its energy consumption.
Subhadeep Banik, Fatih Balli, Francesco Regazzoni, Serge Vaudenay
In CHES 2017, Jean et al. presented a paper on ``Bit-Sliding'' in which the authors proposed lightweight constructions for SPN based block ciphers like AES, PRESENT, and SKINNY. The main idea behind these constructions was to reduce the length of the datapath to 1 bit and to reformulate the linear layer for these ciphers so that they require fewer scan flip-flops (which have built-in multiplexer functionality and so larger in area as compared to a simple flip-flop). In this paper, we develop their idea even further in few separate directions.
First, we prove that given an arbitrary linear transformation, it is always possible to construct the linear layer using merely 2 scan flip-flops. This points to an optimistic venue to follow to gain further GE reductions, yet the straightforward application of the techniques in our proof to PRESENT and GIFT leads to inefficient implementations of the linear layer, as reducing ourselves to 2 scan flip-flops setting requires thousands of clock cycles and leads to very high latency.
Equipped with the well-established formalism on permutation groups, we explore whether we can reduce the number of clock cycles to a practical level, i.e. few hundreds, by adding few more pairs of scan flip flops. For PRESENT, we show that 4 (resp. 8, 12) scan flip-flops are sufficient to complete the permutation layer in 384 (resp. 256, 128) clock cycles. For GIFT, we show that 4 (resp. 8, 10) scan flip flops correspond to 320 (resp. 192, 128) clock cycles. Hence our results give a good balance between throughput and circuit area, that is, we are able to construct circuits with reasonable throughput (by increasing the latency to threefold at most) and smaller than the state-of-the-art implementations of PRESENT and GIFT.
Finally, in order to provide the best of the two worlds (i.e. circuit area and latency), we push our scan flip-flop choices even further to completely eliminate the latency incurred by the permutation layer, without compromising our stringent GE budget. We show that not only 12 scan flip flops are sufficient to execute PRESENT permutation in 64 clock cycles, but also the same scan flip flops can be used readily in a combined encryption decryption circuit. Our final design of PRESENT and GIFT beat the record of Jean et al. and Banik et al. in both latency and in circuit-size metric. We believe that the techniques presented in our work can also be used at choosing bit-sliding-friendly linear layer permutations for the future SPN-based designs.
First, we prove that given an arbitrary linear transformation, it is always possible to construct the linear layer using merely 2 scan flip-flops. This points to an optimistic venue to follow to gain further GE reductions, yet the straightforward application of the techniques in our proof to PRESENT and GIFT leads to inefficient implementations of the linear layer, as reducing ourselves to 2 scan flip-flops setting requires thousands of clock cycles and leads to very high latency.
Equipped with the well-established formalism on permutation groups, we explore whether we can reduce the number of clock cycles to a practical level, i.e. few hundreds, by adding few more pairs of scan flip flops. For PRESENT, we show that 4 (resp. 8, 12) scan flip-flops are sufficient to complete the permutation layer in 384 (resp. 256, 128) clock cycles. For GIFT, we show that 4 (resp. 8, 10) scan flip flops correspond to 320 (resp. 192, 128) clock cycles. Hence our results give a good balance between throughput and circuit area, that is, we are able to construct circuits with reasonable throughput (by increasing the latency to threefold at most) and smaller than the state-of-the-art implementations of PRESENT and GIFT.
Finally, in order to provide the best of the two worlds (i.e. circuit area and latency), we push our scan flip-flop choices even further to completely eliminate the latency incurred by the permutation layer, without compromising our stringent GE budget. We show that not only 12 scan flip flops are sufficient to execute PRESENT permutation in 64 clock cycles, but also the same scan flip flops can be used readily in a combined encryption decryption circuit. Our final design of PRESENT and GIFT beat the record of Jean et al. and Banik et al. in both latency and in circuit-size metric. We believe that the techniques presented in our work can also be used at choosing bit-sliding-friendly linear layer permutations for the future SPN-based designs.
Rio LaVigne, Chen-Da Liu-Zhang, Ueli Maurer, Tal Moran, Marta Mularczyk, Daniel Tschudi
Topology-Hiding Computation (THC) allows a set of parties to securely compute a function over an incomplete network without revealing information on the network topology. Since its introduction in TCC'15 by Moran et al., the research on THC has focused on reducing the communication complexity, allowing larger graph classes, and tolerating stronger corruption types.
All of these results consider a fully synchronous model with a known upper bound on the maximal delay of all communication channels. Unfortunately, in any realistic setting this bound has to be extremely large, which makes all fully synchronous protocols inefficient. In the literature on multi-party computation, this is solved by considering the fully asynchronous model. However, THC is unachievable in this model (and even hard to define), leaving even the definition of a meaningful model as an open problem.
The contributions of this paper are threefold. First, we introduce a meaningful model of unknown and random communication delays for which THC is both definable and achievable. The probability distributions of the delays can be arbitrary for each channel, but one needs to make the (necessary) assumption that the delays are independent. The existing fully-synchronous THC protocols do not work in this setting and would, in particular, leak information about the topology. Second, in the model with trusted stateless hardware boxes introduced at Eurocrypt'18 by Ball et al., we present a THC protocol that works for any graph class. Third, we explore what is achievable in the standard model without trusted hardware and present a THC protocol for specific graph types (cycles and trees) secure under the DDH assumption. The speed of all protocols scales with the actual (unknown) delay times, in contrast to all previously known THC protocols whose speed is determined by the assumed upper bound on the network delay.
All of these results consider a fully synchronous model with a known upper bound on the maximal delay of all communication channels. Unfortunately, in any realistic setting this bound has to be extremely large, which makes all fully synchronous protocols inefficient. In the literature on multi-party computation, this is solved by considering the fully asynchronous model. However, THC is unachievable in this model (and even hard to define), leaving even the definition of a meaningful model as an open problem.
The contributions of this paper are threefold. First, we introduce a meaningful model of unknown and random communication delays for which THC is both definable and achievable. The probability distributions of the delays can be arbitrary for each channel, but one needs to make the (necessary) assumption that the delays are independent. The existing fully-synchronous THC protocols do not work in this setting and would, in particular, leak information about the topology. Second, in the model with trusted stateless hardware boxes introduced at Eurocrypt'18 by Ball et al., we present a THC protocol that works for any graph class. Third, we explore what is achievable in the standard model without trusted hardware and present a THC protocol for specific graph types (cycles and trees) secure under the DDH assumption. The speed of all protocols scales with the actual (unknown) delay times, in contrast to all previously known THC protocols whose speed is determined by the assumed upper bound on the network delay.
Zahra Jafargholi, Sabine Oechsner
A garbling scheme enables one to garble a circuit C and an input x in a way that C(x) can be evaluated, but nothing else is revealed. Since the first construction by Yao, there have been tremendous practical efficiency improvements for selectively secure garbling schemes, where the adversary is forced to choose both input and circuit to be garbled at the same time. However, in the more realistic setting of adaptive security --where an adversary can choose the input adaptively based on the garbled circuit-- not much is known about practical efficiency improvements.
In this work, we initiate the study of practical garbling schemes that are both more efficient than Yao's construction and adaptively secure. We provide insights into characteristics of these schemes and highlight the limitations of current techniques for proving adaptive security in this regime. Furthermore, we present an adaptively secure garbling scheme that garbles XOR gates with 2 and AND gates with 3 ciphertexts per gate, thus providing the first practical garbling scheme with adaptive security based on PRFs whose garbled circuit size is smaller than that of Yao's construction.
In this work, we initiate the study of practical garbling schemes that are both more efficient than Yao's construction and adaptively secure. We provide insights into characteristics of these schemes and highlight the limitations of current techniques for proving adaptive security in this regime. Furthermore, we present an adaptively secure garbling scheme that garbles XOR gates with 2 and AND gates with 3 ciphertexts per gate, thus providing the first practical garbling scheme with adaptive security based on PRFs whose garbled circuit size is smaller than that of Yao's construction.
Hiroshi Onuki, Tsuyoshi Takagi
CSIDH is an isogeny-based key exchange, which is a candidate for post quantum cryptography. It uses the action of an ideal class group on Fp-isomorphic classes of supersingular elliptic curves. In CSIDH, the ideal classes are represented by vectors with integer coefficients. The number of ideal classes represented by these vectors de- termines the security level of CSIDH. Therefore, it is important to investigate the correspondence between the vectors and the ideal classes. Heuristics show that integer vectors in a certain range represent almost uniformly all of the ideal classes. However, the precise correspondence between the integer vectors and the ideal classes is still unclear. In this paper, we investigate the correspondence between the ideal classes and the integer vectors and show that the vector (1, . . . , 1) corresponds to an ideal class of order 3. Consequently, the integer vectors in CSIDH have collisions related to this ideal class. Here, we use the word collision in the sense of distinct vectors belonging to the same ideal class, i.e., distinct secret keys that correspond to the same public key in CSIDH. We further propose a new ideal representation in CSIDH that does not include these collisions and give formulae for efficiently computing the action of the new representation.
Xenia Bogomolec, John Gregory Underhill, Stiepan Aurélien Kovac
We introduce an independent research project on symmetric cryptography with a focus on foreseeable industrial needs and higher post-quantum security compared to currently used symmetric algorithms. It was initiated by the independent IT-Security experts Kovac and Underhill. The result is the new symmetric cryptographic algorithm eAES, which is intended to be a stronger brother of the widely used Advanced Encryption Standard, the standardized version of the Rijndael algorithm.
In this analysis we show, that eAES offers an enhanced complexity by a factor ≥ 2^126 regarding the quantum cryptanalysis Grovers search algorithm compared to AES for 256 bit keys. Furthermore we outline the basic facts and open questions regarding quantum algebraic attacks on eAES.
Borja Gómez
This paper introduces a cryptographic commitment using multiple platform groups where the attacker must solve multiple instances of the Discrete Logarithm Problem to break the scheme. The goal is that Alice and Bob establish a secret communication after verifying a finite set of values that have been computed using multiple trapdoor-permutation functions. Moreover, applicable cryptanalytic techniques and procedures that entirely define this scheme are discussed
Jing Tian; Zhe Liu; Jun Lin; Zhongfeng Wang; Binjing Li
As one of the post-quantum protocol candidates, the supersingular isogeny key encapsulation (SIKE) protocol delivers promising public and secret key sizes over other candidates. Nevertheless, the considerable computations form the bottleneck and limit its practical applications. The modular multiplication operations occupy a large proportion of the overall computations required by the SIKE protocol. The VLSI implementation of the high-speed modular multiplier remains a big challenge. In this paper, we propose three improved modular multiplication algorithms based on an unconventional radix for this protocol, all of which cost about 20% fewer computations than the prior art. Besides, a multi-precision scheme is also introduced for the proposed algorithms to improve the scalability in hardware implementation, resulting in three new algorithms. We then present very efficient high-speed modular multiplier architectures for the six algorithms. It is shown that these new architectures can be highly optimized and extensively pipelined to obtain high throughput thanks to the adopted overlapping processing scheme. The FPGA implementation results show the proposed multipliers without the multi-precision scheme all achieve about 60 times higher throughput than the state-of-the-art design (the FFM2 multiplier), and those with the multi-precision scheme all acquire almost 10 times higher throughput than this work. Meanwhile, each of the multi-precision based designs has almost the same resource consumptions as the FFM2 does.
Yfke Dulek, Alex Grilo, Stacey Jeffery, Christian Majenz, Christian Schaffner
The cryptographic task of secure multi-party (classical) computation has received a lot of attention in the last decades. Even in the extreme case where a computation is performed between k mutually distrustful players, and security is required even for the single honest player if all other players are colluding adversaries, secure protocols are known. For quantum computation, on the other hand, protocols allowing arbitrary dishonest majority have only been proven for k = 2. In this work, we generalize the approach taken by Dupuis, Nielsen and Salvail (CRYPTO 2012) in the two-party setting to devise a secure, efficient protocol for multi-party quantum computation for any number of players k, and prove security against up to k − 1 colluding adversaries. The quantum round complexity of the protocol for computing a quantum circuit with g gates acting on w qubits is O((w + g)k). To achieve efficiency, we develop a novel public verification protocol for the Clifford authentication code, and a testing protocol for magic-state inputs, both using classical multi-party computation.
15 October 2019
Gorjan Alagic, Christian Majenz, Alexander Russell
We consider the problem of efficiently simulating random quantum states and random unitary operators, in a manner which is convincing to unbounded adversaries with black-box oracle access.
This problem has previously only been considered for restricted adversaries. Against adversaries with an a priori bound on the number of queries, it is well-known that t-designs suffice. Against polynomial-time adversaries, one can use pseudorandom states (PRS) and pseudorandom unitaries (PRU), as defined in a recent work of Ji, Liu, and Song; unfortunately, no provably secure construction is known for PRUs.
In our setting, we are concerned with unbounded adversaries. Nonetheless, we are able to give stateful quantum algorithms which simulate the ideal object in both settings of interest. In the case of Haar- random states, our simulator is polynomial-time, has negligible error, and can also simulate verification and reflection through the simulated state. This yields an immediate application to quantum money: a money scheme which is information-theoretically unforgeable and untraceable. In the case of Haar-random unitaries, our simulator takes polynomial space, but simulates both forward and inverse access with zero error.
These results can be seen as the first significant steps in developing a theory of lazy sampling for random quantum objects.
Cyprien Delpech de Saint Guilhem, Marc Fischlin, Bogdan Warinschi
We present a systematic approach to define and study authentication notions in authenticated key-exchange protocols. We propose and use a flexible and expressive predicate-based definitional framework. Our definitions capture key and entity authentication, in both implicit and explicit variants, as well as key and entity confirmation, for authenticated key-exchange protocols. In particular, we capture critical notions in the authentication space such as key-compromise impersonation resistance and security against unknown key-share attacks. We first present and explore these definitions within the Bellare-Rogaway model and then extend them to Canetti-Krawczyk-style models.
We then show two useful applications of our framework. First, we look at the authentication guarantees of three representative protocols to draw several useful lessons for protocol design. The core technical contribution of this paper is then to formally establish that composition of secure implicitly authenticated key-exchange with subsequent confirmation protocols yields explicit authentication guarantees. Without a formal separation of implicit and explicit authentication from secrecy, a proof of this folklore result could not have been established.
We then show two useful applications of our framework. First, we look at the authentication guarantees of three representative protocols to draw several useful lessons for protocol design. The core technical contribution of this paper is then to formally establish that composition of secure implicitly authenticated key-exchange with subsequent confirmation protocols yields explicit authentication guarantees. Without a formal separation of implicit and explicit authentication from secrecy, a proof of this folklore result could not have been established.
Wouter Castryck, Lorenz Panny, Frederik Vercauteren
In this paper, we introduce a polynomial-time algorithm to compute a connecting $\mathcal{O}$-ideal between two supersingular elliptic curves over $\mathbb{F}_p$ with common $\mathbb{F}_p$-endomorphism ring $\mathcal{O}$, given a description of their full endomorphism rings. This algorithm provides a reduction of the security of the CSIDH cryptosystem to the problem of computing endomorphism rings of supersingular elliptic curves. A similar reduction for SIDH appeared at Asiacrypt 2016, but relies on totally different techniques. Furthermore, we also show that any supersingular elliptic curve constructed using the complex-multiplication method can be located precisely in the supersingular isogeny graph by explicitly deriving a path to a known base curve. This result prohibits the use of such curves as a building block for a hash function into the supersingular isogeny graph.
Olivier Sanders
Let us assume that Alice has received a constant-size signature on a set of messages $\{m_i\}_{i=1}^n$ from some organization. Depending on the situation, Alice might need to disclose, prove relations about or hide some of these messages. Ideally, the complexity of the corresponding protocols should not depend on the hidden messages. In particular, if Alice wants to disclose only $k$ messages, then the authenticity of the latter should be verifiable in at most $O(k)$ operations.
Many solutions were proposed over the past decades, but they only provide a partial answer to this problem. In particular, we note that they suffer either from the need to prove knowledge of the hidden elements or from the inability to prove that the latter satisfy some relations.
In this paper, we propose a very efficient constant-size redactable signature scheme that addresses all the problems above. Signatures can indeed be redacted to remain valid only on a subset of $k$ messages included in $\{m_i\}_{i=1}^n$. The resulting redacted signature consists of 4 elements and can be verified with essentially $k$ exponentiations. Different shows of the same signature can moreover be made unlinkable leading to a very efficient anonymous credentials system.
Many solutions were proposed over the past decades, but they only provide a partial answer to this problem. In particular, we note that they suffer either from the need to prove knowledge of the hidden elements or from the inability to prove that the latter satisfy some relations.
In this paper, we propose a very efficient constant-size redactable signature scheme that addresses all the problems above. Signatures can indeed be redacted to remain valid only on a subset of $k$ messages included in $\{m_i\}_{i=1}^n$. The resulting redacted signature consists of 4 elements and can be verified with essentially $k$ exponentiations. Different shows of the same signature can moreover be made unlinkable leading to a very efficient anonymous credentials system.
A note on short invertible ring elements and applications to cyclotomic and trinomials number fields
Thomas Attema, Ronald Cramer, Chaoping Xing
Ring-SIS based $\Sigma$-protocols require the construction of a challenge set $\mathcal{C}$ in some ring $R$, usually an order in a number field $L$. These protocols impose various requirements on the subset $\mathcal{C}$, and constructing a good or even optimal challenge set is a non-trivial task that involves making various trade-offs. </p>
In particular, the set $\mathcal{C}$ should be 'large', elements in $\mathcal{C}$ should be 'small', differences of distinct elements in $\mathcal{C}$ should be invertible modulo a rational prime $p$, this prime $p$ should be small, and finally primes $p$ that split in many factors are favorable. Clearly, these requirements on $\mathcal{C}$ require certain trade-offs. The splitting behavior and size of the prime $p$, for example, influence the invertibility condition. </p>
Given an order $\mathcal{O}$ in an arbitrary number field $L$, this work aims at constructing subsets $\mathcal{C} \subset \mathcal{O}$ with precisely the above mentioned properties. Cyclotomic number fields possess some convenient properties and as a result most protocols are defined over these specific fields. However, recent attacks have shown that these convenient properties might also be of use to an attacker, thereby weakening or even breaking the cryptographic schemes. </p>
In this paper, we show that a known result on constructing challenge sets in cyclotomic number fields (Lyubashevsky and Seiler 2018) follows from standard Galois theory, thereby simplifying the proof. In addition, this approach leads to a natural generalization from cyclotomic to arbitrary number fields. Along the way we prove a conjectured result on the practical applicability for cyclotomic number fields and prove the optimality of certain constructions. We apply the generalization to construct challenge sets in trinomial number fields of the form $\mathbb{Q}[X]/(f)$ with $f=X^n+aX^k+b \in \mathbb{Z}[X]$ irreducible. Finally, we find a new construction for challenge sets resulting in smaller prime sizes at the cost of slightly increasing the $\ell_2$-norm of the challenges.
In particular, the set $\mathcal{C}$ should be 'large', elements in $\mathcal{C}$ should be 'small', differences of distinct elements in $\mathcal{C}$ should be invertible modulo a rational prime $p$, this prime $p$ should be small, and finally primes $p$ that split in many factors are favorable. Clearly, these requirements on $\mathcal{C}$ require certain trade-offs. The splitting behavior and size of the prime $p$, for example, influence the invertibility condition. </p>
Given an order $\mathcal{O}$ in an arbitrary number field $L$, this work aims at constructing subsets $\mathcal{C} \subset \mathcal{O}$ with precisely the above mentioned properties. Cyclotomic number fields possess some convenient properties and as a result most protocols are defined over these specific fields. However, recent attacks have shown that these convenient properties might also be of use to an attacker, thereby weakening or even breaking the cryptographic schemes. </p>
In this paper, we show that a known result on constructing challenge sets in cyclotomic number fields (Lyubashevsky and Seiler 2018) follows from standard Galois theory, thereby simplifying the proof. In addition, this approach leads to a natural generalization from cyclotomic to arbitrary number fields. Along the way we prove a conjectured result on the practical applicability for cyclotomic number fields and prove the optimality of certain constructions. We apply the generalization to construct challenge sets in trinomial number fields of the form $\mathbb{Q}[X]/(f)$ with $f=X^n+aX^k+b \in \mathbb{Z}[X]$ irreducible. Finally, we find a new construction for challenge sets resulting in smaller prime sizes at the cost of slightly increasing the $\ell_2$-norm of the challenges.