The Experts below are selected from a list of 13263 Experts worldwide ranked by ideXlab platform
Shafi Goldwasser - One of the best experts on this subject based on the ideXlab platform.
-
circular and leakage resilient public key encryption under subgroup indistinguishability
International Cryptology Conference, 2010Co-Authors: Zvika Brakerski, Shafi GoldwasserAbstract:The main results of this work are new public-key encryption schemes that, under the quadratic residuosity (QR) assumption (or Paillier's decisional composite residuosity (DCR) assumption), achieve key-dependent message security as well as high resilience to secret key leakage and high resilience to the presence of auxiliary input information. In particular, under what we call the subgroup indistinguishability assumption, of which the QR and DCR are special cases, we can construct a scheme that has: - Key-dependent message (circular) security. Achieves security even when encrypting affine Functions of its own secret key (in fact, w.r.t. affine "key-cycles" of predefined length). Our scheme also meets the requirements for extending key-dependent message security to broader classes of Functions beyond affine Functions using previous techniques of Brakerski et al. or Barak et al. - Leakage resiliency. Remains secure even if any adversarial low-entropy (efficiently Computable) Function of the secret key is given to the adversary. A proper selection of parameters allows for a "leakage rate" of (1 - o(1)) of the length of the secret key. - Auxiliary-input security. Remains secure even if any sufficiently hard to invert (efficiently Computable) Function of the secret key is given to the adversary. Our scheme is the first to achieve key-dependent security and auxiliary-input security based on the DCR and QR assumptions. Previous schemes that achieved these properties relied either on the DDH or LWE assumptions. The proposed scheme is also the first to achieve leakage resiliency for leakage rate (1-o(1)) of the secret key length, under the QR assumption. We note that leakage resilient schemes under the DCR and the QR assumptions, for the restricted case of composite modulus product of safe primes, were implied by the work of Naor and Segev, using hash proof systems. However, under the QR assumption, known constructions of hash proof systems only yield a leakage rate of o(1) of the secret key length.
-
circular and leakage resilient public key encryption under subgroup indistinguishability or quadratic residuosity strikes back
Other University Web Domain, 2010Co-Authors: Zvika Brakerski, Shafi GoldwasserAbstract:The main results of this work are new public-key encryp- tion schemes that, under the quadratic residuosity (QR) assumption (or Paillier's decisional composite residuosity (DCR) assumption), achieve key-dependent message security as well as high resilience to secret key leakage and high resilience to the presence of auxiliary input information. In particular, under what we call the subgroup indistinguishability as- sumption, of which the QR and DCR are special cases, we can construct as cheme that has: - Key-dependent message (circular) security. Achieves security even when encrypting affine Functions of its own secret key (in fact, w.r.t. affine "key-cycles" of predefined length). Our scheme also meets the requirements for extending key-dependent message secu- rity to broader classes of Functions beyond affine Functions using previous techniques of Brakerski et al. or Barak et al. - Leakage resiliency. Remains secure even if any adversarial low- entropy (efficiently Computable) Function of the secret key is given to the adversary. A proper selection of parameters allows for a "leakage rate" of (1 − o(1)) of the length of the secret key. - Auxiliary-input security. Remains secure even if any sufficiently hard to invert(efficiently Computable) Function of the secret key is given to the adversary. Our scheme is the first to achieve key-dependent security and auxiliary- input security based on the DCR and QR assumptions. Previous schemes that achieved these properties relied either on the DDH or LWE assump- tions. The proposed scheme is also the first to achieve leakage resiliency for leakage rate (1−o(1)) of the secret key length, under the QR assump- tion. We note that leakage resilient schemes under the DCR and the QR assumptions, for the restricted case of composite modulus product of safe primes, were implied by the work of Naor and Segev, using hash proof systems. However, under the QR assumption, known constructions of hash proof systems only yield a leakage rate of o(1) of the secret key length.
-
circular and leakage resilient public key encryption under subgroup indistinguishability or quadratic residuosity strikes back
IACR Cryptology ePrint Archive, 2010Co-Authors: Zvika Brakerski, Shafi GoldwasserAbstract:The main results of this work are new public-key encryption schemes that, under the quadratic residuosity (QR) assumption (or Paillier’s decisional composite residuosity (DCR) assumption), achieve key-dependent message security as well as high resilience to secret key leakage and high resilience to the presence of auxiliary input information. In particular, under what we call the subgroup indistinguishability assumption, of which the QR and DCR are special cases, we can construct a scheme that has: • Key-dependent message (circular) security. Achieves security even when encrypting affine Functions of its own secret key (in fact, w.r.t. affine “key-cycles” of predefined length). Our scheme also meets the requirements for extending key-dependent message security to broader classes of Functions beyond affine Functions using previous techniques of [BGK, ePrint09] or [BHHI, Eurocrypt10]. • Leakage resiliency. Remains secure even if any adversarial low-entropy (efficiently Computable) Function of the secret key is given to the adversary. A proper selection of parameters allows for a “leakage rate” of (1− o(1)) of the length of the secret key. • Auxiliary-input security. Remains secure even if any sufficiently hard to invert (efficiently Computable) Function of the secret key is given to the adversary. Our scheme is the first to achieve key-dependent security and auxiliary-input security based on the DCR and QR assumptions. Previous schemes that achieved these properties relied either on the DDH or LWE assumptions. The proposed scheme is also the first to achieve leakage resiliency for leakage rate (1 − o(1)) of the secret key length, under the QR assumption. We note that leakage resilient schemes under the DCR and the QR assumptions, for the restricted case of composite modulus product of safe primes, were implied by the work of [NS, Crypto09], using hash proof systems. However, under the QR assumption, known constructions of hash proof systems only yield a leakage rate of o(1) of the secret key length. ∗Weizmann Institute of Science, zvika.brakerski@weizmann.ac.il. †Weizmann Institute of Science and Massachusetts Institute of Technology, shafi@theory.csail.mit.edu.
Zvika Brakerski - One of the best experts on this subject based on the ideXlab platform.
-
circular and leakage resilient public key encryption under subgroup indistinguishability
International Cryptology Conference, 2010Co-Authors: Zvika Brakerski, Shafi GoldwasserAbstract:The main results of this work are new public-key encryption schemes that, under the quadratic residuosity (QR) assumption (or Paillier's decisional composite residuosity (DCR) assumption), achieve key-dependent message security as well as high resilience to secret key leakage and high resilience to the presence of auxiliary input information. In particular, under what we call the subgroup indistinguishability assumption, of which the QR and DCR are special cases, we can construct a scheme that has: - Key-dependent message (circular) security. Achieves security even when encrypting affine Functions of its own secret key (in fact, w.r.t. affine "key-cycles" of predefined length). Our scheme also meets the requirements for extending key-dependent message security to broader classes of Functions beyond affine Functions using previous techniques of Brakerski et al. or Barak et al. - Leakage resiliency. Remains secure even if any adversarial low-entropy (efficiently Computable) Function of the secret key is given to the adversary. A proper selection of parameters allows for a "leakage rate" of (1 - o(1)) of the length of the secret key. - Auxiliary-input security. Remains secure even if any sufficiently hard to invert (efficiently Computable) Function of the secret key is given to the adversary. Our scheme is the first to achieve key-dependent security and auxiliary-input security based on the DCR and QR assumptions. Previous schemes that achieved these properties relied either on the DDH or LWE assumptions. The proposed scheme is also the first to achieve leakage resiliency for leakage rate (1-o(1)) of the secret key length, under the QR assumption. We note that leakage resilient schemes under the DCR and the QR assumptions, for the restricted case of composite modulus product of safe primes, were implied by the work of Naor and Segev, using hash proof systems. However, under the QR assumption, known constructions of hash proof systems only yield a leakage rate of o(1) of the secret key length.
-
circular and leakage resilient public key encryption under subgroup indistinguishability or quadratic residuosity strikes back
Other University Web Domain, 2010Co-Authors: Zvika Brakerski, Shafi GoldwasserAbstract:The main results of this work are new public-key encryp- tion schemes that, under the quadratic residuosity (QR) assumption (or Paillier's decisional composite residuosity (DCR) assumption), achieve key-dependent message security as well as high resilience to secret key leakage and high resilience to the presence of auxiliary input information. In particular, under what we call the subgroup indistinguishability as- sumption, of which the QR and DCR are special cases, we can construct as cheme that has: - Key-dependent message (circular) security. Achieves security even when encrypting affine Functions of its own secret key (in fact, w.r.t. affine "key-cycles" of predefined length). Our scheme also meets the requirements for extending key-dependent message secu- rity to broader classes of Functions beyond affine Functions using previous techniques of Brakerski et al. or Barak et al. - Leakage resiliency. Remains secure even if any adversarial low- entropy (efficiently Computable) Function of the secret key is given to the adversary. A proper selection of parameters allows for a "leakage rate" of (1 − o(1)) of the length of the secret key. - Auxiliary-input security. Remains secure even if any sufficiently hard to invert(efficiently Computable) Function of the secret key is given to the adversary. Our scheme is the first to achieve key-dependent security and auxiliary- input security based on the DCR and QR assumptions. Previous schemes that achieved these properties relied either on the DDH or LWE assump- tions. The proposed scheme is also the first to achieve leakage resiliency for leakage rate (1−o(1)) of the secret key length, under the QR assump- tion. We note that leakage resilient schemes under the DCR and the QR assumptions, for the restricted case of composite modulus product of safe primes, were implied by the work of Naor and Segev, using hash proof systems. However, under the QR assumption, known constructions of hash proof systems only yield a leakage rate of o(1) of the secret key length.
-
circular and leakage resilient public key encryption under subgroup indistinguishability or quadratic residuosity strikes back
IACR Cryptology ePrint Archive, 2010Co-Authors: Zvika Brakerski, Shafi GoldwasserAbstract:The main results of this work are new public-key encryption schemes that, under the quadratic residuosity (QR) assumption (or Paillier’s decisional composite residuosity (DCR) assumption), achieve key-dependent message security as well as high resilience to secret key leakage and high resilience to the presence of auxiliary input information. In particular, under what we call the subgroup indistinguishability assumption, of which the QR and DCR are special cases, we can construct a scheme that has: • Key-dependent message (circular) security. Achieves security even when encrypting affine Functions of its own secret key (in fact, w.r.t. affine “key-cycles” of predefined length). Our scheme also meets the requirements for extending key-dependent message security to broader classes of Functions beyond affine Functions using previous techniques of [BGK, ePrint09] or [BHHI, Eurocrypt10]. • Leakage resiliency. Remains secure even if any adversarial low-entropy (efficiently Computable) Function of the secret key is given to the adversary. A proper selection of parameters allows for a “leakage rate” of (1− o(1)) of the length of the secret key. • Auxiliary-input security. Remains secure even if any sufficiently hard to invert (efficiently Computable) Function of the secret key is given to the adversary. Our scheme is the first to achieve key-dependent security and auxiliary-input security based on the DCR and QR assumptions. Previous schemes that achieved these properties relied either on the DDH or LWE assumptions. The proposed scheme is also the first to achieve leakage resiliency for leakage rate (1 − o(1)) of the secret key length, under the QR assumption. We note that leakage resilient schemes under the DCR and the QR assumptions, for the restricted case of composite modulus product of safe primes, were implied by the work of [NS, Crypto09], using hash proof systems. However, under the QR assumption, known constructions of hash proof systems only yield a leakage rate of o(1) of the secret key length. ∗Weizmann Institute of Science, zvika.brakerski@weizmann.ac.il. †Weizmann Institute of Science and Massachusetts Institute of Technology, shafi@theory.csail.mit.edu.
Daniel Marx - One of the best experts on this subject based on the ideXlab platform.
-
tight bounds for planar strongly connected steiner subgraph with fixed number of terminals and extensions
arXiv: Data Structures and Algorithms, 2019Co-Authors: Rajesh Chitnis, Andreas Emil Feldmann, Mohammadtaghi Hajiaghayi, Daniel MarxAbstract:(see paper for full abstract) Given a vertex-weighted directed graph $G=(V,E)$ and a set $T=\{t_1, t_2, \ldots t_k\}$ of $k$ terminals, the objective of the SCSS problem is to find a vertex set $H\subseteq V$ of minimum weight such that $G[H]$ contains a $t_{i}\rightarrow t_j$ path for each $i\neq j$. The problem is NP-hard, but Feldman and Ruhl [FOCS '99; SICOMP '06] gave a novel $n^{O(k)}$ algorithm for the SCSS problem, where $n$ is the number of vertices in the graph and $k$ is the number of terminals. We explore how much easier the problem becomes on planar directed graphs: - Our main algorithmic result is a $2^{O(k)}\cdot n^{O(\sqrt{k})}$ algorithm for planar SCSS, which is an improvement of a factor of $O(\sqrt{k})$ in the exponent over the algorithm of Feldman and Ruhl. - Our main hardness result is a matching lower bound for our algorithm: we show that planar SCSS does not have an $f(k)\cdot n^{o(\sqrt{k})}$ algorithm for any Computable Function $f$, unless the Exponential Time Hypothesis (ETH) fails. The following additional results put our upper and lower bounds in context: - In general graphs, we cannot hope for such a dramatic improvement over the $n^{O(k)}$ algorithm of Feldman and Ruhl: assuming ETH, SCSS in general graphs does not have an $f(k)\cdot n^{o(k/\log k)}$ algorithm for any Computable Function $f$. - Feldman and Ruhl generalized their $n^{O(k)}$ algorithm to the more general Directed Steiner Network (DSN) problem; here the task is to find a subgraph of minimum weight such that for every source $s_i$ there is a path to the corresponding terminal $t_i$. We show that, assuming ETH, there is no $f(k)\cdot n^{o(k)}$ time algorithm for DSN on acyclic planar graphs.
-
complexity of counting subgraphs only the boundedness of the vertex cover number counts
Foundations of Computer Science, 2014Co-Authors: Radu Curticapean, Daniel MarxAbstract:For a class C of graphs, #Sub(C) is the counting problem that, given a graph H from C and an arbitrary graph G, asks for the number of subgraphs of G isomorphic to H. It is known that if C has bounded vertex-cover number (equivalently, the size of the maximum matching in C is bounded), then #Sub(C) is polynomial-time solvable. We complement this result with a corresponding lower bound: if C is any recursively enumerable class of graphs with unbounded vertex-cover number, then #Sub(C) is #W[1]-hard parameterized by the size of H and hence not polynomial-time solvable and not even fixed-parameter tractable, unless FPT is equal to #W[1]. As a first step of the proof, we show that counting k-matchings in bipartite graphs is #W[1]-hard. Recently, Curticapean [ICALP 2013] proved the #W[1]-hardness of counting k-matchings in general graphs, our result strengthens this statement to bipartite graphs with a considerably simpler proof and even shows that, assuming the Exponential Time Hypothesis (ETH), there is no f(k)*no(k/log(k)) time algorithm for counting k-matchings in bipartite graphs for any Computable Function f. As a consequence, we obtain an independent and somewhat simpler proof of the classical result of Flum and Grohe [SICOMP 2004] stating that counting paths of length k is #W[1]-hard, as well as a similar almost-tight ETH-based lower bound on the exponent.
-
complexity of counting subgraphs only the boundedness of the vertex cover number counts
arXiv: Computational Complexity, 2014Co-Authors: Radu Curticapean, Daniel MarxAbstract:For a class $\mathcal{H}$ of graphs, #Sub$(\mathcal{H})$ is the counting problem that, given a graph $H\in \mathcal{H}$ and an arbitrary graph $G$, asks for the number of subgraphs of $G$ isomorphic to $H$. It is known that if $\mathcal{H}$ has bounded vertex-cover number (equivalently, the size of the maximum matching in $\mathcal{H}$ is bounded), then #Sub$(\mathcal{H})$ is polynomial-time solvable. We complement this result with a corresponding lower bound: if $\mathcal{H}$ is any recursively enumerable class of graphs with unbounded vertex-cover number, then #Sub$(\mathcal{H})$ is #W[1]-hard parameterized by the size of $H$ and hence not polynomial-time solvable and not even fixed-parameter tractable, unless FPT = #W[1]. As a first step of the proof, we show that counting $k$-matchings in bipartite graphs is #W[1]-hard. Recently, Curticapean [ICALP 2013] proved the #W[1]-hardness of counting $k$-matchings in general graphs; our result strengthens this statement to bipartite graphs with a considerably simpler proof and even shows that, assuming the Exponential Time Hypothesis (ETH), there is no $f(k)n^{o(k/\log k)}$ time algorithm for counting $k$-matchings in bipartite graphs for any Computable Function $f(k)$. As a consequence, we obtain an independent and somewhat simpler proof of the classical result of Flum and Grohe [SICOMP 2004] stating that counting paths of length $k$ is #W[1]-hard, as well as a similar almost-tight ETH-based lower bound on the exponent.
-
tight bounds for planar strongly connected steiner subgraph with fixed number of terminals and extensions
Symposium on Discrete Algorithms, 2014Co-Authors: Rajesh Chitnis, Mohammadtaghi Hajiaghayi, Daniel MarxAbstract:Given a vertex-weighted directed graph G = (V, E) and a set T = {t1, t2, ... tk} of k terminals, the objective of the Strongly Connected Steiner Subgraph (SCSS) problem is to find a vertex set H ⊆ V of minimum weight such that G[H] contains a ti → tj path for each i ≠ j. The problem is NP-hard, but Feldman and Ruhl (FOCS '99; SICOMP '06) gave a novel nO(k) algorithm for the SCSS problem, where n is the number of vertices in the graph and k is the number of terminals. We explore how much easier the problem becomes on planar directed graphs. • Our main algorithmic result is a 2O(k log k) · nO(√k) algorithm for planar SCSS, which is an improvement of a factor of O(√k) in the exponent over the algorithm of Feldman and Ruhl. • Our main hardness result is a matching lower bound for our algorithm: we show that planar SCSS does not have an f(k) · no(√k) algorithm for any Computable Function f, unless the Exponential Time Hypothesis (ETH) fails. The algorithm eventually relies on the excluded grid theorem for planar graphs, but we stress that it is not simply a straightforward application of treewidth-based techniques: we need several layers of abstraction to arrive to a problem formulation where the speedup due to planarity can be exploited. To obtain the lower bound matching the algorithm, we need a delicate construction of gadgets arranged in a grid-like fashion to tightly control the number of terminals in the created instance. The following additional results put our upper and lower bounds in context: • Our 2O(k log k) · nO(√k) algorithm for planar directed graphs can be generalized to graphs excluding a fixed minor. • In general graphs, we cannot hope for such a dramatic improvement over the nO(k) algorithm of Feldman and Ruhl: assuming ETH, SCSS in general graphs does not have an f(k) · no(k/logk) algorithm for any Computable Function f. • Feldman and Ruhl generalized their nO(k) algorithm to the more general Directed Steiner Forest (DSF) problem; here the task is to find a subgraph of minimum weight such that for every source si there is a path to the corresponding terminal ti. We show that that, assuming ETH, there is no f(k) · no(k) time algorithm for DSF on acyclic planar graphs.
Apoloniusz Tyszka - One of the best experts on this subject based on the ideXlab platform.
-
mupad codes which implement limit Computable Functions that cannot be bounded by any Computable Function
Federated Conference on Computer Science and Information Systems, 2014Co-Authors: Apoloniusz TyszkaAbstract:Let E{inn} = {x k = 1, x i + x j = x k , x i · x j = x k : i, j, k ∈ {1, …, n}}. For a positive integer n, let f (n) denote the smallest non-negative integer b such that for each system S ⊆ E n with a solution in non-negative integers x 1 , …, x n there exists a solution of S in non-negative integers not greater than b. We prove that if a Function Γ : ℕ \ {0} → ℕ is Computable, then f dominates Γ i.e. there exists a positive integer m such that Γ(n) n with a solution in {0, …, m − 1}n there exists a solution of S in {0, …, b}n. Then, equations and equation We present an infinite loop in MuPAD which takes as input a positive integer n and returns g(n,m) on the m-th iteration.
-
a Function f n 0 n 0 that cannot be bounded by a Computable Function and an infinite loop in mupad such that it takes as input a positive integer n returns non negative integers g n m m 1 2 3 and f n g n m for any m f n
2013Co-Authors: Apoloniusz TyszkaAbstract:For a positive integer n, let f(n) denote the smallest non-negative integer b such that for each system S \subseteq {x_k=1,x_i+x_j=x_k,x_i*x_j=x_k: i,j,k \in {1,...,n}} with a solution in non-negative integers x_1,...,x_n, there exists a solution of S in {0,...,b}^n. We prove that the Function f is strictly increasing and dominates all Computable Functions. We present an infinite loop in MuPAD which takes as input a positive integer n and returns a non-negative integer on each iteration. Let g(n,m) denote the number returned on the m-th iteration, if n is taken as input. Then, g(n,m) \leq m-1, 0=g(n,1) N that cannot be bounded by any Computable Function. This code takes as input a non-negative integer n, immediately returns 0, and computes a system S of polynomial equations. If the loop terminates for S, then the next instruction is executed and returns \xi(n).
-
mupad codes which implement limit Computable Functions that cannot be bounded by any Computable Function
arXiv: Computational Complexity, 2013Co-Authors: Apoloniusz TyszkaAbstract:For a positive integer n, let f(n) denote the smallest non-negative integer b such that for each system S \subseteq {x_k=1,x_i+x_j=x_k,x_i*x_j=x_k: i,j,k \in {1,...,n}} with a solution in non-negative integers x_1,...,x_n, there exists a solution of S in {0,...,b}^n. We prove that the Function f is strictly increasing and dominates all Computable Functions. We present an infinite loop in MuPAD which takes as input a positive integer n and returns a non-negative integer on each iteration. Let g(n,m) denote the number returned on the m-th iteration, if n is taken as input. Then, g(n,m) \leq m-1, 0=g(n,1)<1=g(n,2) \leq g(n,3) \leq g(n,4) \leq ... and g(n,f(n))
-
does there exist an algorithm which to each diophantine equation assigns an integer which is greater than the number heights of integer solutions if these solutions form a finite set
arXiv: Logic, 2011Co-Authors: Apoloniusz TyszkaAbstract:Let E_n={x_i=1, x_i+x_j=x_k, x_i \cdot x_j=x_k: i,j,k \in {1,...,n}}. If Matiyasevich's conjecture on finite-fold Diophantine representations is true, then for every Computable Function f:N->N there is a positive integer m(f) such that for each integer n>=m(f) there exists a system S \subseteq E_n which has at least f(n) and at most finitely many solutions in integers x_1,...,x_n. This conclusion contradicts to the author's conjecture on integer arithmetic, which implies that the heights of integer solutions to a Diophantine equation are computably bounded, if these solutions form a finite set.
-
a hypothetical upper bound for the solutions of a diophantine equation with a finite number of solutions
arXiv: Number Theory, 2009Co-Authors: Apoloniusz TyszkaAbstract:We conjecture that if a system S \subseteq {x_i=1, x_i+x_j=x_k, x_i \cdot x_j=x_k: i,j,k \in {1,...,n}} has only finitely many solutions in integers x_1,...,x_n, then each such solution (x_1,...,x_n) satisfies |x_1|,...,|x_n| \leq 2^{2^{n-1}}. By the conjecture, if a Diophantine equation has only finitely many solutions in integers (non-negative integers, rationals), then their heights are bounded from above by a Computable Function of the degree and the coefficients of the equation. The conjecture implies that the set of Diophantine equations which have infinitely many solutions in integers (non-negative integers) is recursively enumerable. The conjecture stated for an arbitrary Computable bound instead of 2^{2^{n-1}} remains in contradiction to Matiyasevich's conjecture that each recursively enumerable set M \subseteq {\mathbb N}^n has a finite-fold Diophantine representation.
Pietro Ursino - One of the best experts on this subject based on the ideXlab platform.
-
formative processes with applications to the decision problem in set theory ii powerset and singleton operators finiteness predicate
Information & Computation, 2014Co-Authors: Domenico Cantone, Pietro UrsinoAbstract:In this paper we solve the satisfiability problem for the quantifier-free fragment of set theory MLSSPF involving in addition to the basic Boolean set operators of union, intersection, and difference, also the powerset and singleton operators, and a finiteness predicate. The more restricted fragment obtained by dropping the finiteness predicate has been shown to have a solvable satisfiability problem in a previous paper, by establishing for it a small model property. We exploit the latter decision result for dealing also with the finiteness predicate (and therefore with the infiniteness predicate too) and prove a small witness-model property for MLSSPF, asserting that any model for a satisfiable formula @F with m distinct variables of the fragment of our interest admits a finite representation bounded by c(m), where c is a suitable Computable Function. Since such candidate representations are finitely many, their number does not exceed a known bound, and it can be recognized algorithmically whether they indeed represent a(n infinite) model for the input formula, the decidability of the satisfiability problem for MLSSPF follows.
-
formative processes with applications to the decision problem in set theory i powerset and singleton operators
Information & Computation, 2002Co-Authors: Domenico Cantone, Pietro UrsinoAbstract:This paper introduces formative processes, composed by transitive partitions. Given a family F of sets, a formative process ending in the Venn partition e of F is shown to exist. Sufficient criteria are also singled out for a transitive partition to model (via a Function from set variables to unions of sets in the partition) all set-literals modeled by e. On the basis of such criteria a procedure is designed that mimics a given formative process by another where sets have finite rank bounded by C (|e|), with C a specific Computable Function. As a by-product, one of the core results on decidability in Computable set theory is rediscovered, namely the one that regards the satisfiability of unquantified set-theoretic formulae involving Boolean operators, the singleton-former, and the powerset operator. The method described (which is able to exhibit a set-solution when the answer is affirmative) can be extended to solve the satisfiability problem for broader fragments of set theory.