A DIAGNOSTIC EXPERT SYSTEM TO OVERCOME CONSTRUCTION PROBLEMS IN RIGID HIGHWAY PAVEMENT

Constructing highway pavements faces complex problems, which are affected by multiple factors, where solution is nearly impossible without expert assistance. Diagnosing such construction problems and suggesting most suitable cost efficient solutions requires significant engineering expertise, which might not be available in all construction sites due to inadequate resource and remote locations. Developing an expert system in this domain is a very effective way to help novice engineers to overcome these problems and to learn about them. Moreover, the system can be used as an archive to document engineering knowledge and to share expertise among the experts in this domain. This article describes the development and evaluation stages of such a system, including knowledge acquisition, knowledge representation, system building, and system verification and validation. The initial knowledge is acquired from literature reviews. More expert knowledge is elicited through interviews and questionnaires. This knowledge is documented, analyzed, represented, and converted to computer software using the Visual Basic programming language and the system is called ES-CCPRHP. The system has been verified and validated in three ways: by extensive testing, comparison between system performance and expert reasoning, and case study. It can therefore be employed with confidence by end users.

Introduction
Rapid urbanization and increase in population create a high demand for infrastructure to transport products, raw materials, and people faster and safer between localities (Mulungye et al. 2007;Syamsunur et al. 2011). Construction of a highway system as a part of public infrastructure is a significant way for any country to improve and boost economy (Chou, Tseng 2011;Mulungye et al. 2007;Santos et al. 2010).
During the construction of rigid pavements, highway engineers face many problems that they must decide the controlling measures. The expected problems range from mildly disruptive to financially catastrophic. Generally, these problems affect the quality of the construction and increase initial cost. Experts can control and solve these problems using their tacit knowledge (Miller et al. 2007). However, novice engineers cannot overcome such problems, suggest suitable solutions, avoid their causes, and prevent the same problems from occurring in other parts of the work. Transfer of expertise from experts to novices is difficult in the domain of construction (Persson, Landin 2007). Therefore, there is a need for a system in which experts could share their experience with other engineers both during a project and afterward. If no such transfer of expertise and knowledge occurs, the novices may repeat the mistakes that the experts have learned how to avoid (Persson, Landin 2007). Documentation, classification and computerization of these problems, their causes, solutions, and preventive actions can be very helpful for controlling and preventing them. This paper describes the development of an expert system that can be used by novice engineers on rigid highway pavement construction sites to control the problems that they encounter. The system can also be used as an instructional tool for interested highway engineers. In addition, the system can archive and organize raw knowledge from experts for use by all engineers working in this field. Domain experts can use the system to share experiences. The proposed system is supported by a Geographic Information System (GIS) to provide location, weather, and traffic information.
Expert systems are used to overcome problems in fields from assessment to engineering consulting (Ruiz-Mezcua et al. 2011) by employing human expertise in different domains (Qian et al. 2005). Expert systems can be used in any field (Ooshaksaraie et al. 2012). Therefore, using expert systems to solve sophisticated engineering problems that require a significant amount of experience is very common, and researchers have developed many systems for use in different fields (Park et al. 2010).
In highway construction industry, many expert systems were developed in the domain of design and maintenance and rehabilitation, but to author's knowledge, no such systems were developed for pavement construction.
In design stage, Syamsunur et al. (2011) developed an expert system for route selection that uses GIS techniques and opinions of human experts. This system could be considered as a new version of the system developed by Mohsen and Crower (1991). Teh et al. (2005) developed an expert system named RC-MMS, which supports designers in material selection for highway pavements (Teh et al. 2005). This system is similar to the system developed by Hozayen and Haas (1992). Deprizon developed an expert system to assist engineers in the structural design of flexible highway pavements. The system uses the American Association for State Highways and Transportation Officials (AASHTO) standards and human expertise acquired from domain experts to calculate the minimum thickness of the layers of flexible highway pavements (Deprizon et al. 2009). Goh (1993) developed an advisory expert system to simulate the designer procedure in design of structural layers of asphalt pavements based on the available information of materials, traffic and area conditions. Khedr and Mikhail (1996) developed an expert system named EXPAVE to provide assistance to the novice designers in flexible pavements during the design stage. EXPAVE is also capable of predicting the structural performance of the existing pavements and enable designing of the overlays (Khedr, Mikhail 1996).
In the domain of pavement management, Kaur and Tekkedil (2000) developed a fuzzy expert system, which employs the information about the materials used, thickness of the flexible pavement layers, traffic characteristics, and road age to predict the pavement performance in the form of rut depth. Kuprenas et al. (1995) developed a forward-chaining rule-based expert system to identify failure causes in flexible pavements. Tsao et al. (1994) developed a vision expert system to diagnose the distresses in rigid highway pavements without human interaction based on the images of the distresses. Lan et al. (1993) developed an expert system named PDS (Pavement Distress System) to diagnose distresses of flexible pavement based on the expertise of Taiwanese experts. Other expert systems were developed in the domain of pavement maintenance and rehabilitation management as classified by Ismail (2009a, b).
The current study presents the development stages of the ES-CCPRHP, which is an expert system that controls construction problems in rigid highway pavements. Prior to the development process, the need for such a system was determined from a literature review and validated by a questionnaire survey. The first stage involved knowledge acquisition from written sources and from domain experts via interviews and questionnaires. The acquired knowledge was classified under the supervision of domain experts, after which the classified knowledge was represented in the form of rules. The third stage involved building the system by coding the rules using Visual Basic. In the fourth stage, the system was verified and validated by unit and integrated testing, user satisfaction testing, behavior comparison between the system and experts, and case study. The developed system can be used with confidence and easily updated.

Rigid pavement construction
Construction of rigid pavements process is sophisticated, and involves many activities like concrete producing, placing, spreading, compacting, finishing, texturing, curing, protecting, jointing, testing, and other sub-activities. In addition, this process is performed over large areas, outdoors, and under miscellaneous conditions. Therefore, problems are very usual during construction (O'Flaherty 1988;Oglesby, Hicks 1982).
In fact, the same materials, which are, cement, sand, aggregate, water and reinforcement, are used to prepare the mix which is used in the construction of rigid pavements. The obtained slab sometimes behaves and looks good, and other times that same slab can exhibit bad qualities. There is no simple answer to explain these differences in the obtained products, but major contributing factors that can be summarized as follows ( 1) Over the years, the engineers and contractors have had to deal with major changes in methods of construction. There is ever increasing difficulty to find staff with the necessary skill and experience able to carry out concreting operations on site. Computerized design methods move the engineers even further from practical realities. It is still easier to assess and test material products than its construction practices. 2) Most of concrete today is manufactured off the job site and away from the direct control of the resident engineer (which is a ready mixed concrete). This has produced another contractual and communications interface, where misunderstandings and mistakes may occur.
3) The aspect of environmental protection and energy saving has led to greater planning restriction on cement and aggregate material processing and pressed to use by-products such as pulverized fuel ash, ground granulated slag and silica fume, often of unknown and variable quality. Again, the lack of experience, proper understanding, and control over the use of these materials can lead to problems. 4) Adverse climatic conditions may influence the construction operation and then affect the quality desired. 5) Bad preparation and scheduling at the site can cause interruption among the construction operation stages. The experts can manage the operation and overcome the problems faced during construction, but the novice engineers need support to do that.
Cracking is one of the major problems encountered in rigid pavements. Different types of cracks are very common in highway pavements. Crack is a complete or incomplete separation of concrete into two or more parts produced by breaking or fracturing (ACI Committee 116R-00 2000). Cracking can be classified into plastic concrete cracking and cracking of hardened concrete. Cracking of plastic concrete involves cracks occurring at the surface of fresh concrete during the interval after concrete placing (when it is possible to be re-moulded) and before concrete hardening (ACI Committee 116R-00 2000). This interval may range from 1 hour to 12 hours depending on air temperature, water content in mixture, and use of accelerators or retarders in mixture. On the other hand, cracking of hardened concrete occurs due to shrinkage of concrete. Problems involved in this pattern of cracking could be considered as a construction problem if they occur before opening the road for the traffic.
Restraint of pavement can cause cracking in two patterns that are cracks within slab and cracks near joints. Cracking includes the following types: 1) Diagonal shallow cracks; 2) Craze cracks; 3) Transverse and oblique cracks; 4) Longitudinal cracks; 5) Corner cracks (D-cracks); 6) Transverse and diagonal cracks at transverse joints; 7) Longitudinal cracks at longitudinal joints; 8) Cracks at the intersection of joints. Table 1 abstracts the causes of the crack generation.

The need for the proposed system
Based on the literature review and the concepts explained in existing research, there is a serious need for an expert system in the domain under study. This conclusion was tested with a questionnaire survey. This is a new approach in comparison with other studies in this area. Other researchers have depended on the literature to establish the need for their proposed expert system. After developing their system, they use a questionnaire to check if it is needed. The present approach has two major advantages over the approach used by other researchers. First, ensuring that there is a real need for the proposed system before creating it will avoid wasting time, money, and effort on developing a system that is not required. Second, the domain of the study can be specified depending on the comments of questionnaire respondents. The questionnaires were submitted to 30 highway engineers who had different levels of experience. The engineers were divided into two groups. The first group included eight engineers who had between 5 and 9 years of experience and two experts with more than 20 years of experience. The second group included 20 engineers who had 3 years of experience or less. The questionnaire consists of two parts and a total of seven questions. Of these, five questions ask about the significance of the proposed system and its role in the study domain, and the other two questions ask about the number of domain experts. Because a Likert scale is a very effective way to evaluate the results of a questionnaire (Göb et al. 2007;Lee et al. 2010), the questions are evaluated on 5-point Likert scale, where the value 1 represents "strongly disagree" and the value 5 represents "strongly agree". The results, summarized in Table 2, speak for themselves and reflect the significance for the proposed system. The results express a significant concern over the loss of human expertise as experts retire or pass away. The proposed system can preserve their expertise in a classified form and can help to educate a new generation of experts. In summary, the results of the questionnaire validate the conclusion extracted from the literature, that is, there is high demand for an expert system in the domain of highway pavement.

Developing the system
An expert system uses knowledge instead of data to solve problems. An expert system development team is led by a knowledge engineer and includes a domain expert and an end user. The role of the knowledge engineer is to build the system by acquiring knowledge from written sources and from the domain expert. During the knowledge acquisition stage, the knowledge engineer works with the domain expert to acquire, classify and analyze the knowledge. The knowledge engineer codes the acquired knowledge in a classified form to construct a computer system using a programming tool. The constructed system is tested and evaluated by the end user, who is the third member of the team (Alani et al. 2009;Raza 2009;Špundak et al. 2010). The proposed expert system in this study (ES-CCPRHP) has passed through the stages of development successfully.
Many studies have investigated the integrated usage of expert systems, which can simulate the performance of a human expert (Ahmadi, Ebadi 2010), and GIS, which has many uses in decision making (Demircan et al. 2011;Sikder 2009), in fields such as ecology, agriculture, forestry, transportation, traffic, public health, and environmental protection (Wei et al. 2011). GIS can provide information about location, weather conditions, road traffic, and other data (Durduran 2010;Niaraki, Kim 2009;Sadeghi-Niaraki et al. 2011).

Knowledge acquisition and representation
Knowledge acquisition represents the most important stage in the development of an expert system (Raza 2009). It is also complicated and time-consuming (Mohd. Zain et al. 2005;Ooshaksaraie et al. 2012;Tan et al. 2010) as knowledge-based systems require specific analytical approaches (Castellanos et al. 2011). Knowledge acquisition involves obtaining and classifying expertise from miscellaneous sources (Qian et al. 2008). Knowledge engineering methodology usually starts with reviewing written sources, like books, guidelines, manuals, and papers associated with the problem domain. Further knowledge can be elicited from domain experts. Then, the collected knowledge can be combined, studied, and analyzed repeatedly (Negnevitsky 2005).
In the present study, an extensive review of specialized sources is performed to construct the initial background knowledge and understand the concepts of rigid pavement construction and the problems that can be expected to occur during different stages of construction. Through this review, the initial knowledge base is constructed as the foundation for the final knowledge base that represents the core of the expert system. This initial knowledge is analyzed repeatedly to refine it and limit the domain of the study. The review focuses on description, causes, and prevention of problems, instantaneous solutions to problems that occur, and the possible effects of problems that are not avoided or controlled. After construction of the initial knowledge base through a literature review, domain experts were consulted about their knowledge. The experts obtained their domain knowledge gradually through education and experience. Selection of domain experts is very significant in any elicitation expertise. Criteria for choosing domain experts ensure elicitation of correct expert knowledge. There are two major criteria for domain experts. The first is the length of experience in the domain, which affects the judgment and analytical behavior of the expert. The second can be represented in circumstances in which the expertise is obtained, which could be theoretical, practical, or a combination of both (Osuagwu, Okafor 2010). Depending on these criteria, a set of four experts was selected for the human expertise stage in the present study. The selected experts are well known and have broad experience in the domain of rigid pavement construction, as illustrated in Table 3. Another set of experts is selected to participate in the evaluation stage. Knowledge elicitation involves obtaining knowledge from experts to understand how they make decisions. This goal can be achieved by methods such as interviews (Tan et al. 2010). Experts can also be observed as they work to identify implicit knowledge (Castellanos et al. 2011;Tan et al. 2010). The knowledge engineer can decide on which method to use depending on the study domain, amount of knowledge needed, and the efforts required to analyze the collected information (Osuagwu, Okafor 2010). In this paper, expertise was elicited from the selected experts by unstructured interviews, structured interviews, and questionnaires. Unstructured interviews were held with the experts to gain a general understanding of their practical experience with domain problems and to build a friendly relationship with them to simplify the process of expertise elicitation. Problems in the study domain were discussed in general, and a few problems were discussed specifically. Each expert referred to some of his practical experiences with rigid pavement construction problems and the way he dealt with such problems in the field.
During the unstructured interviews, only a few questions were asked of the experts, but the experts gave detailed responses to these questions. After each unstructured interview, the knowledge was reanalyzed, reclassified, and updated in preparation for structured interviews, which represent the next step in expertise elicitation. During structured interviews, a specific aspect of the domain is emphasized in each interview to ensure robust results. The primary knowledge that is collected through expertise elicitation is much more than the secondary knowledge obtained from the literature, because the experts do not document their experiences. The acquired knowledge was abstracted in questionnaire form and submitted to the experts to complete the knowledge acquisition stage. A questionnaire can simplify the process of knowledge elicitation from experts (Ma et al. 2011) because it gives the expert time to think about his response before answering. Questionnaires are an effective way to elicit knowledge as they can save time, money, and effort, especially when the knowledge engineer knows exactly the required knowledge characteristics (Rezaei et al. 2011). In addition, the classified form of the questionnaire simplifies the mission of the expert because he can review each problem separately. Blank spaces were provided following each question for the expert to write his comments. Three experts completed questionnaires, and only one questionnaire form was not returned. One of the experts asked for clarification before answering some of the questions. The experts provided many useful comments on the questionnaire that enriched the knowledge base. After reviewing and analysis of their answers and comments in the questionnaire, the experts were interviewed again to clarify some points in their comments and to focus on some details in their solutions to the problems. In the final step of the knowledge acquisition process, the knowledge base is reanalyzed and rearranged in preparation for final classification. Through the extensive review and repeated analysis of the acquired knowledge, the domain problems are classified depending on their forms, locations, effects, and other common features so that inspectors can diagnose a problem visually or via tests and measurement results. In addition, problems' description, likely causes, preventive actions, instantaneous solutions, and their possible effects if they are not controlled are stated. The repeated classification stages were discussed with experts for modification. The final classification was reviewed by three experts during the focus interviews, and they agreed that it represented their knowledge well. Figure 1 illustrates the classification diagram of the titles of the problems. The problems are identified depending on their characteristics, which could be diagnosed visually by their appearance or by measurements and tests. The name of each problem summarizes its description. Experts can note such problems easily and quickly make decisions to solve them, whereas novice engineers cannot.
Avoiding these problems by preventive actions can save time, money, and effort. Immediate decisions to identify and take preventive measures must be made to control these problems. Site inspectors have the authority to reject any load that contains an imperfect concrete. The decision to reject a load can be based on visual inspection, temperature measurement, or tests. Accepted loads should be documented in detail, including their placing, temperature, sample number, slump, and other remarks.

Building the system
In this study, an expert system is developed to detect problems and guide the user through the diagnostic process. Knowledge about these problems can be represented in the form of rules. Therefore, a rule-based system can be considered as the most correct option. When problems arise, experts need to collect information about it and then make a decision. Therefore, a forward-chaining inference engine, which is data driven, is suitable for knowledge representation in a rule-based expert system (Negnevitsky 2005). This procedure works from the facts in the knowledge base toward the goal or conclusion (Chu et al. 2009;Špundak et al. 2010). The reasoning originates from the given information, and then continues forward with that information. This approach depends on IF-THEN relationships; if the IF condition is matched in a rule, the action in its THEN part is applied (Negnevitsky 2005). This process can be modelled as IF (condition) THEN (conclusion) (Cebi et al. 2009;Přibyl 2010). We created 450 ES-CCPRHP rules, which simulate the manner in which domain experts think.
The classified knowledge, which represents the core of the proposed system, is prepared in the form of rules to be coded in a computer environment. The Microsoft Visual Basic programming language was used to develop ES-CCPRHP, because this language is a very effective and flexible tool for software development in the Windows environment. In addition, Microsoft Visual Basic is suitable for use with GIS (Ooshaksaraie et al. 2012). The source code version of the developed system has multiple forms that are connected together in one structure. Each form includes a number of commands responsible for executing specific functions in the system. The forms and the commands are given clear, expressive names that are related to the functions of each command. In addition, many remarks are included in the coding menus to simplify the updating process. This version (with the extension.vbp) is designed for use by the knowledge engineer who is responsible for developing and updating the system. An executable version (with the extension. exe) is prepared for use by the end user, who is the highway engineer, and this version is protected and cannot be edited. Figure 2 illustrates the relationships among the development team and components of ES-CCPRHP. The system can be operated easily by clicking a button to execute any step using the mouse or the keyboard; the user can return to the last step anytime using a Back button, and he can use the Close button to end the program at any stage. The system is coded in a simple manner to ensure easy updating by the developer or any other knowledge engineer in this domain, who is familiar with Visual Basic language.

System operation
Similar to any software in the environment of Microsoft Windows, the system can be run by clicking the icon of the executable file or its shortcut. The system runs immediately and displays a greeting screen that includes information about the purpose of the system, the domain that the system deals with, a brief guide about operating the system, and three command buttons (CONTINUE, ABOUT, and CLOSE). Users can press any button using the mouse or keyboard, and then proceed to the next screen by pressing the CONTINUE button. The next screen presents the flow chart of domain problems to provide the novices in this domain with an idea about the problems. This screen also describes the construction stages, as well as the probable problems and their probable causes as part of the training process, providing novices a background for moving on to the next screen.
Users can skip this screen by pressing CONTINUE if they already have sufficient background knowledge or if they are in a hurry to find solutions. Such a situation usually occurs in problems encountered during paving operations, including defective concrete loads, bleeding or cracking of fresh concrete, and paving stoppage due to bad weather conditions or equipment breakdown. The next screen includes all the problems that are classified into main and subcategories of common features. The titles of the categories, subcategories, and problems simplify descriptions for users. For example, the cracking category includes two subcategories (cracking of plastic concrete and cracking of hardened concrete). Cracking of plastic concrete includes diagonal shallow cracks and craze cracks. The titles clearly reflect the properties of a problem for simplified diagnosis. Figure 3 presents the cracking subcategories and specific problems in one input screen. In addition, the descriptions of each category, subcategory, and problem can be displayed on separate screens by pressing the related button. Moreover, pictures that clarify the problem can be displayed. Videos of test procedures are also provided, which can be activated with the press of a button. Users can select a category of problems or one problem or more by selecting an option button or checking TICK on checkboxes. The system asks a user if the description presented complies with the description of the problem in the worksite. When a user confirms by selecting the YES button or checking TICK on the checkboxes, the system proceeds with the diagnostic process by asking for more input data, such as test results, field measurements, work requirements that are documented in project files (e.g. designed pavement thickness, designed concrete strength, and specified minimum and maximum values of the tests). The system uses default values when a user does not answer questions by providing the user multiple options. For example, when a structural problem occurs in constructed pavement (thickness and/or strength deficiency), the inference engine will run a redesign subroutine to evaluate the pavement's structural properties on the basis of existing input. The system will ask the user to incorporate some values as explained in Section 3.4.4. One of the required values in this case is the load transfer coefficient. If a user does not know this value, the system presents multiple options for the type of load transfer to help the user select the Fig. 3. ES-CCPRHP cracking input screen Journal of Civil Engineering and Management, 2013, 19(6): 846-861 correct option. In this example, the options are undoweled pavement on crushed aggregate surfacing, doweled pavement on crushed aggregate surfacing, doweled pavement on hot mix asphalt (without a widened outside lane) and tied pavement shoulders, continuously reinforced pavement with hot mix asphalt shoulders, and continuously reinforced concrete pavement with tied concrete shoulders. When the user selects an option, the system uses the related default value stored in the working memory.
The inference engine manipulates the input data and facts in the working memory in a reasoning process in the knowledge base to match these data with related rules, draw a conclusion, and display recommendations. More details can be found in the examples provided in Section 3.4.4.
A variety of tools, such as labels, texts, option buttons, command buttons, check boxes, combo boxes, and images, are provided in the forms to simplify the input and output for the user. These tools are enabled only when they are necessary for data input; otherwise, they are disabled (ineffective) to avoid confusing the user. The user interface displays help and useful details, like explanations about the system, flow charts, and guides. Users can input the required information by clicking to choose the offered options, which cover all of the probable required input data. The system responds immediately by analyzing the inputs in the inference mechanism to provide solutions.

System verification and validation
Verification and validation are the most important and difficult tasks involved in intelligent system development (Aguilar et al. 2008). Verification can be performed through testing activities to verify that the correct system is being built. In effective testing, each test should aim to detect a fault. Each stage and all components of the system should be tested (Qian et al. 2005). Testing is performed periodically during the system development process to guarantee that each activity in the system is performing the intended functions. ES-CCPRHP is evaluated by a number of test procedures, as explained in the following sections.

Unit and integration testing
Unit testing means testing the units one by one by separate testing activities (Aguilar et al. 2008). This testing was performed continually during all of the stages of development of ES-CCPRHP to verify that each unit in the system performs the intended function. The internal structure of the system is checked by the knowledge engineer by covering all possible combinations of constants, variables, relationships among them, and paths of the source code. Few mistakes were diagnosed during the testing process. These mistakes were corrected, while the system was still under construction and before transforming it into an executable version.
Integration testing will be performed by the knowledge engineer to verify that all units are running together in the approved manner (Aguilar et al. 2008;Ooshaksaraie et al. 2012). To run the system, the user will provide the system with the required input data, such as the type of area, description of the problem, its location, and the layer where the problem is detected. The system is provided with many commands that simplify the mission of the user regardless of his skills in highway pavement construction and computer use. The user can enter his input data by clicking the options presented by the system. The input data are processed in the system to identify suitable solutions, possible causes, preventive actions, and the effects of the problem if no actions are taken to control it. The interaction between the user and the ES-CCPRHP was tested by the knowledge engineer. Similar to unit testing, integration testing was performed periodically during construction of ES-CCPRHP to verify its capability to execute the intended functions.

User satisfaction testing
A questionnaire survey was designed to test users' satisfaction with ES-CCPRHP. Three groups of users were selected to participate in these surveys. The first group includes 5 computer specialists. The second group includes four experts in rigid highway pavement construction, who were not involved in the knowledge elicitation stage. The third group consists of 10 novice engineers. The backgrounds of the users mentioned above are listed in Table 4.
The system was used by the participants to evaluate the system depending on the questionnaire presented in Table 5. The result of evaluation reflects the satisfaction of the users through their high mean ratings (more than 3). Validation is performed to ensure that the system represents the knowledge of the experts accurately (Aguilar et al. 2008). The satisfaction of the users in the second group (domain experts) can be considered as evidence for the system's validation as these users are satisfied with the knowledge base content, its speed, help facilities, system results, and other components in the system, as listed in Table 5. Satisfaction of the users in all groups (computer professionals, experts and novice engineers) indicates that the user interface is friendly.
Questionnaire reliability was statistically tested by calculating Cronbach's alpha, which was 0.969, indicating high reliability. The mean and standard deviation values of the evaluation results for each group of participants were calculated. The results were then statistically tested by one-way ANOVA at a 95% confidence level (Table 5). The test shows no significant difference between the mean values of the groups for questions 1, 2, 3, 4, 5, 10, and 16. However, a significant difference was found between the mean values of the groups for questions 6,7,8,9,11,12,13,14, and 15 because the calculated F value is higher than the tabulated F value (3.634). The test indicates that at least one group differs from another, but does not show which group pair or pairs cause the differences. Therefore, the least significant difference (LSD) test by Tukey's method was adopted to specify the pair or pairs from which the differences originate. Following this method, we calculated the difference between each two mean values and compared it with LSD. Table 6 abstracts the result of the comparison. For all the questions, the differences between the mean values of groups 1 and 2 and between groups 1 and 3 were higher than the LSD, indicating significant differences between the mean values of group 1 and those of groups 2 and 3. Conversely, no significant differences were found between the mean values of groups 2 and 3, except for question 12. With respect to questions 6-9 and 11-15 (those related to the evaluation of the knowledge included in the system), the mean values in the second group (domain experts) were very high. This result reflects the validity of the knowledge. The third group (novice highway engineers) also exhibited high mean values, because they have a reasonable background on the domain of the study. The first group had mean values higher than 3 but with significant difference from groups 2 and 3 because this group was not familiar with pavement construction.

Behavior comparison between ES-CCPRHP and experts
Another measure for system validation involves presenting the inputs and outputs of the system to the second set of experts. The results given by the system are compared to the experts' opinions. The system was found to be compatible with their opinions regarding diagnosis, reasoning, conclusions and decisions. Moreover, the experts approved the results presented by the system that related to the causes of the problems, the preventive actions, and their possible effects. The results of validation show that the system provides output that matches the opinions of the second set of experts, as well as those of the first set of experts, who were involved in the knowledge elicitation stage, on whose knowledge the system was based. The overall compatibility between the system and the first set of experts amounts to 97% as the knowledge is already documented based on their expertise. The overall compatibility between the system and the second set of experts amounts to 86%. The variance between the system and the expert recommendation can be justified by the additional information provided by the system according to literature. The system is thus established to be valid and can be used with confidence. Table 7 presents the factors affecting the evaluation of plastic concrete loads supplied to the construction site as an example of the comparison process.

Testing by case study
This test was done to validate the system in a real environment. In this step, a construction site was selected. At this site, the new pavement was evaluated by ES-CCPRHP, and the recommendations obtained were compared with the recommendations reported by the Highway Division in the Department of General Works. The results obtained from the system were in line with the results of the reports. In addition, the results given by the system were checked and approved by the second set of domain experts.
In the selected section, 11 portions were reported as problematic because of deficiencies in structural properties. For example, thickness and concrete compressive strength were less than those required by the design documents. Of these portions, we selected a final set of four (shown in Table 8) as the illustrative examples. Input data were obtained from the reports and entered into the system to evaluate the specified portions. The design data were the same for all the portions, whereas the data obtained from the site differed for each portion. After running the system, the evaluation screen is displayed by selecting the option "structural property deficiency problems" from the main screen. The evaluation screen is shown in Figure 4.
The initial requested input data are: D req : pavement slab depth required by the project documents [design] (mm); D f : constructed pavement slab depth measured in the field (mm); CS req : concrete compressive strength required by the project documents [design] (MPa); CS f : concrete compressive strength measured by testing the cores drilled from the field (MPa).
The inference engine of the system will manipulate these inputs and search the knowledge base for the matching rule as shown below: IF D req -D f ≤ 13 mm and CS req ≤ CS f , THEN Accept the portion IF D req -D f ≤ 13 mm and CS req ≥ CS f , THEN Apply Redesign Procedure IF D req -D f ≥13 mm and CS req ≤ CS f , THEN Apply Redesign Procedure IF D req -D f ≥ 13 mm and CS req ≥ CS f , THEN Reject the portion.
When the system conclusion is "accept the portion", the system will display an output screen to notify the user that the portion can be accepted if there are no other problems; otherwise, the other properties will be evaluated. In addition, the system offers to calculate the value of price deduction, if required. According to the second and third rules, the inference engine will run the redesign subroutine to calculate the minimum thickness that is structurally accepted on the basis of the AASHTO procedure. The calculation is performed according to the following equation (AASHTO 1993):    Table 8 abstracts input, inference, and output for four portions in this case study. Figures 4 and 5 illustrate the input and output screens, respectively.

System updating and maintenance
The system will be updated when new construction technologies, such as new materials, new concrete modifiers, new equipment, or new techniques, are applied in the rigid highway pavement industry. The system will also be updated when new design approaches are developed. Moreover, the creativity of humans is boundless; therefore, the system will be updated when new human expertise is developed. The operation of the system for several days can cause problems; if so, the system can be restarted to solve the problem.

Conclusion
Developing an expert system from scratch was the challenge of this study. The evaluation and development stages of ES-CCPRHP are described in detail in the domain of rigid highway pavement construction. The developed system will be helpful for highway engineers to overcome domain problems to detect problems and make decisions for solving problems quickly. The need  for the system was validated by a questionnaire survey submitted to 30 highway engineers before the system development began. The knowledge base of the system is based primarily on human expertise and secondarily on a literature review. The knowledge base includes the problems encountered in the domain, their causes, preventive actions, instantaneous solutions, and their effects in a classified form. A database of relevant knowledge is represented in the form of rules and coded in this software coded in Microsoft Visual Basic environment and supported by GIS, which is compatible with Visual Basic. The system is verified and validated by extensive testing.
Moreover the system has a flexible and user friendly interface. The system has been verified and validated and can be used confidently by end users. In addition, it can be used as a database to archive the problems encountered in the domain and to share highway engineers' experiences and transfer expertise to successive generations of engineers. Using this system as a foundation, other highway construction expert system can be developed. Any knowledgeable engineer or any competent user of Visual Basic can update this system under supervision by a highway engineer and make it more resourceful for new engineers.
The system is unsuitable for problems that occur in embankment, subgrade, subbase, and base construction, but it considers their effects on the construction of concrete pavements. The system is also inapplicable to prestressed concrete, pervious concrete, roller-compacted concrete, self-consolidating concrete and asphaltic shoulders. The system uses the AASHTO procedure in the redesign process and does not include other procedures. The system works in Microsoft Windows 2000 or higher and requires a memory space of 500 MB.


extfieldsofstudy:
Mathematics
Computer Science

s2fieldsofstudy:
Computer Science
Mathematics

text:
Classical Hardness of Learning with Errors

We show that the Learning with Errors (LWE) problem is classically at least as hard as standard worst-case lattice problems, even with polynomial modulus. Previously this was only known under quantum reductions. Our techniques capture the tradeoff between the dimension and the modulus of LWE instances, leading to a much better understanding of the landscape of the problem. The proof is inspired by techniques from several recent cryptographic constructions, most notably fully homomorphic encryption schemes.

Introduction
Over the last decade, lattices have emerged as a very attractive foundation for cryptography. The appeal of lattice-based primitives stems from the fact that their security can be based on worst-case hardness assumptions, that they appear to remain secure even against quantum computers, that they can be quite efficient, and that, somewhat surprisingly, for certain advanced tasks such as fully homomorphic encryption no other cryptographic assumption is known to suffice.
Virtually all recent lattice-based cryptographic schemes are based directly upon one of two natural average-case problems that have been shown to enjoy worst-case hardness guarantees: the short integer solution (SIS) problem and the learning with errors (LWE) problem. The former dates back to Ajtai's groundbreaking work [Ajt96], who showed that it is at least as hard as approximating several worst-case lattice problems, such as the (decision version of the) shortest vector problem, known as GapSVP, to within a polynomial factor in the lattice dimension. This hardness result was tightened in followup work (e.g., [MR04]), leading to a somewhat satisfactory understanding of the hardness of the SIS problem. The SIS problem has been the foundation for one-way [Ajt96] and collision-resistant hash functions [GGH96], identification schemes [MV03,Lyu08,KTX08], and digital signatures [GPV08,CHKP10,Boy10,MP12,Lyu12].
Our focus in this paper is on the latter problem, learning with errors. In this problem our goal is to distinguish with some non-negligible advantage between the following two distributions: ((a i , a i , s + e i mod q)) i and ((a i , u i )) i , where s is chosen uniformly from Z n q and so are the a i ∈ Z n q , u i are chosen uniformly from Z q , and the "noise" e i ∈ Z is sampled from some distribution supported on small numbers, typically a (discrete) Gaussian distribution with standard deviation αq for α = o(1).
Contrary to the SIS problem, however, the hardness of LWE is not sufficiently well understood. The main hardness reduction for LWE [Reg05] is similar to the one for SIS mentioned above, except that it is quantum. This means that the existence of an efficient algorithm for LWE, even a classical (i.e., non-quantum) one, only implies the existence of an efficient quantum algorithm for lattice problems. This state of affairs is quite unsatisfactory: even though one might conjecture that efficient quantum algorithms for lattice problems do not exist, our understanding of quantum algorithms is still at its infancy. It is therefore highly desirable to come up with a classical hardness reduction for LWE.
Progress in this direction was made by [Pei09] (with some simplifications in the followup by Lyubashevsky and Micciancio [LM09]). The main result there is that LWE with exponential modulus is as hard as some standard lattice problems using a classical reduction. As that hardness result crucially relies on the exponential modulus, the open question remained as to whether LWE is hard for smaller moduli, in particular polynomial moduli. In addition to being an interesting question in its own right, this question is of special importance since many cryptographic applications, as well as the learning theory result of Klivans and Sherstov [KS06], are instantiated in this setting. Some additional evidence that reducing the modulus is a fundamental question comes from the Learning Parity with Noise (LPN) problem, which can be seen as LWE with modulus 2 (albeit with a different error distribution), and whose hardness is a long-standing open question. We remark that [Pei09] does include a classical hardness of LWE with polynomial modulus, albeit one based on a non-standard lattice problem, whose hardness is arguably as debatable as that of the LWE problem itself.
To summarize, prior to our work, the existence of an efficient algorithm for LWE with polynomial modulus was only known to imply an efficient quantum algorithm for lattice problems, or an efficient classical algorithm for a non-standard lattice problem. While both consequences are unlikely, they are arguably not as earth-shattering as an efficient classical algorithm for lattice problems. Hence, some concern about the hardness of LWE persisted, tainting the plethora of cryptographic applications based on it.
Main result. We provide the first classical hardness reduction of LWE with polynomial modulus. Our reduction is the first to show that the existence of an efficient classical algorithm for LWE with any subexponential modulus would indeed have earth-shattering consequences: it would imply an efficient algorithm for worst-case instances of standard lattice problems.
Theorem 1.1 (Informal). Solving n-dimensional LWE with poly(n) modulus implies an equally efficient solution to a worst-case lattice problem in dimension √ n.
modulus and the approximation ratio both remain fixed independently of the target {0, 1}-LWE algorithm. As mentioned above, our alternative to the reduction in [GKPV10] is based on a hybrid argument combined with a new hardness reduction for the "extended LWE" problem, which is a variant of LWE in which in addition to the LWE samples, we also get to see the inner product of the vector of error terms with a vector z of our choosing. This problem has its origins in the cryptographic literature, namely in the work of O'Neill, Peikert, and Waters [OPW11] on (bi)deniable encryption and the later work of Alperin-Sheriff and Peikert [AP12] on key-dependent message security. The hardness reductions included in those papers are not sufficient for our purposes, as they cannot handle large moduli or error terms, which is crucial in our setting. We therefore provide an alternative reduction which is conceptually much simpler, and essentially subsumes both previous reductions. Our reduction works equally well with exponential moduli and correspondingly long error vectors, a case earlier reductions could not handle.
Broader perspective. As a byproduct of the proof of Theorem 1.1, we obtain several results that shed new light on the hardness of LWE. Most notably, our modulus reduction result in Section 3 is actually far more general, and can be used to show a "modulus expansion/dimension reduction" tradeoff. Namely, it shows a reduction from LWE in dimension n and modulus p to LWE in dimension n/k and modulus p k (see Corollary 3.4). Combined with our modulus reduction, this has the following interesting consequence: the hardness of n-dimensional LWE with modulus q is a function of the quantity n log 2 q. In other words, varying n and q individually while keeping n log 2 q fixed essentially preserves the hardness of LWE.
Although we find this statement quite natural (since n log 2 q represents the number of bits in the secret), it has some surprising consequences. One is that n-dimensional LWE with modulus 2 n is essentially as hard as n 2 -dimensional LWE with polynomial modulus. As a result, n-dimensional LWE with modulus 2 n , which was shown in [Pei09] to be as hard as n-dimensional lattice problems using a classical reduction, is actually as hard as n 2 -dimensional lattice problems using a quantum reduction. The latter is presumably a much harder problem, requiring exp( Ω(n 2 )) time to solve. This corollary highlights an inherent quadratic loss in the classical reduction of [Pei09] (and as a result also our Theorem 1.1) compared to the quantum one in [Reg05].
A second interesting consequence is that 1-dimensional LWE with modulus 2 n is essentially as hard as n-dimensional LWE with polynomial modulus. The 1-dimensional version of LWE is closely related to the Hidden Number Problem of Boneh and Venkatesan [BV96]. It is also essentially equivalent to the Ajtai-Dwork-type [AD97] cryptosystem in [Reg03], as follows from simple reductions similar to the one in the appendix of [Reg10a]. Moreover, the 1-dimensional version can be seen as a special case of the Ring-LWE problem introduced in [LPR10] (for ring dimension 1, i.e., ring equal to Z). This allows us, via the ring switching technique from [GHPS12], to obtain the first hardness proof of Ring-LWE, with arbitrary ring dimension and exponential modulus, under the hardness of problems on general lattices (as opposed to just ideal lattice problems). In addition, this leads to the first hardness proof for the Ring-SIS problem [LM06,PR06] with exponential modulus under the hardness of general lattice problems, via the standard LWE-to-SIS reduction. (We note that since both results are obtained by scaling up from a ring of dimension 1, the hardness does not improve as the ring dimension increases.) A final interesting consequence of our reductions is that (the decision form of) LWE is hard with an arbitrary huge modulus, e.g., a prime; see Corollary 3.3. Previous results (e.g., [Reg05,Pei09,MM11,MP12]) required the modulus to be smooth, i.e., all its prime divisors had to be polynomially bounded.
Open questions. As mentioned above, our Theorem 1.1 inherits from [Pei09] a quadratic loss in the dimension, which does not exist in the quantum reduction [Reg05] nor in the known hardness reductions for SIS. At a technical level, this quadratic loss stems from the fact that the reduction in [Pei09] is not iterative. In contrast, the quantum reduction in [Reg05] as well as the reductions for SIS are iterative, and as a result do not incur the quadratic loss. We note that an additional side effect of the non-iterative reduction is that the hardness in Theorem 1.1 and [Pei09] is based only on the worst-case lattice problem GapSVP (and the essentially equivalent BDD and uSVP [LM09]), and not on problems like SIVP, which the quantum reduction of [Reg05] and the hardness reductions for SIS can handle. One case where this is very significant is when dealing with ideal lattices, as in the hardness reduction for Ring-LWE, since GapSVP turns out to be an easy problem there.
We therefore believe that it is important to understand whether there exists a classical reduction that does not incur the quadratic loss inherent in [Pei09] and in Theorem 1.1. In other words, is n-dimensional LWE with polynomial modulus classically as hard as n-dimensional lattice problems (as opposed to √ ndimensional)? This would constitute the first full dequantization of the quantum reduction in [Reg05]. While it is natural to conjecture that the answer to this question is positive, a negative answer would be quite tantalizing. In particular, it is conceivable that there exists a (classical) algorithm for LWE with polynomial modulus running in time 2 O( √ n) . Due to the quadratic expansion in Theorem 1.1, this would not lead to a faster classical algorithm for lattice problems; it would, however, lead to a 2 O( √ n) -time quantum algorithm for lattice problems using the reduction in [Reg05]. The latter would be a major progress in quantum algorithms, yet is not entirely unreasonable; in fact, a 2 O( √ n) -time quantum algorithm for a somewhat related quantum task was discovered by Kuperberg [Kup05] (see also [Reg02]).

Preliminaries
Let T = R/Z denote the cycle, i.e., the additive group of reals modulo 1. We also denote by T q its cyclic subgroup of order q, i.e., the subgroup given by {0, 1/q, . . . , (q − 1)/q}. For two probability distributions P, Q over some discrete domain, we define their statistical distance as |P (i) − Q(i)|/2 where i ranges over the distribution domain, and extend this to continuous distributions in the obvious way. We recall the following easy fact (see, e.g., [AD87, Eq. (2.3)] for a proof).
Claim 2.1. If P and Q are two probability distributions such that P (i) ≥ (1 − ε)Q(i) holds for all i, then the statistical distance between P and Q is at most ε.
We will use the following immediate corollary of the leftover hash lemma [HILL99].
A distinguishing problem P is defined by two distributions P 0 and P 1 , and a solution to the problem is the ability to distinguish between these distributions. The advantage of an algorithm A with binary output on P is defined as A reduction from a problem P to a problem Q is an efficient (i.e., polynomial-time) algorithm A B that solves P given access to an oracle B that solves Q. Most of our reductions (in fact all except the one in Lemma 2.15) are what we call "transformation reductions:" these reductions perform some transformation to the input and then apply the oracle to the result.

Lattices
An n-dimensional (full-rank) lattice Λ ⊆ R n is the set of all integer linear combinations of some set of n linearly independent basis vectors B = {b 1 , . . . , b n } ⊆ R n , The dual lattice of Λ ⊂ R n is defined as Λ * = {x ∈ R n : Λ, x ⊆ Z}. The minimum distance (or first successive minimum) λ 1 (Λ) of a lattice Λ is the length of a shortest nonzero lattice vector, i.e., λ 1 (Λ) = min 0 =x∈Λ x . For an approximation ratio γ = γ(n) ≥ 1, the GapSVP γ is the problem of deciding, given a basis B of an n-dimensional lattice Λ = L(B) and a number d, between the case where λ 1 (L(B)) ≤ d and the case where λ 1 (L(B)) > γd. We refer to [Kho10,Reg10b] for a recent account on the computational complexity of GapSVP γ .

Gaussian measures
For r > 0, the n-dimensional Gaussian function ρ r : R n → (0, 1] is defined as We extend this definition to sets, i.e., ρ r (A) = x∈A ρ r (x) ∈ [0, +∞] for any A ⊆ R n . The (spherical) continuous Gaussian distribution D r is the distribution with density function proportional to ρ r . More generally, for a matrix B, we denote by D B the distribution of Bx where x is sampled from D 1 . When B is nonsingular, its probability density function is proportional to A basic fact is that for any matrices B 1 , B 2 , the sum of a sample from D B 1 and an independent sample from D B 2 is distributed like D C for C = (B 1 B T 1 + B 2 B T 2 ) 1/2 . For an n-dimensional lattice Λ and a vector u ∈ R n , we define the discrete Gaussian distribution D Λ+u,r as the discrete distribution with support on the coset Λ + u whose probability mass function is proportional to ρ r . There exists an efficient procedure that samples within negligible statistical distance of any (not too narrow) discrete Gaussian distribution ([GPV08, Theorem 4.1]; see also [Pei10]). In the next lemma, proved in Section 5, we modify this sampler so that the output is distributed exactly as a discrete Gaussian. This also allows us to sample from slightly narrower Gaussians. Strictly speaking, the lemma is not needed for our results, and we could use instead the original sampler from [GPV08]. Using our exact sampler leads to slightly cleaner proofs as well as a (miniscule) improvement in the parameters of our reductions, and we include it here mainly in the hope that it finds further applications in the future.

Lemma 2.3.
There is a probabilistic polynomial-time algorithm that, given a basis B of an n-dimensional lattice Λ = L(B), c ∈ R n , and a parameter r ≥ B · ln(2n + 4)/π, outputs a sample distributed according to D Λ+c,r .
Here, B denotes the Gram-Schmidt orthogonalization of B, and B is the length of the longest vector in it. We recall the definition of the smoothing parameter from [MR04].
We now collect some known facts on Gaussian distributions and lattices.

Lemma 2.6 ([MR04, Lemma 4.1]). For any
Lemma 2.8 ([Reg05, Claim 3.9]). Let Λ be an n-dimensional lattice, let u ∈ R n be arbitrary, let r, s > 0 and let t = √ r 2 + s 2 . Assume that rs/t = 1/ 1/r 2 + 1/s 2 ≥ η ε (Λ) for some ε < 1/2. Consider the continuous distribution Y on R n obtained by sampling from D Λ+u,r and then adding a noise vector taken from D s . Then, the statistical distance between Y and D t is at most 4ε.

Lemma 2.10 (Special case of [Pei10, Theorem 3.1]).
Let Λ be a lattice and r, s > 0 be such that s ≥ η ε (Λ) for some ε ≤ 1/2. Then if we choose x from the continuous Gaussian D r and then choose y from the discrete Gaussian D Λ−x,s then x + y is within statistical distance 8ε of the discrete Gaussian D Λ,(r 2 +s 2 ) 1/2 .

Learning with Errors
For integers n, q ≥ 1, an integer vector s ∈ Z n , and a probability distribution φ on R, let A q,s,φ be the distribution over T n q × T obtained by choosing a ∈ T n q uniformly at random and an error term e from φ, and outputting the pair (a, b = a, s + e) ∈ T n q × T.
Definition 2.11. For integers n, q ≥ 1, an error distribution φ over R, and a distribution D over Z n , the (average-case) decision variant of the LWE problem, denoted LWE n,q,φ (D), is to distinguish given arbitrarily many independent samples, the uniform distribution over T n q ×T from A q,s,φ for a fixed s sampled from D. The variant where the algorithm only gets a bounded number of samples m ∈ N is denoted LWE n,m,q,φ (D).
Notice that the distribution A q,s,φ only depends on s mod q, and so one can assume without loss of generality that s ∈ {0, . . . , q − 1} n . Moreover, using a standard random self-reduction, for any distribution over secrets D, one can reduce LWE n,q,φ (D) to LWE n,q,φ (U ({0, . . . , q − 1} n )), and we will occasionally use LWE n,q,φ to denote the latter (as is common in previous work). When the noise is a Gaussian with parameter α > 0, i.e., φ = D α , we use the shorthand LWE n,q,α (D). Since the case when D is uniform over {0, 1} n plays an important role in this paper, we will denote it by binLWE n,q,φ (and by binLWE n,m,q,φ when the algorithm only gets m samples). Finally, as we show in the following lemma, one can efficiently reduce LWE to the case in which the secret is distributed according to the (discretized) error distribution and is hence somewhat short. This latter form of LWE, known as the "normal form," was first shown hard in [ACPS09] for the case of prime q. Here we observe that the proof extends to non-prime q, the new technical ingredient being Claim 2.13 below.
Proof. Consider the first 16n + 4 ln ln q samples (a, b). Using Claim 2.13, with probability at least 1 − 2e −1 ≥ 1/4, we can efficiently find a subsequence of the samples such that the matrix A 0 ∈ Z n×n q whose columns are formed by the a in the subset (scaled up by q) has an inverse A −1 0 ∈ Z n×n q modulo q. If we cannot find such a subsequence, we abort. Let b 0 ∈ T n be the vector formed by the corresponding b in the subsequence.
We then apply the given LWE oracle to the resulting m ′ pairs and output its result. We now analyze the reduction. First notice that the construction of A 0 depends only on the a component of the input samples, and hence the probability of finding it is the same in case the input is uniform and in case it consists of LWE samples. It therefore suffices in the following to show that there is a distinguishing gap conditioned on successfully finding an A 0 . To that end, first observe that if the input samples (a, b) are uniform in T n q × T then so are the output samples (a ′ , b ′ ). Next consider the case that the input samples are distributed according to A q,s,Dα for some s ∈ Z n . Then since s ≥ η ε (q −1 Z) by Lemma 2.5, using Lemma 2.10 we get that where e is an independent error from D α . Therefore, the output samples are distributed according to A q,−qe 0 ,Dα , completing the proof.
Claim 2.13. For any q ≥ 25, n ≥ 1, and t 1 ≥ 4, t 2 ≥ 1, given a sequence of t 1 n + t 2 ln ln q vectors a 1 , a 2 , . . . chosen uniformly and independently from Z n q , except with probability e −t 1 n/16 + e −t 2 /4 , there exists a subsequence of n vectors such that the n × n matrix they form is invertible modulo q. Moreover, such a subsequence can be found efficiently.
Proof. We consider the following procedure. Let k be a counter, initialized to 0, indicating the number of vectors currently in the subsequence, and let A ∈ Z n×k q be the matrix whose columns are formed by the current subsequence. We also maintain a unimodular matrix U ∈ Z n×n , initially set to the identity, satisfying the invariant that U · A ∈ Z n×k q has the following form: its top k × k submatrix is upper triangular with each diagonal coefficient coprime with q; its bottom (n − k) × k submatrix is zero. The procedure considers the vectors a i one by one. For each vector a, if it is such that the gcd of the last n − k entries of U a, call it g, is coprime with q, then it does the following: it adds a to the subsequence, computes (using, say, the extended GCD algorithm) a unimodular matrix V that acts as identity on the first k coordinates and for which the last n − k coordinates of V U a are (g, 0, . . . , 0), replaces U with V U , and increments k.
It is easy to see that the procedure's output is correct if it reaches k = n. It therefore suffices to analyze the probability that this event happens. For this we use the following two facts to handle the cases k < n − 1 and k = n − 1, respectively. First, the probability that the gcd of two uniformly random numbers modulo q is coprime with q is where ζ is the Riemann zeta function. Second, the probability that one uniformly random number modulo q is coprime with q is ϕ(q)/q, where ϕ is Euler's totient function. By [BS96,Theorem 8.8.7], this probability is at least (e γ ln ln q + 3/(ln ln q)) −1 where γ is Euler's constant, which for q ≥ 25 is at least (4 ln ln q) −1 .
Using the (multiplicative) Chernoff bound, the first fact, and the fact that U a is uniform in Z n q since U is unimodular, we see that the probability that k < n − 1 after considering t 1 n vector is at most e −t 1 n/16 . Moreover, once k = n − 1, using the second fact we get that the probability that after considering t 2 ln ln q additional vectors we still have k = n − 1 is at most e −t 2 /4 . Unknown (Bounded) Noise Rate. We also consider a variant of LWE in which the amount of noise is some unknown β ≤ α (as opposed to exactly α), with β possibly depending on the secret s. As the following lemma shows, this does not make the problem significantly harder.
Lemma 2.15. Let A be an algorithm for LWE n,m,q,α with advantage at least ε > 0. Then there exists an algorithm B for LWE n,m ′ ,q,≤α using oracle access to A and with advantage at least 1/3, where both m ′ and its running time are poly(m, 1/ε, n, log q).
The proof is standard (see, e.g., [Reg05, Lemma 3.7] for the analogous statement for the search version of LWE). The idea is to use Chernoff bound to estimate A's success probability on the uniform distribution, and then add noise in small increments to our given distribution and estimate A's behavior on the resulting distributions. If there is a gap between any of these and the uniform behavior, the input distribution is deemed non-uniform. The full proof is omitted.
Relation to Lattice Problems. Regev [Reg05] and Peikert [Pei09] showed quantum and classical reductions (respectively) from the worst-case hardness of the GapSVP problem to the search version of LWE. (We note that the quantum reduction in [Reg05] also shows a reduction from SIVP.) As mentioned in the introduction, the classical reduction only works when the modulus q is exponential in the dimension n. This is summarized in the following theorem, which is derived from [Reg05, Theorem 3.1] and [Pei09, Theorem 3.1].
Theorem 2.16. Let n, q ≥ 1 be integers and let α ∈ (0, 1) be such that αq ≥ 2 √ n. Then there exists a quantum reduction from worst-case n-dimensional GapSVP O(n/α) to LWE n,q,α . If in addition q ≥ 2 n/2 then there is also a classical reduction between those problems.
In order to obtain hardness of the decision version of LWE, which is the one we consider throughout the paper, one employs a search-to-decision reduction. Several such reductions appear in the literature (e.g., [Reg05,Pei09,MP12]). The most recent reduction by Micciancio and Peikert [MP12], which essentially subsumes all previous reductions, requires the modulus q to be smooth. Below we give the special case when the modulus is a power of 2, which suffices for our purposes. It follows from our results that (decision) LWE is hard not just for a smooth modulus q, as follows from [MP12], but actually for all moduli q, including prime moduli, with only a small deterioration in the noise (see Corollary 3.3). 3.1]). Let q be a power of 2, and α satisfy 1/q < α < 1/ω( √ log n). Then there exists an efficient reduction from search LWE n,q,α to (decision) LWE n,q,α ′ for α ′ = α · ω(log n).

Modulus-Dimension Switching
The main results of this section are Corollaries 3.2 and 3.4 below. Both are special cases of the following technical theorem. We say that a distribution D over Z n is (B, δ)-bounded for some reals B, δ ≥ 0 if the probability that x ← D has norm greater than B is at most δ.
Then there is an efficient (transformation) reduction from LWE n,m,q,≤α (D) to LWE n ′ ,m,q ′ ,≤β (G · D) that reduces the advantage by at most δ + 14εm.
Here we use the notation B from Lemma 2.3. We also note that if needed, the distribution on secrets produced by the reduction can always be turned into the uniform distribution on Z n ′ q ′ , as mentioned after Definition 2.11. Also, we recall that there exists an elementary reduction from LWE n ′ ,q ′ ,≤β to LWE n ′ ,q ′ ,β (see Lemma 2.15).
In particular, by using the normal form of LWE (Lemma 2.12), in which the secret has distribution D = D Z n , √ 2αq , we can switch to a power-of-2 modulus with only a small loss in the noise rate, as described in the following corollary. Together with the known search-to-decision reduction (Theorem 2.17), this extends the known hardness of (decision) LWE to any modulus q. Here we use that D = D Z n ,r is (Cr n log(n/δ), δ)bounded for some universal constant C > 0, which follows by taking union bound over the n coordinates. (Alternatively, one could use that it is (r √ n, 2 −n )-bounded, as follows from [Ban93, Lemma 1.5], leading to a slightly tighter statement for large n.) Corollary 3.3. Let δ ∈ (0, 1/2), m ≥ n ≥ 1, q ′ ≥ 25. Let also q ∈ [q ′ , 2q ′ ) be the smallest power of 2 not smaller than q ′ and α ≥ ln(2n(1 + 16/δ)/π)/q. There exists an efficient (transformation) reduction from LWE n,m,q,α to LWE n,m ′ ,q ′ ,≤β where m ′ = m − (16n + 4 ln ln q) and β = Cα √ n log(n/δ) log(m/δ) for some universal constant C > 0, that turns advantage of ζ into an advantage of at least (ζ − δ)/4.
Another corollary illustrates a modulus-dimension tradeoff. Assume n = kn ′ for some k ≥ 1, and let q ′ = q k . Let G = I n ′ ⊗ g, where g = (1, q, q 2 , . . . , q k−1 ) T ∈ Z k . We then have Λ = q −k G T Z n ′ + Z n . A basis of Λ is given by this is since the column vectors of B belong to Λ and the determinants match. Orthogonalizing from left to right, we have B = q −1 I and so B = q −1 . We therefore obtain the following corollary, showing that we can trade off the dimension against the modulus, holding n log q = n ′ log q ′ fixed. For example, letting D = D Z n ,αq (corresponding to a secret in normal form, see Lemma 2.12), which is (αq √ n, 2 −n )bounded, the reduction increases the error rate by about a √ n factor.
Theorem 3.1 follows immediately from the following lemma.
There is an efficient mapping from T n q × T to T n ′ q ′ × T, which has the following properties: • If the input is uniformly random, then the output is within statistical distance 4ε from the uniform distribution.
Proof. The main idea behind the reduction is to encode T n q into T n ′ q ′ , so that the mod-1 inner products between vectors in T n q and a short vector s ∈ Z n , and between vectors in T n ′ q ′ and Gs ∈ Z n ′ , are nearly equivalent. In a bit more detail, the reduction will map its input vector a ∈ T n q (from the given LWE-oruniform distribution) to a vector a ′ ∈ T n ′ q ′ , so that a ′ , Gs = G T a ′ , s ≈ a, s mod 1 for any (unknown) s ∈ Z n . To do this, it randomly samples a ′ so that G T a ′ ≈ a mod Z n , where the approximation error will be a discrete Gaussian of parameter r.
We can now formally define the reduction, which works as follows. On an input pair (a, b) ∈ T n q × T, it does the following: • Choose f ← D Λ−a,r using Lemma 2.3 with basis B, and let v = a + f ∈ Λ/Z n . (The coset Λ − a is well defined since a =ā + Z n is some coset of Z n ⊆ Λ.) Choose a uniformly random solution a ′ ∈ T n ′ q ′ to the equation G T a ′ = v mod Z n . This can be done by computing a basis of the solution set G T a ′ = 0 mod Z n , and adding a uniform element from that set to an arbitrary solution to the equation G T a ′ = v mod Z n .
• Choose e ′ ← D rB and let b ′ = b + e ′ ∈ T.
We now analyze the reduction. First, if the distribution of the input is uniform, then it suffices to show that a ′ is (nearly) uniformly random, because both b and e ′ are independent of a ′ , and b ∈ T is uniform. To prove this claim, notice that it suffices to show that the coset v ∈ Λ/Z n is (nearly) uniformly random, because each v has the same number of solutions a ′ to G T a ′ = v mod Z n . Next, observe that for anȳ a ∈ T n q andf ∈ Λ −ā, we have by Lemma 2.7 (using that r ≥ η ε (Λ) by Lemma 2.5) that where C = q −n /ρ r (Λ) is a normalizing value that does not depend onā orf . Therefore, by summing over allā,f satisfyingā +f =v, we obtain that for anyv ∈ Λ/Z n , Since r ≥ η ε (q −1 Z n ) (by Lemma 2.5), Lemma 2.7 implies that Pr[v =v] ∈ 1−ε 1+ε , 1+ε 1−ε C ′ for a constant C ′ that is independent ofv. By Claim 2.1, this shows that a ′ is within statistical distance 1−((1−ε)/(1+ε)) 2 ≤ 4ε of the uniform distribution.
It remains to show that the reduction maps A q,s,Dα to A q ′ ,Gs,D β . Let the input sample from the former distribution be (a, b = a, s + e), where e ← D α . As argued above, the output a ′ is (nearly) uniform over T n ′ q ′ . So condition now on any fixed value a ′ ∈ T n ′ q ′ of a ′ , and letv = G T a ′ mod Z n . We have b ′ = a, s + e + e ′ = a ′ , Gs + e + −f , s + e ′ mod 1.

Hardness of LWE with Binary Secret
The following is the main theorem of this section.
For most purposes the sum over prime factors of q in (4.1) is negligible. For instance, in deriving the formal statement of Theorem 1.1 above, we used a q that is a power of 2, in which case the sum is 2 −k−1 = 2 − √ n−1 , which is negligible. If needed, one can improve this by applying the modulus switching reduction (Corollary 3.3) before applying Theorem 4.1 in order to make q prime. (Strictly speaking, one also needs to apply Lemma 2.15 to replace the "unknown noise" variant of LWE given by Corollary 3.3 with the fixed noise variant.) This improves the advantage loss to q − √ n−1 which is roughly 2 −n .
In a high level, the proof of the theorem follows by combining three main steps. The first, given in Section 4.1, reduces LWE to a variant in which the first equation is errorless. The second, given in Section 4.2, reduces the latter to the intermediate problem extLWE, another variant of LWE in which some information on the noise elements is leaked. Finally, in Section 4.3, we reduce extLWE to LWE with {0, 1} secret. We note that the first reduction is relatively standard; it is the other two that we consider as the main contribution of this section. We now proceed with more details (see also Figure 1).
Proof. First, since m ≥ n, Lemma 4.3 provides a transformation reduction from LWE k,m,q,α to first-iserrorless LWE k+1,n,q,α , while reducing the advantage by at most 2 −k+1 . Next, Lemma 4.7 with Z = {0, 1} n , which is of quality ξ = 2 by Claim 4.6, reduces the latter problem to extLWE k+1,n,q, √ 5α,{0,1} n while reducing the advantage by at most 33ε/2. Then, Lemma 4.8 reduces the latter problem to extLWE m k+1,n,q, √ 5α,{0,1} n , while losing a factor of m in the advantage. Finally, Lemma 4.9 provides three reductions to binLWE n,m,q,≤ √ 10nα : two from the latter problem, and one from LWE k+1,m,q, √ 5nα , guaranteeing that the sum of advantages is at least the original advantage minus 4mε + δ. Together with the trivial reduction from LWE k,m,q,α to LWE k+1,m,q, √ 5nα (which incurs no loss in advantage), this completes the proof.

First-is-errorless LWE
We first define a variant of LWE in which the first equation is given without error, and then show in Lemma 4.3 that it is still hard.
Definition 4.2. For integers n, q ≥ 1 and an error distribution φ over R, the "first-is-errorless" variant of the LWE problem is to distinguish between the following two scenarios. In the first, the first sample is uniform over T n q × T q and the rest are uniform over T n q × T. In the second, there is an unknown uniformly distributed s ∈ {0, . . . , q − 1} n , the first sample we get is from A q,s,{0} (where {0} denotes the distribution that is deterministically zero) and the rest are from A q,s,φ . Lemma 4.3. For any n ≥ 2, m, q ≥ 1, and error distribution φ, there is an efficient (transformation) reduction from LWE n−1,m,q,φ to the first-is-errorless variant of LWE n,m,q,φ that reduces the advantage by at most p p −n , with the sum going over all prime factors of q. Notice that if q is prime the loss in advantage is at most q −n . Alternatively, for any number q we can bound it by which might be good enough when n is large.
Proof. The reduction starts by choosing a vector a ′ uniformly at random from {0, . . . , q − 1} n . Let r be the greatest common divisor of the coordinates of a ′ . If it is not coprime to q, we abort. The probability that this happens is at most p prime, p|q p −n .
Assuming we do not abort, we proceed by finding a matrix U ∈ Z n×n that is invertible modulo q and whose leftmost column is a ′ . Such a matrix exists, and can be found efficiently. For instance, using the extended GCD algorithm, we find an n × n unimodular matrix R such that Ra ′ = (r, 0, . . . , 0) T . Then R −1 · diag(r, 1, . . . , 1) is the desired matrix. We also pick a uniform element s 0 ∈ {0, . . . , q − 1}. The reduction now proceeds as follows. The first sample it outputs is (a ′ /q, s 0 /q). The remaining samples are produced by taking a sample (a, b) from the given oracle, picking a fresh uniformly random d ∈ T q , and outputting (U(d|a), b + (s 0 · d)) with the vertical bar denoting concatenation. It is easy to verify correctness: given uniform samples, the reduction outputs uniform samples (with the first sample's b component uniform over T q ), up to statistical distance 2 −n+1 ; and given samples from A q,s,φ , the reduction outputs one sample from A q,s ′ ,{0} and the remaining samples from A q,s ′ ,φ , up to statistical distance 2 −n+1 , where s ′ = (U −1 ) T (s 0 |s) mod q. This proves correctness since U, being invertible modulo q, induces a bijection on Z n q , and so s ′ is uniform in {0, . . . , q − 1} n .

Extended LWE
We next define the intermediate problem extLWE. (This definition is of an easier problem than the one considered in previous work [AP12], which makes our hardness result stronger.) Definition 4.4. For n, m, q, t ≥ 1, Z ⊆ Z m , and a distribution χ over 1 q Z m , the extLWE t n,m,q,χ,Z problem is as follows. The algorithm gets to choose z ∈ Z and then receives a tuple Its goal is to distinguish between the following two cases. In the first, A ∈ T n×m q is chosen uniformly, e i ∈ 1 q Z m are chosen from χ, and b i = A T s i + e i mod 1 where s i ∈ {0, . . . , q − 1} n are chosen uniformly. The second case is identical, except that the b i are chosen uniformly in T m q independently of everything else.
When t = 1, we omit the superscript t. Also, when χ is D q −1 Z m ,α for some α > 0, we replace the subscript χ by α. We note that a discrete version of LWE can be defined as a special case of extLWE by setting Z = {0 m }. We next define a measure of quality of sets Z.
Definition 4.5. For a real ξ > 0 and a set Z ⊆ Z m we say that Z is of quality ξ if given any z ∈ Z, we can efficiently find a unimodular matrix U ∈ Z m×m such that if U ′ ∈ Z m×(m−1) is the matrix obtained from U by removing its leftmost column then all of the columns of U ′ are orthogonal to z and its largest singular value is at most ξ.
The idea in this definition is that the columns of U ′ form a basis of the lattice of integer points that are orthogonal to z, i.e., the lattice {b ∈ Z m : b, z = 0}. The quality measures how "short" we can make this basis.
Proof. Let z ∈ Z and assume without loss of generality that its first k ≥ 1 coordinates are 1 and the remaining m − k are 0. Then consider the upper bidiagonal matrix U whose diagonal is all 1s and whose diagonal above the main diagonal is (−1, . . . , −1, 0, . . . , 0) with −1 appearing k − 1 times. The matrix is clearly unimodular and all the columns except the first one are orthogonal to z. Moreover, by the triangle inequality, we can bound the operator norm of U by the sum of that of the diagonal 1 matrix and the off-diagonal matrix, both of which clearly have norm at most 1.
Proof. We first describe the reduction. Assume we are asked to provide samples for some z ∈ Z. We compute a unimodular U ∈ Z m×m for z as in Definition 4.5, and let U ′ ∈ Z m×(m−1) be the matrix formed by removing the first column of U. We then take m samples from the given distribution, resulting in . We also sample a vector f from the m-dimensional continuous Gaussian distribution D α(ξ 2 I−U ′ U ′T ) 1/2 , which is well defined since ξ 2 I − U ′ U ′T is a positive semidefinite matrix by our assumption on U. The output of the reduction is the tuple where b ′ = Ub+f , and c is chosen from the discrete Gaussian distribution D q −1 Z m −b ′ ,r (using Lemma 2.3). We now prove the correctness of the reduction. Consider first the case that we get valid LWE equations, i.e., A is uniform in T n×m q and b = A T s + e ∈ T m where s ∈ {0, . . . , q − 1} n is uniformly chosen, the first coordinate of e ∈ R m is 0, and the remaining m − 1 coordinates are chosen from D α . Since U is unimodular, A ′ = AU T is uniformly distributed in T n×m q as required. From now on we condition on an arbitrary A ′ and analyze the distribution of the remaining two components of (4.2). Next, Since Ue is distributed as a continuous Gaussian D αU ′ , the vector Ue + f is a distributed as a spherical continuous Gaussian D αξ . Moreover, since A ′T s ∈ T m q , the coset q −1 Z m − b ′ is identical to q −1 Z m − (Ue + f ), so we can see c as being chosen from D q −1 Z m −(Ue+f ),r . Therefore, by Lemma 2.10 and using that r ≥ η ε (q −1 Z m ) by Lemma 2.5, the distribution of Ue + f + c is within statistical distance 8ε of D q −1 Z m ,(α 2 ξ 2 +r 2 ) 1/2 . This shows that the second component in (4.2) is also distributed correctly. Finally, for the third component, by our assumption on U and the fact that the first coordinate of e is zero, and so the third component gives the inner product of the noise with z, as desired.
We now consider the case where the input is uniform, i.e., that A is uniform in T n×m q and b is independent and uniform in T q × T m−1 . We first observe that by Lemma 2.6, since α ≥ η ε/m (q −1 Z) (by Lemma 2.5), the distribution of (A, b) is within statistical distance ε/2 of the distribution of (A, e ′ + e) where e ′ is chosen uniformly in T m q , the first coordinate of e is zero, and its remaining m − 1 coordinates are chosen independently from D α . So from now on assume our input is (A, e ′ + e). The first component of (4.2) is uniform in T n×m q as before, and moreover, it is clearly independent of the other two. Moreover, and so c is distributed identically to the case of a valid LWE equation, and in particular is independent of e ′ . This establishes that the third component of (4.2) is correctly distributed; moreover, since e ′ is independent of the first and third components, and Ue ′ is uniform in T m q (since U is unimodular), we get that the second component is uniform and independent of the other two, as desired.
We end this section by stating the standard reduction to the multi-secret (t ≥ 1) case of extended LWE.
Lemma 4.8. Let n, m, q, χ, Z be as in Definition 4.4 with χ efficiently sampleable, and let t ≥ 1 be an integer. Then there is an efficient (transformation) reduction from extLWE n,m,q,χ,Z to extLWE t n,m,q,χ,Z that reduces the advantage by a factor of t.
The proof is by a standard hybrid argument. We bring it here for the sake of completeness. We note that the distribution of the secret vector s needs to be sampleable but otherwise it plays no role in the proof. The lemma therefore naturally extends to any (sampleable) distribution of s.
Proof. Let A be an algorithm for extLWE t n,m,q,χ,Z , let z be the vector output by A in the first step (note that this is a random variable) and let H i denote the distribution where u i+1 , . . . , u t are sampled independently and uniformly in T m q . Then by definition Adv We now describe an algorithm B for extLWE n,m,q,χ,Z : First, B runs A to obtain z and sends it to the challenger as its own z. Then, given an input (A, d, z, y) for extLWE n,m,q,χ,Z , the distinguisher B samples i * ← [t], and in addition s 1 , . . . , s i * −1 ← Z n q , e 1 , . . . , e i * −1 , e i * +1 , . . . , e t ← χ m , u i * +1 , . . . , u t ← T m q . It sets b i = A T · s i + e i (mod 1), and sends the following to A: (A, {b 1 , . . . , b i * −1 , d, u i * +1 , . . . , u t }, z, { z, e 1 , . . . , z, e i * −1 , y, z, e i * +1 , . . . , z, e t }) .
Finally, B outputs the same output as A did.
Note that when the input to B is distributed as P 0 = (A, b, z, z T · e) with b = A T · s + e (mod 1), then B feeds A with exactly the distribution H i * . On the other hand, if the input to B is P 1 = (A, u, z, z T · e) with u ← T m q , then B feeds A with H i * −1 . Since i * is uniform in [t], we get that and the result follows.
Proof. The proof follows by a sequence of hybrids. Let k, n, m, q, ε, α, β, γ be as in the lemma statement. We consider z ← {0, 1} n and e ← D m α ′ for α ′ = β 2 z 2 + γ 2 ≤ √ 2nβ = α. In addition, we let A ← T n×m q , u ← T m , and define b:=A T · z + e (mod 1). We consider an algorithm A that distinguishes between (A, b) and (A, u).
We let H 0 denote the distribution (A, b) and H 1 the distribution where N ← D n×m q −1 Z,β andê ← D m γ . Using z ≤ √ n and that β ≥ √ 2η ε (Z n )/q (by Lemma 2.5), it follows by Lemma 2.9 that the statistical distance between −N T z +ê and D m α ′ is at most 4mε. It thus follows that We define a distribution H 2 as follows. Let B ← T k×m q and C ← T k×n q . LetÂ:=qC T · B + N (mod 1). Finally, H 2 = (Â,Â T · z − N T z +ê) = (Â, qB T · C · z +ê) .
We now argue that there exists an adversary B 1 for problem extLWE m k,n,q,β,{0,1} n , such that This is because H 1 , H 2 can be viewed as applying the same efficient transformation on the distributions (C, A, N T z) and (C,Â, N T z) respectively. Since distinguishing the latter distributions is exactly the extLWE m k,n,q,β,{0,1} n problem (where the columns of q · B are interpreted as the m secret vectors), the distinguisher B 1 follows by first applying the aforementioned transformation and then applying A.
For the next hybrid, we define H 3 = (Â, B T · s +ê), for s ← Z k q . It follows that by the leftover hash lemma (see Lemma 2.2), since H 2 , H 3 can be derived from (C, qC · z) and (C, s) respectively, whose statistical distance is at most δ. Our next hybrid makes the second component uniform: Eq. (4.7) is derived very similarly to Eq. (4.4): We notice that H 4 , H 5 can be viewed as applying the same efficient transformation on the distributions (C,Â) and (C, A) respectively. Since distinguishing the latter distributions is exactly the extLWE m k,n,q,β,{0 n } problem (where the columns of q · B are interpreted as the m secret vectors), the distinguisher B 3 follows by first applying the aforementioned transformation and then applying A.

Exact Gaussian Sampler
In this section we prove Lemma 2.3. As in [GPV08], the proof consists of two parts. In the first we consider the one-dimensional case, and in the second we use it recursively to sample from arbitrary lattices. Our one-dimensional sampler is based on rejection sampling, just like the one in [GPV08]. Unlike [GPV08], we use the continuous normal distribution as the source distribution which allows us to avoid truncation, and as a result obtain an exact sample. Our second part uses the same recursive routine as in [GPV08], but adds a rejection sampling step to it in order to take care of the deviation of its output from the desired distribution.

The one-dimensional case
Here we show how to sample from the discrete Gaussian distribution on arbitrary cosets of one-dimensional lattices. We use a standard rejection sampling procedure (see, e.g. [Dev86, Page 117] for a very similar procedure). By scaling, we can restrict without loss of generality to the lattice Z, i.e., we consider the task of sampling from D Z+c,r for a given coset representative c ∈ [0, 1) and parameter r > 0. The sampling procedure is as follows. Let Z 0 = ∞ c ρ r (x)dx, and Z 1 = c−1 −∞ ρ r (x)dx. These two numbers can be computed efficiently by expressing them in terms of the error function. Let Z = Z 0 + Z 1 + ρ r (c)+ ρ r (c− 1). The algorithm repeats the following until it outputs an answer: • With probability ρ r (c)/Z it outputs c; • With probability ρ r (c − 1)/Z it outputs c − 1; • With probability Z 0 /Z it chooses x from the restriction of the continuous normal distribution D r to the interval [c, ∞). Let y be the smallest element in Z + c that is larger than x. With probability ρ r (y)/ρ r (x) output y, and otherwise repeat; • With probability Z 1 /Z it chooses x from the restriction of the continuous normal distribution D r to the interval (−∞, c − 1]. Let y be the largest element in Z + c that is smaller than x. With probability ρ r (y)/ρ r (x) output y, and otherwise repeat.
Consider now one iteration of the procedure. The probability of outputting c is ρ r (c)/Z, that of outputting c − 1 is ρ r (c − 1)/Z, that of outputting c + k for some k ≥ 1 is and similarly, that of outputting c−1−k for some k ≥ 1 is ρ r (c−1−k)/Z. From this it follows immediately that conditioned on outputting something, the output distribution has support on Z + c and probability mass function proportional to ρ r , and is therefore the desired discrete Gaussian distribution D Z+c,r . Moreover, the probability of outputting something is Therefore at each iteration the procedure has probability of at least 1/2 to terminate. As a result, the probability that the number of iterations is greater than t is at most 2 −t , and in particular, the expected number of iterations is at most 2.

The general case
For completeness, we start by recalling the SampleD procedure described in [GPV08]. This is a recursive procedure that gets as input a basis B = (b 1 , . . . , b n ) of an n-dimensional lattice Λ = L(B), a parameter r > 0, and a vector c ∈ R n , and outputs a vector in Λ + c whose distribution is close to that of D Λ+c,r . Let b 1 , . . . , b n be the Gram-Schmidt orthogonalization of b 1 , . . . , b n , and let b 1 , . . . , b n be the normalized Gram-Schmidt vectors, i.e., b i = b i / b i . The procedure is the following.
1. Let c n ← c. For i ← n, . . . , 1, do: (a) Choose v i from D b i Z+ c i ,b i ,r using the exact one-dimensional sampler.
It is easy to verify that the procedure always outputs vectors in the coset Λ+c. Moreover, the probability of outputting any v ∈ Λ + c is where c i are the values computed in the procedure when it outputs v. Notice that by Lemma 2.5 and our assumption on r, we have that r ≥ η 1/(n+1) ( b i Z) for all i. Therefore, by Lemma 2.7, we have that for all c ∈ R, ρ r ( b i Z + c) ∈ 1 − 2 n + 2 , 1 ρ r ( b i Z).
In order to get an exact sample, we combine the above procedure with rejection sampling. Namely, we apply SampleD to obtain some vector v. We then output v with probability ∈ 1 − 2 n + 2 n , 1 ⊆ (e −2 , 1], (5.1) and otherwise repeat. This probability can be efficiently computed, as we will show below. As a result, in any given iteration the probability of outputting the vector v ∈ Λ + c is .
Since the denominator is independent of v, we obtain that in any given iteration, conditioned on outputting something, the output is distributed according to the desired distribution D Λ+c,r , and therefore this is also the overall output distribution of our sampler. Moreover, by (5.1), the probability of outputting something in any given iteration is at least e −2 , and therefore, the probability that the number of iterations is greater than t is at most (1 − e −2 ) t , and in particular, the expected number of iterations is at most e 2 . It remains to show how to efficiently compute the probability in (5.1). By scaling, it suffices to show how to compute ρ r (Z + c) = k∈Z exp(−π(k + c) 2 /r 2 ) for any r > 0 and c ∈ [0, 1). If r < 1, the sum decays very fast, and we can achieve any desired t bits of accuracy in time poly(t), which agrees with our notion of efficiently computing a real number (following, e.g., the treatment in [Lov86, Section 1.4]). For r ≥ 1, we use the Poisson summation formula (see, e.g., [MR04, Lemma 2.8]) to write ρ r (Z + c) = r · k∈Z exp(−πk 2 r 2 + 2πick) = r · k∈Z exp(−πk 2 r 2 ) cos(2πck), which again decays fast enough so we can compute it to within any desired t bits of accuracy in time poly(t).