IBM Research welcomes members of the research community to our seminars. To ensure compliance with IBM security guidelines, we request you to contact the seminar host in advance. When you arrive at the Research lab, please provide the host's name to the receptionist.
| The Move to Resilient Botnets | ||||
| Sven Dietrich | On: | 2-Nov-2009 10:00 AM - 11:30 AM | ||
| Stevens Institute | At: | Watson Research Center (Hawthorne), Room 3S-K24 | ||
| Host: | Wietse Venema | |||
Abstract: Botnets have come a long way from the early days of DDoS, moving from simple hierarchical to IRC-based, and finally P2P-based topologies. Various factors have driven the development of botnets forward into the resilient realm. While simple botnets stick to HTTP or IRC for command and control (C&C), resilient botnets feature a better C&C structure, probabilistic delegation, modularization, and code obfuscation. Sophisticated C&C mechanisms such as probabilistic delegation are making detection and mitigation difficult, not only for disruption of the C&C channels, but also for the correlation of attack traffic generated from these botnets. We provide some details of such techniques used in modern botnets and how it impacts attack traffic. Speaker biography: Dr. Sven Dietrich is an assistant professor in the computer science department at Stevens Institute of Technology. Prior to joining Stevens in August 2007, he was a Senior Member of the Technical Staff at CERT Research at Carnegie Mellon University and also held an appointment at the Carnegie Mellon University CyLab, a university-wide cybersecurity research and education initiative. He taught cryptography in the Mathematics and Computer Science Department at Duquesne University in Spring 2007. From 1997 to 2001, he was a senior security architect at the NASA Goddard Space Flight Center, where he observed and analyzed the first distributed denial-of-service attacks against the University of Minnesota in 1999. He taught Mathematics and Computer Science as adjunct faculty at Adelphi University, his alma mater, from 1991 to 1997. His research interests include computer and network security, anonymity, cryptographic protocols, and cryptography. His previous work has included a formal analysis of the secure sockets layer protocol (SSL), intrusion detection, analysis of distributed denial-of-service tools, and the security of IP communications in space. His publications include the book Internet Denial of Service: Attack and Defense Mechanisms (Prentice Hall, 2004), as well as recent articles on botnets. Dr. Dietrich has a Doctor of Arts in Mathematics, a M.S. in Mathematics, and a B.S. in Computer Science and Mathematics from Adelphi University in Garden City, New York. | ||||
| Online Algorithms For Real-Time Relay-Node Detection and Flow Correlation | ||||
| Baris Coskun | On: | 23-Oct-2009 01:00 PM - 02:00 PM | ||
| Polytechnic Institute of NYU | At: | Watson Research Center (Hawthorne), Room 4S-K21 | ||
| Host: | Reiner Sailer | |||
Abstract: Real-time network monitoring often requires continuous processing of high-volume network data streams. In this talk, we first present an efficient online algorithm to detect low-latency relay-nodes in a network in real-time. Detecting relay nodes is important since unexpected relay activity is often associated with network intrusions, such as stepping stone attacks, botnet command and control, etc. In addition to relay-nodes, identifying particular flows, which carry the relay traffic, is critical for attack attribution purposes. It allows us to determine where the attack comes from and where it goes to. Hence, in the second part of the talk, we discuss another online algorithm to identify correlated flows based on real-time packet-timing sketches. | ||||
| BitBlaze: Security via Binary Analysis | ||||
| Dawn Song | On: | 25-Sep-2009 10:00 AM - 11:30 AM | ||
| U.C. Berkeley | At: | Watson Research Center (Hawthorne), Room GN-K35 | ||
| Host: | Mihai Christodorescu | |||
Abstract: In this talk, I will present the BitBlaze project, a new approach to computer security via binary analysis. In particular, BitBlaze focuses on building a unified binary analysis platform and using it to provide novel solutions to a broad spectrum of different security problems. The binary analysis platform is designed to provide an extensible architecture, and combines static and dynamic analysis as well as program verification techniques to satisfy the common needs of security applications. By extracting security-related properties from binary programs directly, BitBlaze provides a new arsenal for a principled, root-cause based approach to computer security. BitBlaze has enabled over a dozen different security applications, such as patch-based exploit generation, automatic generation of vulnerability signatures for defense, and model extraction from browsers (such as IE) for vulnerability discovery. I will give an overview of the BitBlaze project and present some recent results in addressing a number of security problems using BitBlaze. I will also briefly describe a new project, WebBlaze, where we employ experiences learned from BitBlaze to build techniques and tools for vulnerability discovery and defense on the web. Solutions proposed in WebBlaze have been deployed in Google Chrome. For more information, please see http://bitblaze.cs.berkeley.edu and http://webblaze.cs.berkeley.edu. Speaker biography: Dawn Song is an Associate Professor in Computer Science at University of California, Berkeley. She obtained her PhD in Computer Science from UC Berkeley (2002). Prior to joining UC Berkeley, she was an Assistant Professor at Carnegie Mellon University from 2002 to 2007. Her research interest lies in security and privacy issues in computer systems and networks. She is the author of more than 70 research papers in areas ranging from software security, networking security, database security, distributed systems security, to applied cryptography. She is the recipient of various awards including the NSF CAREER Award, the IBM Faculty Award, the George Tallman Ladd Research Award, the Alfred P. Sloan Research Fellowship Award, the Okawa Foundation Research Award, the MIT Technology Review TR-35 Award, and Best Paper Awards in top security conferences. | ||||
| Slaying the Snooping Dragon: Detecting Botnets via Structured Graph Analysis | ||||
| Shishir Nagaraja | On: | 1-Sep-2009 10:00 AM - 12:00 PM | ||
| UIUC | At: | Watson Research Center (Hawthorne), Room 1S-F40 | ||
| Host: | Mihai Christodorescu | |||
Abstract: Botnets are a rapidly emerging information security threat and present a challenging research problem. In the first part of this talk, I shall discuss a real-world attack involving a new type of botnet called the surveillance botnet. Its design employs targeted attacks using a social malware infection strategy and its objective is to compromise secrecy and integrity of information rather than carrying out DDOS attacks. In the second part, I shall present a graph based technique of detecting botnets from among a set of cooperating ISPs or enterprises. Our technique is based on the key feature that individual bots, unlike worms or other malicious hosts, communicate with one another. This lets them carry out sophisticated coordinated activities, but it can also be used as a point of detection.``Graphsplicer'' is an algorithm to localize botnet members based on the unique communication patterns arising from their overlay topologies used for command and control. Early results on synthetic topologies embedded within Internet traffic traces from an ISP's backbone network indicate that our techniques (i) can localize the majority of bots with low false positive rate, and (ii) are resilient to the partial visibility arising from partial deployment of monitoring systems, and measurement inaccuracies arising from partial visibility and dynamics of background traffic. Graphsplicer has a time complexity of O(m n^2) in the worst case, and O(n^2 logn) in most real-world cases. Speaker biography: For more information about Shishir Nagaraja, please see his web page at http://www.hatswitch.org/~sn275/ | ||||
| Deploying Programs and VMs to Satisfy System Security Goals | ||||
| Trent Jaeger | On: | 7-Aug-2009 10:30 AM - 11:30 AM | ||
| Penn State U. | At: | Watson Research Center (Hawthorne), Room 4S-K21 | ||
| Host: | Reiner Sailer | |||
Abstract: When a new program is installed on a system, the aim should be for the installer to ensure that the system security requirements can be correctly enforced. However, current installers update security enforcement in an ad hoc manner, leading to vulnerabilities. These vulnerabilities often impact system security because many programs are entrusted to enforce system security, as well as themselves. In an SELinux/MLS system, over 30 programs are explicitly designated as "trusted" because they are given exceptional access to secret information. Further, many more programs are entrusted to protect their integrity despite handling low integrity inputs. We expect this same problem to appear in the deployment of virtual machines as well. In this talk, we will discuss approaches to deploying programs and VMs in a manner that verifies enforcement of system security requirements. In addition, we will examine the integrity measurement requirements necessary to construct attestations of such enforcement. First, we define the problem of policy compliance, a requirement that one policy (e.g., program policy) comply with a security goal policy (e.g., a system policy). Second, we propose the use of Clark-Wilson integrity as our basis for integrity verification. Third, we use policy compliance and Clark-Wilson integrity as the foundations for guiding comprehensive integrity measurement, with the ultimate aim of integrity proof construction for entire distributed systems. We study these topics in the context of SELinux and the new Xen Security Modules framework. We demonstrate Eclipse-based policy analysis tools and a Xen-based integrity measurement prototype. | ||||
| Black-Box Constructions of Two-Party Protocols | ||||
| Hoeteck Wee | On: | 7-Apr-2009 11:00 AM - 12:30 PM | ||
| Queens College | At: | Watson Research Center (Hawthorne), Room 3N-J21 | ||
| Host: | Rosario Gennaro | |||
Abstract: I will present several black-box constructions of two-party protocols. These include: * constant-round zero-knowledge arguments for any language in NP, constant-round trapdoor commitment scheme, and constant-round parallel coin-tossing from one-way functions; * constant-round malicious oblivious transfer (OT) starting from constant-round semi-honest OT, for both static and adaptive corruptions. Based on joint works with Rafael Pass (Cornell), and with Seung Geol Choi, Dana Dachman-Soled and Tal Malkin (Columbia) | ||||
| Non-malleable Extractors and Symmetric Key Cryptography from Weak Secrets | ||||
| Yevgeniy Dodis | On: | 26-Mar-2009 11:00 AM - 12:30 PM | ||
| NYU | At: | Watson Research Center (Hawthorne), Room GN-K35 | ||
| Host: | Rosario Gennaro | |||
Abstract: We study the question of information-theoretically secure authenticated key agreement from weak secrets. In this setting, Alice and Bob share a n-bit secret W, which might *not* be uniformly random but the adversary has at least k bits of uncertainty about it (formalized using conditional min-entropy). Alice and Bob wish to use W to agree on a nearly uniform secret key R, over a public channel controlled by an *active* adversary Eve. We show that non-interactive (single-message) protocols do not work when k <= n/2, and require poor parameters even when n/2 < k << n. On the other hand, for arbitrary values of k, we design a communication efficient two-message protocol extracting nearly k random bits. This dramatically improves the only previously known protocol of Renner and Wolf [RW03], which required O(s) rounds where s is the security parameter. Our solution takes a new approach by studying and constructing **non-malleable seeded randomness extractors ** --- if an attacker sees a random seed X and comes up with an arbitrarily related seed X', then we bound the relationship between R= Ext(W;X) and R' = Ext(W;X'). We also extend our one-round key agreement protocol to the "fuzzy" setting, where Alice and Bob share "close'' (but not equal) secrets W_A and W_B, and to the Bounded Retrieval Model (BRM) where the size of the secret W is huge. Joint work with Daniel Wichs from STOC 2009. | ||||
| Adaptive Zero-Knowledge Proofs and Adaptively Secure Oblivious Transfer | ||||
| Hila Zarosim | On: | 20-Mar-2009 11:00 AM - 12:30 PM | ||
| Bar-Ilan University | At: | Watson Research Center (Hawthorne), Room GN-K30 | ||
| Host: | Rosario Gennaro | |||
Abstract: In the setting of secure computation, a set of parties wish to securely compute some function of their inputs, in the presence of an adversary. The adversary in question may be static (meaning that it controls a predetermined subset of the parties) or adaptive (meaning that it can choose to corrupt parties during the protocol execution and based on what it sees). In this talk, we study two fundamental questions relating to the basic zero-knowledge and oblivious transfer protocol problems: Adaptive zero-knowledge proofs: We ask whether it is possible to construct adaptive zero-knowledge proofs (with unconditional soundness). Beaver (STOC 1996) showed that known zero-knowledge proofs are not adaptively secure, and in addition showed how to construct zero-knowledge arguments (with computational soundness). Adaptively secure oblivious transfer: All known protocols for adaptively secure oblivious transfer rely on seemingly stronger hardness assumptions than for the case of static adversaries. We ask whether this is inherent, and in particular, whether it is possible to construct adaptively secure oblivious transfer from enhanced trapdoor permutations alone. We provide surprising answers to the above questions, showing that achieving adaptive security is sometimes harder than achieving static security, and sometimes not. First, we show that assuming the existence of one-way functions only, there exists adaptive zero-knowledge proofs for all languages in NP. In order to prove this, we overcome the problem that all adaptive zero-knowledge protocols known until now used equivocal commitments (which would enable an all-powerful prover to cheat). Second, we prove a black-box separation between adaptively secure oblivious transfer and enhanced trapdoor permutations. As a corollary, we derive a black-box separation between adaptively and statically securely oblivious transfer. This is the first black-box separation to relate to adaptive security and thus the first evidence that it is indeed harder to achieve security in the presence of adaptive adversaries than in the presence of static adversaries. | ||||
| Weak Verifiable Random Functions | ||||
| Zvika Brakerski | On: | 12-Mar-2009 11:00 AM - 12:30 PM | ||
| Weizmann Institute | At: | Watson Research Center (Hawthorne), Room GN-K35 | ||
| Host: | Rosario Gennaro | |||
Abstract: Verifiable random functions (VRFs), introduced by Micali, Rabin and Vadhan, are pseudorandom functions in which the owner of the seed produces a public-key that constitutes a commitment to all values of the function. It can then produce, for any input $x$, a proof that the function has been evaluated correctly on $x$, preserving pseudorandomness for all other inputs. No public-key (even a falsely generated one) allows for proving more than one value per input (compare to signature schemes where soundness is only required for legal public-keys). VRFs are both a natural and a useful primitive, and previous works have suggested a variety of constructions and applications. Still, there are many open questions in the study of VRFs, especially their relation to more widely studied cryptographic primitives and constructing them from a wide variety of cryptographic assumptions. In this work we define a natural relaxation of VRFs that we call weak verifiable random functions, where pseudorandomness is required to hold only for randomly selected inputs. We conduct a study of weak VRFs, focusing on applications, constructions, and their relationship to other cryptographic primitives. We show: * Constructions. We present constructions of weak VRFs based on a variety of assumptions, including general assumptions such as (enhanced) trapdoor permutations, as well as constructions based on specific number-theoretic assumptions such as the Diffie-Hellman assumption in bilinear groups. * Separations. Verifiable random functions (both weak and standard) cannot be constructed from one-way permutations in a black-box manner. This constitutes the first result separating (standard) VRFs from any cryptographic primitive. * Applications. Weak VRFs capture the essence of constructing non-interactive zero-knowledge proofs for all NP languages. Joint work with Shafi Goldwasser, Guy Rothblum and Vinod Vaikuntanathan. | ||||
| Establishing Trust in Malicious Systems | ||||
| Jonathon Giffin | On: | 5-Mar-2009 01:00 PM - 02:30 PM | ||
| Georgia Tech | At: | Watson Research Center (Hawthorne), Room 3S-K24 | ||
| Host: | Mihai Christodorescu | |||
Abstract: Large scale cyber attacks, including botnets, rootkits, keyloggers, and spyware, today frequently incorporate malicious operating system components in the form of kernel modules and drivers that have full access to kernel internals. Traditional host-level software protections, such as anti-virus utilities or firewalls, cannot alone continue to address the threats. New, hypervisor-based solutions extract information about the security state of a guest operating system using a technique called virtual machine introspection (VMI). Unfortunately, VMI produces a trust inversion: the security software implemented in the low-level hypervisor relies on trust in higher-level operating system memory integrity. I will present a system, Sentry, that unwinds the backwards trust by created protected memory regions from the unified space of OS memory. Sentry provides kernel memory access control over dynamically-allocated data structures with access decisions based on kernel execution path analysis. Sentry prevents malicious kernel modules and drivers from altering critical data of guest operating systems. Once hypervisor-based security software is able to trust information extracted from guest systems, many security solutions adapt well to the virtualized environment. I will provide an lightning overview of hypervisor-level security research underway at Georgia Tech, including the following projects: Tamper resistant, application-aware firewalling. Detection of system-call interface obfuscation. Forensic analysis and remediation of bot-infected systems. Malware analyzers hidden from the malware itself. Toolkits for security monitoring. Post-attack mobile phone recovery. Speaker biography: Jonathon Giffin is an Assistant Professor who recently joined the Georgia Tech College of Computing in Fall 2006. He earned his Ph.D. from the University of Wisconsin in 2006, where he was a Wisconsin Distinguished Fellow. Also at Wisconsin, he received his B.S. degree in Mathematics in 2000 and his M.S. degree in Computer Sciences in 2002. He enjoys research in software security, operating system security, and attack analysis. His research builds upon techniques from program analysis, formal methods, and operating systems to retrofit security to insecure systems and software. He investigates both defensive systems and attacks against those systems. On the defensive side, he designs new intrusion detection systems that prevent anomalous program execution by constraining execution to a model of expected execution behavior derived from static program analysis. To evaluate the ability of intrusion detectors to actually detect attacks, he then attacks the detectors. Formal analysis of the detectors provides insight into their true attack detection capability and illuminates weaknesses requiring continued research into intrusion detection. | ||||
| Protecting Java from Native Code | ||||
| Prof. Gang Tan | On: | 12-Feb-2009 10:00 AM - 11:15 AM | ||
| (Lehigh University | At: | Watson Research Center (Hawthorne), Room 1N-F28 | ||
| Host: | Martin Hirzel | |||
Abstract: Most software systems are multilingual; that is, they consist of components developed in multiple programming languages. For example, Sun's Java Development Kit 1.6 (JDK) contains around 2 million lines of Java code as well as 800,000 lines of C/C++ code for implementing native methods. It is well known that native methods in Java defeat Java's guarantees of safety and security and are constant sources of software bugs and vulnerabilities. This was confirmed by our recent empirical security study, which identified O(100) bugs in the native code of JDK 1.6. In this talk, we present language-based techniques for ensuring safety and security of Java-C interoperation. The first system, SafeJNI, employs static and dynamic checks to enforce security policies on C code (such as protecting the integrity of the JVM heap). The second system, ILEA, enables existing Java analyzers to understand foreign C code, by automatically extracting an approximate Java specification from C code. Finally, we discuss some ongoing work, including binary rewriting for enforcing security policies on native code. Speaker biography: Gang Tan is an assistant professor of Computer Science and Engineering at Lehigh University. He received his B.E. degree in Computer Science from Tsinghua University in 1999, and his Ph.D. degree from Princeton University in 2005. His research interests are in the areas of programming languages and computer security. | ||||
| Sybil-resilient online content voting | ||||
| Jinyang Li | On: | 9-Jan-2009 10:00 AM - 11:30 AM | ||
| NYU | At: | Watson Research Center (Hawthorne), Room 1S-F40 | ||
| Host: | Catherine Zhang | |||
Abstract: Obtaining user feedback (using votes) is essential in ranking user-generated online content. However, any online voting system is susceptible to the Sybil attack where adversaries can out-vote real users by creating several Sybil identities. In this talk, I will present SumUp, a Sybil-resilient online content rating system that leverages trust networks among users to defend against Sybil attacks with strong security guarantees. SumUp addresses the basic vote aggregation problem of how to aggregate votes from different users in a trust network in the face of Sybil identities casting an arbitrarily large number of bogus votes. We introduce the technique of adaptive vote flow aggregation that allows SumUp to significantly limit the number of bogus votes cast by adversaries to no more than the number of attack edges in the trust network (with high probability). By applying SumUp on the voting trace of Digg (online news voting site), we have detected strong evidence of attack on many articles marked ``popular'' by Digg. Speaker biography: Jinyang Li has been an assistant professor in computer science at New York University since 2006. She is interested in distributed systems and networks, especially how to build reliable large scale systems. Her group is currently working on making peer-to-peer systems more trustworthy and applicable to a variety of applications such as censorship circumvention and cooperative storage systems. With her colleagues at MIT, Jinyang is also leading a project to build a wide are file system, WheelFS, to simplify the construction of distributed applications that handle large amounts of data. WheelFS allows applications to control the performance/consistency tradeoff by embedding semantic cues in file path names to inform WheelFS how it should handle failures and long delays. Jinyang received a Ph.D. from MIT in 2005 and was a postdoctoral researcher at UC Berkeley from 2005-2006. While at MIT, she worked on scalable lookup protocols for large distributed systems and multihop wireless routing. | ||||
| On Constant-Round Concurrent Zero-Knowledge | ||||
| Muthu Venkitasubramaniam | On: | 5-Jan-2009 11:00 AM - 12:30 PM | ||
| Cornell University | At: | Watson Research Center (Hawthorne), Room GN-K35 | ||
| Host: | Rosario Gennaro | |||
Abstract: Loosely speaking, an interactive proof is said to be zero- knowledge if the view of every “efficient” verifier can be “efficiently” simulated. An outstanding open question regarding zero-knowledge is whether constant-round concurrent zero-knowledge proofs exists for non- trivial languages. We answer this question to the affirmative when mod- eling “efficient adversaries” as probabilistic quasi-polynomial time ma- chines (instead of the traditional notion of probabilistic polynomial-time machines). | ||||
| On Cryptography with Auxiliary Input | ||||
| Yael Tauman Kalai | On: | 18-Dec-2008 11:00 AM - 12:30 PM | ||
| Microsoft Research | At: | Watson Research Center (Hawthorne), Room GN-K35 | ||
| Host: | Rosario Gennaro | |||
Abstract: We study the question of designing cryptographic schemes which are secure even if an arbitrary function f(sk) of the secret key is leaked, as long as the secret key sk is still (exponentially) hard to compute from this auxiliary input. We note that this assumption on the auxiliary input is weaker than the more traditional assumption that sk has high min-entropy, and applies even to situations where f(sk) information-theoretically determines the entire secret key sk. As our main result, we construct CPA/CCA secure symmetric encryption schemes that remain secure with exponentially hard-to-invert auxiliary input. We give several applications of such schemes. (1) We construct an average-case obfuscator for the class of point functions, which remains secure with exponentially hard-to-invert auxiliary input, and is reusable. (2) We construct a reusable and robust extractor, which remains secure with exponentially hard-to-invert auxiliary input. Our results rely on the existence of trapdoor permutations, and on a new cryptographic assumption, which is a generalized version of the learning parity-with-noise (LPN) assumption. We stress that this assumption is ``efficiently falsifiable'' and does not quantify over all auxiliary functions f. | ||||
| Delegating Computation: Interactive Proofs for Muggles | ||||
| Guy Rothblum | On: | 26-Nov-2008 11:00 AM - 12:30 PM | ||
| MIT CSAIL | At: | Watson Research Center (Hawthorne), Room 4N-B17 | ||
| Host: | Tal Rabin | |||
Abstract: We consider the question of designing interactive proofs that can be used by real-world parties. Namely, the (honest) prover should be efficient and run in polynomial time, the verifier should be super-efficient and run in nearly-linear time. Such a proof system can be used for delegating computation: a server can run a computation for a client and prove the correctness of the result, where the client can verify the proof very quickly. We construct, for many efficiently computable languages, public-coin interactive proofs where the verifier's running time is quasi-linear, the prover's running time is polynomial, and the communication is poly-logarithmic. In particular, we give such a proof system for any language in (uniform) NC. This result is in the (single prover) interactive proof model, and makes no assumptions on the computational power of the dishonest prover. Our results allow us to make progress on other related questions, such as the length of zero-knowledge proofs for NP languages, the expressive power of public-coin interactive proofs with log-space verifiers, and constructing short efficiently verifiable non-interactive certificates of correctness for computations without resorting to the random oracle model. Previously, the question of efficiently proving the correctness of computations was addressed in the PCP model by BFLS and in computational settings (under assumptions) by Kilian and Micali. Joint work with Shafi Goldwasser and Yael Kalai. | ||||
| Zero-Knowledge Sets with short proofs | ||||
| Dario Fiore | On: | 20-Nov-2008 11:00 AM - 12:30 PM | ||
| Universita' di Catania, Italy | At: | Watson Research Center (Hawthorne), Room GN-K35 | ||
| Host: | Rosario Gennaro | |||
Abstract: Zero Knowledge Sets, introduced by Micali, Rabin and Kilian, allow a prover to commit to a secret set S, in a way such that it can later prove, non interactively, statements of the form x \in S (or x \notin S ), without revealing any further information (on top of what explicitly revealed by the inclusion/exclusion statements above) on S , not even its size. Later, Chase et al. abstracted away the Micali, Rabin and Kilianā€™s construction by introducing an elegant new variant of commitments, that they called (trapdoor) mercurial commitments. Using this primitive, it was shown how to construct zero knowledge sets from a variety of assumptions (both general and number theoretic). In this paper, we introduce the notion of trapdoor q-mercurial commitments (qTMCs), a notion of mercurial commitment that allows the sender to commit to an ordered sequence of exactly q messages, rather than to a single one. Then we show how to construct ZKS from qTMCs and collision resistant hash functions. Then, we present an eļ¬ƒcient realization of qTMCs that is secure under the so called Strong Diļ¬ƒe Hellman assumption, a number theoretic conjecture recently introduced by Boneh and Boyen. Using our scheme as basic building block, we obtain a construction of ZKS that allows for proofs that are much shorter with respect to the best previously known implementations. In particular, for an appropriate choice of the parameters, our proofs are up to 33% shorter, for the case of proofs of membership, and up to 73% shorter, for the case of proofs of non membership. | ||||