(Verifiable) delay functions from Lucas sequences
Hoffmann C, Hubáček P, Kamath C, Krňák T. 2023. (Verifiable) delay functions from Lucas sequences. 21st International Conference on Theory of Cryptography. TCC: Theory of Cryptography, LNCS, vol. 14372, 336–362.
Download (ext.)
Conference Paper
| English
Scopus indexed
Author
Hoffmann, CharlotteISTA 
;
Hubáček, Pavel;
Kamath, Chethan;
Krňák, Tomáš
;
Hubáček, Pavel;
Kamath, Chethan;
Krňák, TomášDepartment
Series Title
LNCS
Abstract
Lucas sequences are constant-recursive integer sequences with a long history of applications in cryptography, both in the design of cryptographic schemes and cryptanalysis. In this work, we study the sequential hardness of computing Lucas sequences over an RSA modulus.
First, we show that modular Lucas sequences are at least as sequentially hard as the classical delay function given by iterated modular squaring proposed by Rivest, Shamir, and Wagner (MIT Tech. Rep. 1996) in the context of time-lock puzzles. Moreover, there is no obvious reduction in the other direction, which suggests that the assumption of sequential hardness of modular Lucas sequences is strictly weaker than that of iterated modular squaring. In other words, the sequential hardness of modular Lucas sequences might hold even in the case of an algorithmic improvement violating the sequential hardness of iterated modular squaring.
Second, we demonstrate the feasibility of constructing practically-efficient verifiable delay functions based on the sequential hardness of modular Lucas sequences. Our construction builds on the work of Pietrzak (ITCS 2019) by leveraging the intrinsic connection between the problem of computing modular Lucas sequences and exponentiation in an appropriate extension field.
Publishing Year
Date Published
2023-11-27
Proceedings Title
21st International Conference on Theory of Cryptography
Acknowledgement
Home Theory of Cryptography Conference paper
(Verifiable) Delay Functions from Lucas Sequences
Download book PDF
Download book EPUB
Similar content being viewed by others
Slider with three content items shown per slide. Use the Previous and Next buttons to navigate the slides or the slide controller buttons at the end to navigate through each slide.
Previous slide
Generic-Group Delay Functions Require Hidden-Order Groups
Chapter© 2020
Shifted powers in Lucas–Lehmer sequences
Article30 January 2019
A New Class of Trapdoor Verifiable Delay Functions
Chapter© 2023
Weak Pseudoprimality Associated with the Generalized Lucas Sequences
Chapter© 2022
On the Security of Time-Lock Puzzles and Timed Commitments
Chapter© 2020
Generation of full cycles by a composition of NLFSRs
Article08 March 2014
Cryptographically Strong de Bruijn Sequences with Large Periods
Chapter© 2013
Open Problems on With-Carry Sequence Generators
Chapter© 2014
Generically Speeding-Up Repeated Squaring Is Equivalent to Factoring: Sharp Thresholds for All Generic-Ring Delay Functions
Chapter© 2020
Next slide
Go to slide 1
Go to slide 2
Go to slide 3
(Verifiable) Delay Functions from Lucas Sequences
Charlotte Hoffmann, Pavel Hubáček, Chethan Kamath & Tomáš Krňák
Conference paper
First Online: 27 November 2023
83 Accesses
Part of the Lecture Notes in Computer Science book series (LNCS,volume 14372)
Abstract
Lucas sequences are constant-recursive integer sequences with a long history of applications in cryptography, both in the design of cryptographic schemes and cryptanalysis. In this work, we study the sequential hardness of computing Lucas sequences over an RSA modulus.
First, we show that modular Lucas sequences are at least as sequentially hard as the classical delay function given by iterated modular squaring proposed by Rivest, Shamir, and Wagner (MIT Tech. Rep. 1996) in the context of time-lock puzzles. Moreover, there is no obvious reduction in the other direction, which suggests that the assumption of sequential hardness of modular Lucas sequences is strictly weaker than that of iterated modular squaring. In other words, the sequential hardness of modular Lucas sequences might hold even in the case of an algorithmic improvement violating the sequential hardness of iterated modular squaring.
Second, we demonstrate the feasibility of constructing practically-efficient verifiable delay functions based on the sequential hardness of modular Lucas sequences. Our construction builds on the work of Pietrzak (ITCS 2019) by leveraging the intrinsic connection between the problem of computing modular Lucas sequences and exponentiation in an appropriate extension field.
Keywords
Delay functions
Verifiable delay functions
Lucas sequences
Download conference paper PDF
1 Introduction
A verifiable delay function (VDF)
is a function that satisfies two properties. First, it is a delay function, which means it must take a prescribed (wall) time T to compute f, irrespective of the amount of parallelism available. Second, it should be possible for anyone to quickly verify – say, given a short proof
– the value of the function (even without resorting to parallelism), where by quickly we mean that the verification time should be independent of or significantly smaller than T (e.g., logarithmic in T). If we drop either of the two requirements, then the primitive turns out trivial to construct. For instance, for an appropriately chosen hash function h, the delay function
defined by T-times iterated hashing of the input is a natural heuristic for an inherently sequential task which, however, seems hard to verify more efficiently than by recomputing. On the other hand, the identity function
is trivial to verify but also easily computable. Designing a simple function satisfying the two properties simultaneously proved to be a nontrivial task.
The notion of VDFs was introduced in [31] and later formalised in [9]. In principle, since the task of constructing a VDF reduces to the task of incrementally-verifiable computation [9, 53], constructions of VDFs could leverage succinct non-interactive arguments of knowledge (SNARKs): take any sequentially-hard function f (for instance, iterated hashing) as the delay function and then use the SNARK on top of it as the mechanism for verifying the computation of the delay function. However, as discussed in [9], the resulting construction is not quite practical since we would rely on a general-purpose machinery of SNARKs with significant overhead.
Efficient VDFs via Algebraic Delay Functions. VDFs have recently found interesting applications in design of blockchains [17], randomness beacons [43, 51], proofs of data replication [9], or short-lived zero-knowledge proofs and signatures [3]. Since efficiency is an important factor there, this has resulted in a flurry of constructions of VDFs that are tailored with application and practicality in mind. They rely on more algebraic, structured delay functions that often involve iterating an atomic operation so that one can resort to custom proof systems to achieve verifiability. These constructions involve a range of algebraic settings like the RSA or class groups [5, 8, 25, 42, 55], permutation polynomials over finite fields [9], isogenies of elliptic curves [21, 52] and, very recently, lattices [15, 28]. The constructions in [42, 55] are arguably the most practical and the mechanism that underlies their delay function is the same: carry out iterated squaring in groups of unknown order, like RSA groups [47] or class groups [12]. What distinguishes these two proposals is the way verification is carried out, i.e., how the underlying “proof of exponentiation” works: while Pietrzak [42] resorts to an LFKN-style recursive proof system [35], Wesolowski [55] uses a clever linear decomposition of the exponent.
Iterated Modular Squaring and Sequentiality. The delay function that underlies the VDFs in [5, 25, 42, 55] is the same, and its security relies on the conjectured sequential hardness of iterated squaring in a group of unknown order (suggested in the context of time-lock puzzles by Rivest, Shamir, and Wagner [48]). Given that the practically efficient VDFs all rely on the above single delay function, an immediate open problem is to identify additional sources of sequential hardness that are structured enough to support practically efficient verifiability.
1.1 Our Approach to (Verifiable) Delay Functions
In this work, we study an alternative source of sequential hardness in the algebraic setting and use it to construct efficient verifiable delay functions. The sequentiality of our delay function relies on an atomic operation that is related to the computation of so-called Lucas sequences [29, 34, 57], explained next.
Lucas Sequences. A Lucas sequence is a constant-recursive integer sequence that satisfies the recurrence relation
for integers P and Q.Footnote1 Specifically, the Lucas sequences of integers
and
of the first and second type (respectively) are defined recursively as
with
, and
with
.
These sequences can be alternatively defined by the characteristic polynomial
. Specifically, given the discriminant
of the characteristic polynomial, one can alternatively compute the above sequences by performing operations in the extension field
using the identities
where
and its conjugate
are roots of the characteristic polynomial. Since conjugation and exponentiation commute in the extension field (i.e.,
), computing the i-th terms of the two Lucas sequences over integers reduces to computing
in the extension field, and vice versa.
The intrinsic connection between computing the terms in the Lucas sequences and that of exponentiation in the extension has been leveraged to provide alternative instantiations of public-key encryption schemes like RSA and ElGamal in terms of Lucas sequences [7, 30]. However, as we explain later, the corresponding underlying computational hardness assumptions are not necessarily equivalent.
Overview of Our Delay Function. The delay function in [5, 25, 42, 55] is defined as the iterated squaring base x in a (safe) RSA groupFootnote2 modulo N:
Our delay function is its analogue in the setting of Lucas sequences:
As mentioned above, computing
can be carried out equivalently in the extension field
using the known relationship to roots of the characteristic polynomial of the Lucas sequence. Thus, the delay function can be alternatively defined as
Note that the atomic operation of our delay function is “doubling” the index of an element of the Lucas sequence modulo N (i.e.,
) or, equivalently, squaring in the extension field
(as opposed to squaring in
). Using the representation of
as
, squaring in
can be expressed as a combination of squaring, multiplication and addition modulo N, since
(1)
Since
is a group of unknown order (provided the factorization of N is kept secret), iterated squaring remains hard here. In fact, we show in Sect. 3.2 that iterated squaring in
is at least as hard as iterated squaring for RSA moduli N. Moreover, we conjecture in Conjecture 1 that it is, in fact, strictly harder (also see discussion below on advantages of our approach).
Verifying Modular Lucas Sequence. To obtain a VDF, we need to show how to efficiently verify our delay function. To this end, we show how to adapt the interactive proof of exponentiation from [42] to our setting, which then – via the Fiat-Shamir Transform [22] – yields the non-interactive verification algorithm.Footnote3 Thus, our main result is stated informally below.
Theorem 1
(Informally stated, see Theorem 2). Assuming sequential hardness of modular Lucas sequence, there exists statistically-sound VDF in the random-oracle model.
However, the modification of Pietrzak’s protocol is not trivial and we have to overcome several hurdles that we face in this task, which we elaborate on in Sect. 1.2. We conclude this section with discussions about our results.
Advantage of Our Approach. Our main advantage is the reliance on a potentially weaker (sequential) hardness assumption while maintaining efficiency: we show in Sect. 3.2 that modular Lucas sequences are at least as sequentially-hard as the classical delay function given by iterated modular squaring [48]. Despite the linear recursive structure of Lucas sequences, there is no obvious reduction in the other direction, which suggests that the assumption of sequential hardness of modular Lucas sequences is strictly weaker than that of iterated modular squaring (Conjecture 1). In other words, the sequential hardness of modular Lucas sequences might hold even in the case of an algorithmic improvement violating the sequential hardness of iterated modular squaring. Even though both assumptions need the group order to be hidden, we believe that there is need for a nuanced analysis of sequential hardness assumptions in hidden order groups, especially because all current delay functions that provide sufficient structure for applications are based on iterated modular squaring. If the iterated modular squaring assumption is broken, our delay function is currently the only practical alternative in the RSA group.
Delay Functions in Idealised Models. Recent works studied the relationship of group-theoretic (verifiable) delay functions to the hardness of factoring in idealised models such as the algebraic group model and the generic ring model [27, 50]. In the generic ring model, Rotem and Segev [50] showed the equivalence of straight-line delay functions in the RSA setting and factoring. Our construction gives rise to a straight-line delay function and, by their result, its sequentiality is equivalent to factoring for generic algorithms. However, their result holds only in the generic ring model and leaves the relationship between the two assumptions unresolved in the standard model.
Compare this with the status of the RSA assumption and factoring. On one hand, we know that in the generic ring model, RSA and factoring are equivalent [2]. Yet, it is possible to rule out certain classes of reductions from factoring to RSA in the standard model [11]. Most importantly, despite the equivalence in the generic ring model, there is currently no reduction from factoring to RSA in the standard model and it remains one of the major open problems in number theory related to cryptography since the introduction of the RSA assumption.
In summary, speeding up iterated squaring by a non-generic algorithm could be possible (necessarily exploiting the representations of ring elements modulo N), while such an algorithm may not lead to a speed-up in the computation of modular Lucas sequences despite the result of Rotem and Segev [50].
1.2 Technical Overview
Pietrzak’s VDF. Let
be an RSA modulus where p and q are safe primes and let x be a random element from
. At its core, Pietrzak’s VDF relies on the interactive protocol for the statement
“(N, x, y, T) satisfies
”.
The protocol is recursive and, in a round-by-round fashion, reduces the claim to a smaller statement by halving the time parameter. To be precise, in each round, the (honest) prover sends the “midpoint”
of the current statement to the verifier and they together reduce the statement to
“
satisfies
”,
where
and
for a random challenge r. This is continued till
is obtained at which point the verifier simply checks whether
using a single modular squaring.
Since the challenges r are public, the protocol can be compiled into a non-interactive one using the Fiat-Shamir transform [22] and this yields a means to verify the delay function
It is worth pointing out that the choice of safe primes is crucial for proving soundness: in case the group has easy-to-find elements of small order then it becomes easy to break soundness (see, e.g., [10]).
Adapting Pietrzak’s Protocol to Lucas Sequences. For a modulus
and integers
, recall that our delay function is defined as
or equivalently
for the discriminant
of the characteristic polynomial
. Towards building a verification algorithm for this delay function, the natural first step is to design an interactive protocol for the statement
“(N, P, Q, y, T) satisfies
.”
It turns out that the interactive protocol from [42] can be adapted for this purpose. However, we encounter two technicalities in this process.
Dealing with elements of small order. The main problem that we face while designing our protocol is avoiding elements of small order. In the case of [42], this was accomplished by moving to the setting of signed quadratic residues [26] in which the sub-groups are all of large order. It is not clear whether a corresponding object exists for our algebraic setting. However, in an earlier draft of Pietrzak’s protocol [41], this problem was dealt with in a different manner: the prover sends a square root of
, from which the original
can be recovered easily (by squaring it) with a guarantee that the result lies in a group of quadratic residues
. Notice that the prover knows the square root of
, because it is just a previous term in the sequence he computed.
In our setting, we cannot simply ask for the square root of the midpoint as the subgroup of
we effectively work in has a different structure. Nevertheless, we can use a similar approach: for an appropriately chosen small a, we provide an a-th root of
(instead of
itself) to the prover in the beginning of the protocol. The prover then computes the whole sequence for
. In the end, he has the a-th root of every term of the original sequence and he can recover any element of the original sequence by raising to the a-th power.
Sampling strong modulus. The second technicality is related to the first one. In order to ensure that we can use the above trick, we require a modulus where the small subgroups are reasonably small not only in the group
but also in the extension
. Thus the traditional sampling algorithms that are used to sample strong primes (e.g., [46]) are not sufficient for our purposes. However, sampling strong primes that suit our criteria can still be carried out efficiently as we show in the full version.
Comparing Our Technique with [8, 25]. The VDFs in [8, 25] are also inspired by [42] and, hence, faced the same problem of low-order elements. In [8], this is dealt with by amplifying the soundness at the cost of parallel repetition and hence larger proofs and extra computation. In [25], the number of repetitions of [8] is reduced significantly by introducing the following technique: The exponent of the initial instance is reduced by some parameter
and at the end of an interactive phase, the verifier performs final exponentiation with
, thereby weeding out potential false low-order elements in the claim. This technique differs from the approach taken in our work in the following ways: The technique from [25] works in arbitrary groups but it requires the parameter
to be large and of a specific form. In particular, the VDF becomes more efficient when
is larger than
. In our protocol, we work in RSA groups whose modulus is the product of primes that satisfy certain conditions depending on a. This enables us to choose a parameter a that is smaller than a statistical security parameter and thereby makes the final exponentiation performed by the verifier much more efficient. Further, a can be any natural number, while
must be set as powers of all small prime numbers up a certain bound in [25].
1.3 More Related Work
Timed Primitives. The notion of VDFs was introduced in [31] and later formalised in [9]. VDFs are closely related to the notions of time-lock puzzles [48] and proofs of sequential work [36]. Roughly speaking, a time-lock puzzle is a delay function that additionally allows efficient sampling of the output via a trapdoor. A proof of sequential work, on the other hand, is a delay “multi-function”, in the sense that the output is not necessarily unique. Constructions of time-lock puzzles are rare [6, 38, 48], and there are known limitations: e.g., that it cannot exist in the random-oracle model [36]. However, we know how to construct proofs of sequential work in the random-oracle model [1, 16, 19, 36].
Since VDFs have found several applications, e.g., in the design of resource-efficient blockchains [17], randomness beacons [43, 51] and proof of data replication [9], there have been several constructions. Among them, the most notable are the iterated-squaring based construction from [8, 25, 42, 55], the permutation-polynomial based construction from [9], the isogenies-based construction from [13, 21, 52] and the construction from lattice problems [15, 28]. The constructions in [42, 55] are quite practical (see the survey [10]) and the VDF deployed in the cryptocurrency Chia is basically their construction adapted to the algebraic setting of class groups [17]. This is arguably the closest work to ours. On the other hand, the constructions from [21, 52], which work in the algebraic setting of isogenies of elliptic curves where no analogue of square and multiply is known, simply rely on “exponentiation”. Although, these constructions provide a certain form of quantum resistance, they are presently far from efficient. Freitag et al. [23] constructed VDFs from any sequentially hard function and polynomial hardness of learning with errors, the first from standard assumptions. The works of Cini, Lai, and Malavolta [15, 28] constructed the first VDF from lattice-based assumptions and conjectured it to be post-quantum secure.
Several variants of VDFs have also been proposed. A VDF is said to be unique if the proof that is used for verification is unique [42]. Recently, Choudhuri et al. [5] constructed unique VDFs from the sequential hardness of iterated squaring in any RSA group and polynomial hardness of LWE. A VDF is tight [18] if the gap between simply computing the function and computing it with a proof is small. Yet another extension is a continuous VDF [20]. The feasibility of time-lock puzzles and proofs of sequential works were recently extended to VDFs. It was shown [50] that the latter requirement, i.e., working in a group of unknown order, is inherent in a black-box sense. It was shown in [18, 37] that there are barriers to constructing tight VDFs in the random-oracle model.
VDFs also have surprising connection to complexity theory [14, 20, 33].
Work Related to Lucas Sequences. Lucas sequences have long been studied in the context of number theory: see for example [45] or [44] for a survey of its applications to number theory. Its earliest application to cryptography can be traced to the
factoring algorithm [56]. Constructive applications were found later thanks to the parallels with exponentiation. Several encryption and signature schemes were proposed, most notably the LUC family of encryption and signatures [30, 39]. It was later shown that some of these schemes can be broken or that the advantages it claimed were not present [7]. Other applications can be found in [32].
2 Preliminaries
2.1 Interactive Proof Systems
Interactive Protocols. An interactive protocol consists of a pair
of interactive Turing machines that are run on a common input
. The first machine
is the prover and is computationally unbounded. The second machine
is the verifier and is probabilistic polynomial-time.
In an
-round (i.e.,
-message) interactive protocol, in each round
, first
sends a message
to
and then
sends a message
to
, where
is a finite alphabet. At the end of the interaction,
runs a (deterministic) Turing machine on input
. The interactive protocol is public-coin if
is a uniformly distributed random string in
.
Interactive Proof Systems. The notion of an interactive proof for a language L is due to Goldwasser, Micali and Rackoff [24].
Definition 1
For a function
, an interactive protocol
is an
-statistically-sound interactive proof system for L if:
Completeness: For every
, if
interacts with
on common input
, then
accepts with probability 1.
Soundness: For every
and every (computationally-unbounded) cheating prover strategy
, the verifier
accepts when interacting with
with probability less than
, where
is called the soundness error.
2.2 Verifiable Delay Functions
We adapt the definition of verifiable delay functions from [9] but we decouple the verifiability and sequentiality properties for clarity of exposition of our results. First, we present the definition of a delay function.
Definition 2
A delay function
consists of a triple of algorithms with the following syntax:
:
On input a security parameter
, the algorithm
outputs public parameters
.
:
On input public parameters
and a time parameter
, the algorithm
outputs a challenge x.
:
On input a challenge pair (x, T), the (deterministic) algorithm
outputs the value y of the delay function in time T.
The security property required of a delay function is sequential hardness as defined below.
Definition 3
(Sequentiality). We say that a delay function
satisfies the sequentiality property, if there exists an
such that for all
and for every adversary
, where
uses
processors and runs in time
, there exists a negligible function
such that
figure a
A few remarks about our definition of sequentiality are in order:
1.
We require computing
to be hard in less than T sequential steps even using any polynomially-bounded amount of parallelism and precomputation. Note that it is necessary to bound the amount of parallelism, as an adversary could otherwise break the underlying hardness assumption (e.g. hardness of factorization). Analogously, T should be polynomial in
as, otherwise, breaking the underlying hardness assumptions becomes easier than computing
itself for large values of T.
2.
Another issue is what bound on the number of sequential steps of the adversary should one impose. For example, the delay function based on T repeated modular squarings can be computed in sequential time
using polynomial parallelism [4]. Thus, one cannot simply bound the sequential time of the adversary by o(T). Similarly to [38], we adapt the
bound for
which, in particular, is asymptotically smaller than
.
3.
Without loss of generality, we assume that the size of
is at least linear in n and the adversary A does not have to get the unary representation of the security parameter
as its input.
The definition of verifiable delay function extends a delay function with the possibility to compute publicly-verifiable proofs of correctness of the output value.
Definition 4
A delay function
is a verifiable delay function if it is equipped with two additional algorithms
and
with the following syntax:
:
On input public parameters and a challenge pair (x, T), the
algorithm outputs
, where
is a proof that the output y is the output of
.
:
On input public parameters, a challenge pair (x, T), and an output/proof pair
, the (deterministic) algorithm
outputs either
or
.
In addition to sequentiality (inherited from the underlying delay function), the
and
algorithms must together satisfy correctness and (statistical) soundness as defined below.
Definition 5
(Correctness). A verifiable delay function
is correct if for all
figure b
Definition 6
(Statistical soundness). A verifiable delay function
is statistically sound if for every (computationally unbounded) malicious prover
there exists a negligible function
such that for all
figure c
3 Delay Functions from Lucas Sequences
In this section, we propose a delay function based on Lucas sequences and prove its sequentiality assuming that iterated squaring in a group of unknown order is sequential (Sect. 3.1). Further, we conjecture (Sect. 3.2) that our delay function candidate is even more robust than its predecessor proposed by Rivest, Shamir, and Wagner [48]. Finally, we turn our delay function candidate into a verifiable delay function (Sect. 4).
3.1 The Atomic Operation
Our delay function is based on subsequences of Lucas sequences, whose indexes are powers of two. Below, we use
to denote the set of non-negative integers.
Definition 7
For integers
, the Lucas sequences
and
are defined for all
as
with
and
, and
with
and
.
We define subsequences
, respectively
, of
, respectively
for all
as
(2)
Although the value of
depends on parameters (P, Q), we omit (P, Q) from the notation because these parameters will be always obvious from the context.
The underlying atomic operation for our delay function is
There are several ways to compute
in T sequential steps, and we describe two of them below.
An Approach Based on Squaring in a Suitable Extension Ring. To compute the value
, we can use the extension ring
, where
is the discriminant of the characteristic polynomial
of the Lucas sequence. The characteristic polynomial f(z) has a root
, and it is known that, for all
, it holds that
Thus, by iterated squaring of
, we can compute terms of our target subsequences. To get a better understanding of squaring in the extension ring, consider the representation of the root
for some
. Then,
Then, the atomic operation of our delay function can be interpreted as
, defined for all
as
(3)
An Approach Based on Known Identities. Many useful identities for members of modular Lucas sequences are known, such as
(4)
Setting
we get
(5)
The above identities are not hard to derive (see, e.g., Lemma 12.5 in [40]). Indexes are doubled on each of application of the identities in Eq. (5), and, thus, for
, we define an auxiliary sequence
by
. Using the identities in Eq. (5), we get recursive equations
(6)
Then, the atomic operation of our delay function can be interpreted as
, defined for all
as
(7)
After a closer inspection, the reader may have an intuition that an auxiliary sequence
, which introduces a third state variable, is redundant. This intuition is indeed right. In fact, there is another easily derivable identity
(8)
which can be found, e.g., as Lemma 12.2 in [40]. On the other hand, Eq. (8) is quite interesting because it allows us to compute large powers of an element
using two Lucas sequences. We use this fact in the security reduction in Sect. 3.2. Our construction of a delay function, denoted
, is given in Fig. 1.
Fig. 1.
figure 1
Our delay function candidate
based on a modular Lucas sequence.
Full size image
On the Discriminant D. Notice that whenever D is a quadratic residue modulo N, the value
is an element of
and hence
. By definition, LCS.Gen generates a parameter D that is a quadratic residue with probability 1/4, so it might seem that in one fourth of the cases there is another approach to compute
: find the element
and then perform n sequential squarings in the group
. However, it is well known that finding square roots of uniform elements in
is equivalent to factoring the modulus N, so this approach is not feasible. We can therefore omit any restrictions on the discriminant D in the definition of our delay function LCS.
3.2 Reduction from RSW Delay Function
In order to prove the sequentiality property (Definition 3) of our candidate
, we rely on the standard conjecture of the sequentiality of the
time-lock puzzles, implicitly stated in [48] as the underlying hardness assumption.
Definition 8
(
delay function). The
delay function is defined as follows:
: Samples two n-bit primes p and q and outputs
.
: Outputs an x sampled from the uniform distribution on
.
: Outputs
.
Theorem 2
If the
delay function has the sequentiality property, then the
delay function has the sequentiality property.
Proof
Suppose there exists an adversary
who contradicts the sequentiality of
, where
is a precomputation algorithm and
is an online algorithm. We construct an adversary
who contradicts the sequentiality of
as follows:
The algorithm
is defined identically to the algorithm
.
On input
,
picks a P from the uniform distribution on
, sets
and it runs
to compute
. The algorithm
computes
using the identity in Eq. (8).
Note that the input distribution for the algorithm
produced by
differs from the one produced by
, because the
generator samples Q from the uniform distribution on
(instead of
). However, this is not a problem since the size of
is negligible compared to the size of
, so the statistical distance between the distribution of D produced by
and the distribution of D sampled by
is negligible in the security parameter. Thus, except for a negligible multiplicative loss, the adversary
attains the same success probability of breaking the sequentiality of
as the probability of
breaking the sequentiality of
– a contradiction to the assumption of the theorem.
We believe that the converse implication to Theorem 2 is not true, i.e., that breaking the sequentiality of
does not necessarily imply breaking the sequentiality of
. Below, we state it as a conjecture.
Conjecture 1
Sequentiality of
cannot be reduced to sequentiality of
.
One reason why the above conjecture might be true is that, while the
delay function is based solely only on multiplication in the group
, our
delay function uses the full arithmetic (addition and multiplication) of the commutative ring
.
One way to support the conjecture would be to construct an algorithm that speeds up iterated squaring but is not immediately applicable to Lucas sequences. By [49] we know that this cannot be achieved by a generic algorithm. A non-generic algorithm that solves iterated squaring in time
is presented in [4]. The main tool of their construction is the Explicit Chinese Remainder Theorem modulo N. However, a similiar theorem exists also for univariate polynomial rings, which suggests that a similar speed-up can be obtained for our delay function by adapting the techniques in [4] to our setting.
4 VDF from Lucas Sequences
In Sect. 3.1 we saw different ways of computing the atomic operation of the delay function. Computing
in the extension field seems to be the more natural and time and space effective approach. Furthermore, writing the atomic operation
as
is very clear, and, thus, we follow this approach throughout the rest of the paper.
4.1 Structure of
To construct a VDF based on Lucas sequences, we use an algebraic extension
(9)
where N is an RSA modulus and
. In this section, we describe the structure of the algebraic extension given in Expression (9). Based on our understanding of the structure of the above algebraic extension, we can conclude that using modulus N composed of safe primes (i.e., for all prime factors p of N,
has a large prime divisor) is necessary but not sufficient condition for security of our construction. We specify some sufficient conditions on factors of N in the subsequent Sect. 4.2.
First, we introduce some simplifying notation for quotient rings.
Definition 9
For
and
, we denote by
the quotient ring
, where (m, f(x)) denotes the ideal of the ring
generated by m and f(x).
Observation 1, below, allows us to restrict our analysis only to the structure of
for prime
.
Observation 1
Let
be distinct primes,
and
. Then
Proof
Using the Chinese reminder theorem, we get
as claimed.
The following lemma characterizes the structure of
with respect to the discriminant of f. We use
to denote the standard Legendre symbol.
Lemma 1
Let
and
be a polynomial of degree 2 with the discriminant D. Then
Proof
We consider each case separately:
If
, then f(x) is irreducible over
and
is a field with
elements. Since
is a finite field,
is cyclic and contains
elements.
If
, then
and f has some double root
and it can be written as
for some
. Since the ring
is isomorphic to the ring
(consider the isomorphism
), we can restrict ourselves to describing the structure of
.
We will prove that the function
,
is an isomorphism. First, the polynomial
is invertible if and only if
(inverse is
). For the choice
, we have
Thus
is onto. Second,
is, in fact, a bijection, because
(10)
Finally,
is a homomorphism, because
If
, then f(x) has two roots
. We have an isomorphism
and
.
4.2 Strong Groups and Strong Primes
To achieve the verifiability property of our construction, we need
to contain a strong subgroup (defined next) of order asymptotically linear in p. We remark that our definition of strong primes is stronger than the one by Rivest and Silverman [46].
Definition 10
(Strong groups). For
, we say that a non-trivial group
is
-strong, if the order of each non-trivial subgroup of
is greater than
.
Observation 2
If
and
are
-strong groups, then
is a
-strong group.
It can be seen from Lemma 1 that
always contains groups of small order (e.g.
). To avoid these, we descend into the subgroup of a-th powers of elements of
. Below, we introduce the corresponding notation.
Definition 11
For an Abelian group
and
, we define the subgroup
of
in the multiplicative notation and
in the additive notation.
Further, we show in Lemma 2 below that
-strong primality (defined next) is a sufficient condition for
to be a
-strong group.
Definition 12
(Strong primes). Let
and
. We say that p is a
-strong prime, if
and there exists
,
, such that
and every prime factor of W is greater than
.
Since a is a public parameter in our setup, super-polynomial a could reveal partial information about the factorization of N. However, we could allow a to be polynomial in
while maintaining hardness of factoring N.Footnote4 For the sake of simplicity of Definition 12, we rather use stronger condition
. The following simple observation will be useful for proving Lemma 2.
Observation 3
For
.
Lemma 2
Let p be a
-strong prime and
be a quadratic polynomial. Then,
is a
-strong group.
Proof
From definition of the strong primes, there exists
, whose factors are bigger than
and
. We denote
a factor of W. Applying Observation 3 to Lemma 1, we get
In particular, we used above the fact that Observation 2 implies that
as explained next. Since
, all divisors of
are divisors of aW. By definition of a and W in Definition 12, we also have that
, which implies that any factor of
divides either a or W, but not both. When we divide
by all the common divisors with a, only the common divisors with W are left, which implies
. The proof of the lemma is now completed by Observation 2.
Corollary 1
Let p be a
-strong prime, q be a
-strong prime,
,
,
and
. Then
is
-strong.
4.3 Our Interactive Protocol
Our interactive protocol is formally described in Fig. 3. To understand this protocol, we first recall the outline of Pietrzak’s interactive protocol from Sect. 1.2 and then highlight the hurdles. Let
be an RSA modulus where p and q are strong primes and let x be a random element from
. The interactive protocol in [42] allows a prover to convince the verifier of the statement
“(N, x, y, T) satisfies
”.
The protocol is recursive and in a round-by-round fashion reduces the claim to a smaller statement by halving the time parameter. To be precise, in each round the (honest) prover sends the “midpoint”
of the current statement to the verifier and they together reduce the statement to
“
satisfies
”,
where
and
for a random challenge r. This is continued until
is obtained at which point the verifier simply checks whether
.
The main problem, we face while designing our protocol is ensuring that the verifier can check whether
sent by prover lies in an appropriate subgroup of
. In the first draft of Pietrzak’s protocol [41], prover sends a square root of
, from which the original
can be recovered easily (by simply squaring it) with a guarantee, that the result lies in a group of quadratic residues
. Notice that the prover knows the square root of
, because it is just a previous term in the sequence he computed.
Using Pietrzak’s protocol directly for our delay function would require computing a-th roots in RSA group for some arbitrary a. Since this is a computationally hard problem, we cannot use the same trick. In fact, the VDF construction of Wesolowski [54] is based on similar hardness assumption.
While Pietrzak shifted from
to the group of signed quadratic residues
in his following paper [42] to get unique proofs, we resort to his old idea of ‘squaring a square root’ and generalise it.
The high level idea is simple. First, on input
, prover computes the sequence
. Next, during the protocol, verifier maps all elements sent by the prover by homomorphism
(11)
into the target strong group
. This process is illustrated in Fig. 2. Notice that the equality
for the original sequence implies the equality
for the mapped sequence
.
Fig. 2.
figure 2
Illustration of our computation of the iterated squaring using the a-th root of
. Horizontal arrows are
and diagonal arrows are
.
Full size image
Restriction to Elements of
. Mapping Eq. (11) introduces a new technical difficulty. Since
is not injective, we narrow the domain inputs, for which the output of our VDF is verifiable, from
to
. Furthermore, the only way to verify that a certain x is an element of
is to get an a-th root of x and raise it to the ath power. So we have to represent elements of
by elements of
anyway. To resolve these two issues, we introduce a non-unique representation of elements of
.
Definition 13
For
and
, we denote
(an element of
) by [x]. Since this representation of
is not unique, we define an equality relation by
We will denote by tilde () the elements that were already powered to the a by a verifier (i.e. ). Thus tilded variables verifiably belong to the target group
.
In the following text, the goal of the brackets notation in Definition 13 is to distinguish places where the equality means the equality of elements of
from those places, where the equality holds up to
. A reader can also see the notation in Definition 13 as a concrete representation of elements of a factor group
.
Our security reduction 2 required the delay function to operate everywhere on
. This is not a problem if the
algorithm is modified to output the set
.
Fig. 3.
figure 3
Our Interactive Protocol for
.
Full size image
4.4 Security
Recall here that
is
-strong group, so there exist
and
such that
(12)
Definition 14
For
and
, we define
as i-th coordinate of
, where
is the isomorphism given by Eq. (12).
Lemma 3
Let
and
. If
, then
(13)
Proof
Fix
,
and y. Let some
satisfy
(14)
Using notation from Definition 14, we rewrite Eq. (14) as a set of equations
For every
, by reordering the terms, the j-th equation becomes
(15)
If
, then
. Further for every
. It follows that
. Putting these two equations together gives us
, which contradicts our assumption
.
It follows that there exists
such that
(16)
Thereafter there exists
such that
divides
and
(17)
Furthermore, from Eq. (15),
divides
. Finally, dividing eq. Eq. (15) by
, we get that r is determined uniquely (
),
Using the fact that
, this uniqueness of r upper bounds number of
, such that Eq. (14) holds, to one. It follows that the probability that Eq. (14) holds for r chosen randomly from the uniform distribution over
is less than
.
Corollary 2
The halving protocol will turn an invalid input tuple (i.e.
) into a valid output tuple (i.e.
) with probability less than
.
Theorem 3
For any computationally unbounded prover who submits anything other than
such that
in phase 2 of the protocol, the soundness error is upper-bounded by
Proof
In each round of the protocol, T decreases to
. It follows that the number of rounds of the halving protocol before reaching
is upper bounded by
.
If the verifier accepts the solution tuple
in the last round, then the equality
must hold. It follows that the initial inequality must have turned into equality in some round of the halving protocol. By Lemma 3, the probability of this event is bounded by
. Finally, using the union bound for all rounds, we obtain the upper bound (
.
4.5 Our VDF
Analogously to the VDF of Pietrzak [42], we compile our public-coin interactive proof given in Fig. 3 into a VDF using the Fiat-Shamir heuristic. The complete construction is given in Fig. 4. For ease of exposition, we assume that the time parameter T is always a power of two.
Fig. 4.
figure 4
based on Lucas sequences
Full size image
As discussed in Sect. 4.3, it is crucial for the security of the protocol that the prover computes a sequence of powers of the a-th root of the challenge and the resulting value (as well as the intermediate values) received from the prover is lifted to the appropriate group by raising it to the a-th power. We use the tilde notation in Fig. 4 in order to denote elements on the sequence relative to the a-th root.
Note that, by the construction, the output of our VDF is the
-th power of the root of the characteristic polynomial for Lucas sequence with parameters P and Q. Therefore, the value of the delay function implicitly corresponds to the
-th term of the Lucas sequence.
Theorem 4
Let
be the statistical security parameter. The
VDF defined in Fig. 4 is correct and statistically-sound with a negligible soundness error if
is modelled as a random oracle, against any adversary that makes
oracle queries.
Proof
The correctness follows directly by construction.
To prove its statistical soundness, we proceed in a similar way to [42]. We cannot apply Fiat-Shamir transformation directly, because our protocol does not have constant number of rounds, thus we use Fiat-Shamir heuristic to each round separately.
First, we use a random oracle as the
function. Second, if a malicious prover computed a proof accepted by verifier for some tuple
such that
(19)
then he must have succeeded in turning inequality from Eq. (19) into equality in some round. By Lemma 3, probability of such a flipping is bounded by
. Every such an attempt requires one query to random oracle. Using a union bound, it follows that the probability that a malicious prover who made q queries to random oracle succeeds in flipping initial inequality into equality in some round is upper-bounded by
.
Since q is
,
is a negligible function and thus the soundness error is negligible.
Notes
1.
Note that integer sequences like Fibonacci numbers and Mersenne numbers are special cases of Lucas sequences.
2.
The choice of modulus N is said to be safe if
for safe primes
and
, where
and
are also prime.
3.
Further, using the ideas from [14, 20], it is possible to construct so-called continuous VDFs from Lucas sequences.
4.
Since we set a to be at most polynomial in
, its is possible to go over all possible candidate values for a in time polynomial in
. Thus, any algorithm that could factor N using the knowledge of a can be efficiently simulated even without the knowledge of a.
References
Abusalah, H., Kamath, C., Klein, K., Pietrzak, K., Walter, M.: Reversible proofs of sequential work. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11477, pp. 277–291. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17656-3_10
CrossRef
Google Scholar
Aggarwal, D., Maurer, U.: Breaking RSA generically is equivalent to factoring. IEEE Trans. Inf. Theory 62(11), 6251–6259 (2016). https://doi.org/10.1109/TIT.2016.2594197
CrossRef
MathSciNet
MATH
Google Scholar
Arun, A., Bonneau, J., Clark, J.: Short-lived zero-knowledge proofs and signatures. In: Agrawal, S., Lin, D. (eds.) Advances in Cryptology – ASIACRYPT 2022. Lecture Notes in Computer Science, vol. 13793, pp. 487–516. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-22969-5_17
CrossRef
Google Scholar
Bernstein, D., Sorenson, J.: Modular exponentiation via the explicit Chinese remainder theorem. Math. Comput. 76, 443–454 (2007). https://doi.org/10.1090/S0025-5718-06-01849-7
CrossRef
MathSciNet
MATH
Google Scholar
Bitansky, N., et al.: PPAD is as hard as LWE and iterated squaring. IACR Cryptol. ePrint Arch., p. 1072 (2022)
Google Scholar
Bitansky, N., Goldwasser, S., Jain, A., Paneth, O., Vaikuntanathan, V., Waters, B.: Time-lock puzzles from randomized encodings. In: ITCS, pp. 345–356. ACM (2016)
Google Scholar
Bleichenbacher, D., Bosma, W., Lenstra, A.K.: Some remarks on Lucas-based cryptosystems. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 386–396. Springer, Heidelberg (1995). https://doi.org/10.1007/3-540-44750-4_31
CrossRef
Google Scholar
Block, A.R., Holmgren, J., Rosen, A., Rothblum, R.D., Soni, P.: Time- and space-efficient arguments from groups of unknown order. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, vol. 12828, pp. 123–152. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-84259-8_5
CrossRef
Google Scholar
Boneh, D., Bonneau, J., Bünz, B., Fisch, B.: Verifiable delay functions. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10991, pp. 757–788. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96884-1_25
CrossRef
Google Scholar
Boneh, D., Bünz, B., Fisch, B.: A survey of two verifiable delay functions. IACR Cryptol. ePrint Arch. 2018, 712 (2018)
MATH
Google Scholar
Boneh, D., Venkatesan, R.: Breaking RSA may not be equivalent to factoring. In: Nyberg, K. (ed.) Advances in Cryptology - EUROCRYPT ’98. Lecture Notes in Computer Science, vol. 1403, pp. 59–71. Springer, Cham (1998). https://doi.org/10.1007/BFb0054117
CrossRef
Google Scholar
Buchmann, J., Williams, H.C.: A key-exchange system based on imaginary quadratic fields. J. Cryptol. 1(2), 107–118 (1988). https://doi.org/10.1007/BF02351719
CrossRef
MathSciNet
MATH
Google Scholar
Chavez-Saab, J., Rodríguez-Henríquez, F., Tibouchi, M.: Verifiable Isogeny walks: towards an isogeny-based postquantum VDF. In: AlTawy, R., Hülsing, A. (eds.) SAC 2021. LNCS, vol. 13203, pp. 441–460. Springer, Cham (2022). https://doi.org/10.1007/978-3-030-99277-4_21
CrossRef
Google Scholar
Choudhuri, A.R., Hubáček, P., Kamath, C., Pietrzak, K., Rosen, A., Rothblum, G.N.: PPAD-hardness via iterated squaring modulo a composite. IACR Cryptol. ePrint Arch. 2019, 667 (2019)
Google Scholar
Cini, V., Lai, R.W.F., Malavolta, G.: Lattice-based succinct arguments from vanishing polynomials. In: Handschuh, H., Lysyanskaya, A. (eds.) Advances in Cryptology - CRYPTO 2023. Lecture Notes in Computer Science, pp. 72–105. Springer Nature Switzerland, Cham (2023). https://doi.org/10.1007/978-3-031-38545-2_3
CrossRef
Google Scholar
Cohen, B., Pietrzak, K.: Simple proofs of sequential work. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10821, pp. 451–467. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78375-8_15
CrossRef
Google Scholar
Cohen, B., Pietrzak, K.: The Chia network blockchain. Technical report, Chia Network (2019). https://www.chia.net/assets/ChiaGreenPaper.pdf. Accessed 29 July 2022
Döttling, N., Garg, S., Malavolta, G., Vasudevan, P.N.: Tight verifiable delay functions. In: Galdi, C., Kolesnikov, V. (eds.) SCN 2020. LNCS, vol. 12238, pp. 65–84. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-57990-6_4
CrossRef
Google Scholar
Döttling, N., Lai, R.W.F., Malavolta, G.: Incremental proofs of sequential work. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11477, pp. 292–323. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17656-3_11
CrossRef
Google Scholar
Ephraim, N., Freitag, C., Komargodski, I., Pass, R.: Continuous verifiable delay functions. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12107, pp. 125–154. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45727-3_5
CrossRef
Google Scholar
De Feo, L., Masson, S., Petit, C., Sanso, A.: Verifiable delay functions from supersingular isogenies and pairings. In: Galbraith, S.D., Moriai, S. (eds.) ASIACRYPT 2019. LNCS, vol. 11921, pp. 248–277. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-34578-5_10
CrossRef
Google Scholar
Fiat, A., Shamir, A.: How to prove yourself: practical solutions to identification and signature problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186–194. Springer, Heidelberg (1987). https://doi.org/10.1007/3-540-47721-7_12
CrossRef
Google Scholar
Freitag, C., Pass, R., Sirkin, N.: Parallelizable delegation from LWE. IACR Cryptol. ePrint Arch., p. 1025 (2022)
Google Scholar
Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems. SIAM J. Comput. 18(1), 186–208 (1989)
CrossRef
MathSciNet
MATH
Google Scholar
Hoffmann, C., Hubáček, P., Kamath, C., Klein, K., Pietrzak, K.: Practical statistically sound proofs of exponentiation in any group. In: Dodis, Y., Shrimpton, T. (eds.) Advances in Cryptology – CRYPTO 2022. Lecture Notes in Computer Science, vol. 13508, pp. 1–30. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-15979-4_13
CrossRef
MATH
Google Scholar
Hofheinz, D., Kiltz, E.: The group of signed quadratic residues and applications. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 637–653. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03356-8_37
CrossRef
Google Scholar
Katz, J., Loss, J., Xu, J.: On the security of time-lock puzzles and timed commitments. In: Pass, R., Pietrzak, K. (eds.) TCC 2020, Part III. LNCS, vol. 12552, pp. 390–413. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64381-2_14
CrossRef
MATH
Google Scholar
Lai, R.W.F., Malavolta, G.: Lattice-based timed cryptography. In: Handschuh, H., Lysyanskaya, A. (eds.) Advances in Cryptology - CRYPTO 2023. Lecture Notes in Computer Science, pp. 782–804. Springer Nature Switzerland, Cham (2023). https://doi.org/10.1007/978-3-031-38554-4_25
CrossRef
Google Scholar
Lehmer, D.H.: An extended theory of Lucas’ functions. Ann. Math. 31(3), 419–448 (1930). https://www.jstor.org/stable/1968235
Lennon, M.J.J., Smith, P.J.: LUC: A new public key system. In: Douglas, E.G. (ed.) Ninth IFIP Symposium on Computer Security, pp. 103–117. Elsevier Science Publishers (1993)
Google Scholar
Lenstra, A.K., Wesolowski, B.: Trustworthy public randomness with sloth, unicorn, and trx. IJACT 3(4), 330–343 (2017)
CrossRef
MathSciNet
MATH
Google Scholar
Lipmaa, H.: On Diophantine complexity and statistical zero-knowledge arguments. In: Laih, C.-S. (ed.) ASIACRYPT 2003. LNCS, vol. 2894, pp. 398–415. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-40061-5_26
CrossRef
Google Scholar
Lombardi, A., Vaikuntanathan, V.: Fiat-Shamir for repeated squaring with applications to PPAD-hardness and VDFs. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12172, pp. 632–651. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56877-1_22
CrossRef
Google Scholar
Lucas, E.: Théorie des fonctions numériques simplement périodiques. Am. J. Math. 1(4), 289–321 (1878). https://www.jstor.org/stable/2369373
Lund, C., Fortnow, L., Karloff, H.J., Nisan, N.: Algebraic methods for interactive proof systems. J. ACM 39(4), 859–868 (1992)
CrossRef
MathSciNet
MATH
Google Scholar
Mahmoody, M., Moran, T., Vadhan, S.P.: Publicly verifiable proofs of sequential work. In: ITCS, pp. 373–388. ACM (2013)
Google Scholar
Mahmoody, M., Smith, C., Wu, D.J.: A note on the (Im)possibility of verifiable delay functions in the random oracle model. IACR Cryptol. ePrint Arch. 2019, 663 (2019)
Google Scholar
Malavolta, G., Thyagarajan, S.A.K.: Homomorphic time-lock puzzles and applications. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11692, pp. 620–649. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26948-7_22
CrossRef
Google Scholar
Müller, W.B., Nöbauer, W.: Some remarks on public-key cryptosystems. Studia Sci. Math. Hungar. 16, 71–76 (1981)
MathSciNet
MATH
Google Scholar
Bressoud, D.M.: Factorization and primality testing. Math. Comput. 56(193), 400 (1991)
CrossRef
Google Scholar
Pietrzak, K.: Simple verifiable delay functions. IACR Cryptol. ePrint Arch. 2018, 627 (2018). https://eprint.iacr.org/2018/627/20180720:081000
Pietrzak, K.: Simple verifiable delay functions. In: ITCS. LIPIcs, vol. 124, pp. 1–15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
Google Scholar
Rabin, M.O.: Transaction protection by beacons. J. Comput. Syst. Sci. 27(2), 256–267 (1983)
CrossRef
MathSciNet
MATH
Google Scholar
Ribenboim, P.: My Numbers, My Friends: Popular Lectures on Number Theory. Springer-Verlag, New York (2000)
CrossRef
MATH
Google Scholar
Riesel, H.: Prime Numbers and Computer Methods for Factorization, Progress in Mathematics, vol. 57. Birkhäuser, Basel (1985)
CrossRef
MATH
Google Scholar
Rivest, R., Silverman, R.: Are ’strong’ primes needed for RSA. Cryptology ePrint Archive, Report 2001/007 (2001). https://eprint.iacr.org/2001/007
Rivest, R.L., Shamir, A., Adleman, L.M.: A method for obtaining digital signatures and public-key cryptosystems (reprint). Commun. ACM 26(1), 96–99 (1983)
CrossRef
MATH
Google Scholar
Rivest, R.L., Shamir, A., Wagner, D.A.: Time-lock puzzles and timed-release crypto. Technical report, Massachusetts Institute of Technology (1996)
Google Scholar
Rotem, L., Segev, G.: Generically speeding-up repeated squaring is equivalent to factoring: sharp thresholds for all generic-ring delay functions. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12172, pp. 481–509. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56877-1_17
CrossRef
Google Scholar
Rotem, L., Segev, G., Shahaf, I.: Generic-group delay functions require hidden-order groups. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12107, pp. 155–180. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45727-3_6
CrossRef
Google Scholar
Schindler, P., Judmayer, A., Hittmeir, M., Stifter, N., Weippl, E.R.: RandRunner: distributed randomness from trapdoor VDFs with strong uniqueness. In: 28th Annual Network and Distributed System Security Symposium, NDSS 2021, virtually, 21–25 February 2021. The Internet Society (2021)
Google Scholar
Shani, B.: A note on isogeny-based hybrid verifiable delay functions. IACR Cryptol. ePrint Arch. 2019, 205 (2019)
Google Scholar
Valiant, P.: Incrementally verifiable computation or proofs of knowledge imply time/space efficiency. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 1–18. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78524-8_1
CrossRef
MATH
Google Scholar
Wesolowski, B.: Efficient verifiable delay functions. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11478, pp. 379–407. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17659-4_13
CrossRef
Google Scholar
Wesolowski, B.: Efficient verifiable delay functions. J. Cryptol. 33(4), 2113–2147 (2020). https://doi.org/10.1007/s00145-020-09364-x
CrossRef
MathSciNet
MATH
Google Scholar
Williams, H.C.: A
method of factoring. Math. Comput. 39(159), 225–234 (1982)
MathSciNet
MATH
Google Scholar
Williams, H.C.: Édouard lucas and primality testing. Math. Gaz. 83, 173 (1999)
CrossRef
Google Scholar
Download references
Acknowledgements
We thank Krzysztof Pietrzak and Alon Rosen for several fruitful discussions about this work and the anonymous reviewers of SCN 2022 and TCC 2023 for valuable suggestions.
Pavel Hubáček is supported by the Czech Academy of Sciences (RVO 67985840), by the Grant Agency of the Czech Republic under the grant agreement no. 19-27871X, and by the Charles University project UNCE/SCI/004. Chethan Kamath is supported by Azrieli International Postdoctoral Fellowship, by the European Research Council (ERC) under the European Union’s Horizon Europe research and innovation programme (grant agreement No. 101042417, acronym SPP), and by ISF grant 1789/19.
Volume
14372
Page
336-362
Conference
TCC: Theory of Cryptography
Conference Location
Taipei, Taiwan
Conference Date
2023-11-29 – 2023-12-02
ISBN
ISSN
eISSN
IST-REx-ID
Cite this
Hoffmann C, Hubáček P, Kamath C, Krňák T. (Verifiable) delay functions from Lucas sequences. In: 21st International Conference on Theory of Cryptography. Vol 14372. Springer Nature; 2023:336-362. doi:10.1007/978-3-031-48624-1_13
Hoffmann, C., Hubáček, P., Kamath, C., & Krňák, T. (2023). (Verifiable) delay functions from Lucas sequences. In 21st International Conference on Theory of Cryptography (Vol. 14372, pp. 336–362). Taipei, Taiwan: Springer Nature. https://doi.org/10.1007/978-3-031-48624-1_13
Hoffmann, Charlotte, Pavel Hubáček, Chethan Kamath, and Tomáš Krňák. “(Verifiable) Delay Functions from Lucas Sequences.” In 21st International Conference on Theory of Cryptography, 14372:336–62. Springer Nature, 2023. https://doi.org/10.1007/978-3-031-48624-1_13.
C. Hoffmann, P. Hubáček, C. Kamath, and T. Krňák, “(Verifiable) delay functions from Lucas sequences,” in 21st International Conference on Theory of Cryptography, Taipei, Taiwan, 2023, vol. 14372, pp. 336–362.
Hoffmann C, Hubáček P, Kamath C, Krňák T. 2023. (Verifiable) delay functions from Lucas sequences. 21st International Conference on Theory of Cryptography. TCC: Theory of Cryptography, LNCS, vol. 14372, 336–362.
Hoffmann, Charlotte, et al. “(Verifiable) Delay Functions from Lucas Sequences.” 21st International Conference on Theory of Cryptography, vol. 14372, Springer Nature, 2023, pp. 336–62, doi:10.1007/978-3-031-48624-1_13.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
Google Scholar
ISBN Search